摘要

本文提出了一种用于部分同步模型的基于领导者的拜占庭容错复制协议HotStuff。一旦网络通信变得同步，HotStuff就能让正确的领导者以实际的（与最大的）网络延迟（一种称为响应性的属性）的速度驱动协议达成一致，通信复杂性与副本数量成线性关系。据我们所知，HotStuff是第一个展示这些组合属性的部分同步BFT复制协议。它的简单性使其能够进一步流水线化并简化为用于构建大规模复制服务的实用、简洁的协议。
关键字：拜占庭容错，共识，响应性，可伸缩性，区块链

引言

拜占庭容错(BFT)是指计算系统在采取对系统运行至关重要的操作时，能够忍受其组件的任意(即拜占庭)故障的能力。在状态机复制(SMR)的上下文中[35,47]，系统作为一个整体提供了一个复制服务，其状态是跨n个确定性副本镜像的。BFT SMR协议用于确保非错误副本对客户端发起的服务命令的执行顺序达成一致，尽管有拜占庭副本的努力。这又确保了n-f个没有错误的副本将以相同的方式运行命令，从而为每个命令产生相同的响应。通常，我们在这里关注的是部分同步通信模型[25]，在此消息传输的已知边界∆在某个未知的全局稳定时间(GST)后保持。在该模型中，非故障副本需要n≥3f + 1以相同的顺序(如[12])同意相同的命令，只有在GST[27]之后才能确定进度。
在最初设想BFT SMR协议时，典型的目标系统大小为n = 4或n = 7，部署在局域网中。然而，拜占庭容错技术在区块链上的应用所带来的新兴趣，现在要求解决方案可以扩展到更大的n。与无权限的区块链(例如支持比特币的区块链)相比，所谓的许可区块链涉及一组固定的副本，这些副本共同维护一个有序的命令账本，或者换句话说，支持SMR。尽管它们的性质是被允许的，但其复制品的数量在数百甚至数千是被设想的(例如，[30,42])。此外，它们部署到广域网络需要设置∆以适应通信延迟的更高可变性。

扩展的挑战。自从引入PBFT[20](部分同步模型中第一个实用的BFT复制解决方案)以来，围绕其核心的两阶段范式构建了许多BFT解决方案。实际的方面是，一个稳定的领导人可以在两轮信息交换中推动共识决策。第一阶段通过形成由(n - f)票组成的仲裁证书(QC)来保证提案的唯一性。第二阶段保证下一个领导者可以说服复制人投票支持一个安全的提议。
一个新的领导者收集信息并向副本提出建议的算法——称为视图变化——是复制的中心。不幸的是，基于两阶段范式的视图更改远不是简单的[38]，而是容易出现bug的[4]，并且即使是中等大小的系统也会带来很大的通信损失。它要求新的领导者从(n - f)副本传递信息，每个副本报告自己的最高已知QC。即使只计算验证器(数字签名或消息验证码)，在PBFT中传递一个新提议的通信足迹为O(n3)个验证器，而通过阈值数字签名(如[18,30])将多个验证器组合成一个的变体仍然发送O(n2)个验证器。在PBFT中，如果在达成单一共识决策之前发生O(n)个视图变化，那么传输的验证器总数是O(n4)，即使有阈值签名也是O(n3)。这种扩展挑战不仅困扰PBFT，而且自那时以来开发的许多其他协议，如Prime [9]， Zyzzyva [34]， Upright [22]， BFT-SMaRt [13]， 700BFT[11]和SBFT[30]。
HotStuff围绕着一个三相核心，允许一个新的领导者简单地选择它所知道的最高QC。它引入了第二个阶段，允许复制人在该阶段投票后“改变他们的想法”，根本不需要领导者的证明。这减轻了上述复杂性，同时大大简化了leader替换协议。最后，把所有阶段都规范化之后，就可以很容易地将HotStuff流水线化，并频繁地轮换领导者。
据我们所知，在区块链领域，只有Tendermint[15,16]和Casper[17]等BFT协议遵循这样简单的领导机制。然而，这些系统是围绕一个同步核心构建的，其中的提议是在预先确定的间隔内提出的，必须适应在一个广域点对点八卦网络上传播消息所需的最坏情况时间。在这样做的过程中，他们放弃了大多数实用的BFT SMR解决方案(包括上面列出的那些)的标志，即乐观响应[42]。非正式地说，响应性要求一个没有错误的leader，一旦指定，就可以仅根据实际的消息延迟，独立于任何已知的消息传输延迟上限[10]，及时驱动协议达成共识。更适合我们的模型的是乐观响应性，它只需要在有益的(希望是常见的)情况下进行响应—这里是在达到GST之后。不管乐观与否，Tendermint/Casper等设计都不具备响应性。问题的关键是，可能存在一个诚实的复制品，拥有最高的QC，但领导不知道。我们可以构建这样的场景，它会阻止无限的进展(参见4.4节了解详细的无活动场景)。事实上，未能在关键协议步骤纳入必要的延迟可能会导致完全失去活性，正如在一些现有部署中报告的那样，例如，见[2,3,19]。

