6.2 共识协议

6.2.1 公链共识机制

任何用户都可在无须审核授权的情况下自由加入或退出公链，因此不仅要考虑故障节点，还要考虑作恶节点。

一、PoW

PoW，即工作量证明，是比特币采用的共识机制。工作量证明的逻辑类似于现实工作中向老板证明自己的工作量，与其让老板持续监测工作过程，不如直接拿出工作结果。在比特币系统中，拿出“解题”结果的节点就会获得记账权和区块奖励，而题目就是遍历区块头中的Nonce，找到一个数使区块头的两次哈希后的值小于目标值。显然，目标值越小难度越大，二者成反比关系。每2016个区块会更新一次难度值，更新公式为（单位为分钟）：

由上式可知，每次难度调整都在尝试让出块时间保持在10分钟左右。如图6-8所示，假如有两个矿工A和B同时挖出第N个区块，这一结果将向全网广播。部分矿工先收到A链的新区块，有些则先收到B链的新区块。而矿工们接收到消息就会停止挖第N个区块，开始第N+1个区块的挖掘，延伸A链或B链。率先挖出第N+1个区块的一方将形成更长的链，再将N+1个区块的结果向全网广播，矿工们开始在胜出的链上投入N+2个区块的挖掘，而另一方则被矿工们废弃。

这种投票方式有诸多优点。

首先，它无须各个矿工回复同意的投票，减轻了网络压力。

其次，避免了统计得票率的麻烦，不必存在权威计票人，也不需要知道具体有多少节点存在网络中。

最后，实实在在的算力保障系统的安全。伪造同意的消息比较简单，但是拥有大量算力必须花费大量金钱。只认可最长合法链的共识，使矿工们最经济的选择就是在新区块挖掘后延长该链。因此只要诚实节点掌控的算力大于串通攻击者的算力，那么系统就是安全的，因为攻击者如果想要对某个已经出现的区块进行修改，那么它还必须完成之后所有区块的工作量。

攻击者完成之后所有区块的工作量，追上诚实链的难度或说概率具体分析如下。

攻击者追上诚实链的过程可以用二叉树随机漫步来描述。设p为诚实链拉开一个区块距离的概率，q=1-p为攻击者追上一个区块的概率，那么攻击者成功填补n个落后区块、完成攻击的概率可以表示为

p> 0.5时意味着诚实矿工算力更大，但假如攻击者运气够好，它依然有机会完成攻击，就好像赌场里输的概率更大，但总有幸运儿会赚一笔一样。由于领先0个区块时攻击成功，领先无穷个区块时不可能完成攻击，所以有f (0 ) = 1, f (∞ ) = 0。同时，领先n个区块被超过的概率，相当于以下两个事件的概率和：①拉开一块距离，再以领先n+1块的优势输掉；②被追上一块距离，再以领先n-1块的优势输掉。即 。因此 。递减n直到1并求和得：

当n= ∞时，代入可解得 ，由此可知，f 。

p< 0.5时意味着攻击者算力多于一半，攻击必然成功。有趣的是，p=0.5时攻击依然必定成功，与我们常听说的“51%攻击不同”。这是因为在双方算力相等的情况下，两条链的长度差将进行一维随机漫步。当随机漫步经过0时，攻击者生成的链与诚实链一样长，有些单纯逐利矿工会加入攻击者这一边，因为它们只认链的长度，不做“恶意”或“诚实”之类的主观判断。由于攻击者在自己的链更短时仍然坚持挖矿，而那些单纯逐利矿工在诚实链更短（或等长）时可能倒向另一方，攻击者其实是占优的。事实上，如果矿工都是单纯逐利的，自私挖矿（Selfish Mining）可以通过掌握至少1/4的算力，就能完成攻击。

假设攻击者打算赖账，并且在广播交易的同时就开始准备修改该交易的平行链，那么当收款人等待z个确认后（诚实链产生z个区块），攻击者产生的区块个数将是个期望为 的泊松分布，将追上的可能性加权求和，得到赖账的成功率为 当q< p时，随着z的增加，赖账成功率呈指数衰减，等待多个区块确认后，可以在概率上认为这份账本为大家所确认。在这里，比特币采用的PoW共识机制牺牲了强一致性，获得高可用性和分区容错性，从而达到最终一致性——比特币的交易账本会随着时间的推移最终达到一致。PoW完全去中心化，节点自由进出，攻击系统成本很高。但是它浪费资源，而且矿池的出现违背了去中心化的初衷。

