区块链里什么是拜占庭容错算法 拜占庭错误容忍算法

本篇文章主要给网友们分享区块链里什么是拜占庭容错算法的知识，其中更加会对拜占庭错误容忍算法进行更多的解释，如果能碰巧解决你现在面临的问题，记得关注本站！

[转载] 分布式系统核心问题--拜占庭问题与算法

拜占庭问题（Byzantine Problem）更为广泛区块链里什么是拜占庭容错算法，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭容错（Byzantine Fault Tolerant，BFT）算法讨论的是在拜占庭情况下对系统如何达成共识。

在拜占庭将军问题之前，就已经存在两将军问题（Two Generals Paradox）区块链里什么是拜占庭容错算法：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失或伪造），如何达成一致？根据FLP不可能原理，这个问题无通用解。

拜占庭问题又叫拜占庭将军问题（Byzantine Generals Problem），是Leslie Lamport等科学家于1982年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图干扰共识的达成。拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。

论文中指出，对于拜占庭问题来说，假如节点总数为N，叛变将军数为F，则当N≥3F+1时，问题才有解，由BFT算法进行保证。

例如，N=3，F=1时。

提案人不是叛变者，提案人发送一个提案出来，叛变者可以宣称收到的是相反的命令。则对于第三个人（忠诚者）收到两个相反的消息，无法判断谁是叛变者，则系统无法达到一致。

提案人是叛变者，发送两个相反的提案分别给另外两人，另外两人都收到两个相反的消息，无法判断究竟谁是叛变者，则系统无法达到一致。

更一般的，当提案人不是叛变者，提案人提出提案信息1，则对于合作者来看，系统中会有N-F份确定的信息1，和F份不确定的信息（可能为0或1，假设叛变者会尽量干扰一致的达成），N-FF，即N2F情况下才能达成一致。

当提案人是叛变者，会尽量发送相反的提案给N-F个合作者，从收到1的合作者看来，系统中会存在（N-F）/2个信息1，以及（N-F）/2个信息0；从收到0的合作者看来，系统中会存在（N-F）/2个信息0，以及（N-F）/2个信息1；另外存在F-1个不确定的信息。合作者要想达成一致，必须进一步对所获得的消息进行判定，询问其他人某个被怀疑对象的消息值，并通过取多数来作为被怀疑者的信息值。这个过程可以进一步递归下去。

Leslie Lamport等人在论文《Reaching agreement in the presence of faults》中证明，当叛变者不超过1/3时，存在有效的拜占庭容错算法（最坏需要F+1轮交互）。反之，如果叛变者过多，超过1/3，则无法保证一定能达到一致结果。

那么，当存在多于1/3的叛变者时，有没有可能存在解决方案呢？

设想F个叛变者和L个忠诚者，叛变者故意使坏，可以给出错误的结果，也可以不响应。某个时候F个叛变者都不响应，则L个忠诚者取多数即能得到正确结果。当F个叛变者都给出一个恶意的提案，并且L个忠诚者中有F个离线时，剩下的L-F个忠诚者此时无法分别是否混入了叛变者，仍然要确保取多数能得到正确结果，因此，L-FF，即L2F或NF2F，所以系统整体规模N要大于3F。

能确保达成一致的拜占庭系统节点数至少为4，此时最多允许出现1个坏的节点。

3.拜占庭容错算法

拜占庭容错算法（Byzantine Fault Tolerant，BFT）是面向拜占庭问题的容错算法，解决的是在网络通信可靠但节点可能故障情况下如何达成共识。拜占庭容错算法最早的讨论在1980年Leslie Lamport等人发表的论文《Polynomial Algorithms for Byzantine Agreement》，之后出现了大量的改进工作。长期以来，拜占庭问题的解决方案都存在复杂度过高的问题，直到PBFT算法的提出。

1999年，Castro和Liskov于论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出的Practical Byzantine Fault Tolerant（PBFT）算法，基于前人工作进行了优化，首次将拜占庭容错算法复杂度从指数级降低到了多项式级，目前已得到广泛应用。其可以在失效节点不超过总数1/3的情况下同时保证Safety和Liveness。

PBFT算法采用密码学相关技术（RSA签名算法、消息验证编码和摘要）确保消息传递过程无法被篡改和破坏。

算法的基本过程如下：

·首先通过轮换或随机算法选出某个节点为主节点，此后只要主节点不切换，则称为一个视图（View）；

·在某个视图中，客户端将请求REQUEST，operation，timestamp，client发送给主节点，主节点负责广播请求到所有其他副本节点；

·所有节点处理完成请求，将处理结果REPLY，view，timestamp，client，id_node，response返回给客户端。客户端检查是否收到了至少f+1个来自不同节点的相同结果，作为最终结果。主节点广播过程包括三个阶段的处理：预准备（pre-prepare）阶段、准备（prepare）阶段和提交（commit）阶段。预准备和准备阶段确保在同一个视图内请求发送的顺序正