我们的贡献。据我们所知，我们提出了第一个BFT SMR协议，称为HotStuff，以实现以下两个属性:
  • 线性视图变化：在GST之后，任何正确的leader，一旦被指定，只发送O(n)个验证器来驱动共识决策。这包括领导者被替换的情况。因此，在级联leader失败的最坏情况下，GST后达成共识的通信成本为O(n2)个验证器。
  • 乐观响应(Optimistic Responsiveness):在GST之后，任何一个正确的leader，一旦被指定，只需要等待第一个n - f个响应，以确保它可以创建一个有进展的提案。这包括领导者被替换的情况。
HotStuff的另一个特点是，一个新的领导者推动协议达成共识的成本并不比当前的领导者高。因此，HotStuff支持频繁的领导人交替，这在区块链环境中被认为是有用的，以确保链质量[28]。
HotStuff通过为每个视图添加另一个阶段来实现这些属性，以较小的延迟代价换取相当程度上简化leader替换协议。这种交换只会导致实际的网络延迟，实际情况下通常远小于∆。因此，我们希望这种增加的延迟比以前的协议(放弃响应性来实现线性视图变化)产生的延迟要小得多。此外，由于我们在第5节中介绍的高效管道，吞吐量不会受到影响。
HotStuff还有一个特别简单的好处。安全性是通过节点图上的投票和提交规则来指定的。实现起搏器活性所需的机制被封装在起搏器内，与安全所需的机制完全分离(第6节)。

相关工作

在面对拜占庭失败时达成共识被Lamport et al.[37]定义为拜占庭将军问题，Lamport et al.[37]也创造了术语“拜占庭失败”。第一个同步方案由Pease等人[43]提出，之后由Dolev和Strong[24]改进。改进后的协议具有O(n3)的通信复杂度，Dolev和Reischuk[23]对其进行了优化。Katz和Koo[32]给出了一个使用随机性的基于领导者的同步协议，显示了一个具有(n−1)/2弹性的预期恒轮解决方案。
同时，在异步设置中，Fischer等人[27]表明，在异步设置中，面对单个故障，这个问题是确定性地不可解决的。此外，BenOr[12]证明了任何异步解决方案的弹性边界为(n−1)/3。为了避免这种不可能，设计了两种方法。一种依赖于随机性，最初由Ben-Or[12]展示，通过过程使用独立随机的硬币投掷，直到它们碰巧收敛到一致。后来的作品使用加密方法来共享不可预测的硬币，并将复杂性降低到不变的预期轮数，以及O(n3)通信[18]。
第二种方法依赖于部分同步，Dwork、Lynch和Stockmeyer (DLS)[25]首先展示了这种方法。该协议在异步期间保持安全性，在系统变为同步后，DLS保证终止。一旦保持了同步，DLS就会产生O(n4)次的总通信和O(n)次决策。
状态机复制的核心依赖于共识来对客户端请求进行排序，以便正确的副本按此顺序执行它们。SMR中反复出现的共识需求导致Lamport设计了Paxos[36]协议，该协议运行一个高效的管道，其中稳定的领导者通过线性通信和一次往返驱动决策。基于类似的强调，Castro和Liskov[20, 21]开发了一种高效的基于leader的拜占庭SMR协议，名为PBFT，其稳定的leader需要O(n2)通信，每个决策需要两次往返，leader替换协议需要O(n3)通信。PBFT已部署在多个系统中，包括BFT-SMaRt[13]。Kotla等人在PBFT中引入了一个名为Zyzzyva[34]的乐观线性路径，该路径被用于多个系统，如直立[22]和拜占庭[33]。乐观路径具有线性复杂度，而leader替换协议保持O(n3)。Abraham等人随后揭露了Zyzzyva的安全违规，并提出了修复方案[5,30]。另一方面，为了降低协议本身的复杂性，Song等人提出了Bosco[49]，这是一个简单的一步协议，在乐观路径上具有低延迟，需要5f + 1副本。SBFT[30]引入了一个O(n2)通信视图改变协议，它支持一个稳定的leader协议，具有乐观线性的、一次往返的决策。它通过利用两种方法降低了通信的复杂性:Reiter[45]提出的基于收集器的通信范式，以及Cachin等人[18]提出的基于协议投票的阈值加密的签名组合。

