【共识专栏】HotStuff 共识

——  前言 ——

我们已经了解到分布式系统一般通过状态复制机[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.