确；准备和提交阶段则确保在不同视图之间的确认请求是保序的：

·预准备阶段： 主节点为从客户端收到的请求分配提案编号，然后发出预准备消息 PRE-PREPARE，view，n，digest，message给各副本节点，其中message是客户端的请求消息，digest是消息的摘要；

·准备阶段： 副本节点收到预准备消息后，检查消息合法，如检查通过则向其他节点发送准备消息PREPARE，view，n，digest，id，带上自己的id信息，同时接收来自其他节点的准备消息。收到准备消息的节点对消息同样进行合法性检查。验证通过则把这个准备消息写入消息日志中。集齐至少2 f+1个验证过的消息才进入准备状态；

·提交阶段： 广播commit消息，告诉其他节点某个提案n在视图v里已经处于准备状态。如果集齐至少2 f+1个验证过的commit消息，则说明提案通过。

具体实现上还包括视图切换、checkpoint机制等，可自行参考论文内容。

Tendermint 共识算法

分布式一致性算法一般可以分为两类：拜占庭容错和非拜占庭容错。

非拜占庭容错算法如 Paxos, Raft 等在当前区块链里什么是拜占庭容错算法的分布式系统中已经广泛使用区块链里什么是拜占庭容错算法，而拜占庭容错算法的实际应用范围相对来说小很多(特别是在区块链问世之前)。

Tendermint 属于拜占庭容错算法区块链里什么是拜占庭容错算法，它针对传统的 PBFT 算法做了优化，只需要有两轮投票即可达成共识，目前 Tendermint 算法主要应用在区块链系统中，这篇文章就从原理上来介绍 Tendermint 的共识机制。

关于 Tendermint 算法的完整描述在 这里 。

这里先介绍一下算法的流程，理解了算法流程之后，再来阐述该算法的安全性证明 (Proof of Safty) 和活性证明 (Proof of Liveness)。

下面这张图是 tendermint 状态转换图

算法主要有 NewHeigh - Propose - Prevote - Precommit - Commit 一共 5 个状态（阶段）。

上述每个状态都被称为一个 Step，首尾的 NewHeigh 和 Commit 这两个 Steps 被称为特殊的 Step，而中间加粗体的三个 Steps 则被称为一个 Round，是共识阶段，也是也是算法的核心原理所在。

需要注意的是，一个块的最终提交（Commit）可能需要多个 Round 过程，这是因为有许多原因可能会导致当前 Round 不成功（比如出块节点 Offline，提出的块是无效块，收到的 Prevote 或者 Precommit 票数不够 +2/3 等等），出现这些情况的话，解决方案就是移步到下一轮，或者增加 timeout 时间）。

这里，还要介绍一个重要概念：PoLC，全称为 Proof of Lock Change，表示在某个特定的高度和轮数(height, round)，对某个块或 nil (空块)超过总结点 2/3 的 Prevote 投票集合，简单来说 PoLC 就是 Prevote 的投票集。

Tendermint 中有两种类型的节点，Validator 节点和 Non-Validator 节点，顾名思义，只有 Validator 节点会参与共识投票，而普通节点作为 Non-Validator 节点，不参与共识投票，只协助传递状态或向 Validator 节点发送交易请求。

初始状态下（创世块），高度为 0， 此时，系统会基于 Round Robin 原则来选出一个 Validator（每个 Validator 都有一定的 Voting Power），由这个 Validator 打包一个新的 Block， 并向所有节点发出 Proposal，剩余的 Validator 节点对该 Proposal 进行投票，最终达成共识。

以下，分阶段来阐述各个阶段:

当上一轮 Commit 结束，就会出现新高度，这是就需要进入下一轮共识了，也就是说，这就是新一轮共识过程的开始，这时候需要选出一个 Proposer。选择算法是 Round Robin，基于他们的 Voting Power（上一轮的选中的 Validator 节点会把其 Voting Power 值减去 Total Voting Power，也就是说上一轮的 Validator 在这一轮，其 Voting Power 会变成负数）。

在 Propose 节点开始的时候，该轮指定的 proposer 需要通过 gossip 广播一条 proposal 到所有的 peers。如果此时这个 proposer 被锁在上一轮的某个 block 上，那么它就直接 propose 那个 block，同时包含一条 proof of lock 的信息。

Validator 节点收到 propose 信息之后就进入 Prevote 投票阶段。投票时，如果 Validator 被锁在之前一个 block 上，那么还是给之前那个 block 投 prevote 票，否则就投当前的 block。同时，它会继续收集对这个 block 的 prevote 投票，等轮到他 propose 的时候打包进 PoLC。

注意：

如果自己有 Lock-Block，这时又收到一个新的针对另外一个块的 PoLC，并且满足LastLockRound PoLC-Round 当前 Round，则解锁 Lock-Block。