二、PoS

PoS，即权益证明，由Peer Coin最先采用，并且以太坊也开始由PoW转向PoS。它的出现解决了持币人对于系统没有话语权、矿工用户利益不一致的问题，并且无须浪费大量计算资源。

假如一个用户持有n个代币t天，那么可以定义币龄为n× t。币龄越长，拥有的权益越大。拥有权益的节点可以将自己的权益放入PoS机制中去竞争记账权，权益越大被选中的概率越高。比如有的实现方式是利用权益调整PoW中的难度值，权益越大，难度值越小，也就更容易出块。

PoS优势：PoS除了环保外，性能也比较高。因为无须解题，所以拿到交易后可以很快地打包并广播，其延迟主要受限于网络因素。此外PoS还更加安全。首先，因为一般而言，获得总量某个比例的代币，比获得总量某个比例的算力成本要高得多。其次，有恒产者有恒心。拥有某个系统越多的代币，出于经济利益考量，越不容易作恶，因为作恶会导致自己代币价值的大幅缩水。但是PoW作恶的代价小得多，比如BTC中的大矿池可以切换算力去攻击总算力较低的BCH，攻击完成后又可以切换回BTC。

但是PoS机制也有许多不足，比如PoS分叉的成本几乎为0。在PoW中，两条分叉的链在一方占据优势时，大量逐利的矿工会倒向优势的一方，因为如果把算力浪费在劣势的链上，很可能一无所获，而算力是需要电力成本的。然而，如果是PoS系统，并且你手中的币不多，你可能就不那么在乎系统的整体利益，那么你将很有动机发动一种无风险攻击（Nothing-at-stake Attack）。这种攻击正如它的名字，即使失败了也没有什么关系。这种攻击指一个矿工在最长链挖矿的同时，还创造了一个分支，只在自己的区块上挖矿。在PoW中这么做是不值得的，但是PoS看重的是币龄而不是算力，只需要做几个简单的签名之类的加密计算就可以了，即使失败了也没什么损失，在分支挖矿不会影响自己在最长链上的币龄。同理，你不仅有动机发起分叉，而且当其他人发起分叉的时候，你也有动机参与到这个分叉。理由是相同的，成本几乎为零，如果运气好这个分叉成功了，那么你就赚了。

6.2.2 联盟链共识机制

在联盟链的共识机制中，记账权竞争既无须工作量证明，又无须权益证明。为何如此？因为联盟链的核审准入机制能够防范女巫攻击（Sybil Attack）。女巫攻击指的是单个节点模仿成多个节点，就好像常见的用多个IP刷量一样。因为无从在虚拟世界中认定一个人的身份，所以公链才被迫采用工作证明和权益证明，因为这些东西难以伪造。联盟链的核审准入机制使它的共识机制具有更高的性能和更少的资源消耗。

依据是否容忍拜占庭错误，联盟链的共识算法可以分为BFT类算法与CFT类算法，进一步细分如图6-9所示。

一、BFT

BFT（Byzantine Fault Tolerance），即拜占庭容错，是一种常见的联盟链共识机制。

解释这一机制需要引入拜占庭将军问题。拜占庭将军问题是莱斯利·兰伯特（Leslie Lamport）用来描述分布式系统一致性问题的例子。问题描述如下：拜占庭帝国派出了n支军队去包围敌军，军队间依靠通信兵来协商行动计划。但是n名将军中可能有m个叛徒，叛徒会尝试阻止忠诚的将军达成一致。这里假设信道是可靠的，因为信道不可靠的情况下此问题无解。

我们现在需要一个共识机制保证以下两点：①忠诚将军对某个提案达成共识。②叛徒不会导致忠诚将军的共识是个“坏计划”。注意，我们永远无法保证选出来的计划是过半忠诚将军同意的。假设51%的忠诚将军希望进攻，49%的忠诚将军希望撤退，那么显然一小撮叛徒就可以通过他们的投票来让最终计划是撤退。但这种情况下我们不会称撤退是个“坏计划”，因为有不少忠诚将军本身就同意撤退。

