锐客网

  1. 首页 > it技术 > >

共识与拜占庭将军问题

学习笔记

1、共识基础 人们对共识机制的研究其实由来已久，从上世纪70年代就开始了相关研究，其目的是为了解决分布式系统中的一致性问题。Fischer, Lynch 和 Patterson在1985年发表的论文中提出了可以说是最重要的分布式系统定理：FLP不可能定理（在异步通信场景，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性）；2000年，EricBrewer教授又进一步提出了CAP猜想：一致性、可用性和分区容错性三者无法在分布式系统中被同时满足，并且最多只能满足其中两个；2002年，Lynch与其他人证明了Brewer的猜想，从而把CAP上升为一个定理。这期间和之后，涌现了一些著名的分布式一致性算法，如LeslieLamport在1989年提出的Paxos算法，1999年Castro和Liskov提出的PBFT算法等。直到比特币采用POW进行记账后，共识算法才真正进入到了大众的视野里。
一般来说根据处理的异常情况不同，可以把共识算法分为两种类型，一种是针对非拜占庭错误的，这类算法性能较高，但容错性较差，如Paxos、Raft等；另一种是针对拜占庭错误的，这类算法往往容错性较高，但是性能相对较差，包括工作量证明（POW）、权益证明（POS）、委托权益证明（DPOS）、实用拜占庭容错算法（PBFT）等。处理拜占庭错误的算法有两种思路，一种是通过提高作恶成本以降低作恶节点出现的概率，如工作量证明、权益证明等，其中工作量证明是通过算力，而权益证明则是通过持有权益。另外一种是在允许一定的作恶节点存在的前提下，依然使得各节点之间达成共识，如实用拜占庭容错算法等。下面我们就来讲讲目前存在的主流共识算法。
2、拜占庭将军问题 1982年，Leslie Lamport等科学家提出了著名的拜占庭将军问题（Byzantine failures），其讨论的是允许存在少数节点作恶场景下的一致性达成问题。简单描述下： 国土辽阔的拜占庭帝国，基于防御目的，将每支军队分别部署在全国各地。因为距离遥远，将军们只能靠信差传递消息。战争爆发时，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军，以获取作战胜利。然而将军们无法确定他们中是否存在叛徒，叛徒可能擅自变更进攻意向或者进攻时间，以破坏进攻的一致性，致使作战失败。在这种状态下，拜占庭将军们该商定一种怎样的远程沟通办法，以达到一致呢？
共识与拜占庭将军问题
文章图片

论文中指出，对于拜占庭问题来说，假如节点总数为N，叛变将军数为F，则当N≥3F+1时，问题才有解，由拜占庭容错算法BFT进行保证。简单说一下论证过程：假设节点总数为N，作恶节点总数为F，有效的善良节点数为L1，无效（发生故障）的善良节点数为L2； 那么系统要安全的达成一致则必须满足2点：有效的善良节点超过作恶节点，同时也必须超过故障的善良节点。转化为数学公式则：L1≥F+1，L1≥L2+1（L2=F），又L1=N-L2-F，即N-F-F≥F+1，得出N≥3F+1；因此当叛变者不超过1/3时，存在有效的拜占庭容错算法。但BFT一直存在复杂度过高的问题，并没有真正落地到实际场景中。
Miguel Castro和Barbara Liskov在1999年提出了实用拜占庭容错算法PBFT(Practical Byzantine Fault Tolerance)，以解决原始拜占庭容错算法效率不高的问题，将算法复杂度大为降低，使得拜占庭容错算法在实际系统应用中变得可行。PBFT是针对状态机副本复制为主的分布式系统执行环境开发的算法，旨在让系统中大部分的诚实节点来覆盖恶意节点或无效节点的行为。其运作步骤为： (1)随机取一个副本作为主节点，其他的副本作为备份； (2)用户端向主节点发送使用服务操作的请求； (3)主节点通过广播将请求发送给其他副本； (4)所有副本执行请求并将结果发回用户端； (5) 用户端需要等待F+1个不同副本节点发回相同的结果，作为整个操作的最终结果。PBFT算法要求系统的失效节点数量不得超过全网节点的1/3，容错率相对较低。
共识与拜占庭将军问题
文章图片