Ramasamy等人提出了一种采用随机化的基于leader的拜占庭SMR协议，Miller等人开发了一种名为HoneyBadgerBFT的无leader变体。这些随机化的拜占庭解决方案的核心是采用随机化的异步拜占庭共识，其最著名的通信复杂度是O(n3)(见上文)，通过批处理分摊成本。然而，最近，基于这篇HotStuff论文中的想法，一个并行提交到PODC ' 19[8]进一步提高了通信复杂度O(n2)。
比特币的核心是一个被称为中本共识[40]的协议，这是一个同步协议，只有概率安全保证，没有终结性(见[6,28,41]的分析)。它在一个无权限的模型中运行，参与者是未知的，并且通过工作量证明(Proof-of-Work)保持弹性。如上所述，最近的区块链解以各种方式将功证明解与经典BFT解杂交[7,17,26,29,31,33,42]。在这些混合解决方案中，需要解决轮流领导的问题，以及其他问题，这正是HotStuff背后的动力所在。

模型

我们考虑一个由n = 3f +1副本组成的固定集合组成的系统，索引为i∈[n]，其中[n] ={1，…n}。一个集F⊂[n]至多F = |F |副本是拜占庭错误，其余的是正确的。我们经常将拜占庭副本称为由对手协调的副本，它了解到这些副本持有的所有内部状态(包括它们的加密密钥，见下文)。
网络通信是点对点的、经过身份验证的、可靠的：当且仅当一个正确的副本将消息发送给前者时，另一个正确的副本将接收来自后者的消息。当我们提到“广播”时，它涉及到广播者，如果正确的话，发送相同的点对点消息给所有副本，包括它自己。我们采用Dwork等[25]的部分同步模型，其中有已知的界限∆和未知的全球稳定时间(GST)，因此在GST之后，两个正确副本之间的所有传输都在时间∆内到达。我们的协议将始终确保安全，并将保证在GST后的有限时间内的进展。(在商品及服务税之前保证进展是不可能的。)在实践中，如果系统在GST之后足够长的时间内保持稳定(即，如果消息在∆时间内到达)，我们的协议将保证进度，尽管假设它永远这样做会简化讨论。

加密原语。HotStuff使用阈值签名[14,18,48]。在(k,n)-阈值签名方案中，所有副本都持有一个单一的公钥，而这n个副本中的每个副本都持有一个不同的私钥。第i个副本可以使用它的私钥在消息m上贡献一个ρi←tsigni(m)的部分签名ρi}i∈i，其中| i | = k和每个ρi←tsigni(m)，可以用来在m上产生一个数字签名σ←tcombine(m， {ρi}i∈i)。任何其他副本可以使用公钥和函数tverify验证签名。我们要求对于每个i∈i，如果ρi←tsigni(m)， | i | = k，如果σ←tcombine(m， {ρi}i∈i)，则tverify(m， σ)返回true。然而，给定oracle访问oracle {tsigni(·)}i∈[n]\F，在严格少于k−F的这些oracle上查询tsigni(m)的对手为消息m产生签名σ的概率可以忽略(即，这样tverify(m， σ)返回true)。在本文中，我们使用k = 2f +1的阈值。同样，我们通常会在协议描述中隐式地保留对tverify的调用。
我们还需要一个加密哈希函数h(也称为消息摘要函数)，它将任意长度的输入映射到固定长度的输出。哈希函数必须是抗碰撞的[46]，它非正式地要求对手产生输入m和m '的概率使h(m) = h(m ')可以忽略不计。因此，h(m)可以作为协议中唯一输入m的标识符。

