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

这篇文章将简单解读一下 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 系列共识协议能有深入了解。

Libra和EOS共识算法的微妙区别

根据的白皮书,Libra采用了一个BFT算法的变种LibraBFT作为共识机制,这就很容易联想到同样用了BFT的EOS。

严格来说,EOS的DPoS机制由三个阶段构成。第一阶段,EOS持币者通过公投竞选出21个Block Producer,BP们参与共识。第二阶段,被选出的BP轮流产生区块,产生的区块进入下一个阶段。最后阶段,21个BP之间进行BFT共识,把通过共识的区块标记成不可逆区块。到此为止,区块才算是真正被确认。

EOS可以保持0.5s的出块时间,但实际区块确认时间依赖BFT算法,需要两三分钟左右。

Libre就比较有趣了,它没有EOS特有的DPoS预出快,而是直接执行LibreBFT。有论文(HotStuff: BFT Consensus in the Lens of Blockchain 9)表示,一次BFT共识的延迟只要20-30ms,按照白皮书,2-3个确认就可以标记区块不可逆,如果不考虑交易从mempool到区块的延迟,一笔交易的确认时间只需要90ms,显著低于EOS的两分钟。

天下没有免费的午餐,当时Vitalik怼BM,EOS在算法上没什么突破但性能都比ETH高很多,那EOS到底牺牲了什么?现在都知道EOS是牺牲了安全(去中心化)换便捷,那问题来了,Libre和EOS相比,各自怎么把握这个平衡?