共计 3328 个字符，预计需要花费 9 分钟才能阅读完成。
—— 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.