复杂性测量。我们关心的复杂度度量是验证者复杂度，具体来说，它是在协议中副本i∈[n]在GST后达成共识决策所接收到的验证者数量的总和。(同样，在商品及服务税之前，在最坏的情况下可能根本无法达成共识。)在这里，身份验证器要么是部分签名，要么是签名。由于多种原因，身份验证器复杂性是衡量通信复杂性的一个有用指标。首先，与比特复杂度和消息复杂度一样，它隐藏了传输拓扑结构中不必要的细节。例如，携带一个验证器的n条消息与携带n个验证器的消息计数相同。其次，在像我们这样反复达成共识的协议中，每个共识决策(或在达成共识决策的过程中提出的每个观点)都由一个单调递增的计数器来标识，验证器复杂性比比特复杂性更适合用于捕获成本。也就是说，因为这样一个计数器无限增加，发送这样一个计数器的协议的位复杂度是不受限制的。第三，由于在实践中，生成或验证数字签名以及生成或组合部分签名的加密操作通常是使用它们的协议中计算最密集的操作，验证者的复杂性也提供了对协议的计算负担的洞察。

基本的HOTSTUFF

HotStuff解决了状态机复制(SMR)问题。SMR的核心是一种协议，用于确定客户端不断增长的命令请求日志。一组状态机副本以一致的顺序应用命令。客户端向所有副本发送命令请求，并等待其中(f + 1)个副本的响应。在大多数情况下，我们在讨论中省略了客户机，并参考标准文献中关于客户机请求的编号和重复删除的问题。
基本HotStuff解决方案在算法2中给出。该协议工作在视图的连续视图中，视图编号单调递增。每个viewNumber都有一个唯一的、为所有人所知的专用leader。每个副本存储一棵挂起的命令树作为其本地数据结构。每个树节点包含一个建议的命令(或一批命令)、与协议相关的元数据和一个父链接。由给定节点领导的分支是通过访问父链接从节点一直到树的根的路径。在协议期间，一个单调增长的分支被提交。为了被提交，提出分支的特定视图的领导者必须在三个阶段(准备、预提交和提交)从quorum (n - f)副本中收集选票。
协议中的一个关键成分是对领导提议的(n−f)投票集合，称为仲裁证书(或简称“QC”)。QC与特定的节点和视图编号相关联。tcombine实用程序使用阈值签名方案来生成(n - f)签名投票的表示，作为单个验证器。
下面，我们分阶段给出协议逻辑的操作描述，然后在算法2中给出精确的规范，并以安全性、活动性和复杂性的论点结束本节。

阶段

准备阶段。对于一个新的leader，协议首先从(n - f)个副本收集新视图消息。new-view消息是由副本发送的，因为它过渡到viewNumber(包括第一个视图)，并携带副本收到的最高的prepareQC(如果没有)，如下所述。
leader处理这些消息，以便选择一个拥有最高的前置视图的分支，在该分支中形成了prepareQC。leader在新视图消息中选择最高视图highQC的prepareQC。因为highQC是(n - f)个副本中最高的，没有更高的视图可以做出提交决定。因此，high QC.node所领导的分支是安全的。
收集新观点信息来选择一个安全的部门可能会被现任领导省略，他可能会选择自己的最高准备qc作为highQC。我们将此优化推迟到第6节，在本节中只描述一个单一的、统一的leader协议。请注意，与pbft类协议不同的是，在leader协议中包括这一步是直接的，而且无论在什么情况下，它都会产生与协议的所有其他阶段相同的线性开销。
leader使用createLeaf方法来扩展highQC的尾巴。节点有一个新的提议。该方法创建一个新的叶节点作为子节点，并将父节点的摘要嵌入到子节点中。然后leader在准备消息中向所有其他副本发送新节点。该方案具有较高的安全合理性。在从leader接收到当前视图的准备消息后，副本r使用safeNode谓词来决定是否接受它。如果被接受，副本将为提案发送一个带有部分签名(由tsignr产生)的准备投票给leader
safeNode谓词。safeNode谓词是协议的核心组成部分。它检查携带QC justification m.justify的提案消息m，并决定是否可以安全接受m.node。接受提议的安全规则是m.node的分支扩展自当前锁定的节点lockedQC.node。另一方面，活性规则是，如果m.justify的视图比当前lockedQC的视图高，则副本将接受m。只要两个规则中有一个成立，谓词就为真。
预准备阶段。当leader收到(n−f)对当前提案curProposal的准备投票时，它将它们合并到一个prepareQC中。领导广播预提交消息中的prepareQC。副本以预先提交的投票响应leader，并具有签名的提案摘要。
提交阶段。提交阶段类似于预提交阶段。当leader收到(n−f)个预提交投票时，它将它们组合成一个precommitQC并在提交消息中广播它;副本以提交投票回应它。重要的是，通过将副本的lockedQC设置为precommitQC(算法2的第25行)，在这一点上，副本将被锁定在precommitQC上。这对于保护提案的安全性至关重要，以防它成为一个共识决策。
决定阶段。当leader收到(n−f)提交选票时，它将它们合并成一个commitQC。一旦leader组装了一个commitQC，它将它发送到一个决定消息给所有其他副本。在接收到decision消息时，副本将commitQC中包含的提议视为已提交的决策，并执行已提交分支中的命令。该副本递增viewNumber并启动下一个视图。
nextView中断。在所有阶段中，副本在视图viewNumber上等待消息的超时时间，由辅助的nextView(viewNumber)实用程序确定。如果nextView(viewNumber)中断等待，副本也增加viewNumber并开始下一个视图。

