【共识专栏】Quorum 机制与 PBFT

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