HotStuff算法详解

背景

状态机复制 (State machine Replication, SMR)是人们为了解决分布式系统同步问题提出的一种理论框架。为了让一个系统拥有较强的容错能力，人们通常会部署多个完全相同的副本节点，任意一个节点的崩溃都不会影响整个系统的正常工作。在工程上，这些副本节点通常使用状态机复制理论进行同步。

状态机复制的核心思想是在所有副本上面运行一套相同的状态机，只要所有副本都有相同的初始状态，并且对于初始状态赋予相同的一组操作，那么所有副本的最终状态一定是相同的。

如何确定这一组操作的顺序，就需要系统中所有未出错的节点，对于某一个待提交操作序列达成共识，这就类似于著名的拜占庭将军问题中，军官们面临的困境。在拜占庭问题的诸多解决方案中，都会保证个节点中，只要有个未出错的副本，这些未出错的副本就可以不受其他出错（甚至恶意）的副本影响而达成共识。

HotStuff是尹茂帆等人提出的分布性一致性协议，在该算法中，最多出错节点个数为。该算法有两个优点，第一个优点是，相比于之前的算法，HotStuff是基于leader节点的，拥有线性复杂度，可以极大地降低节点出错时，系统的共识消耗。同时，更替leader的低复杂度，鼓励网络频繁更迭leader节点，对于区块链等领域非常有用。第二个优点是该模型隔离了安全性与活跃性，安全性通过节点投票保证，而活跃性则通过 Pacemaker 保证。

学习HotStuff除了阅读本文，还可以阅读原论文 《HotStuff : BFT Consensus in the Lens of Blockchain》 ，或是原论文的中文翻译。Facebook的Libra数字货币也使用的该算法的变种 LibraBFT 。

算法

原论文提出了HotStuff的三种实现形式，分别为简易的HotStuff算法(Basic HotStuff)，链状HotStuff算法(Chained HotStuff)和事件驱动的HotStuff算法(Event-driven HotStuff)。工程上，人们通常使用Event-driven HotStuff算法，但是如果直接去阅读Event-driven HotStuff算法的源代码会不知所云。

Event-driven HotStuff算法之所以比较难以理解，是因为它——

• 使用了Basic HotStuff算法的共识逻辑，特别的，包括leader如何与replica交互形成共识；
• 运用了Chained HotStuff提出的流水线优化思想，特别的，如何使用流水线并行优化原算法中相似的阶段；
• 最后Event-driven HotStuff是Chained HotStuff事件驱动形式，特别的，将原始实现中轮询产生的驱动改为由leader节点发出的事件驱动。

一方面，从论文的结构上来看，先介绍了前两者，最后才在Implementation章节介绍了Event-driven HotStuff。但另一方面，Event-driven HotStuff又是三者中代码最简单的，也是三者中唯一一个可以在网上找到 大量源码 进行对照的实现。因此直接上手阅读源码，在遇到困难时再去查阅简单版本的实现也是一个很好地做法（事实上论文作者也推荐直接阅读Event-driven HotStuff）。

简单HotStuff算法

如果本节下面的内容理解上有困难可以参考原文对应章节。

视图

状态机复制中单次状态转移在HotStuff中以视图(View)的形式出现，leader节点收集网络中其他节点的信息，发送提案并取得共识的整个过程可以看做是一个视图，视图实际上可以类比于状态机的一次转移，其中包含了这次转移需要执行的用户命令。而整个分布式系统，正是通过一次又一次的视图变换(View-Change)，得以逐轮推进运作。

分支

直观地看，HotStuff中，每一个副本节点都会在自己的内存中维护一个待提交指令的树状结构。每个树叶子节点都包含了一个待提交的指令，树节点到根节点组成了一个分支。未提交的分支之间互相是竞争关系，一轮中只会有一个分支被节点所共识。

系统中存在一个唯一的leader被其他所有节点所公认，这个leader会尝试将包含“待执行指令”的提议附加到一个已经被个副本投票支持的分支。并尝试就新的分支与其他副本达成共识，共识成功后，整个系统所有节点都会提交并执行这些新的附加操作指令。

【值得注意的是HotStuff并不关心leader的选取过程，因此在后续算法中，我们需要默认leader已经由其他模块指定。】

仲裁证书

HotStuff中的投票使用密码学中的仲裁证书(Quorum Certificate, QC)，每一个视图都会关联一个仲裁证书，仲裁证书表明该视图是否获得了足够多副本的认可。仲裁证书本质是副本节点通过自己的私钥签名的一种凭证。

如果一个副本节点认同某一个分支，它会使用自己的私钥对该分支签名，创建一个部分证书发送给leader。leader收集到个部分证书，可以合成一个仲裁证书，一个拥有仲裁证书的视图意味着获得了多数节点的投票支持。