我们可以设想一种最简单的协议：每个将军将自己的提案v ₁ 发送给其他所有人，然后每个人按照少数服从多数的决策函数得到某个结果。如果大家接收到的提案都一样，那么结果也是一致的：

遗憾的是，叛徒会给不同节点发送不同的消息，对有的人说自己希望进攻，对有的人说自己希望撤退。也就是说每个人接收到的v可能是不同的，所以最终作出的decision也可能不同。在这里，我们明确描述下叛徒的行为：叛徒会对不同节点发送不同的提案，因为只有这样，才能扰乱各个将军的决策。都进攻或都撤退都算是算法成功了，只有不一致（有进攻有撤退）才算失败。

在这个期望的协议中，有两点要求：①设 为第i个将军认为的第j个将军的提案。为了保证每个按算法忠实行动的将军都能达到相同的决定，需要它们的 都一致。②忠诚将军j的提案必须正确地传达到忠诚将军i的手中，即 。但是对于叛徒k的提案只需要 来满足①，因为叛徒没有唯一确定的v _k 。

兰伯特将上面的问题转化为一个司令-副官问题。但是下面会用发言者代替司令，听者代替副官，因为发言者的声明不一定被听取，这与“司令”这个词所带有的权威性冲突。之所以问题能如此转化，是因为发言者-听者问题将原问题划分为N个子问题：对于每个将军，忠诚的发言被听者听取，就保证 ；对叛徒的发言最终共识一致，就保证 。这个算法有个递归的结构，这个结构源于以下事实。

①发言者对n个听者分别发送消息，但是每个听者都不清楚发言者给他们的信息是不是一致的，于是他们应该互相交换信息，也就是每个听者应告知剩下n-1个听者发言者对自己说了什么。

②但是某个听者a告知剩下n-1个听者它收到什么时，a就好像一个发言者，a也可能散播不同版本的消息，所以剩下n-1个听者之间也应该互相交换信息，这就回到跟①一样的结构。对于m个叛徒，要递归深度为m，下面将举例来帮助理解这个抽象的算法。

假设叛徒有m=3个，则至少要求n=3m+1=10个将军，记为g ₀ ,g ₁ ,…,g ₉ 。将其划分为10个子问题。第一个子问题要求g ₀ 的提案v ₀ 在g ₁ ,…,g ₉ 忠诚者中达成共识，即 ，i、j忠诚。此时处于递归第一层OM（3）。分两种可能，第一种可能：g ₀ 是叛徒。那么它对g ₁ ,⋯,g ₉ 分别发送信息a,b,c,…,h,i，这里面的字母各不相同，表示它们收到的版本各不相同。现在，g ₁ ,⋯,g ₉ 要开始交换信息，只要交换信息后忠于算法的将军能得到相同的v（0 而不管v ₀ 具体是什么），就算子问题达成共识。

现在我们处于OM（3）的听者信息交换阶段，它被视为递归的第二层OM（2）。OM（2）可以被划分为9个子问题。第一个子问题是g ₁ 向g ₂ ,…,g ₉ 声明它从g ₀ 收到的值，这个值需要在g ₂ ,…,g ₉ 忠诚者中达成共识。我们不妨先考虑g ₁ 是忠诚的情况，g ₁ 忠实地向g ₂ ,…,g ₉ 告知自己从g ₀ 收到a。

现在我们处于OM（2）的听众信息交换阶段，它被视为递归的第三层OM（1）。OM（1）可以被划分为8个子问题。第一个子问题是g ₂ 向g ₃ ,…,g ₉ 声明它上一层从g ₁ 收到的值，这个值需要在g ₃ ,…,g ₉ 忠诚者中达成共识。我们假设剩下两个叛徒是g ₈ 、g ₉ ，那么g ₂ 是忠诚的情况。g ₂ 忠实地向g ₃ ,…,g ₉ 告知自己从g ₁ 收到a。

