HotStuff: BFT Consensus in the Lens of Blockchain

Facebook 近日公布的 Libra 白皮书引起各界持续关注，其网站公开的技术文档也被诸多专家审视，文档提到Libra 区块链将使用基于拜占庭容错共识的「LibraBFT」共识算法，而 LibraBFT 则是「HotStuff」的一个变种。

HotStuff的论文由云计算公司 VMWare 的研究团队发表，第一作者尹茂帆，在美国康奈尔大学（Cornell）大学读博士学位，当前的主攻方向是分布式系统的基础研究，导师是著名计算机科学家 Emin Gun Sirer，另一导师是 Robbert van Renesse。

尹茂帆解释说，取名为 HotStuff，是因为这个单词在英文里有三重意思：一是性感的人，一是炙手可热的好东西，一是某个动画里的小恶魔的名字。

摘要

由于恶意攻击和软件错误会导致故障节点表现出拜占庭行为，拜占庭容错的算法变得越来越重要，本文提出了一种用于部分同步模型的基于Leader的拜占庭容错协议HotStuff：一旦网络通信变得同步，HotStuff就能让正确的Leader以实际的网络延迟的速度驱动协议达成一致，通信的复杂性和副本数量呈线性关系。

引言

分布式系统一般是通过状态复制机(State Machine Replication)原理实现一致性，核心思想是系统中所有副本运行着相同的状态机，只要所有副本都已相同的初始状态开始，并基于相同的初始状态执行一组相同顺序的操作，那么所有的状态最终都会收敛一致，即整个系统对外表现出一致性。而确定一组相同顺序的操作需要系统达成共识，即所有诚实节点对执行顺序达成共识，这就是著名的拜占庭将军问题。
拜占庭类共识算法的理论安全保证，即n>3f，n为总的节点数量，f为恶意节点数量。一个拜占庭共识算法需要保证两个性质：
Safety 所有诚实的节点都认为某一时刻系统状态为s
Liveness 所有诚实节点最终能确定s为系统状态

其中s是一个抽象的概念，可以理解为系统内存在一个变量S，这个变量S的取值为系统状态，系统内节点接收一系列关于S的操作指令，某时刻（假设每个节点时钟没有误差）就S的取值进行共识，所有诚实节点确定变量S=s则满足安全性，所有诚实节点对变量S的取值必须做出决定且终止则满足活性。

在这篇文章中，系统作为一个整体提供了一个复制服务，状态是跨n个确定性镜像副本的，BFT SMR协议用于确保非错误副本对客户端发起的服务命令的执行顺序一致，尽管受到f的影响，但仍能够确保n-f个诚实节点可以按照相同的方式运行命令，从而为每个命令产生相应的响应。通常在半同步网络模型中，消息传输的已知边界∆在某个未知的全局稳定时间(GST)后保持的。

可扩展性挑战

PBFT包含了两个主要的工作流
1.网络环境良好情况下的正常工作模式（网络节点都同步，并且Leader运行正常）
2.用于更换崩溃的Leader的view-change模式

工作流1包含三阶段（pre-prepare，prepare，commit），
当Leader收到客户端的交易，根据交易广播pre-prepare消息，
收到pre-prepare消息的节点广播prepare消息，
当节点收到2f个preparep消息，广播commit消息，
当节点收到2f+1个commit消息后，处理交易。

当正常工作模式出现超时，共识发生停滞的时候，节点会更换到view-change模式，并将节点本地的view-number++，同时广播view-change消息；
如果节点的正常工作模式没有出现超时，但收到了f+1个view-change消息，也会切换到view-change模式，并将节点本地的view-number++，同时广播view-change消息；
view-change模式规定新Leader为view-change消息的height mod 节点总数N，因此新的Leader的转换过程是在节点集合中循环的。
当节点发现自己是新view的Leader，并收到2f+1个view-change消息，广播new-view消息，收到的2f+1个view-change消息被组合起来作为new-view消息的proof；当节点接收到一个number>=自己当前view-number的new-view消息，更新自己的view-number到new-view的number，如果收到的小于就忽略。
节点进入view-change模式后，维护一个timeout计时器，每一次view-change工作模式的失败都会是计时器的超时时间翻倍。

HotStuff围绕着一个三相核心，允许一个新的领导者简单地选择它所知道的最高QC，引入了第二个阶段，允许复制人在该阶段投票后“改变他们的想法”，根本不需要领导者的证明。这减轻了上述复杂性，同时大大简化了leader替换协议。最后，把所有阶段都规范化之后，就可以很容易地将HotStuff流水线化，并频繁地轮换领导者。

