共计 8633 个字符，预计需要花费 22 分钟才能阅读完成。
实用性拜占庭容错算法（Practical Byzantine Fault Tolerance，PBFT），是一种在信道牢靠的状况下解决拜占庭将军问题的实用办法。拜占庭将军问题最早由 Leslie Lamport 等人在 1982 年发表的论文 [1] 提出，论文中证实了在将军总数 n 大于 3f，背叛者为 f 或者更少时，虔诚的将军能够达成命令上的统一，即 3f+1<=n，算法复杂度为 O(n^(f+1))。随后 Miguel Castro 和 Barbara Liskov 在 1999 年发表的论文 [2] 中首次提出 PBFT 算法，该算法容错数量也满足 3f+1<=n，算法复杂度升高到了 O(n^2)。
如果对于 PBFT 共识算法有所理解，对节点总数 n 与容错下限 f 的关系可能会比拟相熟：在零碎内最多存在 f 个谬误节点的前提下，零碎内总节点数量 n 应该满足 n >3f，在推动共识过程中则须要收集肯定数目的投票，能力实现认证过程。在本节当中，咱们将首先探讨这些数值间关系该如何得出。
–Quorum 机制 –
在有冗余数据的分布式存储系统当中，冗余数据对象会在不同的机器之间寄存多份拷贝。然而在同一时刻，一个数据对象的多份拷贝只能用于读或者写。为了保持数据冗余与一致性，须要对应的投票机制进行维持，这就是 Quorum 机制。区块链作为一种分布式系统，同样也须要该机制进行集群保护。
为了更好地了解 Quorum 机制，咱们先来理解一种与之相似，然而更加极其的投票机制——WARO 机制（Write All Read One）。应用 WARO 机制保护节点总数为 n 的集群时，节点执行写操作的“票数”该当为 n，而读操作时的“票数”能够设置为 1。也就是说，在执行写入时，须要保障全副节点实现写入操作才可视该操作为实现，否则会写入失败；相应地，在执行读操作时，只须要读取一个节点的状态，就能够对该零碎状态进行确认。能够看到，在应用 WARO 机制的集群中，写操作的执行十分软弱：只有有一个节点执行写入失败，那么这次操作就无奈实现。不过，尽管就义了写操作健壮性，然而，在 WARO 机制下，对于该集群执行读操作会非常容易。
Quorum 机制 [3] 就是对读写操作的折衷思考，对于同一份数据对象的每一份拷贝，不会被超过两个拜访对象读写，并且衡量读写时的汇合大小要求。在一个分布式集群当中，每一份数据拷贝对象都被赋予了一票。假如：
零碎中有 V 票，这就意味着一个数据对象有 V 份冗余拷贝；
对于每一个读操作，取得的票数必须不小于最小读票数 R（read quorum）才能够胜利读取；
对于每个写操作，取得的票数必须不小于最小写票数 W（write quorum）才能够胜利写入。
此时，为了维持集群一致性，V、R、W 应满足不等关系，R+W>V 且 W >V/2。其中，R+W>V 保障了一个数据不会被同时读或写。当一个写操作申请传入，它必须要取得 W 票，而剩下的数量是 V - W 有余 R，因而不会再解决读申请。同理，当读申请曾经取得了 R 票，写申请就无奈被解决。W>V/2，保障了数据的串行批改，也就是说，一份数据的冗余拷贝不可能同时被两个写申请批改。
对于集群中的共识节点，在推动共识算法时，参加共识的节点会同时对集群进行读写操作。为了均衡读写操作对于汇合大小的要求，每个节点的 R 与 W 取同样大小，记为 Q。当集群中总共存在 n 个节点，并且其中最多呈现 f 个谬误节点的状况下，咱们该如何计算 n、f、Q 之间的关系呢？接下来，咱们将从最简略的 CFT 场景登程，逐渐摸索如何在 BFT 场景中失去这些数值取值之间的关系。
▲CFT
CFT（Crash Fault Tolerance），示意零碎中的节点只会呈现宕机（Crash）这种错误行为，任何节点不会被动收回谬误音讯。当咱们在探讨共识算法可靠性时，通常会关注算法两种根本性质：活性（liveness）与安全性（safety）。在计算 Q 的大小时，同样也能够从这两个角度登程进行思考。
对于活性与安全性，有一种比拟直观的形容形式：
something eventually happens[4]，某个事件最终会产生
something good eventually happens[4]，这个最终会产生的事件正当
从活性角度登程，咱们的集群须要可能继续运行上来，不会因为某些节点的谬误导致无奈持续共识。从安全性角度登程，咱们的集群在共识推动的过程中，可能继续取得某个正当的后果，对于分布式系统来说，这种“正当”的后果，其最根本的要求就是集群整体状态的一致性。
于是，在 CFT 场景下，对于 Q 数值的确定就变得简略明确：
活性：因为咱们须要保障集群可能继续运行，所以，在任何场景下都要保障有获取到 Q 票的可能性，从而为汇合读写数据。因为集群中最多会有 f 个节点产生宕机，所以为了保障能获取到 Q 票，该值的大小须要满足：Q<=n-f。
安全性：因为咱们须要保障集群不产生一致，所以，依照 Quorum 机制的根本要求，须要满足在上一节当中提到的两个不等式，将 Q 作为最小读汇合与最小写汇合带入该组不等式，此时，Q 满足不等关系，Q+Q>n 且 Q >n/2，因而，该值的大小须要满足：Q>n/2。
▲BFT
BFT（Byzantine Fault Tolerance），示意集群中的谬误节点不仅可能会产生宕机，也可能存在歹意行为，即拜占庭（Byzantine）行为，例如被动进行状态分叉。在这种状况下，对于集群整体而言，只有 n - f 个节点的状态牢靠，当咱们收集到 Q 个投票时，其中也只有 Q - f 个投票来自牢靠的节点。因而，在安全性方面，BFT 场景下须要保障状态牢靠的节点之间不会产生一致，因而失去以下两种关系：
活性：仍然只须要保障每时每刻都有获取 Q 票的可能性，因而，Q<=n-f。
安全性：对于全副保障正确的节点（总数 n -f）不会产生一致，此时，该当满足不等关系，(Q-f)+(Q-f)>n- f 且(Q-f)>(n-f)/2，因而，此时 Q 的大小须要满足的关系为，Q>(n+f)/2。
▲节点总数与容错下限
对于节点总数 n 与容错下限 f，在 PBFT 论文当中给出的解释[1]：因为存在 f 个节点可能产生宕机，因而咱们至多须要在收到 n - f 条音讯时进行响应，而对于咱们收到的来自 n - f 个节点的音讯，因为其中最多可能存在 f 条音讯来自于不牢靠的拜占庭节点，因而须要满足 n -f-f>f，所以，n>3f。
简略来说，PBFT 的作者从集群活性与安全性登程，失去了节点总数与容错下限之间的关系。上一节中，咱们也是从活性与安全性角度，取得了 n、f 与 Q 的关系，在这里也能够用来推导 n 与 f 的关系：为了同时满足活性与安全性的要求，Q 须要满足不等关系，Q<=n- f 且 Q >(n+f)/2，因而，能够失去 n 与 f 之间的不等关系，(n+f)/2<n-f，也就是 n >3f。
(通过相似的形式，也能够失去 CFT 场景中 n 与 f 的关系，n>2f。)
–PBFT 与 RBFT —
在了解 BFT 场景中 n、f、Q 的关系后，接下来进入到 PBFT 的介绍。在此之前，简略提一下 SMR（State Machine Replication）复制状态机[5]。在该模型当中，对于不同的状态机，如果从同样的初始状态登程，依照同样的程序输出同样的指令集，那么它们失去的最终后果总会统一。对于共识算法而言，其只须要保障“依照同样的程序输出同样的指令”，即可在各个状态机上取得同样的状态。而 PBFT 就是对指令执行程序的共识。
那么，PBFT 是如何保障指令执行程序的一致性呢？PBFT 集群为主从构造，由主节点提出提案，并通过集群中各个节点间的交互进行验证，从而使得每个正确节点遵循同样的程序对指令集进行执行。在这个交互过程中，就须要应用 Quorum 机制保障集群整体状态的一致性。上面咱们将对 PBFT 进行具体介绍。
▲两阶段共识
相比拟常见的“三阶段“概念（pre-preapre、prepare、commit），将 PBFT 视为一种两阶段共识协定或者更能体现每个阶段的目标：提案阶段（pre-prepare 与 prepare）和提交阶段（commit）。在每个阶段中，各个节点都须要收集来自 Q 个节点统一的投票后，才会进入到下一个阶段。为了更不便探讨，这里将探讨节点总数为 3f+ 1 时的场景，此时，读写集票数 Q 为 2f+1。
图片
1) 提案阶段
在该阶段中，由主节点发送 pre-prepare 发动共识，由从节点发送 prepare 对主节点的提案进行确认。主节点在收到客户端的申请后，会被动向其它节点播送 pre-prepare 音讯 <pre-prepare, v, n, D(m)>
v 为以后视图
n 为主节点调配的申请序号
D(m)为音讯摘要
m 为音讯自身
从节点在收到 pre-prepare 音讯之后，会对该音讯进行合法性验证，若通过验证，那么该节点就会进入 pre-prepared 状态，示意该申请在从节点处通过合法性验证。否则，从节点会回绝该申请，并触发视图切换流程。当从节点进入到 pre-prepared 状态后，会向其它节点播送 prepare 音讯 <prepare, v, n, D(m), i>，
i 为以后节点标识序号
其余节点收到音讯后，如果该申请曾经在以后节点进入 pre-prepared 状态，并且收到 2f 条来自不同节点对应的 prepare 音讯（蕴含本身），从而进入到 prepared 状态，提案阶段实现。此时，有 2f+ 1 个节点认可将序号 n 调配给音讯 m，这就意味着，该共识集群曾经将序号 n 调配给音讯 m。
2) 提交阶段
当申请在以后节点进入 prepared 状态后，本节点会向其它节点播送 commit 音讯 <commit, v, n, i>。如果该申请曾经在以后节点达到 prepared 状态，并且收到 2f+ 1 条来自不同节点对应的 commit 音讯（蕴含本身)，那么该申请就会进入到 committed 状态，并能够进行执行。此时，有 2f+ 1 个节点曾经得悉共识集群曾经将序号 n 调配给音讯 m。执行结束后，节点会将执行后果反馈给客户端进行后续判断。
▲检查点机制
PBFT 共识算法在运行过程中，会产生大量的共识数据，因而须要执行正当的垃圾回收机制，及时清理多余的共识数据。为了达成这个目标，PBFT 算法设计了 checkpoint 流程，用于进行垃圾回收。
checkpoint 即检查点，这是查看集群是否进入稳固状态的流程。在进行查看时，节点播送 checkpoint 音讯 <checkpoint, n, d, i>
n 为以后申请序号
d 为音讯执行后取得的摘要
i 为以后节点示意
当节点收到来自不同节点的 2f+ 1 条有雷同 <n,d> 的 checkpoint 音讯后，即可认为，以后集群对于序号 n 进入了稳固检查点（stable checkpoint）。此时，将不再须要 stable checkpoint 之前的共识数据，能够对其进行清理。不过，如果为了进行垃圾回收而频繁执行 checkpoint，那么将会对系统运行带来显著累赘。所以，PBFT 为 checkpoint 流程设计了执行距离，设定每执行 k 个申请后，节点就被动发动一次 checkpoint，来获取最新的 stable checkpoint。
除此之外，PBFT 引入了高下水位（high/low watermarks）的概念，用于辅助进行垃圾回收。在共识进行的过程中，因为节点之间的性能差距，可能会呈现节点间运行速率差别过大的状况。局部节点执行的序号可能会当先于其余节点，导致于当先节点的共识数据长时间得不到清理，造成内存占用过大的问题，而高下水位的作用就是对集群整体的运行速率进行限度，从而限度了节点的共识数据大小。
高下水位零碎中，低水位记为 h，通常指的是最近一次的 stable checkpoint 对应的高度。高水位记为 H，计算形式为 H =h+L，L 代表了共识缓存数据的最大限度，通常为 checkpoint 距离 K 的整数倍。当节点产生的 checkpoint 达到到 stable checkpoint 状态时，节点将更新低水位 h。在执行到最高水位 H 时，如果低水位 h 没有被更新，节点会暂停执行序号更大的申请，期待其余节点的执行，待低水位 h 更新后从新开始执行更大序号的申请。
▲视图变更
当主节点超时无响应或者从节点个体认为主节点是问题节点时，就会触发视图变更（view-change）。视图变更实现后，视图编号将会加 1，随之主节点也会切换到下一个节点。如图所示，节点 0 产生异样触发视图变更流程，变更实现后，节点 1 成为新的主节点。
图片
当视图变更产生时，节点会被动进入到新视图 v + 1 中，并播送 view-change 音讯，申请进行主节点切换。此时，共识集群须要保障，在旧视图中曾经实现共识的申请可能在新视图中失去保留。因而，在视图变更申请中，个别须要附加局部旧视图中的共识日志，节点播送的申请为 <viewchange, v+1, h, C, P, Q, i>
i 为发送者节点的身份标识
v+ 1 示意申请进入的新视图
h 为以后节点最近一次的稳固检查点的高度
C：以后节点曾经执行过的检查点的汇合，数据依照 <n,d> 的形式进行存储，示意以后节点曾经执行过序号为 n 摘要为 d 的 checkpoint 查看，并发送过相应的共识音讯。
P：在以后节点曾经达成 prepared 状态的申请的汇合，即，以后节点曾经针对该申请收到了 1 条 pre-prepare 音讯与 2f 条 prepare 音讯。在汇合 P 中，数据依照 <n,d,v> 的形式进行存储，示意在视图 v 中，摘要为 d 序号为 n 的申请曾经进入了 prepared 状态。因为申请曾经达成了 prepared 状态，阐明至多有 2f+ 1 个节点领有并且认可该申请，只差 commit 阶段即可实现一致性确认，因而，在新的视图中，这一部分音讯能够间接应用本来的序号，无需调配新序号。
Q：在以后节点曾经达成 pre-prepared 状态的申请的汇合，即，以后节点曾经针对该申请发送过对应的 pre-prepare 或 prepare 音讯。在汇合 Q 中，数据同样依照 <n,d,v> 的形式进行存储。因为申请曾经进入 pre-prepared 状态，示意该申请曾经被以后节点认可。
然而，视图 v + 1 对应的新主节点 P 在收到其余节点发送的 view-change 音讯后，无奈确认 view-change 音讯是否拜占庭节点收回的，也就无奈保障肯定应用正确的音讯进行决策。PBFT 通过 view-change-ack 音讯让所有节点对所有它收到的 view-change 音讯进行检查和确认，而后将确认的后果发送给 P。主节点 P 统计 view-change-ack 音讯，能够分别哪些 view-change 是正确的，哪些是拜占庭节点收回的。
节点在对 view-change 音讯进行确认时，会对其中的 P、Q 汇合进行查看，要求汇合中的申请音讯小于等于视图 v，若满足要求，就会发送 view-change-ack 音讯 <viewchange-ack, v+1, i, j, d>
i 为发送 ack 音讯的节点标识
j 为要确认的 view-change 音讯的发送者标识
d 为要确认的 view-change 音讯的摘要
不同于个别音讯的播送，这里不再应用数字签名标识音讯的发送方，而是采纳会话密钥保障以后节点与主节点通信的可信，从而帮忙主节点断定 view-change 音讯的可信性。
新的主节点 P 保护了一个汇合 S，用来寄存验证正确的 view-change 音讯。当 P 获取到一条 view-change 音讯以及共计 2f- 1 条对应的 view-change-ack 音讯时，就会将这条 view-change 音讯退出到汇合 S。当汇合 S 的大小达到 2f+ 1 时，证实有足够多的非拜占庭节点发动视图变更。主节点 P 会依照收到的 view-change 音讯，产生 new-view 音讯并播送，<new-view, v+1, V, X>
V：视图变更验证汇合，依照 <i,d> 的形式进行存储，示意节点 i 发送的 view-change 音讯摘要为 d，均与汇合 S 中的音讯绝对应，其余节点能够应用该汇合中的摘要以及节点标识，确认本次视图变更的合法性。
X：蕴含稳固检查点以及选入新视图的申请。新的主节点 P 会依照汇合中 S 的 view-change 音讯进行计算，依据其中的 C、P、Q 汇合，确定最大稳固检查点以及须要保留到新视图中的申请，并将其写入汇合 X 中，具体选定过程绝对繁琐，如果有趣味，读者能够参阅原始论文[6]。
▲改良空间与 RBFT
RBFT（Robust Byzantine Fault Tolerance），是趣链科技基于 PBFT 为企业级联盟链平台研发的高鲁棒性共识算法。相比拟 PBFT 来说，咱们在共识音讯解决、节点状态复原、集群动静保护等多方面进行了优化改进，使得 RBFT 共识算法可能应答更简单多样的理论场景。
1) 交易池
包含 RBFT 在内，许多共识算法的工业实现中，都设计了独立的交易池模块。在收到交易后，将交易自身寄存在交易池里，并通过交易池对交易进行共享，使得各个共识节点都能取得共享的交易。在共识的过程中，只需对交易哈希进行共识即可。
在解决较大交易时，交易池对于共识的稳定性有不错的晋升。将交易池与共识算法自身进行解耦，也更不便通过交易池实现更多的性能个性，比方交易去重。
2) 被动复原
在 PBFT 中，当节点借由 checkpoint 或 view-change 发现本身的低水位落后，即稳固检查点落后时，落后节点就会触发相应的复原过程，以拉取该稳固检查点之前的数据。这样的落后复原机制有一些有余：一方面，该复原流程的触发是被动的，须要在 checkpoint 过程或者触发 view-change 实现时能力触发落后复原；另一方面，对于落后节点来说，如果通过 checkpoint 发现本身稳固检查点落后时，落后节点只能复原到最新的稳固检查点，而无奈取得该检查点后落后的共识音讯，可能始终无奈真正参加到共识当中。
在 RBFT 中，咱们设计了被动的节点复原机制：一方面，该复原机制能够被动触发，更快地帮忙落后节点进行复原；另一方面，在复原到最新的稳固检查点根底之上，咱们设计了水位间的复原机制，从而使得落后节点可能获取到最新的共识音讯，更快地参加到失常共识流程。
3) 集群动静保护
Raft 作为一种广泛应用在工程中的共识算法，其重要劣势之一，就是可能动静实现集群成员变更。而 PBFT 没有给出集群成员动静变更计划，在理论利用中存在有余。在 RBFT 中，咱们设计了一种动静变更集群成员的计划，使得不须要停启集群整体的状况下，就能够对集群成员进行增删。
新增或删除节点时，由管理员向集群发交易创立操作节点的提案，并期待其余管理员投票，投票通过后由创立提案的管理员再次向集群发执行提案配置交易，执行时会更改集群配置。
对于共识局部，当解决执行提案配置交易时，集群中的节点将进入配置变更状态，不再打包其余交易。主节点将该交易独自打包生成配置包，并对该配置包进行共识。当该配置包实现共识，它将被执行并生成配置区块。为了保障改配置区块不可回滚，共识层将期待改配置包的执行后果，确定集群中曾经对于该配置包所在高度造成稳固检查点，才会解除节点的配置状态，持续进行其余交易的打包。
对于集群不同的配置状态，咱们通过世代（epoch）进行辨别。不同世代领有其独立的编号，该编号为枯燥递增的，每次执行实现一笔执行提案配置交易，将会对世代编号进行更新。对于集群中不同的节点，如果它们处于同一个世代下，则能够进行失常的信息交互。否则，节点之间只能进行状态复原相干音讯的交互。因为配置变更的信息曾经被写入链上，因而，咱们能够通过间接同步区块的形式为落后节点进行配置更新。通过上一节所说的被动复原协定，世代落后的节点能够获取到最新的状态，并通过间接同步区块的形式复原至最新的稳固检查点，同时实现节点世代与配置状态的复原。
通过这样的动静变更集群成员的形式，使得集群配置保护更加牢靠与便捷，并且能够为动静批改更多配置信息提供了可能。
作者简介
王广任
趣链科技根底平台部共识算法钻研小组
参考文献
[1] Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the Works of Leslie Lamport. 2019: 203-226.
[2] Castro M, Liskov B. Practical Byzantine fault tolerance[C]//OSDI.1999, 99(1999): 173-186.
[3] https://en.wikipedia.org/wiki… _ (distributed_computing)
[4] Owicki S, Lamport L. Proving liveness properties of concurrent programs[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 455-495.
[5] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Comput. Surv., 22(4):299–319, 1990.
[6] Castro M, Liskov B. Practical Byzantine fault tolerance andproactive recovery[J]. ACM Transactions on Computer Systems (TOCS), 2002,20(4): 398-461.