现在我们处于OM（1）的听者信息交换阶段，也是递归的最底层。交换信息时，都会忠实地告诉其他人它们从g ₂ 收到。但是会发送任意可能的值（我们不关心叛徒之间互相发送什么值，因为它们本来就不按照算法约定行事），比如发给其他人g ₉ 。现在我们考察忠诚将军的情况。虽然它们接收到的信息可能各不相同，但是少数服从多数的情况下majority ( a,a,a,a,a,x _i ,y _i )都是一样的。现在忠诚将军对g ₂ 从g ₁ 收到达成了共识，同理，对从g ₁ 收到也能达成共识。为什么这里我们能直接把多数答案当作结果？因为每一次从OM（m）到OM（m-1）都排除了一个节点。就算每次排除的都是诚实节点，从OM（m）到OM（1）原来的2m+1个诚实节点还剩下m+1个，依然多于叛徒m个。

OM（1）中剩下的子问题是对g ₈ 、g ₉ 从g ₁ 收到什么能否达成共识（答案是否）。假设g ₉ 分别欺骗g ₂ ,…,g ₇ 自己从g ₁ 收到的是p ₂ ,…,p ₇ ，那么接下来进入OM（1）的听众信息交换阶段。 g _i ,i∈{2,3,…,7}会诚实地告知其他人自己g ₉ 收到p _i ，但是g ₈ 这个叛徒会向g ₂ ,…,g ₇ 分别发送虚假信息，声称自己从g ₉ 收到q ₂ ,…,q ₇ 。现在我们考察忠诚将军g ₂ ,…,g ₇ 的情况。g _i ,i∈{2,…7}从g ₉ 收到p _i ，从g _j ， j ∈{2,…7}且j ≠ i收到p _j ，从g ₈ 收到q _i 。综合就是收到(p ₂ ,p ₃ ,p ₄ ,p ₅ ,p ₆ ,p ₇ ,q _i )。在这种情况下，无法保证majority(p ₂ ,p ₃ ,p ₄ ,p ₅ ,p ₆ ,p ₇ ,q _i )相同，所以忠诚将军g ₂ ,…,g ₇ 对于g ₈ 、g ₉ 从g ₁ 收到什么各有看法。现定义g ₂₈₁ 表示g ₂ 对“g ₈ 从g ₁ 收到什么”的看法，以此类推。

现在我们完成了OM（3）的所有子问题。对于忠诚将军，它们自己从g ₁ 收到a，同时对其他忠诚将军从g ₁ 收到a达成共识。但是对于叛徒g ₈ 、g ₉ 从g ₁ 收到什么没有达成共识。所以可以列出它们的状态。

可以发现，忠诚的将军对于g ₁ 发送的消息能够达成共识a，也就是说它们都认同g ₁ 从g ₀ 收到a。因为g ₂ ,…,g ₇ 也是忠诚将军，所以OM（2）中关于g ₂ ,…,g ₇ 的子问题也能得到解决。也就是说忠诚将军达成共识：g ₂ 从g ₀ 收到b，g ₃ 从g ₀ 收到c……剩下的问题是它们能否就叛徒g ₈ 、g ₉ 从g ₀ 收到什么达成共识（答案为肯定的）。

虽然g ₉ 从g ₀ 收到i,但是它作为叛徒不会遵守算法，而是分别向g ₁ ,…,g ₇ 声明自己从g ₀ 收到t ₁ ,…,t ₇ 。现在进入OM（2）中的信息交换阶段，也就是OM（1）。可以划分为8个子问题。第一个子问题是就g ₁ 从g ₉ 收到什么达成共识。g ₁ 告知g ₂ ,…,g ₈ 自己收到t ₁ ，然后进入OM（1）中的信息交换阶段。因为g ₁ 是诚实的，g ₂ ,…,g ₈ 只有1个叛徒，所以最终结果是忠诚将军对于g ₁ 从g ₉ 收到t ₁ 达成一致。剩下7个子问题中关于g ₂ ,…， g ₇ 的6个也是一样的，最终结果是忠诚将军对于g _i 从g ₉ 收到t _i 达成一致i=1,…,7。那么最后一个子问题中，忠诚将军能够就叛徒g ₈ 从g ₉ 收到什么达成一致吗？答案是可以。设g ₈ 向g ₁ ,…,g ₇ 发送k ₁ ,…,k ₇ ，因为g ₁ ,…,g ₇ 都是忠诚的，所以交换消息后大家能得到同样的结果序列，再取多数的结果可以得到相同的majority(k ₁ ,…，k ₇ )。所以大家就g ₈ 从g ₉ 收到什么达成一致。因为忠诚将军就g ₁ ,…,g ₈ 从g ₉ 收到什么都达成共识，所以可以认为g ₉ 发送的值为r ₉ = majority (t ₁ ,…,t ₇ ,majority ( k ₁ ,…,k ₇ ))。同理也可以对g ₈ 发送的值r ₈ 达成共识。