视图的投票总共分为三个步骤，准备阶段prepare, 预提交阶段pre-commit，提交阶段commit。每一次投票都会合成一个仲裁证书，不同阶段的证书从含义上稍微有些区别，在后续章节的阅读时需要注意。

算法

下面是HotStuff的伪代码，其中算法1是重要函数的伪代码，涉及到到消息创建、投票创建、叶节点创建、仲裁证书创建、消息验证、仲裁证书验证、节点安全性判断这些功能。算法2则是HotStuff的运行流程，在每一个阶段，领导节点leader和所有副本replica（包括leader)都会等待特定类型的消息，并进行处理。下面，我会依次讲解每一个阶段究竟做了什么事情。

 

简单HotStuff涉及函数

 

简单HotStuff算法流程

prepare阶段

在视图编号增加时，所有节点都会发送New-View类别的消息给leader节点，消息中捎带当前节点的prepareQC值（这里伪代码没写），leader节点在接收到个New-View消息即可以默认已经有足够多的副本等待接收新的提案。

prepareQC是一个仲裁证书，记录了一个最后获得了个节点投票的已提交分支，leader节点从所有New-View消息捎带的仲裁证书中，选择了一个拥有视图编号最大的仲裁证书highQC，基于highQC对应的节点，创建叶节点拓展待提交的指令curProposal，这样对于leader来说是最安全的。

最后leader节点会将curProposal、highQC封装到prepare类型的消息中发送给副本节点，而副本节点对于接收到的prepare类型消息，进行安全性检测safeNode。

从算法1中，我们可以看到，安全性判定分为两个规则，安全性规则和活跃性规则。安全性规则检测消息对应的节点是否是仲裁证书的直接子节点，如果是的话，说明副本节点的待提交节点和leader的待提交节点都是同步，中间没有任何步骤缺失。活跃性规则则检测自身的lockedQC的视图编号是否小于仲裁证书的的视图编号，如果小于的话，就说明自己被卡在了一个其他节点早已达成共识的视图，因此可以忽略自身的lockedQC，直接尝试与leader重新同步。

pre-commit预提交阶段

当leader节点收到个为当前提案curProposal投票时，将他们合并为prepareQC，此时的prepareQC已经获得了这个副本的投票。而对于副本节点，prepareQC则被赋值为prepare阶段中leader节点的highQC，即最近已提交分支。

commit提交阶段

commit阶段类似于pre-commit阶段。当leader接收到个pre-commit投票时，它将它们组合成一个precommitQC，并在commit类型消息中广播它；副本用commit投票来响应它。重要的是，此时通过将副本的lockedQC设置为precommitQC（算法2的第25行），副本将被锁定在precommitQC上。这对于保护提案的安全至关重要，以防提案成为一项协商一致的决定。

decide决定阶段

当leader节点收到个commit的选票时，它将它们合并成一个commitQC。一旦leader节点获得了commitQC，它就会以decide消息的形式将其发送给所有其他副本。在接收到decide消息时，副本将commitQC中包含的提案视图视为已提交的决策，并在已提交的分支中执行命令。副本将增加viewNumber并启动下一个视图。

下一个视图(nextView)中断

在所有阶段中，副本都会在viewNumber视图处等待由函数确定的超时时间段。如果中断等待，副本也会增加viewNumber并开始下一个视图。

理解

正如代码中蓝色部分所强调的，系统的replica在每一阶段都会维护一个量：

• prepareQC，表示该仲裁证书曾经获得过一次majority投票
• lockedQC，是一个用于保证安全性的中间量
• commitQC，是个表示决策已经成了的凭证，不论之后发生什么样的问题（网络延迟、节点崩溃），只要有个正确节点，这个决定都是会被继续尊重

为什么上述算法是安全的，核心就是证明下面的命题：

如果和是冲突的节点，那么他们不能够同时被某个正确的副本所提交(commit)。

该命题的证明在文末附录1，如果想要搞清楚lockedQC具体的含义，可以尝试阅读一下证明。 接着证明上述算法的活跃性，活跃性的核心是证明下面的命题：

我们首先定义全局稳定时间GST之后，存在一个有界的持续时间，满足如果所有副本在期间仍然在视图中，且视图的leader节点正常运行，那么决定(decision)可以到达。

该命题的证明在文末附录2.

链状HotStuff算法

如果本节对应的内容理解有难度，可以参考 原文对应章节

。 在Basic HotStuff中，不难发现每个阶段都是极其同构且独立的，因此可以进行流水线优化。

 

图1 Chained HotStuff是Basic HotStuff的流水线版本，QC可以同时处于多个阶段。 对于节点b，单箭头表示b.parent字段，双箭头表示b.justify.node。

