共计 7435 个字符，预计需要花费 19 分钟才能阅读完成。
—— 前言 ——
咱们曾经理解到分布式系统个别通过状态复制机 [1] 原理来实现一致性。其核心思想是零碎中所有正本运行着雷同的状态机，只有所有正本都以雷同的初识状态开始，并基于雷同的初识状态执行一组雷同程序的操作，那么所有的状态最终会收敛统一，即整个零碎对外体现出一致性。而确定这一组雷同程序的操作须要零碎达成共识，进一步说即所有诚恳节点对执行程序达成共识，这便是驰名的拜占庭将军 [2] 问题。
拜占庭类共识算法的实践平安保障，即 n >3f，n 为总的节点数量，f 为歹意节点数量。一个拜占庭共识算法须要保障两个性质：
安全性：所有诚恳节点都认为某一时刻零碎状态为 s
活性：所有诚恳节点最终能确定 s 为零碎状态
其中 s 是一个形象的概念，能够了解为零碎内存在一个变量 S，这个变量 S 的取值为零碎状态，零碎内节点接管一系列对于 S 的操作指令，某时刻（假如每个节点时钟没有误差）就 S 的取值进行共识，所有诚恳节点确定变量 S = s 则满足安全性，所有诚恳节点对变量 S 的取值必须做出决定且终止则满足活性。
以往，在分布式系统的钻研中，拜占庭类共识往往都随同着较高的通信复杂度，对网络造成的耗费极大，零碎规模不易扩充。如经典的 PBFT 算法，其达成共识须要通过三个阶段，PRE-PREPARE 阶段主节点将申请音讯发送给其余节点，其余节点对该音讯验证过后，各自发送 prepare 音讯给其余节点，这个阶段产生了 n^2 条音讯。为了保障跨视图上的一致性，节点在收到至多 quorum 的 prepare 音讯后再发送 commit 音讯给其余节点。当节点最终收到至多 quorum 的 commit 音讯时，再最终对该申请进行提交。而网络异样节点超时触发视图切换时，则须要 o(n^3)的通信复杂度
了解 PBFT 中每个阶段的工作是 HotStuff 的根底，PBFT 中每个阶段都指标都是为保障安全性和活性。
假如零碎某时刻收到指令 S ’=S+1，主节点将这条指令 S ’=S+ 1 发送给非主节点（这是 pre-prepare 音讯），因为是拜占庭问题，诚恳节点不确定本人收到的是否和其余诚恳节点统一（主节点发送不统一音讯），节点之间须要进行一次互相通信，确定本人和其余诚恳节点收到的音讯统一（确定主节点没有发送不统一音讯），每个节点发送 prepare 音讯给其余所有节点，之后若收到 quorum 个数量的 prepare 音讯，且通过验证（验证 prepare 中指向的指令与本人统一），达成第一轮共识（这是 PREPARE 阶段）。此时，仿佛能够确定了诚恳节点收到的音讯统一。然而这里隐含条件是，达到共识的节点只是在本人的视角看到：我收到并验证了 quorum 个统一的音讯。但其余节点不肯定和本人一样收到 quorum 个 prepare 音讯达成共识，如果此时进行提交，呈现了网络故障，提交了的节点晓得曾经达成共识，只有等网络复原，这条指令肯定会被整个零碎提交。但其余节点可能因为网络故障还未达成共识，他们无奈确定始终等上来是否提交。为了让零碎放弃活性，进行视图切换，此时新的主节点须要确定是在 S ’ 还是 S 的根底上执行新的指令。如果没有发现局部节点曾经提交了该指令，且对另一条指令 S ”=S+ 2 进行了共识并提交，系统对变量 S 的取值产生了不统一。因而，在此时提交有安全性的问题。
如果再进行一个阶段的共识，在达成 PREPARE 共识之后，各自再发送一个 commit 音讯，各自节点期待承受并验证 quorum 个 commit 音讯之后再提交。会遇到同样的问题，达成 COMMIT 共识的节点提交了，他们晓得如果网络失常，零碎迟早都会提交，然而其余未达成 COMMIT 共识的节点不确定最初是否提交。网络产生故障后新视图中的主节点如果没有发现曾经提交了的节点，仍然会造成不统一。这里的矛盾是咱们为了活性须要切换视图持续共识；为了安全性还要确保新视图开始共识前 S 的取值统一，曾经提交了的指令在新视图中也肯定须要被提交。而在 PBFT 中采纳视图切换时向其余节点发送音讯证实本人 S 的状态的办法，即发送本人最新的 S 的一条 pre-prepare 音讯和对应的 quorum 条 prepare 音讯。视图切换时，新主节点共识前就能判断 S ’=S+ 1 是否须要提交。
如果没有任何一个节点就 S ’=S+ 1 达成 PREPARE 阶段共识，则不会持续对 S ’=S+ 1 进行提交。
如果存在一个节点对达成了 S ’=S+ 1 达成了 PREPARE 阶段共识，则不可能对一条抵触的指令 S ”=S+ 2 达成共识并提交，
依照这种规定安全性和活性就失去了保障，而这种办法带来的复杂度却是 o(n^3)。因而该算法仍然不可能使用在大规模的网络当中。尹茂帆等人提出的 HotStuff 共识算法 [4] 具备线性视图变更的个性，解决了经典的 PBFT 甚至 BFT 类共识的瓶颈，主节点的切换无需减少其余协定和代价，零碎仍能对外工作体现一致性，使得共识流程通信复杂度升高至 o(n)。
—— HotStuff 基本概念 ——
理解 hotstuff 算法须要介绍几个与共识流程相干的概念：
1）门限签名[5]（Threshold signatures）：一个（k，n）门限签名计划指由 n 个成员组成的签名群体，所有成员独特领有一个公共密钥，每个成员领有各自的私钥。只有收集到 k 个成员的签名，且生成一个残缺的签名，该签名能够通过公钥进行验证。
2）证书（Quorum Certificate，QC）：主节点收到至多 quorum 个节点对用一个提案的投票音讯（带签名）后，利用门限签名将其合成一个 QC，这个 QC 能够了解为门限签名生成的残缺签名，示意对该次提案达成一次共识。
3）视图（View）：视图是共识的根本单元，一个视图至少达成一次共识，并且枯燥递增，每个视图逐步轮换推动共识。
4）共识状态树：每个共识区块能够看做是一个树节点，每个树节点内蕴含对应的提案内容（前文的操作指令）和绝对应的 QC，每个树节点蕴含一个父亲树节点的哈希，造成一棵树状构造，主节点基于本地最长的分支生成新的树节点。落后节点依据其余节点的最长分支上的最新树节点来同步两头缺失的树节点。
—— HotStuff 共识流程 ——
HotStuff 的外围围绕着三轮共识投票开展，原论文中提出了三种模式：简易版 HotStuff（Basic HotStuff），链状 HotStuff（Chained HotStuff），事件驱动的 HotStuff（Event-Driven HotStuff）。接下来将通过比照 PBFT 中每个阶段共识的过程来了解 HotStuff 算法。
▲ Basic Hotstuff
Basic HotStuff 是共识的根本过程。其中，视图以枯燥递增的形式一直切换。每个视图内都有一个惟一的主节点负责提案、收集和转发音讯并生成 QC，整个过程包含 4 个阶段：筹备阶段（PREPARE）、预提交阶段（PRE-COMMIT）、提交阶段（COMMIT）、决定阶段（DECIDE），主节点提交（达成共识）某个分支，在 PREPARE、PRE-COMMIT、COMMIT 三个阶段收集 quorum 个共识节点带签名的投票音讯，利用门限签名合成一个 QC，而后播送给其余节点。
HotStuff 联合门限签名能够将之前相互播送共识音讯的形式，转为由主节点解决、合并转发，通信复杂度能够升高到 o(n)，简而言之就是 HotStuff 用门限签名 + 两轮通信达到了 PBFT 一轮通信的共识成果。
比照 PBFT 算法，共识开启于主节点将申请附带在 pre-prepare 中发送给其余节点，主节点即履行完了该轮共识的职责，接下来和其余节点一样。整个共识过程包含一个播送提案阶段（PRE-PREPARE 阶段），两个共识阶段（PREPARE 阶段、COMMIT 阶段）。
PREPARE 阶段：
主节点：1）依据收到的 quorum 条 New-View 音讯，该音讯中蕴含了发送方的状态树中高度最高的 prepareQC，主节点在收到的 prepareQC 中计算出高度最高的 QC，记为 highQC；
2）依据这个 highQC 的节点所指向的分支，打包区块创立新的树节点，其父节点为 highQC 指向的节点；
3）将生成的提案附带在 prepare 音讯中发送给其余从节点，且以后提案蕴含 highQC。
从节点：1）收到该 prepare 音讯之后，对 prepare 中的信息进行验证，包含 qc 中签名的合法性；是否以后视图的提案；
2）prepare 音讯中的节点是否扩大自 lockedQC 的分支（即孩子节点）或者 prepare 音讯中的 highQC 的视图号大于 lockedQC（前者为平安条件，后者为活性条件保障节点落后时及时同步）；
3）生成 prepare-vote 音讯并附带一个签名发送给主节点。
PRE-COMMIT 阶段：
主节点收到 quorum 个以后提案的 prepare-vote 音讯时，通过聚合 quorum 个局部签名失去 prepareQC；而后主节点播送 pre-commit 音讯附带聚合失去的 prepareQC。
从节点：其余节点收到 pre-commit 音讯，验证之后，发送 pre-commit vote 音讯给主节点。
⚠️留神此时，在主节点发送的 pre-commit 中的 prepareQC 就表明了 prepare 音讯中的提案音讯，所有节点投票胜利达成了共识，这一时刻与 PBFT 中 PREPARE 阶段达成共识相似。
Commit 阶段：
主节点：与 pre-commit 阶段相似。1）主节点先收集 quorum 个 pre-commit vote 音讯，而后聚合出这一阶段的 pre-commitQC，附带在 commit 音讯中发送给其余节点。2）设置本地 lockedQC 为 pre-commitQC。
从节点：收到 commit 音讯时，音讯验证通过同样更新本地的 lockedQC 为 commit 音讯中的 pre-commitQC，对其签名并生成 commit vote 并发送给主节点
⚠️留神此时，主节点发送的 commit 音讯附带的 pre-commitQC 即与 PBFT 中的第二轮 COMMIT 阶段共识相似，其中 PBFT 中该阶段共识表明了节点对的第一阶段达成共识这件事的共识，即确保了至多 quorum 个节点曾经实现 PREPARE 阶段，在产生视图切换时，有足够多的节点可能证实对该提案达成了 PREPARE 共识，在新视图中提案内容须要被提交。
DECIDE 阶段：
主节点：1）收集到 quorum 个 commit vote 音讯时，聚合失去 commitQC，并且附带在 decide 音讯中发送给其余节点；
2）当其余节点收到 decide 音讯时，其中 commitQC 指向的提案中的交易就会被执行；
3）之后减少视图号 viewnumber，开启下一轮共识，依据 prepareQC 结构 New-View 音讯。
从节点：验证音讯后执行 decide 音讯中 commitQC 指向的树节点的交易。
nextView interrupt 阶段：在共识中任何其余阶段产生了超时事件，发送新视图的 new-view 音讯，都会间接开启下一轮新的共识。
⚠️留神，HotStuff 中一笔交易从开始到提交进行了三轮共识，第三轮共识的退出，克服了经典两阶段范式的共识算法扩大的瓶颈。PBFT 中为了保证系统在遇到歹意节点时能持续工作（活性），须要进行视图切换，而新视图中为了确定上一个视图中的区块是否达成共识，须要在 view-change 音讯中附带本人收集到的 quorum 个 prepare 音讯和绝对应的一个 pre-prepare 音讯作为证实，而后每个节点播送 view-change 音讯申请视图切换，此时播送的音讯复杂度 o(n^2)，音讯的量级为 o(n)，因而视图切换的复杂度为 o(n^3)。安全性和活性让 PBFT 须要 o(n^3)的通信复杂度，对于网络的负载极大，限度了其向大规模网络的扩大。而 HotStuff 中如果咱们对某一区块达成了两轮共识，在更换主节点时便能确定，主节点只须要基于最新的两轮共识节点产生新节点是平安的。换句话说，只须要依据区块本身的状态（通过几轮共识）就能够确定是否在新的视图中基于该区块打包块新区块，升高了在视图切换时候的通信复杂度。
▲ Chained HotStuff
能够发现在 Basic HotStuff 中的各个阶段流程都高度的类似，HotStuff 的作者便提出了 Chained HotStuff 来简化 Basic HotStuff 的音讯类型，并容许 Basic HotStuff 的各个阶段以流水线形式进行解决交易。
Chained HotStuff 的流程如图：
从图中能够看出，每个阶段都会切换视图，因而每个提案都有本人的视图。节点对于不同的提案来说处在不同的视图上，PREPARE 阶段的投票被以后视图的主节点合成 QC，并转发给下一个视图的主节点，即下一视图在进行 PREAPRE 阶段的同时，也在进行上一个视图的 PRE-COMMIT 阶段。每个阶段具备相似的构造，视图 v + 1 的 PREPARE 阶段能够看作是视图 v 的 PRE-COMMIT 阶段。视图 v + 2 的的 PREPARE 阶段看作是视图 v + 1 的 PRE-COMMIT 阶段和视图 v 的 COMMIT 阶段。v1 中的 cmd1 将在视图 v1，v2，v3 中别离进行 PREPARE、PRE-COMMIT、COMMIT 阶段，在 v4 中就进行提交。cmd2 以此类推。每个阶段的 cmd 提案产生将会附带上一阶段投票产生的 QC。通过流水线简化版本的 HotStuff 工作过程如下：
主节点：1）期待 NEW-VIEW 音讯，收回本人的提案；
2）期待其余节点进行投票；
3）向下一个主节点发送 NEW-VIEW 音讯。
从节点：1）期待主节点的提案音讯；
2）查看提案中的 QC，更新本地 highQC，lockedQC，发送投票；
3）向下一个主节点收回 NEW-VIEW 音讯。
▲ Event-driven HotStuff
从 Chained HotStuff 到 Event-driven HotStuff，实现原论文中将整个协定的安全性（safety）和活性（liveness）解耦开，活性成为独自的 pacemaker 模块。pacemaker 模块保障了在全局稳固工夫（GST）之后的活性。提供两个性能：
抉择、校验每个视图的主节点。
帮忙主节点生成提案。
换而言之，在如此低的视图切换代价下，pacemaker 中能够采纳任何适合的节点轮换机制，以及任何提案生成策略。
Event-driven Hotstuff 与其余版本原理还是外围的三阶段共识，区别只是工程实现上的便当，具体可见论文伪代码[4]
—— HotStuff 之改良优化 -NoxBFT ——
活性机制优化
活性机制是共识可能继续推动的要害。在原 HotStuff 论文中活性机制应用了一个全局统一的超时工夫确定了视图超时。在 NoxBFT 中，咱们设计了更灵便的机制应答网络环境的不稳固。
具体：每个节点进入新的视图后，依据配置期待超时工夫，如果本视图未超时，则定时器时长不变。若超时，则一直播送 TimeoutMsg，直到收到 quorum 个 TimeoutMsg 进入下一视图，此时定时器置为配置工夫 k 倍，间断超时 n 次则置超时器为 k^n 倍。以此类推，这样防止在网络不稳固时频繁切换视图。
交易缓存池
在区块链的利用中，为防止交易失落，咱们设计了交易缓存池缓存客户端交易。共识模块被动拉取交易进行打包。交易池也能够加重共识工作量，进行交易去重，咱们通过交易内容 hash 标识交易，将曾经执行的交易写入布隆过滤器，避免双花攻打，晋升共识算法的稳定性。
疾速复原机制
不稳固的网络环境可能使共识节点失落共识音讯，导致节点落后。在 HotStuff 原论文中，作者将此局部具体实现留给了开发者。咱们实现了工程可用的同步算法，让落后共识节点复原定序性能，分为两步：
1）节点落后较多，间接向其余节点拉取区块执行复原到最新检查点。
2）检查点之后的共识进度落后，向其余节点拉取最新的 CommitQC 疾速复原共识进度。
为提高效率，咱们采取并行向不同节点拉取区块的机制，能够灵便配置并行度。并行拉取的区块先进行长久化再有序执行，同时记录各个节点拉取效率的分数，以便下次高效选取指标节点进行同步。整个过程能够以最快的速度拉取所有失落的交易，缩小整个过程的等待时间。
聚合签名
NoxBFT 中实现并改良了 Ed25519 聚合签名算法。一方面通过编译事后计算的数据减速；另一方面，咱们实现了大数类型专用的减速 Ed25519 的计算过程，压缩大数的存储。最终 Ed25519 算法要比官网快 2.5 倍，签名算法也实现了更高的性能。
总结
在 BFT 类的共识钻研中，安全性的要求须要在视图切换时，主节点确保本人是基于最新的零碎状态工作的，视图切换与零碎状态的共识产生了 o(n^3)的通信复杂度。而 HotStuff 通过减少一轮共识来解决，再联合门限签名升高了通信复杂度。不仅如此，流水线的工作形式，让算法变得足够简洁优雅，这与 raft 的工作形式类似，采取了先上链再共识，通过三轮共识之后再执行。这种链式的构造，不再辨别每个阶段通信的意义（PBFT 中 prepare、commit），灵便的主节点更换的机制，在节点更换时不须要通信来确定最新共识的状态，对安全性与活性进行隔离，投票保障了安全性，pacemaker 保障了其在网络异步时的活性。
作者简介
程泰宁
趣链科技根底平台部共识算法钻研小组
参考文献
[1] Schneider F B . The state machine approach: A tutorial[J]. Springer New York, 1990.
[2] Lamport L , Shostak R , Pease M . The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3).
[3] Castro M, Liskov B. Practical Byzantine fault tolerance[C]. OSDI.1999, 99(1999): 173-186.
[4] Yin M , Malkhi D , Reiter M K , et al. HotStuff: BFT Consensus in the Lens of Blockchain[J]. 2018.
[5] Shoup V . Practical Threshold Signatures[C]// International Conference on Theory & Application of Cryptographic Techniques. Springer-Verlag, 2000.