数据结构

消息。协议中的消息m有一组固定的字段，使用算法1中所示的Msg()实用程序填充这些字段。m会自动加curView，即发送者的当前视图号。每个消息都有一个类型m.type∈{new-view, prepare, pre-commit, commit, decide}。M.node包含一个拟节点(拟分支的叶节点)。有一个可选字段m.justify。leader总是用这个字段来携带不同阶段的QC。副本在new-view消息中使用它来携带最高的prepareQC。在副本角色中发送的每条消息都包含一个部分签名。发送方通过元组⟨m.type、m.viewNumber、m.node⟩，添加在voteMsg()实用程序中。
法定证书。元组⟨type, viewNumber, node⟩上的仲裁证书(QC)是一种数据类型，它组合了由(n−f)副本签名的相同元组的签名集合。给定一个QC qc，我们用qc.type, qc.viewNumber, qc.node引用原始元组的匹配字段。
树和树枝。每个命令都包装在一个节点中，该节点还包含一个父链接，该链接可以是父节点的散列摘要。我们省略了伪代码中的实现细节。在协议期间，副本只有在节点所领导的分支已经在其本地树中之后才会发送消息。在实践中，落后的接收者可以通过从其他副本获取丢失的节点来弥补。为了简单起见，伪代码中也省略了这些细节。如果两个分支都不是另一个的延伸，那么这两个分支就是冲突的。如果两个节点所领导的分支是冲突的，那么它们就是冲突的。
记账变量。副本使用额外的局部变量来记录协议状态：（i）视图编号，最初为1，通过完成决策或下一个视图中断来增加；（ii）锁定的法定人数证书lockedQC，最初⊥, 存储副本投票提交的最高QC；和（iii）初步准备质量控制⊥, 存储副本投票预提交的最高QC。此外，为了以增量方式执行已提交的命令日志，副本将维护其分支已执行的最高节点。为了简洁起见，下面省略了这一点。

协议规范

算法2中给出的协议被描述为一个迭代的逐视图循环。在每个视图中，副本根据其角色连续执行阶段，描述为连续的“as”块。一个副本可以有多个角色。例如，leader也是一个(正常的)副本。可以跨角色并发地执行as块。每个as块的执行都是原子的。nextView中断中止任何as块中的所有操作，并跳转到“Finally”块。


安全、活力和复杂性

安全。我们首先定义仲裁证书qc，使其在tverify(⟨qc.type, qc.viewNumber, qc.node⟩, qc.sig)为真。
引理1。对于任何有效的qc1, qc2，其中qc1.type=qc2.type和qc1.node与qc2.node冲突。我们有qc1.viewNumber和qc2.viewNumber。
证明。为了显示矛盾，假设qc1.viewNumber=qc2.viewNumber=v。因为一个有效的QC只能用n - f = 2f + 1投票(即部分签名)为它形成，必须有一个正确的副本，在v的相同阶段投票两次，这是不可能的，因为伪代码只允许在每个视图的每个阶段投票一次。
定理2。如果w和b是冲突的节点，那么它们不能同时被一个正确的副本提交。
证明。我们用反证法来证明这个重要的定理。让qc1表示一个有效的commitQC（即qc1.Type = commit）这样qc1.node = w，并且qc2表示一个有效的commitQC，这样qc2.node = b，表示v1 = qc1.viewNumber和v2 = qc2.viewNumber。由引理1得到v1 v2。假设v1<v2。
现在，我们将用vs表示比v1高的最低视图，其中存在有效的prepareQC，qcs(即qcs.type = prepare)，其中qcs.viewnumber = vs，qcs.node与w冲突。正式地，我们为任何prepareQC定义以下谓词：
我们现在可以设置第一个切换点qcs：
注意，通过假设，这样的qcs必须存在；例如，qcs可以是视图v2中的prepareQC。
发送部分结果tsignr的正确副本(⟨qc1.type, qc1.viewNumber, qc1.node⟩)，让r是第一个贡献tsignr的(⟨qcs.type, qcs.viewNumber, qcs.node⟩)；这样的r必须存在，否则，qc1.sig和QCS.sig不能被创建。在视图v1中，副本r在算法2的第25行更新它的锁lockedQC到w上的预提交qc。由于vs最小，副本r在w上的锁在qcs形成之前不会被改变。否则，一定是看到了其他一些用较低视角的prepareQC，因为第17行在第25行之前，这与最小化相矛盾。现在考虑一下在视图的准备阶段vs副本r对safeNode的调用，其中消息m携带m.node = qcs.node。假设m.node与lockedQC .node冲突，因此算法1第26行的间断为假。此外，m.justify.viewNumber祝辞v1违背了vs的最小值，所以算法1第27行中的间断也是假的。因此，safeNode必须返回false，r不能对view vs中冲突的分支进行准备投票，这是一个矛盾。