更具体地说，在Chained HotStuff协议中，prepare阶段的副本的投票由leader节点加以收集，并且储存在状态变量genericQC里。接下来，genericQC被转发给下一个视图的leader，实质上是将下一阶段的职责（这曾经由pre-commit阶段负责的）委托给下一个leader节点。然而，下一位leader实际上并不单独进行pre-commit阶段，而是启动一个新的prepare阶段，添加自己的提议。视图的prepare阶段同时充当视图的pre-commit阶段。视图的prepare阶段同时充当视图的pre-commit阶段和视图

的commit阶段。 在实际的实现中，还有一些细节，比如说，当一个leader没有成功获得足够的仲裁证书，那么就可能出现一个节点的justify的视图编号并不连续，如图2所示，这种情况需要通过添加哑结点补齐。

 

图2 v8的父节点没有成功获得仲裁证书

我们按照节点的依次向上访问，可以获得流水线中各个阶段的节点。令,,

。

• 如果，说明的prepare阶段成功完成，当副本投票给时，还需要执行。需要注意的是，即使，执行上述赋值也是安全的，我们在下一节Event-driven HotStuff中会使用后者。
• 如果，说明的pre-commit阶段成功完成，需要同步更新。
• 如果，说明的commit阶段完成，就变成一个已提交的决策。

下面是Chained HotStuff的伪代码，其中略去了很多特殊情况的判断。

 

事件驱动的HotStuff

从Chained HotStuff到Event-driven HotStuff也并不困难。最终伪代码涉及了如下的数据结构——

• 将节点映射到投票
• 最近投票节点的高度
• 被锁定的节点（和lockedQC相似）
• 最后执行的节点
• 由Pacemaker维护的最高的已知QC（与genericQC相似）
• 由Pacemaker维护的叶节点

下面两个代码共同组成了一个工程上实现高效的Event-driven HotStuff算法，他们分别描述了安全性相关模块和活跃性相关模块。和Chained HotStuff源码进行对比，不难理解其中各个函数的功能，同时，读者也可以结合 网络上公开的实现

进行理解。

 

 

上述的HotStuff是三阶段的，而论文中还介绍了一个两阶段的HotStuff变种算法，其优势是更少的阶段，更快的效率，而劣势则是乐观响应性的损失。

 

附录1. 证明HotStuff安全性

证明： 如果和是冲突的节点，那么他们不能够同时被某个正确的副本所提交(commit) .

先证明一个特殊情况，假设和的高度相同，上述命题不成立。这其实是很显然的，毕竟副本的提交需要多数节点的投票，而每个副本每个阶段只会投一个提案，不可能出现两个同样深度树节点得票数同时过半的情况。

 

w和b高度不同的情况

假设和高度不同，不妨设，，是高度 大于 且与 冲突 的， 高度最小 的那个 合法的 prepareQC仲裁证书。 即

 

 

和都是合法的commitQC仲裁证书，是一个合法的prepareQC证书。算法29行说明一个commitQC是由个lockedQC组成，而算法13行则说明一个prepareQC需要个副本同时通过safeNode检验。 而一个commitQC需要由个lockedQC组成，和一个prepareQC需要的次safeNode检验，一定存在一个公有的，在视图的时候，会设置lockedQC为precommitQC（），当尝试检验safeNode谓词时，就会发现既不满足“extends from”，也不满足“”。这意味着

甚至根本无法生成，与假设矛盾。 反证法的结论就是不可能存在两个冲突的commitQC。

附录2. 活跃性证明

我们首先定义全局稳定时间GST之后，存在一个有界的持续时间，满足如果所有副本在期间仍然在视图中，且视图的leader节点正常运行，那么决定(decision)可以到达。 引理 如果一个正常运行的副本已经锁定了，且锁定在了，那么至少个副本投票了与匹配的。 引理证明 如果一些副本锁定了，那么在prepare阶段一定获得了个投票(算法2的第10行)，由于，所以其中至少个是正常运行的副本。 活跃性证明 从一个新的视图开始，leader节点收集个newView消息，并计算出他们的highQC，最后广播prepare消息。假设在所有副本中（包括leader本身），最高的锁定QC是，通过引理， 我们知道了，至少有个正确的副本曾经向一个匹配的投票，并且该值已经被附在NewView消息中，传送给leader节点。在这些New-View消息中，至少有一个会被leader接受，并赋值到highQC中。基于假设条件，所有正确的副本在该视图中处于同步状态(synchronized)，且leader节点是无缺陷的。因此，所有正确的副本都会在prepare阶段投票，由于在函数里面，算法1第27行的条件被满足了（即使节点的消息和副本的冲突，即26行条件不满足）。然后，在leader为这个视图聚合出有效的prepareQC之后，所有副本将在接下来的所有阶段进行投票，从而产生一个新的决策。在GST之后，这些阶段完成的持续时间是有界的。