—— 前言 ——
咱们曾经理解到分布式系统个别通过状态复制机[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.
发表回复