活性。在上一节中，有两个函数未定义：leader和nextView。它们的定义不会影响协议的安全性，尽管它们对存活率有影响。在给出候选定义之前，我们首先证明了在GST之后，有一个有界持续时间Tf，如果在Tf期间所有正确的副本都留在视图v中，并且视图v的leader是正确的，那么就可以做出决定。下面，如果qc1和qc2有效，我们说qc1和qc2匹配，即qc1.node=qc2.node，qc1.viewNumber=qc2.viewNumber。

引理3。如果一个正确的副本被锁定为lockedQC=precommitQC，那么至少有f + 1个正确的副本投票给一些匹配lockedQC的prepareQC。
证明。假设副本r在precommitQC上被锁定。然后，在准备阶段（算法2的第10行）对匹配的prepareQC进行(n−f)投票，其中至少f + 1来自正确的副本。
定理4。在GST之后，存在一个有界时间段Tf，如果在Tf期间所有正确的副本都留在视图v中，并且视图v的leader是正确的，那么就可以做出决定。
证明。leader从一个新的view开始，收集(n - f)个newview消息，计算出自己的highQC，然后广播一个准备消息。假设在所有副本中(包括leader本身)，保持的最高锁是lockedQC=precommitQC∗。通过引理3，我们知道至少有f +1个正确的副本投票给了匹配的prepareQC∗，并且已经在它们的新视图消息中把它们发送给了leader。因此，leader必须至少在这些new-view消息中学习一个匹配的prepareQC∗，并在它的prepare消息中使用它作为highQC。通过这种假设，所有正确的副本在它们的视图中都是同步的，leader没有错误。因此，所有正确的副本将在准备阶段投票，因为在safeNode中，算法1的第27行条件是满足的（即使消息中的节点与副本的陈旧的lockedQC.node冲突，因此第26行不冲突）。然后，在领导为这个视图组装一个有效的prepareQC之后，所有副本将在接下来的所有阶段进行投票，从而产生一个新的决定。在GST之后，这些阶段完成的持续时间Tf是有界的。
协议是乐观响应的，因为没有显式的“wait-for-∆”步骤，并且safeNode中的逻辑分离被用来在三相范式的帮助下覆盖失效的锁。
我们现在为leader和nextView提供了简单的结构，足以确保在GST之后，最终会到达一个视图，其中leader是正确的，所有正确的副本在Tf时间内都保持在这个视图中。leader只要返回一些从视图号到副本的确定性映射就足够了，最终在所有副本中循环。nextView的一个可能的解决方案是利用指数回退机制来维护超时间隔。然后在进入每个视图时设置一个计时器。当计时器没有做出任何决定时，副本将间隔加倍，并调用nextView来推进视图。由于每次的间隔都是双倍的，所以所有正确副本的等待间隔最终将至少有Tf重叠，在此期间leader可以驱动一个决策。
两个阶段的Livelessness。现在，我们简要演示了“两相”热点的无限非决定性场景。这解释了在Casper和Tendermint中引入同步延迟的必要性，从而放弃（乐观）响应。
在两阶段的HotStuff变体中，我们省略了预提交阶段，直接进行提交。当对prepareQC进行投票时，副本将被锁定。假设，在视图v中，一个leader提出了b，它完成了prepare阶段，某个replica rv投票给prepareQC，比如qc，使得qc.node = b。因此，rv被锁定在qc上。异步网络调度会导致其他副本在没有接收qc的情况下移动到v + 1视图。
我们现在无限重复下面的单视图记录。我们开始查看v + 1时，只有rv持有系统中最高的prepareQC(即qc)。新的leader l从2f + 1副本(rv除外)收集新视图消息。其中，最高的prepareQC qc '，有视图v−1，b ' = qc '。节点与b冲突，l提出扩展b '的b '，对此有2f个诚实副本进行投票，但rv拒绝它，因为它被锁定在qc上，b '与b和qc '冲突低于qc。最终，2f副本放弃并移动到下一个视图。就在这时，一个错误的副本响应了l的提议，l然后将一个准备qc (v +1,b ")和一个副本放在一起，说rv+1投票给它，并锁定它。