目前来说，区块链中的BFT协议想Tendermint和Csaper能够如此更迭Leader。但这些系统都建立在同步核心的基础上，其中的提议是在预先确定的时间间隔内提出的，需要适应一个P2P gossip network的传播的最差情况时间，在这个过程中放弃了大多数可用的BFT SMR解决方案，因为响应要求一个没有错误的Leader。

我们的贡献

提出了第一个BFT SMR协议，称为HotStuff，实现了两个属性
1.线性视图变换：在GST之后，任何正确的Leader，一旦被指定，只发送O(n)个验证器来驱动共识决策，包括Leader被替换的情况，因此在级联Leader失败的最差情况下，GST后达成共识的通信成本为O(

n

2

n^2

n2)
2.乐观响应：在GST之后，任何正确的Leader，一旦被指定，需要等到一个n-f个响应，来保证能够生成一个提议做出决定，包含Leader被取代的情况。
HotStuff中一个新的Leader推动协议达成共识的成本不会超出现在的Leader，因此HotStuff支持频繁迭代Leader，这在区块链环境中可以确保链的质量。
HotStuff通过为每个视图添加另一个阶段来实现这些属性，以较小的延迟代价换取了协议的简化，延迟在实际中通常小于∆。我们希望这种增加的延迟比以前的协议通过放弃响应来实现view-change而产生的延迟要小得多。
HotStuff的安全性是依赖节点view的投票和提交规则来指定的，实现Pacemaker活性所需的机制被封装在内，和安全性相关的机制是完全分离的。

相关工作

拜占庭问题下的共识达成的解决方案，归结为两个解决方案：

1.增加随机选举领导节点
2.依赖部分同步的网络，即在异步期间保持安全性

模型

我们考虑一个由n=3f+1副本组成的固定集合系统，索引为i ∈ [n] where [n] = {1, . . . , n}，拜占庭集合F ⊂ [n] of up to f = |F |。
我们的模型采用部分同步模型，已知延迟界限∆和位置的全局稳定时间GST，在GST之后，两个副本之间得到所有传输都在时间∆内达到。HotStuff协议将确保始终安全，并在GST之后的有限时间内的进展。

知识储备

门限签名Threshold signatures

一个（k，n）门限签名方案指由n个成员组成的签名群体，所有成员共同拥有一个公共密钥，每个成员拥有各自的私钥。只要收集到k个成员的签名，且生成一个完整的签名，该签名可以通过公钥进行验证。

证书Quorum Certificate，QC

主节点收到至少quorum个节点对用一个提案的投票消息（带签名）后，利用门限签名将其合成一个QC，这个QC可以理解为门限签名生成的完整签名，表示对该次提案达成一次共识。

视图View

视图是共识的基本单元，一个视图至多达成一次共识，并且单调递增，每个视图逐渐轮换推进共识。

共识状态树

每个共识区块可以看做是一个树节点，每个树节点内包含对应的提案内容（前文的操作指令）和相对应的QC，每个树节点包含一个父亲树节点的哈希，形成一棵树状结构，主节点基于本地最长的分支生成新的树节点。落后节点根据其他节点的最长分支上的最新树节点来同步中间缺失的树节点。

复杂度衡量

这个复杂度指代验证者复杂度，在这个共识协议中副本在GST之后达成共识决策所接收到的验证者数量的总和。
在这个反复达成共识的协议中，每个决策都有一个单调递增的计数器来表示。

prepareQC

对于某个prepare消息，Leader收集齐n-f个节点签名所生成的证据（聚合签名或者消息集合），可视为第1轮投票达成共识的证据。

lockedQC

对于某个commit消息，Leader收集齐n-f个节点签名所生成的证据（聚合签名或者消息集合），可视为第2轮投票达成共识的证据。

Basic HotStuff

HotStuff解决了状态机复制(SMR)问题。SMR的核心是一种协议，用于确定客户端不断增长的命令请求日志，一组状态机副本以一致的顺序应用命令。客户端向所有副本发送命令请求，并等待其中(f + 1)个副本的响应。在大多数情况下，我们在讨论中省略了客户端，并参考标准文献中关于客户端请求的编号和重复删除的问题。

基本HotStuff解决方案在算法2中给出。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阶段

主节点：
1 类似于Pre-commit阶段，主节点收集到quorum个pre-commit vote消息，聚合出这一阶段的pre-commit QC，附带在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 之后增加视图号view-number，开启下一轮共识，根据prepareQC构造New-View消息。
从节点：
验证消息后执行decide消息中commitQC指向的树节点的交易。
next-View 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的各个阶段以流水线方式进行处理交易。