如果 timeout 期间没收到 proposal，或者收到的 proposal 是无效的，那么就投 nil 票。

在 Prevote 阶段不会锁住任何 block。

Prevote 超时或者收到的 Prevote 的 nil 票超过 2/3 时，就进入 Precommit 阶段。

如果此时收到了 +2/3 的 prevote 投票，就广播一条 precommit 投票，同时， 把自己锁在当前的 block 上（把之前的都释放掉） 。一个节点一次只能锁在一个块上。

如果收到 +2/3 的 nil 投票，那么就释放锁。

当一个节点锁在一个 block 上的时候（有 PoLC） ，它会将 LastLockRound 置为当前 Round，并对这个块投 Precommit 票。

如果有针对 nil 票的 PoLC，则解锁并且对 nil 投 Precommit 票；否则的话保持 Lock-Block 不变，并投 nil 。

如果在 timeout 期间内，没有收到对某个块的足够的 +2/3 投票（prevote 或者 nil 都行），那么就什么也不干。

最终，如果一个节点收到了 +2/3 的 precommit 投票，就进入 Commit 阶段。否则，继续进入下一轮的 Propose 阶段。

Commit 阶段是一个特殊阶段，有两个并行的条件必须满足：

At any time during the consensus process if a node receives more than 2/3 of commits for a particular block, it immediately enters the Commit step if it hadn’t already. Thus there are two ways to enter the Commit step. A commit-vote for a block at round R counts as prevotes and precommits for all rounds R0 where R R0 . Commit-votes are gossipped to neighboring peers in the background re-gardless of the current round or step。

At any time during the consensus process if a node is locked on a block from round R but receives a proof-of-lock for a round R0 where R R0 , the node unlocks.

Tendermint 的安全性就是说，在对高度为 H 的块达成共识之后，不可能会出现新的高度为 H 的块，也就是说 Tendermint 保证不会分叉，保证不会分叉的主要角色就是 Lock-Block。

先看下wiki对于安全性证明的描述：

Assume that at most -1/3 of the voting power of validators is byzantine. If a validator commits block B at

round R, it's because it saw +2/3 of precommits at round R. This implies that 1/3+ of honest nodes are still

locked at round R' R. These locked validators will remain locked until they see a PoLC at R' R, but this

won't happen because 1/3+ are locked and honest, so at most -2/3 are available to vote for anything other

than B.

翻译：

假定有最多小于总结点 1/3 的拜占庭节点。如果一个节点在第 R 轮提交一个块，则表明此节点在第 R 轮收到大于 2/3 的针对此块的 Precommit 投票。这也就意味有

