Facebook主导的Libra所基于的共识HotStuff是如何工作的？

共识协议 HotStuff 由 VMware Research 等团队于2018年3月提出，其预印版经过五轮迭代修改，并将于并行与分布计算领域著名的国际会议 PODC 2019上正式发表。HotStuff 是一个基于主节点（Leader）的拜占庭容错共识协议。我们可以看到，和很多共识协议一样，其网络被假定为了一个可靠安全的点对点网络，其通信模型采用了部分同步模型。所谓部分同步模型，就是网络中存在一个消息传递延迟的上界，这个上界要么不为网络中的节点所知，要么所有节点知道这个上界，并在某个未知点后遵循这个上界。

这篇文章将简单解读一下 HotStuff 的工作原理。我们将从 PBFT 共识协议出发，分析 HotStuff 是如何一步步改变以达到其目标。

一、从 PBFT 出发

粗略地来说，共识协议的目标是在去中心化的网络中就系统的状态达成统一的认识，以便所有的（诚实）节点统一从一个状态迁移到另一个状态。

正常流程下，PBFT 采用了两轮点对点通信来完成这个目标。

当主节点把其所提议的（合法）状态迁移权要求广播给其它节点后，作为系统中的一个诚实节点，首先它要知道足够多的节点也接收到了这一个状态迁移要求，即它能确认这次状态迁移要求是有效的。在此基础上，它要知道足够多的节点也确认了该状态迁移是有效的，以此确认这次状态迁移是全局的。

当协议运行过程中主节点发生故障，例如节点发现无法和主节点进行通信等，这时候需要更换主节点，即切换视图。此时，系统中的节点会广播视图切换请求，当某个节点收到足够多的视图切换请求后会发送视图切换确认给新的主节点。当新的主节点收到足够多的视图切换确认后开始下一视图。

二、HotStuff 基础协议介绍

我们认为 HotStuff 做出的第一个改变，也是最重要的一个改变，就是将 PBFT 的网状通信网络拓扑变成了星形通信网络拓扑，即它每次通信都依靠主节点。节点不再通过 p2p 网络将消息广播给其它节点，而是将消息发送给主节点，由主节点处理后发送给其它节点。得益于星型通信网络拓扑，系统的通信复杂度得到了大大降低。和 PBFT 中类似地，主节点会提议进行状态迁移，其它节点收到该状态迁移要求后，会检查其合法性。

图：网状通信网络拓扑向星形通信网络拓扑转变

我们觉得 HotStuff 做出的第二个重要改变是将视图切换流程和正常流程进行合并，即不再有单独的视图切换流程，降低了视图切换的复杂度。可以看到，在 HotStuff 中切换视图时，系统中的某个节点也无需再确认“足够多的节点希望进行视图切换”这一消息后再通知新的主节点，它直接切换到新视图并通知新的主节点。HotStuff 把确认“足够多的节点希望进行视图切换”这一消息的行为放进了正常流程中。这一做法比较新颖，但必然会给正常流程引入新的确认阶段。因此，HotStuff 把 PBFT 的两阶段确认扩展成了三阶段确认。

在了解了这两个改变后，我们可以简单描述一下 HotStuff 的流程。HotStuff 以 prepare 阶段作为协议的开始阶段。在这一阶段中，当主节点收集到足够的节点发来新视图请求后，它开始新视图并提出自己的状态迁移要求，发送 prepare 消息给其它节点。系统中的其它节点在接收到 prepare 消息后，验证其合法性并进行如下三阶段确认：

1. pre-commit 阶段：其它节点对 prepare 消息进行投票。在收到足够多的投票后，主节点向所有节点广播 pre-commit 消息，向它节点表明足够多的节点确认了此次状态迁移的要求。

2. commit 阶段：其它节点对 pre-commit 消息进行投票。在收到足够多的投票后，主节点向所有节点广播 commit 消息。此时，收到 commit 消息的节点可以锁定当前状态迁移要求以便即使视图切换也可以顺利达成共识。

3. decide 阶段：其它节点对 commit 消息进行投票。在收到足够多的投票后，主节点向所有节点广播 decide 消息。当某个节点收到 decide 消息后将执行状态迁移，并开始新的视图。

图：Basic HotStuff 的流程

为了进一步减少通信量，HotStuff 做出了第三个改变，即和一些共识协议一样，引入了一个新的密码学原语：门限签名。

简单介绍一下这个密码学原语。

对于一个(k, n)-门限签名方案，假定存在一个公钥，而 n 个签名者每人都拥有自己的私钥（分片）。只要其中至少 k 个签名者对消息进行部分签名，那么由这 k 个部分签名可以导出对消息的完整签名，并且这个完整签名可以由公钥来验签。

一般情况下，完整签名的大小和签名者的个数无关。HotStuff 用门限签名来减少共识协议中签名的个数。本体对于门限签名方案做了大量的研究，在和区块链的结合上，已经有了很多的想法和实践，会在以后的技术视点中逐步展现。

我们可以看到，在 HotStuff 的三阶段确认中，所谓投票，就是其它节点即对某个消息进行门限签名并发送给主节点。当主节点收到足够多的投票时会导出完整签名。主节点向其它节点广播下一阶段消息时将附上这个签名，供其它节点将验证。

图：(3,5)-门限签名

三、HotStuff 的流水化处理

可以看到，上述 HotStuff 基础协议的这三个确认阶段采取了类似的行为：其它节点对某一消息进行投票，主节点合成投票意见并通知给其它节点。这些过程可以统一表示，并采用流水化来处理。这是 HotStuff 做出的第四个改变：共识过程的流水化处理。

图：流水化 HotStuff（来源于原论文）

流水化的 HotStuff 是在基础版 HotStuff 上进行了变化扩展，即每个 prepare 阶段都会切换视图。其实我们可以看到，这本质上就是让下一个视图的 prepare 阶段为当前视图的 prepare 阶段进行确认，即下一个 prepare 阶段（隐含地）包含了对当前视图的 pre-commit 确认，并以此类推。HotStuff 基础协议中的三阶段确认拥有相同的结构，因此这种流水化扩展是可以做到的。

四、后记

我们简单介绍了下共识协议 HotStuff 的原理。从通信复杂度而言，这几大改变带给了 Hotstuff 实质性的变化。同时，这也让HotStuff有了一些新的属性，例如文中提到的 Optimistic Responsiveness。从应用上看，不仅 Libra 采用了该共识协议，还有其它项目也采用了该协议。

BFT 共识系列在很多区块链项目中得到了应用，比如本体采用可验证随机函数 VRF 和 BFT 结合的 VBFT 共识协议。我们希望这篇简短的介绍能让大家迅速理解 HotStuff 的工作流程，并以此对 LibraBFT、VBFT 等 BFT 系列共识协议能有深入了解。

本期互动题目

本体 VBFT 算法是 BFT 与什么的结合？

上期获奖名单

以下哪个选项是关于链外扩容的正确说法？