从图中可以看出，每个阶段都会切换视图，因此每个提案都有自己的视图。节点对于不同的提案来说处在不同的视图上，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。经过流水线简化版本的Chained-HotStuff工作过程如下：

主节点：
1）等待new-view消息，发出自己的proposal；

2）等待其他节点进行投票；

3）向下一个主节点发送NEW-VIEW消息。

从节点：
1）等待主节点的提案消息；

2）检查提案中的QC，更新本地highQC，lockedQC，发送投票；

3）向下一个主节点发出NEW-VIEW消息。

Dummy nodes
为了简化树结构，生成叶子节点来自通用的QC.node和未知节点到提案view的高度，需要保持view-number和节点高度能够一致，如果在一个view中不能达成共识，就在这个view里添加一个dummy block。

One-Chain，Two-Chai，and Three-Chain
当节点

b

∗

b^*

b∗携带一个指向父节点的QC即

b

∗

b^*

b∗.justify.node =

b

∗

b^*

b∗.parent，我们可以说它形成了一个单链。用 b′′ =

b

∗

b^*

b∗.justify.node 表示表示节点

b

∗

b^*

b∗形成一个双链，如果除了形成一个单链，b′′.justify.node = b′′.parent。如果 b′′ 形成双链，则它形成三链。查看链 b = b’.justify.node, b’ = b’‘.justify.node, b’’ = b∗.justify.node，任何一个节点都可能出现祖先差距。这些情况类似于 Basic HotStuff 的领导者未能完成三个阶段中的任何一个，并被 next view 打断到下一个视图。如果

b

∗

b^*

b∗形成一个单链，则 b′′ 的准备阶段已经成功。因此，当一个副本为

b

∗

b^*

b∗投票时，它应该记住 genericQC ←

b

∗

b^*

b∗.justify，我们注意到即使 One-Chain 不是直接的，更新 genericQC 也是安全的，只要它高于当前的 genericQC 即可。在第 6 节描述的实现代码中，我们确实在这种情况下更新了 genericQC。
这么理解吧，就是一个区块中的QC是对其直接父区块的确认，称之为1-chain；同理，一个区块b后面没有Dummy block的情况下，连续产生了k个区块，那么称这段区块链分支是区块b的k-chain。
如果b’对b形成了1-chain，那么b’相当于b的prepare阶段达成（第一轮投票成功），节点会将本地的prepareQC更新。

每当一个新的区块形成，节点都会检查是否会形成1-chain，2-chian，3-chain.
1-chain: 有新的prepareQC形成，更新本地的prepareQC
2-chain: 有新的precommitQC形成，更新本地的lockedQC
3-chian: 有新的commitQC形成，有新的区块分支进入commit状态，执行确认的区块分支

实现

对于高效的状态复制机系统的构建，HotStuff是很实用的协议。因为HotStuff简单明里哦啊，我们可以很容易将Algorithm3转变为事件驱动机制的HotStuff。

如Algorithm 4所示，通过将事件驱动机制从主体中提取到一个名为 Pacemaker 的模块中，进一步简化和概括了代码。 与下一个Leader在开始其统治之前总是在通用阶段结束时等待通用QC不同，这个逻辑被委托给了Pacemaker。 一个稳定的Leader可以跳过这一步，并在多个高度上简化提案。 此外，我们放宽了 1 的直接父约束。保持最高的 genericQC 和锁定的 QC ，同时仍然保留有效节点中的 QC 始终引用其祖先的要求。 正确性证明类似于 Chained HotStuff，我们也将其推迟到 [50] 的附录中。

Data structures

每个副本u保持对主状态变量的追踪

它还保持一个常数 b0，即所有正确副本都知道的同一创世节点。 为了引导，b0 包含自己的硬编码 QC，block、bexec、bleaf 都初始化为 b0，qchigh 包含 b0 的 QC。

Pacemaker

Pacemaker是一种保证GST之后进展的机制，它通过两种成分来实现这一点。
第一个是“同步”，将所有正确的副本和唯一的领导者带入一个足够长的时期内的共同高度。文献 [25, 20, 15] 中通常的同步机制是让副本增加他们在更大高度上花费的 Δ 的数量，直到取得进展。确定性选举领导者的一种常见方法是使用轮换领导者方案，其中所有正确的副本都保持预先定义的领导者计划，并在领导者降级时轮换到下一个。
其次，Pacemaker 需要为领导者提供一种方法来选择将由正确副本支持的提案。

