实用性拜占庭容错算法（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.