3、PoW：工作量证明机制 比特币的区块链网络在设计时，针对PBFT中同时存在多个提案和最终一致性确认的问题进行了创造性的改进，提出并采用了PoW算法。通过消耗大量能源来计算一个满足条件的Hash值来获得记账权（发起提案），某个节点成功找到满足条件的Hash值之后，会马上对全网进行广播打包区块，网络中的节点收到区块后，会立刻对其进行验证。如果验证通过，则表明已经有节点成功记账，自己就不再竞争当前的区块，而是选择接受这个区块，记录到自己的账本中，然后进行下一个区块的竞争记账。同时记账节点会得到代币奖励，进而吸引更多节点参与竞争。假如节点有任何的作弊行为，都会导致验证不通过，并直接丢弃其打包的区块，作弊的节点不但得不到奖励，还损失了巨大挖矿成本。这样全网节点始终维护着拥有最大工作量的链，从而保证整个账本的相对一致性。
PoW算法简单来说就是算力越大，记账成功率越高（干的越多，获得越多）。其实现了完全去中心化，节点可以自由进出且实现简单。同时其容错性方面得到了提升，允许全网50%的节点出错，破坏系统需要投入极大的成本。它的缺点也很明显，首当其冲便是浪费能源，其次是共识效率低下，并且存在算力集中的风险。目前很难满足商业化应用的需求，典型项目如比特币。
4、PoS：权益证明机制 PoS也称股权证明机制，其诞生的初衷是为了解决PoW带来的能耗问题。这种模式下持有币的数量越多、时间越长，记账成功率就越高（持有越多，获得越多），类似于利息制度。举例来说，PoS算法中有一个名词叫币龄，每个币每天产生1币龄，如果你持有100个币，总共持有了30天，那么此时你的币龄就为3000。这个时候如果你发现了一个PoS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的奖励(相当于年利率5%)，在这个案例中，奖励 = 3000 * 5% / 365 = 0.41个币，即持币有利息。
PoS作为PoW的一种升级共识机制，根据每个节点所持有代币的数量和时间，等比例的降低挖矿难度，在一定程度上缩短了共识达成的时间，但最重要的是不再需要消耗大量能源进行挖矿。它的缺点在于：性能提升有限，持币吃息的模式会导致代币的大量集中，流动性变得匮乏起来。典型项目如以太坊，目前正在从PoW切换至PoS机制。
5、DPoS：委托权益证明机制 【共识与拜占庭将军问题】DPoS是权益证明的一种改进版本，共识过程不再需要所有参与节点进行验证，而是委托部分代表来进行，很大程度上提高了共识效率。BitShares社区首先提出了DPoS机制，并引入了见证人的概念。见证人可以生成区块（记账并获得奖励），每一个持有比特股的人都可以投票选举见证人。得票数前100名的候选者可以当选为见证人，见证人的候选名单每个维护周期更新一次。见证人通过随机排列后，依次轮流生成区块（限时2s内出块），若见证人在2s内未能出块，则自动跳到下一个见证人。由于持股人可以随时通过投票更换见证人，因此见证人为了获得奖励和避免损失保证金，就必须提供稳定高效的出块能力。
可以看出，DPoS实际上是对共识进行了分级，先通过投票选举达成见证人共识（选出极少数可信的见证人），然后见证人之间再达成交易验证共识，这样大大提高了整个系统的共识效率。从某种角度来看，DPoS与议会制度或人民代表大会制度有相似之处。如果代表不能履行他们的职责，例如未能按时出块，就会被网络选出的新见证节点所取代。DPoS算法从性能和能耗的角度来说完全可以满足商用，但也不可避免地带来了过于中心化的问题。比如现在很火的EOS超级节点竞选就变成了鲸鱼们的合纵游戏，甚至被质疑是伪区块链项目。当然这种看法笔者并不赞同，毕竟上期也讲到3类区块链，采用DPoS算法的项目应当算作联盟链，只不过有些联盟比较开放有了大量散户，从运营模式上看更像公链。
6、其它共识机制 Paxos和Raft是另外两种经典的共识算法，准确的说应该是分布性一致算法，它们都是为了解决非拜占庭问题下实现分布式系统数据一致性的问题（主要防范节点故障，而非节点作恶）。这个过程如同选举一样，参选者需要说服大多数选民(服务器)投票给他，一旦选定后就跟随其操作。Paxos和Raft的区别在于选举的具体过程不同，有兴趣的读者可以自行了解下。
7、共识的价值 共识机制解决了区块链如何在分布式场景下达成一致性的问题，通过算法创造了信任，从而极大地减少当前金融系统及其他社会系统中的信用成本。小到菜市场的价格形成，大到一个国家的建立，这背后都意味着一种共识，所以共识本身就是价值，但价值大小要看其运用的场景。回过头来再看看市场上充斥着的价格混杂的各种数字货币，它们落地时的用途才真正决定着其价值，思考清楚了再入场不迟，当然纯投机的话可以完全不用考虑。现阶段并没有完美的共识机制，每种算法差异的背后都是对性能效率和去中心化不同的取舍。随着区块链应用场景的不断扩展，未来必然会不断涌现出新的共识算法，或许某一天会诞生出具有普适性的算法，给人类社会带来深层次的变革。

    推荐阅读


    上一篇：基于ALS算法的简易在线推荐系统

    下一篇：将图片转换成json code码