最终我们回到了递归的最上层OM（3）。忠诚将军已经对g ₁ ,…,g ₉ 分别从g ₀ 收到什么达成了共识。那么每个忠诚将军i可以最终决定g ₀ 的提案v ⁱ ₀ 。对于所有忠诚将军都有：

忠诚将军就叛徒g ₀ 的提案实现了v ⁱ ₀ = v ^j ₀ 的共识。读者可以自行证明忠诚将军能够就其他忠诚将军j达成v ^j _j = v _j 的共识。每个忠诚将军都得到了相同的{v ₁ ,v ₂ ,⋯v _N }，自然可以就最终方案达成共识。

原始拜占庭算法的复杂度是指数级的。因为OM（m）可以递归为n-1个OM（m-1）问题，OM(m-1)可以递归为n-2个OM(m-2)，所以复杂度可以表示为OM(m )=(n- 1)(n- 2)…(n- m+ 1)OM(1 ) =O ( n ^{m- 1} )。复杂度过高，实际现实中难以应用。

二、PBFT

芭芭拉·利斯科夫（Barbara Liskov）等人在1999年提出实用拜占庭容错算法（PBFT）。它的容错能力同BFT一样，也是能在3f+1个节点中容忍f个拜占庭节点。

它的节点提供具有确定性的副本复制服务，不仅能读写，而且能基于状态和操作参数进行确定性计算。客户端发出请求后会受到阻塞并等待回复，目标是获得正确、可信的结果。某个副本作为主节点，其他副本作为备份，被称为系统的一个view。v是不断递增1的整数，主节点的编号为n _primary =vmod N，N为节点总数。假如主节点超时，就切换到下一个view。

从状态机的角度看，假设一开始各个节点状态相同，那么给予相同的输入序列后，它们的状态依然相同。所以主节点收到请求m时，除了将其保存在本地日志并广播外，还要给它分配一个序号。将这称作pre-prepare阶段，其消息格式为

其中v是view编号，n是请求m的序号，d (m )是m的消息摘要。其他节点收到这个消息后，首先做签名验证，之后确认在视图v中还没有收到序号为n的其他消息。此外n需要在当前接收窗口内。如上面的检查都通过，则节点i接受这条信息并记入日志，进入prepare阶段并广播prepare信息＜PREPARE,v,n,d ( m) ,i＞。

节点收到prepare消息后，同样会验证签名、检查当前view、序号n是否在窗口内。验证通过则接受消息。假如一个节点拥有消息m、关于m的pre-prepare消息、2f个其他节点的prepare消息，它进入prepared状态，可以确保消息m有全局一致的顺序。

（1）对正常节点不能同时有m 、m'序号都是n 。

（2）正常节点对于m的序号n达成共识。

