【共识专栏】共识的分类（下）

—— Part4 拜占庭容错算法 ——

▲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²)。

下面介绍 PBFT 算法的核心共识流程[3]，如图 4 所示。

图 4. 三阶段共识

在请求 request 阶段，客户端发起请求，主节点收到客户端的请求后，将触发核心共识流程。算法的核心共识流程分为三个阶段：pre-prepare 阶段，prepare 阶段，commit 阶段。其中，节点在 prepare 阶段和 commit 阶段各进行了一轮投票，分别对消息的合法性与待执行进行了确认。图中，c 代表客户端，0、1、2、3 代表节点的编号，在视图为 0（view=0）的情况下，节点 0 是主节点，节点 1、2、3 为从节点。打叉的 3 号代表拜占庭节点，这里表现的恶意行为就是对其它节点的请求无响应。

pre-prepare 阶段：主节点在收到客户端的请求后，会主动向其它节点广播 pre-prepare 消息<pre-prepare, v, n, D(m)>， 其中，v 为当前视图，n 为主节点分配的请求序号，D(m)为消息摘要，m 为消息本身。从节点在收到 pre-prepare 消息之后，会对该消息进行合法性验证，若通过验证，那么该节点就会进入 pre-prepared 状态，表示该请求在从节点处通过合法性验证。否则，从节点会拒绝该请求，并触发视图切换流程。

prepare 阶段：当从接到进入到 pre-prepared 状态后，会向其它节点广播 prepare 消息<prepare, v, n, D(m), i>，其中，i 为当前节点标识序号。其他节点收到消息后，如果该请求已经在当前节点进入 pre-prepared 状态，并且收到 2f 条来自不同节点对应的 prepare 消息（包含自身发出的以及主节点的 pre-prepared 消息)，那么该请求就进入到 prepared 状态。

commit 阶段：当请求在当前节点进入 prepared 状态后，本节点会向其它节点广播 commit 消息<commit, v, n, i>。如果该请求已经在当前节点达到 prepared 状态，并且收到 2f+1 条来自不同节点对应的 commit 消息（包含自身)，那么该请求就会进入到 committed 状态，并可以进行执行。执行完毕后，节点会将执行结果反馈给客户端进行后续判断。

—— Part5 新型共识算法 ——

 ▲HotStuff

HotStuff 是一个建立在部分同步模型（partial synchrony model）上的拜占庭容错协议。HotStuff 具有线性视图变更（Linear View Change）的特性，把轮换主节点融入了常规共识流程中，切换主节点无需增加其他协议和代价，且系统在此期间还能继续对外提供服务。该特性解决了 PBFT 最棘手的视图变更（View Change）问题，包括实现复杂度高、完成时间不确定以及整个过程系统不能正常对外提供服务等[4]。此外，HotStuff 还将共识流程的通信复杂度降低至 O(n)。

HotStuff 的基础共识流程（Basic-HotStuff）围绕一个核心的三轮共识投票展开，在该过程中，视图（view）以单调递增的方式不断切换。在每个视图内，都有一个唯一主节点负责打包区块、收集和转发消息并生成 QC。整个过程包括 5 个阶段，准备阶段（PREPARE）、预提交阶段（PRE-COMMIT）、提交阶段（COMMIT）、决定阶段（DECIDE）和最终阶段（FINALLY）（如图所示）。主节点想要提交（达成最终共识）某个分支，需要在 PREPARE、PRE-COMMIT 和 COMMIT 这三个阶段收集 n-f 个共识节点的带签名的投票消息，并利用门限签名算法（threshold signatures）把他们合成一个证书（Quorum Certificate，QC），随后广播给从节点。

图 5. Basic HotStuff 共识流程

Basic-HotStuff 各个阶段的流程高度相似，HotStuff 作者便提出 Chained-HotStuff 来简化 Basic-HotStuff 的消息类型，并允许 Basic-HotStuff 的各阶段进行流水线（pipelining）处理。流程如图 6 所示：

图 6.Chained-HotStuff 是 Basic-HotStuff 的流水线形式，v 表示视图 view，圆角矩阵表示一个 node

 ▲HoneyBadgerBFT

FLP 定理从理论上证明了在纯异步环境下不可能存在一种确定性的共识协议。后世的研究者们为了绕过这个定理，不得不在两个方向上进行妥协：要么加强对网络的假设（部分同步协议），要么引入随机源。HoneyBadgerBFT 协议，这是一个完全异步的共识协议，它不依赖于任何关于网络环境的时间假设。异步共识协议则完全不需要考虑 timer 的设置。为了保证协议的活性，异步协议需要引入随机源，简单来说就是当协议无法达成共识的时候，借助上帝抛骰子的方式随机选择一个结果作为最终结果。

HoneyBadgerBFT[5]通过模块化的方式解决了拜占庭环境下的原子广播（Atomic Broadcast，ABC）问题，即如何保证在异步和拜占庭环境下，各个节点按相同顺序收到相同的消息。HoneyBadgerBFT 首先将 ABC 分解成一个核心模块，异步共同子集（Asynchronous Common Subset，ACS）。之后将 ACS 分解成了 RBC(Reliable Broadcast) 和 ABA(Asynchronous Binary Agreement)两个子模块。整体的算法分为三个步骤：

1）每个节点交易随机选择一些交易，所有节点的总交易个数是 B。每个节点的交易进行加密生成 x。

2）通过 ACS 协议将每个节点加密的交易进行广播，以及形成统一交易序列。

3）解密交易生成区块。

—— Part6 总结 ——

上述介绍的共识机制有着各自的优缺点，对于不同的区块链系统，我们需要结合实际使用场景与网络规模，采用不同的共识算法。下面我将以表格的形式对目前各平台使用的共识机制进行简要的对比与总结：

作者简介

袁超

趣链科技基础平台部共识算法研究小组

参考文献

[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] Castro M, Liskov B. Practical Byzantine fault tolerance and proactive recovery[J]. ACM Transactions on Computer Systems (TOCS), 2002, 20(4): 398-461.

[4] Ittai Abraham, Guy Gueta, Dahlia Malkhi, Lorenzo Alvisi, Ramakrishna Kotla, and Jean-Philippe Martin. Re- visiting fast practical byzantine fault tolerance. CoRR, abs/1712.01367, 2017.

[5] Miller A ,  Xia Y ,  Croman K , et al. The Honey Badger of BFT Protocols[C]// Acm Sigsac Conference on Computer & Communications Security. ACM, 2016:31-42.