复杂性。在HotStuff的每个阶段，只有leader向所有副本广播，而副本以部分签名回应发送者一次，以证明投票。在leader的消息中，QC由之前收集的(n - f)投票证明组成，可以通过单个阈值签名进行编码。在副本的响应中，来自该副本的部分签名是唯一的身份验证器。因此，在每个阶段，总共接收到O(n)个验证者。由于存在恒定数量的阶段，每个视图的总体复杂度为O(n)。

链接HOTSTUFF

Basic HotStuff负责人提交提案需要三个阶段。除了从副本中收集选票外，这些阶段并没有做“有用”的工作，而且它们都非常相似。在Chained HotStuff中，我们改进了Basic HotStuff协议实用程序，同时大大简化了它。这样做的目的是改变对每个准备阶段的看法，这样每个提案都有自己的看法。这减少了消息类型的数量，并允许对决策进行流水线处理。Casper[1]中也建议使用类似的方法来减少消息类型。
更具体地说，在Chained HotStuff中，准备阶段的投票被leader收集到一个genericQC视图中。然后将通用qc传递给下一个视图的领导，本质上是将下一阶段的责任委托给下一个领导，这将是预先提交的。然而，下一个领导者实际上并不进行预提交阶段，而是发起一个新的准备阶段，并添加自己的建议。视图v +1的准备阶段同时作为视图v的预提交阶段。视图v + 2的准备阶段同时作为视图v +1的预提交阶段和视图v的提交阶段。这是可能的，因为所有阶段都具有相同的结构。
图1描述了嵌入在链式HotStuff提议链中的基本HotStuff协议阶段的流水线。Chained HotStuff的v1、v2、v3视图作为v1中cmd1的准备、预提交和提交基本HotStuff阶段。该命令在v4结束时提交。视图v2、v3、v4作为在v2中提出的cmd2的三个基本HotStuff阶段，并在v5结束时提交。在这些阶段中生成的其他建议以类似的方式继续管道，并由虚线框表示。在图1中，一个箭头表示节点b的b.parent字段，一个双箭头表示b.justify.node。
因此，在Chained HotStuff中只有两种类型的消息，新视图消息和通用阶段通用消息。在所有逻辑流水线阶段的通用QC函数。接下来，我们将解释管道中负责锁定和提交的机制，这只发生在Basic HotStuff的提交和决定阶段。
虚拟节点。某个视图viewNumber中leader使用的genericQC可能不会直接引用前一个视图(viewNumber−1)的proposal，原因可能是前一个视图leader无法获取到一个QC，可能是提议冲突，也可能是良性崩溃。为了简化树结构，createLeaf将带有空节点的genericQC .node扩展到提议视图的高度(节点分支上父链接的数量)，因此视图号与节点高度相等。因此，嵌入在节点b中的QC可能不指向它的父节点，也就是说，b.justify.node可能不等于b.parent(图2中的最后一个节点)。
单链、二链、三链。当节点b∗携带一个指向直接父节点的QC时，即b∗.justify.node= b∗.parent，我们说它形成了单链。表示为b"= b∗. justification.node。节点b*形成一个二链，如果在形成一个一链的同时，b".justify.node.parent = b''。如果b"形成一个二链，它就形成一个三链。
看看链b=b'.justify.node，b'=b".justify.node，b"=b∗.justify.node，血统差距可能发生在任何一个节点。这些情况类似于Basic HotStuff的领导者没有完成三个阶段中的任何一个，被nextView打断到下一个视图。