两者都可用反证法证明。以第一个为例，若某个正常节点认为m的序号是n，说明有2f+1个节点发送＜PREPARE,v,n,d (m ) ,i＞，同理还有2f+1个节点发送＜PREPARE,v,n,d (m' ) ,i＞。由于总结点只有3f+1个，至少有f+1个节点两个消息都发送了，也就是存在f+1个拜占庭节点，这与容错条件是矛盾的。

节点进入prepared状态后，会广播commit消息：

prepared节点收到并验证2f+1个commit消息后，系统对于消息m有了全局一致的顺序，可以执行消息中的命令并将返回值返回给客户。流程示意如图6-10所示，其中3表示发生了故障。

由于日志空间有限，需要每隔一段时间设定checkpoint。当一个节点执行完第n个消息后，广播＜CHECKPOINT,n,d,i＞，其中d是当前状态的摘要。节点收到2f+1个checkpoint消息后，产生一个本地的checkpoint，清除比n小的消息，然后将接收消息的窗口调整为[n,n+windowsize]。显然，不同节点的速度不同，假如某个节点处理到了窗口上限，它就会停下等待比较慢的节点。窗口机制避免了不同节点状态差异过大。

假如有节点检测到主节点超时或作恶，它会发送viewchange消息：＜VIEWCHANGE,n,C,P,i＞。

n是最近一个checkpoint对应的序号，C是该checkpoint的2f+1个checkpoint消息集合，用来证明它是真实的。P是消息集合，它包含了所有序号大于n的消息m的1个pre-prepare消息和2f+1个prepare消息。i是节点的序号。

假如新的主节点n _primary =(v+ 1)mod N收到2f个有效的viewchange消息，就会广播＜NEWVIEW, v+ 1,V,O＞。V是viewchange消息集合，相当于用选票来证明自己的合法性。O是未完成的pre-prepare消息集合，它们的序号最小从V中最小的checkpoint开始，最大到V中最大的消息编号。假如能找到对应序号的消息m，则向O加入：

＜＜PRE- PREPARE,v+ 1,n,d (m )＞,m＞

假如找不到对应序号的消息m，则向O加入：

＜＜PRE- PREPARE,v+ 1,n,d ( null )＞,null＞

副本收到主节点的newview消息后，如果通过验证，则自己进入v+1的新view，然后开始处理O中的pre-prepare消息。

三、CFT

上述算法都是拜占庭容错的，而诸如Paxos、Raft则是非拜占庭容错的异步系统共识机制，统称为容错（Crash Fault Tolerance，CFT）类算法。根据FLP理论，它们在出现故障节点的情况下，是有可能进入死循环而无法结束的。然而由于其概率很低，在放宽可终止性要求的情况下，可以在工程上实现可用的异步网络中的共识机制。

四、Raft

一个Raft系统中，各个节点可能处于以下3种状态中的一种：领导者、候选人、追随者。正常情况下只有一个领导者，剩下的都是追随者。追随者的被动响应来自领导者和候选人（如果有的话）的请求，如果有客户与它通信，它也仅仅是把客户的消息转发给领导者，最终由领导者统一处理所有来自客户的请求。只有在接收不到领导者的消息并且计时器超时后，一个追随者才会变成候选人，尝试竞选领导者。如果它获得了大部分选票，则成为新的领导者。图6-11展现了这3种状态的转换，更具体的规则会在下面讨论。

每一次进行选举都是进入一个新的任期（term），用连续递增的整数表示。由于可能有多个候选人，有可能没有任何一个候选人能获得大多数选票。在选举超时后，这轮term没有选出领导者，就会开始下一轮term，重新尝试选举。每个节点都储存了当前term的值，并且在与其他节点通信时会交换这个值。如果一个节点收到比自己更大的任期号，它会以此更新自己的任期号，如果收到比自己更小的任期号，它会拒绝此次请求。如果领导者收到比自己更大的任期号，它知道产生了新的领导者，就会转换为追随者状态。

Raft中的节点通过远程过程调用（RPC）来通信。AppendEntries RPC由领导者发送，用于复制日志条目。RequestVote RPC由候选人在选举期间触发。一个节点初始化状态为追随者，只要它还能收到来自领导者的RPC，就会保持追随者状态。而领导者也会周期性发送空的AppendEntries RPC，作为心跳包来保证自己的领导地位。如果一个追随者在一段时间内没有收到来自领导者的RPC，就会假定没有可用的领导者并开始一次选举。它将自己转换为候选人，自增任期号，给其他节点发送RequestVote RPC。它将一直处于该状态，直到有人赢得选举或超时。一个任期内，一个节点最多给一个候选人投票，如果某个候选人获得大多数选票，则它成为领导者并向所有节点发送心跳包来建立领导地位。

领导者接受客户请求，并把请求中要求执行的命令加入日志，然后向其他节点发起AppendEntries RPC，要求他们复制这个日志条目。大多数节点完成复制后，称这个条目状态为committed。这时领导者就会对状态机执行这条命令，并且返回结果给客户。领导RPC包会包含处于committed状态最大的索引值，这样追随者就知道这个条目（及它之前的全部）都已经处于committed状态，他可以对自己的状态机执行这条（这些）命令。通过这种机制，我们能够保证日志匹配性（Log Matching Property），即对于不同日志中两个拥有相同任期号和索引值的条目，满足以下两点。

（1）它们储存相同的命令。

（2）它们之前的条目都相同。

因为一个任期的领导者对一个条目给予唯一的索引值，所以第一点可由此直接保证。对于第二点，由AppendEntries RPC的一致性检查保证。AppendEntries RPC在要求追随者复制某个条目时，会将前一个条目的任期号和索引值包含在内。如果追随者在自己的日志中没有找到这样的条目，他就会拒绝新条目。由归纳法可知，若初始状态为空，且增加第n个条目时第n-1个条目相同，那么双方n之前的日志将保持一致。正常情况下，领导者和追随者的日志是一致的，但是当没将自己所有日志都复制完毕就崩溃的时候，不一致就会出现。不一致出现时，领导者要求追随者复制自己的日志并重写（overwrite）。

显然，这种粗暴的做法有一定危险性，为此我们需要保证任何领导者都拥有全部之前任期已经committed的日志条目，因为committed的条目是绝不能被重写的。为此我们要求节点在发现自己的日志比候选人的日志新的时候，拒绝为他投票。要成为领导者需要获得大多数投票，而committed的日志条目至少存在于某个投票者的日志内。如果候选人跟大多数人的日志一样新（或更加新），那么它包含所有committed的日志条目。要比较谁的日志新，首先看任期号。任期号更大的日志更新。如果任期号一样，则日志更长的更新。

我们用反证法来说明为什么这样就能保证新的领导者一定包含全部之前任期已经committed的日志条目。首先假设任期T的领导者t commit了一个条目，但是这个条目没有被未来的某个领导者所有。再假设没有这个条目的领导者中任期最小的是U，那么我们知道T之后U之前的领导者也保存了该committed日志条目。第一，任期U的领导者u在竞选时就没有保存该条目，这是因为领导者不可能删除重写自己的条目。第二，因为大多数节点接受了committed条目，而大多数节点也投票给u，所以至少存在一个节点x接受了该条目，还投票给u，这个节点将是矛盾关键。第三，接收committed条目不可能发生在投票给u之后，因为任期号T＜U,来自t的AppendEntries RPC将被拒绝。第四，节点x在投票给u时依然储存着committed条目，这是因为U之前的领导者也保存了该committed日志条目，所以不会把x接收到的条目重写。第五，x投票给u，则u的日志跟x一样新（或更新）。分两种情况讨论。

（1）x和u最后条目的任期号一样，但u的日志不短于x，所以x有的条目u一定有，但这与x拥有u没有的committed条目矛盾。

（2）u的最后条目的任期号更大。由于T之后U之前的领导者也保存了该committed日志条目，所以该领导者在为u创造一个任期号更大的条目时，根据前面讲到的日志匹配性，u也必须包含committed条目，这也将造成矛盾。

由此得证，任期T之后的领导者都会包含任期T提交的条目。这就说明了Raft算法能够保证副本与主节点一致，且主节点切换时已提交的条目不会被重写。

6.2.3 联盟链常用共识机制架构

一、Hyperledger Fabric

Fabric的架构中，节点被赋予了3种角色：排序节点、背书节点与提交节点。其中，排序节点只负责交易顺序的共识，采用的是Kafka（由于Kafka自身的劣势，Fabric 2.0后已不支持Kafka）或Raft的共识方式；而交易的状态共识是由客户端、背书节点与排序节点完成。

二、FISCO BCOS

FISCO BCOS与Fabric不同，它不仅使用了Raft，还使用了拜占庭容错机制（包括PBFT/RPDFT），可以提供1/3的容错率。FISCO BCOS将链上的节点分为共识节点、只读节点和游离节点，3类节点如表6-1所示。