如算法5所示，视图改变后，在onReceiveNewView中，新的leader通过onNextSyncView收集replica发送的new-view消息，发现满足onReceiveProposal中第二部分条件的最高QC（算法4第18行） ）。然而，在同一个视图中，现任领导者会将新节点链接到它自己最后提出的叶子的末尾，在那里不需要新视图消息。基于一些特定于应用程序的启发式方法（例如，等到先前提议的节点获​​得 QC），当前领导者调用 onBeat 来提议一个携带要执行的命令的新节点。值得注意的是，即使一个糟糕的 Pacemaker 任意调用 onPropose，或者反复选择父级和 QC，并且针对任何调度延迟，始终可以保证安全。因此，仅由算法 4 保证的安全性与算法 5 的任何潜在实例化完全解耦。
Pacemaker实现如下几部分功能
Leader检查
收集NewView消息，对齐View并更新highQC

Two-phase HotStuff variant

为了展现HotStuff框架的灵活性，算法6展示了两阶段HotStuff。

只有有效更新步骤之后，双链做出提交决定，单链锁定。4.4节讨论了两阶段之后会求实积极的响应，和Tendermin/Casper类似。好处是阶段更少，而活跃度可以通过在 Pacemaker 中结合基于最大网络延迟的等待来解决。 进一步讨论见第 7.3 节。

One-Chain and Two-Chain BFT Protocols

在本节中，我们研究了四个 BFT 复制协议，这些协议跨越了拜占庭容错的 40 年研究，将它们转换为类似于 Chained HotStuff 的链式框架。 图 3 提供了我们考虑的协议的提交规则的鸟瞰图，包括 HotStuff。 简而言之，DLS [25] 中的提交规则是单链，允许节点仅由其自己的领导者提交。 PBFT [20]、Tendermint [15, 16] 和 Casper [17] 中的提交规则几乎相同，并且由两条链组成。 它们在为活性引入的机制上有所不同，PBFT 具有二次大小的领导者“证明”（无线性），Tendermint 和 Casper 在每个领导者提议之前引入了强制性的 Δ 延迟（没有乐观响应）。 HotStuff 使用三链规则，并且具有无延迟的线性领导者协议。

DLS

单链的提交规则最简单，该规则以第一个已知的异步拜占庭共识解决方案 Dwork、Lynch 和 Stockmeyer (DLS) 为模型，如图 3(a) 所示。副本在其投票支持的最高节点上被锁定在 DLS 中。不幸的是，如果在某个高度，一个领导者模棱两可，并且两个正确的副本被锁定在那个高度的冲突提案上，这条规则很容易导致僵局。放弃任何一个锁都是不安全的，除非有 2f + 1 表明他们没有投票支持锁定的值。事实上，在 DLS 中，只有每个高度的领导者自己才能通过单链提交规则做出提交决定。因此，如果它模棱两可，只有领导者本身会受到伤害；如果 2f + 1 个副本没有投票支持，或者存在冲突的提案（由领导者签名），副本可以放弃锁；在 DLS 中每个高度末端发生的解锁协议被证明是相当复杂和昂贵的。再加上只有一个高度的领导者可以决定，在没有发生故障且网络及时的最佳情况下，DLS 需要 n 次领导者轮换，并且每个决策需要 O(n4) 次消息传输。虽然它在展示安全异步协议方面开辟了新天地，但 DLS 并非设计为实用的解决方案。

PBFT

两阶段投票，每个view有超时，view-change通过第一轮投票来完成，view-change消息中包含了prepared消息即达成了第一阶段投票的消息。

Tendermit Casper

两阶段投票，第一个回合中的各个阶段都有超时时间，round-change通过超时触发（而不是投票），网络节点保存自己已经达成第一阶段投票的消息（即polka消息）

HotStuff

三阶段投票，每个view有超时，采用阈值签名减小消息复杂度，liveness和safety解耦为两个部分。

Grandpa

将出块和共识确认分离，用来对已经产生的区块链进行投票确认，两阶段投票，但投票是针对区块分支（对一个区块投票也相当于对其所有父区块投票），而不是特定区块，各个节点可以针对不同高度的区块投票。

总结

在BFT类的共识研究中，安全性的要求需要在视图切换时，主节点确保自己是基于最新的系统状态工作的，视图切换与系统状态的共识产生了o(n^3)的通信复杂度。而HotStuff通过增加一轮共识来解决，再结合门限签名降低了通信复杂度。不仅如此，流水线的工作方式，让算法变得足够简洁优雅，这与raft的工作方式相似，采取了先上链再共识，通过三轮共识之后再执行。这种链式的结构，不再区分每个阶段通信的意义（PBFT中prepare、commit），灵活的主节点更换的机制，在节点更换时不需要通信来确定最新共识的状态，对安全性与活性进行隔离，投票保证了安全性，pacemaker保证了其在网络异步时的活性。