如果b*形成一条链，则b''的准备阶段已经成功。因此，当副本投票给b*时，它应该记住genericQC←b*.justify。我们注意到，更新genericQC是安全的，即使One-Chain不是直接的，只要它高于当前的genericQC。在第6节中描述的实现代码中，我们确实在本例中更新了genericQC。
如果b*形成了一个Two-Chain，则b'的预提交阶段成功。因此副本应该更新lockedQC←b".justify。同样，我们注意到，即使双链不是直接的，锁也可以更新——安全性不会被打破——事实上，这在第6节的实现代码中给出了。
最后，如果b*形成一个Three-Chain，则b的提交阶段成功，b成为一个提交决策。
算法3显示了Chained HotStuff的伪代码。[50]给出的安全性证明与Basic HotStuff给出的类似。我们要求有效节点中的QC指向它的祖先。为了简单起见，我们假定约束始终有效，并省略代码中的检入。

实现

HotStuff是一个用于构建高效SMR系统的实用协议。由于其简单性，我们可以很容易地将算法3转换为事件驱动风格的规范，它几乎就像原型实现的代码框架。
如算法4所示，通过将活体机制提取到一个名为Pacemaker的模块中，进一步简化和一般化了代码。而不是下一个leader总是在通用阶段结束后等待一个通用qc开始它的统治，这个逻辑被委托给起跑者。一个稳定的领导者可以跳过这一步，简化多个高度的建议。此外，我们放宽了维护最高的genericQC和lockedQC的直接父级约束，同时仍然保持有效节点中的QC总是引用其祖先的要求。正确性的证明类似于Chained HotStuff，我们也把它放到[50]的附录中。
数据结构。每个副本u跟踪以下主要状态变量:
它还保持一个常量b0，所有正确的副本都知道相同的起源节点。对于bootstrap，b0包含一个硬编码的QC, block,bexec,bleaf都初始化为b0, qchigh包含b0的QC。
Pacemaker。Pacemaker是保证GST后进程的一种机制。它通过两个因素来实现这一点。
第一个是“同步”，将所有正确的副本和一个独特的领导者，在足够长的时间内带入一个共同的高度。文献[15,20,25]中常用的同步机制是，副本增加它们在较大高度花费的∆的数量，直到取得进展。确定选举leader的一种常见方法是使用轮换leader方案，其中所有正确的副本保持预定义的leader时间表，并在leader降级时轮换到下一个leader。
其次，Pacemaker需要为领导者提供一种选择方案的方法，该方案将得到正确副本的支持。如算法5所示，在一次视图变更后，在onreceivenwview中，新的leader通过onNextSyncView收集副本发送的new-view消息，发现最高的QC来满足onReceiveProposal中第二部分的生存条件(算法4第18行)。但在同一视图中，在位leader会将新节点链到自己上次提出的叶子的末端，此时不需要new-view消息。基于某些特定于应用程序的启发式(例如，等待之前提议的节点获得一个QC)，当前的leader调用onBeat来提议一个携带要执行的命令的新节点。
值得注意的是，即使一个坏的Pacemaker任意调用onproposal，或者任意选择一个父端和一个QC，并且针对任何调度延迟，安全总是得到保证的。因此，算法4单独保证的安全性被算法5的任何潜在实例化完全与活性解耦。


两阶段HotStuff变体。为了进一步展示HotStuff框架的灵活性，算法6展示了HotStuff的两阶段变体。只有更新过程会受到影响，到达提交决定时需要TwoChain，而One-Chain决定锁。如上所述(第4.4节)，这种两阶段变体失去了乐观响应性，与Tendermint/Casper类似。这样做的好处是阶段更少，而活性可以通过在起搏器中加入基于最大网络延迟的等待来解决。
评估。由于篇幅限制，我们将评估结果推迟到较长的纸张[50]。在那里，我们将我们的实现与BFT-SMaRt[13]进行比较，bft是一种基于两阶段PBFT变体的最先进的实现。我们表明，即使三阶段HotStuff有一个额外的阶段用于响应，并普遍使用数字签名(其中BFT-SMaRt只使用mac进行投票)，它仍然获得了类似的延迟，同时能够在吞吐量上超过BFT-SMaRt。它的扩展性也比BFT-SMaRt好。

致谢

我们感谢Mathieu Baudet, Avery Ching, George Danezis, François Garillot, Zekun Li, Ben Maurer, Kartik Nayak, Dmitri Perelman和Ling Ren，对HotStuff进行了许多深入的讨论，并在该手稿的ArXiv上发布的之前版本中揭露了一个微妙的错误。