大于1/3 的诚实节点在第 R’ (R' R)轮仍然锁定在这个块上(因为大于 2/3 的 Precommit 投票必定包含大于 1/3 诚实节点的 Precommit 投票)。只有当遇到针对另一个

块的 PoLC 时才会解锁，但是在 R' 轮是不可能有针对某个块的 PoLC，因为已经有大于 1/3 的诚实节点已经锁定在这个块上，所以就不可能有对另外一个块大于 2/3

的 Prevote 投票。

下面给出较为详细的证明过程，假设高度为 H 的块 b 在第 R 轮达成共识。给出如下条件：

需要证明， 当 x 个节点 commit 之后，剩余(也就是 y + z)的没有 Commit 块 b 的节点不会对另外一个块达成共识。

也就是说需要证明：y + z - z0 2/3，假设所有的拜占庭节点都对 b 投了 Precommit，则满足：x + y + z0 2/3。

简而言之，要从 x + y + z0 2/3 证明 y + z - z0 2/3。

区块链里什么是拜占庭容错算法我们通过反证法来证明：

假设 y + z - z0 2/3，也就是在第 r 轮之后有可能造成分叉，则：

x + y + z - z0 2/3 + x = 1 - z0 2/3 + x = x + z0 1/3。

而上面区块链里什么是拜占庭容错算法我们提到了，因为x节点已经 Commit 块 b，则 x + y + z0 2/3，且 y 1/3，则说明 x + z0 必须大于1/3。由此证明，y + z - z0 1/3 成立，在第 R 轮之后无法对另一个块达成共识，也就不可能出现分叉。

活性证明相对来说就要简单一些，假设多于 1/3 的节点分别 Lock 在不同的块上，则在 Prevote 阶段的条件保证最终 round 较小的会 unlock，而且 proposal 的超时时间会随着轮数的提高而提高。

在证明安全性的过程中提到，有可能会有部分节点由于没有收到足够的 Precommit 投票导致无法 commit，这个时候可以通过同步来使各个节点的状态尽量保持一致，在wiki中提到一个 JSet 和 VSet 的概念，当节点已经 commit 时，就可以广播一条消息携带 VSet 给其他节点，其他节点验证对于块的 commit 是否有效。这一点其实和 bft-raft （另外一个拜占庭容错算法，Raft 算法的变种）的做法类似。

区块链 --- 共识算法

PoW算法是一种防止分布式服务资源被滥用、拒绝服务攻击的机制。它要求节点进行适量消耗时间和资源的复杂运算，并且其运算结果能被其他节点快速验算，以耗用时间、能源做担保，以确保服务与资源被真正的需求所使用。

PoW算法中最基本的技术原理是使用哈希算法。假设求哈希值Hash(r)，若原始数据为r（raw），则运算结果为R（Result）。

R = Hash(r)

哈希函数Hash()的特性是，对于任意输入值r，得出结果R，并且无法从R反推回r。当输入的原始数据r变动1比特时，其结果R值完全改变。在比特币的PoW算法中，引入算法难度d和随机值n，得到以下公式：

Rd = Hash(r+n)

该公式要求在填入随机值n的情况下，计算结果Rd的前d字节必须为0。由于哈希函数结果的未知性，每个矿工都要做大量运算之后，才能得出正确结果，而算出结果广播给全网之后，其他节点只需要进行一次哈希运算即可校验。PoW算法就是采用这种方式让计算消耗资源，而校验仅需一次。

PoS算法要求节点验证者必须质押一定的资金才有挖矿打包资格，并且区域链系统在选定打包节点时使用随机的方式，当节点质押的资金越多时，其被选定打包区块的概率越大。

POS模式下，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000。这个时候，如果你验证了一个POS区块，你的币龄就会被清空为0，同时从区块中获得相对应的数字货币利息。

节点通过PoS算法出块的过程如下：普通的节点要成为出块节点，首先要进行资产的质押，当轮到自己出块时，打包区块，然后向全网广播，其他验证节点将会校验区块的合法性。

DPoS算法和PoS算法相似，也采用股份和权益质押。

但不同的是，DPoS算法采用委托质押的方式，类似于用全民选举代表的方式选出N个超级节点记账出块。

选民把自己的选票投给某个节点，如果某个节点当选记账节点，那么该记账节点往往在获取出块奖励后，可以采用任意方式来回报自己的选民。

这N个记账节点将轮流出块，并且节点之间相互监督，如果其作恶，那么会被扣除质押金。

通过信任少量的诚信节点，可以去除区块签名过程中不必要的步骤，提高了交易的速度。

拜占庭问题：

拜占庭是古代东罗马帝国的首都，为了防御在每块封地都驻扎一支由单个将军带领的军队，将军之间只能靠信差传递消息。在战争时，所有将军必须达成共识，决定是否共同开战。

但是，在军队内可能有叛徒，这些人将影响将军们达成共识。拜占庭将军问题是指在已知有将军是叛徒的情况下，剩余的将军如何达成一致决策的问题。

BFT：

BFT即拜占庭容错，拜占庭容错技术是一类分布式计算领域的容错技术。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为，并满足所要解决的问题的规范要求。

拜占庭容错系统 ：

发生故障的节点被称为 拜占庭节点 ，而正常的节点即为 非拜占庭节点 。

假设分布式系统拥有n台节点，并假设整个系统拜占庭节点不超过m台（n ≥ 3m + 1），拜占庭容错系统需要满足如下两个条件：

另外，拜占庭容错系统需要达成如下两个指标：

PBFT即实用拜占庭容错算法，解决了原始拜占庭容错算法效率不高的问题，算法的时间复杂度是O(n^2)，使得在实际系统应用中可以解决拜占庭容错问题

PBFT是一种状态机副本复制算法，所有的副本在一个视图（view）轮换的过程中操作，主节点通过视图编号以及节点数集合来确定，即：主节点 p = v mod |R|。v：视图编号，|R|节点个数，p：主节点编号。

PBFT算法的共识过程如下：客户端（Client）发起消息请求（request），并广播转发至每一个副本节点（Replica），由其中一个主节点（Leader）发起提案消息pre-prepare，并广播。其他节点获取原始消息，在校验完成后发送prepare消息。每个节点收到2f+1个prepare消息，即认为已经准备完毕，并发送commit消息。当节点收到2f+1个commit消息，客户端收到f+1个相同的reply消息时，说明客户端发起的请求已经达成全网共识。

具体流程如下 ：

客户端c向主节点p发送REQUEST, o, t, c请求。o: 请求的具体操作，t: 请求时客户端追加的时间戳，c：客户端标识。REQUEST: 包含消息内容m，以及消息摘要d(m)。客户端对请求进行签名。

主节点收到客户端的请求，需要进行以下交验：

a. 客户端请求消息签名是否正确。

非法请求丢弃。正确请求，分配一个编号n，编号n主要用于对客户端的请求进行排序。然后广播一条PRE-PREPARE, v, n, d, m消息给其他副本节点。v：视图编号，d客户端消息摘要，m消息内容。PRE-PREPARE, v, n, d进行主节点签名。n是要在某一个范围区间内的[h, H]，具体原因参见 垃圾回收 章节。

副本节点i收到主节点的PRE-PREPARE消息，需要进行以下交验：

a. 主节点PRE-PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了一条在同一v下并且编号也是n，但是签名不同的PRE-PREPARE信息。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。正确请求，副本节点i向其他节点包括主节点发送一条PREPARE, v, n, d, i消息, v, n, d, m与上述PRE-PREPARE消息内容相同，i是当前副本节点编号。PREPARE, v, n, d, i进行副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中，用于View Change过程中恢复未完成的请求操作。

主节点和副本节点收到PREPARE消息，需要进行以下交验：

a. 副本节点PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. n是否在区间[h, H]内。

d. d是否和当前已收到PRE-PPREPARE中的d相同

非法请求丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息，则向其他节点包括主节点发送一条COMMIT, v, n, d, i消息，v, n, d, i与上述PREPARE消息内容相同。COMMIT, v, n, d, i进行副本节点i的签名。记录COMMIT消息到日志中，用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的PREPARE消息到log中。

主节点和副本节点收到COMMIT消息，需要进行以下交验：

a. 副本节点COMMIT消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息，说明当前网络中的大部分节点已经达成共识，运行客户端的请求操作o，并返回REPLY, v, t, c, i, r给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的COMMIT消息到log中。

如果主节点作恶，它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性。

如果主节点掉线或者作恶不广播客户端的请求，客户端设置超时机制，超时的话，向所有副本节点广播请求消息。副本节点检测出主节点作恶或者下线，发起View Change协议。

View Change协议 ：

副本节点向其他节点广播VIEW-CHANGE, v+1, n, C , P , i消息。n是最新的stable checkpoint的编号， C 是 2f+1验证过的CheckPoint消息集合， P 是当前副本节点未完成的请求的PRE-PREPARE和PREPARE消息集合。

当主节点p = v + 1 mod |R|收到 2f 个有效的VIEW-CHANGE消息后，向其他节点广播NEW-VIEW, v+1, V , O 消息。 V 是有效的VIEW-CHANGE消息集合。 O 是主节点重新发起的未经完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的选取规则：

副本节点收到主节点的NEW-VIEW消息，验证有效性，有效的话，进入v+1状态，并且开始 O 中的PRE-PREPARE消息处理流程。

在上述算法流程中，为了确保在View Change的过程中，能够恢复先前的请求，每一个副本节点都记录一些消息到本地的log中，当执行请求后副本节点需要把之前该请求的记录消息清除掉。

最简单的做法是在Reply消息后，再执行一次当前状态的共识同步，这样做的成本比较高，因此可以在执行完多条请求K（例如：100条）后执行一次状态同步。这个状态同步消息就是CheckPoint消息。

副本节点i发送CheckPoint, n, d, i给其他节点，n是当前节点所保留的最后一个视图请求编号，d是对当前状态的一个摘要，该CheckPoint消息记录到log中。如果副本节点i收到了2f+1个验证过的CheckPoint消息，则清除先前日志中的消息，并以n作为当前一个stable checkpoint。

这是理想情况，实际上当副本节点i向其他节点发出CheckPoint消息后，其他节点还没有完成K条请求，所以不会立即对i的请求作出响应，它还会按照自己的节奏，向前行进，但此时发出的CheckPoint并未形成stable。

为了防止i的处理请求过快，设置一个上文提到的 高低水位区间[h, H] 来解决这个问题。低水位h等于上一个stable checkpoint的编号，高水位H = h + L，其中L是我们指定的数值，等于checkpoint周期处理请求数K的整数倍，可以设置为L = 2K。当副本节点i处理请求超过高水位H时，此时就会停止脚步，等待stable checkpoint发生变化，再继续前进。

在区块链场景中，一般适合于对强一致性有要求的私有链和联盟链场景。例如，在IBM主导的区块链超级账本项目中，PBFT是一个可选的共识协议。在Hyperledger的Fabric项目中，共识模块被设计成可插拔的模块，支持像PBFT、Raft等共识算法。

Raft基于领导者驱动的共识模型，其中将选举一位杰出的领导者(Leader)，而该Leader将完全负责管理集群，Leader负责管理Raft集群的所有节点之间的复制日志。

下图中，将在启动过程中选择集群的Leader（S1），并为来自客户端的所有命令/请求提供服务。 Raft集群中的所有节点都维护一个分布式日志（复制日志）以存储和提交由客户端发出的命令（日志条目）。 Leader接受来自客户端的日志条目，并在Raft集群中的所有关注者（S2，S3，S4，S5）之间复制它们。

在Raft集群中，需要满足最少数量的节点才能提供预期的级别共识保证， 这也称为法定人数。 在Raft集群中执行操作所需的最少投票数为 (N / 2 +1) ，其中N是组中成员总数，即 投票至少超过一半 ，这也就是为什么集群节点通常为奇数的原因。 因此，在上面的示例中，我们至少需要3个节点才能具有共识保证。

如果法定仲裁节点由于任何原因不可用，也就是投票没有超过半数，则此次协商没有达成一致，并且无法提交新日志。

数据存储：Tidb/TiKV

日志：阿里巴巴的 DLedger

服务发现：Consul etcd

集群调度：HashiCorp Nomad

只能容纳故障节点(CFT)，不容纳作恶节点

顺序投票，只能串行apply，因此高并发场景下性能差

Raft通过解决围绕Leader选举的三个主要子问题，管理分布式日志和算法的安全性功能来解决分布式共识问题。

当我们启动一个新的Raft集群或某个领导者不可用时，将通过集群中所有成员节点之间协商来选举一个新的领导者。 因此，在给定的实例中，Raft集群的节点可以处于以下任何状态: 追随者(Follower)，候选人(Candidate)或领导者(Leader)。

系统刚开始启动的时候，所有节点都是follower，在一段时间内如果它们没有收到Leader的心跳信号，follower就会转化为Candidate；

如果某个Candidate节点收到大多数节点的票，则这个Candidate就可以转化为Leader，其余的Candidate节点都会回到Follower状态；

一旦一个Leader发现系统中存在一个Leader节点比自己拥有更高的任期(Term)，它就会转换为Follower。

Raft使用基于心跳的RPC机制来检测何时开始新的选举。 在正常期间， Leader 会定期向所有可用的 Follower 发送心跳消息（实际中可能把日志和心跳一起发过去）。 因此，其他节点以 Follower 状态启动，只要它从当前 Leader 那里收到周期性的心跳，就一直保持在 Follower 状态。

当 Follower 达到其超时时间时，它将通过以下方式启动选举程序：

根据 Candidate 从集群中其他节点收到的响应，可以得出选举的三个结果。

共识算法的实现一般是基于复制状态机（Replicated state machines），何为 复制状态机 ：

简单来说： 相同的初识状态 + 相同的输入 = 相同的结束状态 。不同节点要以相同且确定性的函数来处理输入，而不要引入一下不确定的值，比如本地时间等。使用replicated log是一个很不错的注意，log具有持久化、保序的特点，是大多数分布式系统的基石。

有了Leader之后，客户端所有并发的请求可以在Leader这边形成一个有序的日志（状态）序列，以此来表示这些请求的先后处理顺序。Leader然后将自己的日志序列发送Follower，保持整个系统的全局一致性。注意并不是强一致性，而是 最终一致性 。

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和日志中包含的数据组成，日志包含的数据可以为任何类型，从简单类型到区块链的区块。每个日志条目可以用[ term, index, data]序列对表示，其中term表示任期， index表示索引号，data表示日志数据。

Leader 尝试在集群中的大多数节点上执行复制命令。 如果复制成功，则将命令提交给集群，并将响应发送回客户端。类似两阶段提交(2PC)，不过与2PC的区别在于，leader只需要超过一半节点同意（处于工作状态）即可。

leader 、 follower 都可能crash，那么 follower 维护的日志与 leader 相比可能出现以下情况

当出现了leader与follower不一致的情况，leader强制follower复制自己的log， Leader会从后往前试 ，每次AppendEntries失败后尝试前一个日志条目（递减nextIndex值）， 直到成功找到每个Follower的日志一致位置点（基于上述的两条保证），然后向后逐条覆盖Followers在该位置之后的条目 。所以丢失的或者多出来的条目可能会持续多个任期。

要求候选人的日志至少与其他节点一样最新。如果不是，则跟随者节点将不投票给候选者。

意味着每个提交的条目都必须存在于这些服务器中的至少一个中。如果候选人的日志至少与该多数日志中的其他日志一样最新，则它将保存所有已提交的条目，避免了日志回滚事件的发生。

即任一任期内最多一个leader被选出。这一点非常重要，在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。在raft中，两点保证了这个属性：

因此， 某一任期内一定只有一个leader 。

当集群中节点的状态发生变化（集群配置发生变化）时，系统容易受到系统故障。 因此，为防止这种情况，Raft使用了一种称为两阶段的方法来更改集群成员身份。 因此，在这种方法中，集群在实现新的成员身份配置之前首先更改为中间状态（称为联合共识）。 联合共识使系统即使在配置之间进行转换时也可用于响应客户端请求，它的主要目的是提升分布式系统的可用性。

拜占庭容错和PBFT共识算法

实用的拜占庭容错算法

BFT 是区块链共识算法中，需要解决的一个核心问题。比特币的POW，eos的dpos，以及共识算法pos，这些公链算法，解决的是共识节点众多情况下的bft问题。

拜占庭将军问题。也称为拜占庭容错。

用来描述分布式系统一致性问题。

背景如下：

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？

单从上面的说明可能无法理解这个问题的复杂性，我们来简单分析一下：

先看在没有叛徒情况下，假如一个将军A提一个进攻提议（如：明日下午1点进攻，你愿意加入吗？）由通信兵通信分别告诉其他的将军，如果幸运中的幸运，他收到了其他6位将军以上的同意，发起进攻。如果不幸，其他的将军也在此时发出不同的进攻提议（如：明日下午2点、3点进攻，你愿意加入吗？），由于时间上的差异，不同的将军收到（并认可）的进攻提议可能是不一样的，这是可能出现A提议有3个支持者，B提议有4个支持者，C提议有2个支持者等等。

再加一点复杂性，在有叛徒情况下，一个叛徒会向不同的将军发出不同的进攻提议（通知A明日下午1点进攻， 通知B明日下午2点进攻等等），一个叛徒也会可能同意多个进攻提议（即同意下午1点进攻又同意下午2点进攻）。

叛徒发送前后不一致的进攻提议，被称为“拜占庭错误”，而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。

使用密码学算法保证节点之间的消息传送是不可篡改的， 通过下面的算法我们可以保证A将军收到B将军发来的消息确实是B将军本人的真实请求 。

我们采用的是哈希函数（散列算法）SHA256 -- 从数据（byte）值中创建独一无二的hash值，并压缩成摘要，将数据格式固定下来。通过这个摘要与个人私钥生成Digital Signature 和个人公钥Public-key certificate，接收方验证签名和摘要，如果是通过验证，即证明摘要内容没有经过篡改。

pbft容忍无效或者恶意节点数量 e 。为了保证整个系统可以正常运作，需要有2f+1个正常节点，系统的总结点数为 ：3f+1。即pbft算法容忍小于1/3的恶意或者无效节点。 原因见节点作恶的极端情况

pbft是一种状态机副本复制算法，所有副本在一个view轮换过程中操作，哪些是主节点（进攻的提议者的大将军们，轮流当）通过view中其他节点（其他将军）赋予的编号和节点数集合来确定，即：主节点p=v mod |R| 。 v：view编号，|R|节点个数，p：主节点编号。 关于状态机复制算法、view change的意义（主要是防止主节点作恶），主节点详见论文。

基于拜占庭将军问题，PBFT算法一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：

[图片上传失败...(image-e3329d-1562488133052)]

首先解释一下上面各个符号表达的意思：

下面结合上图，详细说一下PBFT的步骤：

根据上述流程，在 N ≥ 3F + 1 的情况下一致性是可能解决， N为总计算机数，F为有问题的计算机总数 。

下面所有的校验流程略去对消息内容、签名和身份的验证，即已经保证了节点之间消息传播是不可篡改的

上述算法中，比较重要的一个点是view change，为了能恢复之前的请求，每一个副本节点收到消息之后或者发送消息的时候都会记录消息到本地的log记录中。当执行请求后，副本节点需要把之前该请求的记录消息清除掉。最简单的做法是在reply消息后，在执行一次当前状态的共识同步，但是为了节省资源，一般在多条请求K后执行一次状态同步。这个状态同步就是checkpoint消息。

为了节省内存，系统需要一种将日志中的 无异议消息记录 删除的机制。为了保证系统的安全性，副本节点在删除自己的消息日志前，需要确保至少 f+1 个正常副本节点执行了消息对应的请求，并且可以在视图变更时向其他副本节点证明。另外，如果一些副本节点错过部分消息，但是这些消息已经被所有正常副本节点删除了，这就需要通过 传输部分或者全部服务状态实现该副本节点的同步 。因此，副本节点同样需要证明状态的正确性。

在每一个操作执行后都生成这样的证明是非常消耗资源的。因此，证明过程只有在请求序号可以被某个常数（比如100）整除的时候才会周期性地进行。我们将这些请求执行后得到的状态称作 检查点（checkpoint） ，并且将具有证明的检查点称作 稳定检查点（stable checkpoint） 。

上述情况是理想情况，实际上当副本节点i向其他节点发出checkpoint消息之后，其他节点还没有完成K条请求的相互共识，所以不会立即对i的请求作出响应。其他节点会按照自己的处理步骤和顺序，向前行进和共识。但是此时i发出的checkpoint没有形成stable，为了防止i太快，超过自己太多，于是被便会设置一个高水位H=h+L，其中L就是我们指定允许的高度差，等于checkpoint周期处理数K的整数倍，可以设置为L=2K。当副本节点i处理请求超过高水位H时，副本节点即使接受到请求也会视为非法请求。等待stable checkpoint发生变化，再继续向前推进处理。

如果主节点作恶，它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻请求的序号不连续。备份节点（备份主节点）应当有职责来主动检查这些序号的合法性。如果主节点掉线或者作恶不广播客户端的请求，客户端设置超时机制，超时的话，向所有副本节点广播请求消息。副本节点检测出主节点或者下线，发起view change流程。

我们在上面讲到，当网络中有F台有问题的计算机时，至少需要3F+1台计算机才能保证一致性问题的解决，我们在这里讨论一下原因。

我们可以考虑：由于有F个节点为故障或被攻击的节点，故我们只能从N-F个节点中进行判断。但是由于异步传输，故当收到N-F个消息后，并不能确定后面是否有新的消息。（有可能是目前收到的N-F个节点的消息中存在被攻击的节点发来的消息，而好的节点的消息由于异步传输还没有被收到。）

我们考虑最坏的情况，即剩下F个都是好的节点，收到的中有F个被攻击的节点，故我们需要使得收到的中好节点的数量 (N-F)-F 大于被攻击节点的数量 F ，于是有 N-2FF ，即 N3F ，所以N的最小整数为 N=3F+1 。

pbft是需要参与认证的节点进行的。所以一个完整的共识算法包括DPOS+PBFT。其速度是可以达到1500tps左右的。

参考文献：

Practical Byzantine Fault Tolerance

Miguel Castro and Barbara Liskov Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139 castro,liskov @lcs .mit.edu

部分论文翻译

共识算法4 (BFT)

拜占庭将军问题（Byzantine Generals Problem），由Leslie Lamport、Robert Shostak和Marshall Pease，在其同名论文中提出（1982年）。拜占庭将军问题现在主要指分布式对等网络节点间的通信容错问题。在分布式网络中，不同的计节点通过交换信息达成共识。但有时候，系统中的成员节点可能出错而发送错误的信息，用于传递信息的通讯网络也可能导致信息损坏，也可能存在恶意节点或被黑客攻破的节点故意发送错误的信息，从而导致系统无法达成共识或者达成错误的共识。（参考： BFT Wikipedia ）

拜占庭将军问题提出后，有很多的算法被提出用于解决这个问题。这类算法统称拜占庭容错算法（BFT: Byzantine Fault Tolerance）。BFT从上世纪80年代开始被研究，目前已经是一个被研究得比较透彻的理论，具体实现都已经有现成的算法。

BFT算法中最典型的是PBFT（Practical BFT）。PBFT是由Miguel Castro和Barbara Liskov于1999年提出。PBFT算法解决了之前拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。PBFT在保证安全性和可用性的前提下，提供了 (n-1)/3 的容错性。（细节请参考： PBFT ）

PBFT之后，很多进一步提升性能或鲁棒性的BFT算法先后被提出，例如Zyzzyva、ABsTRACTs、Aardvark、RBFT等等。近几年，由于区块链的热度，无数针对区块链应用场景优化过的BFT算法也不断涌现出来。虽然目前PBFT已经不能说是最好的，或最适合区块链的BFT算法。但是PBFT已经足够好了，而且在实际应用中已经非常成熟。

在BFT共识机制中，网络中节点的数量和身份必须是提前确定好的。BFT共识机制无法做到PoW共识机制中实现的任何人都可以随时加入挖矿。另外，BFT算法无法应用到大量的节点，业内普遍认为100个节点是BFT算法的上限。所以BFT算法无法直接用于公有链，BFT算法适合的场景是私有链和联盟链。业内大名鼎鼎的联盟链Hyperledger fabric v0.6采用的是PBFT，v1.0又推出PBFT的改进版本SBFT。这里再顺便提一句，在可信环境下共识算法一般使用传统的分布式一致算法PAXOS或者RAFT。

公有链使用BFT的一个例外是NEO，NEO使用了DBFT（delegated BFT）共识机制。DBFT共识机制下投票选出7个共识节点。这些代理节点是通过静态选出的，并完全由项目方部署。这也是NEO被外界质疑过于中心化的原因。（参考： 早期公有链明星项目-NEO ）

BFT算法和公有链合适的结合点在于基于BFT的PoS共识算法（BFT based PoS）。基于BFT的PoS共识算法要点有：一，网络节点通过锁定虚拟资产申请成为区块链系统的验证者（或矿工）。系统验证者的数量是动态变化的。二，系统从当前验证者中随机选择一个人作为区块提案人。三，系统验证者对区块提案进行投票表决，投票可能要进行多轮才能达成共识。每个人的投票比重与锁定的虚拟资产成比例。

基于BFT的PoS的典型例子是tendermint（Cosmos采用了tendermint作为共识核心）。

区块链里什么是拜占庭容错算法的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于拜占庭错误容忍算法、区块链里什么是拜占庭容错算法的信息别忘了在本站进行查找喔。