HotStuff算法详解 _HotStuff算法

背景
状态机复制 (State machine Replication, SMR)是人们为了解决分布式系统同步问题提出的一种理论框架。为了让一个系统拥有较强的容错能力，人们通常会部署多个完全相同的副本节点，任意一个节点的崩溃都不会影响整个系统的正常工作。在工程上，这些副本节点通常使用状态机复制理论进行同步。
状态机复制的核心思想是在所有副本上面运行一套相同的状态机，只要所有副本都有相同的初始状态，并且对于初始状态赋予相同的一组操作，那么所有副本的最终状态一定是相同的。
如何确定这一组操作的顺序，就需要系统中所有未出错的节点，对于某一个待提交操作序列达成共识，这就类似于著名的拜占庭将军问题中，军官们面临的困境。在拜占庭问题的诸多解决方案中，都会保证个节点中，只要有个未出错的副本，这些未出错的副本就可以不受其他出错（甚至恶意）的副本影响而达成共识。
HotStuff是尹茂帆等人提出的分布性一致性协议，在该算法中，最多出错节点个数为。该算法有两个优点，第一个优点是，相比于之前的算法，HotStuff是基于leader节点的，拥有线性复杂度，可以极大地降低节点出错时，系统的共识消耗。同时，更替leader的低复杂度，鼓励网络频繁更迭leader节点，对于区块链等领域非常有用。第二个优点是该模型隔离了安全性与活跃性，安全性通过节点投票保证，而活跃性则通过 Pacemaker 保证。
学习HotStuff除了阅读本文，还可以阅读原论文《HotStuff : BFT Consensus in the Lens of Blockchain》，或是原论文的中文翻译。Facebook的Libra数字货币也使用的该算法的变种 LibraBFT 。
算法原论文提出了HotStuff的三种实现形式，分别为简易的HotStuff算法(Basic HotStuff)，链状HotStuff算法(Chained HotStuff)和事件驱动的HotStuff算法(Event-driven HotStuff) 。工程上，人们通常使用Event-driven HotStuff算法，但是如果直接去阅读Event-driven HotStuff算法的源代码会不知所云。
Event-driven HotStuff算法之所以比较难以理解，是因为它——

使用了Basic HotStuff算法的共识逻辑，特别的，包括leader如何与replica交互形成共识；
运用了Chained HotStuff提出的流水线优化思想，特别的，如何使用流水线并行优化原算法中相似的阶段；
最后Event-driven HotStuff是Chained HotStuff事件驱动形式，特别的，将原始实现中轮询产生的驱动改为由leader节点发出的事件驱动。

一方面，从论文的结构上来看，先介绍了前两者，最后才在Implementation章节介绍了Event-driven HotStuff 。但另一方面，Event-driven HotStuff又是三者中代码最简单的，也是三者中唯一一个可以在网上找到大量源码进行对照的实现。因此直接上手阅读源码，在遇到困难时再去查阅简单版本的实现也是一个很好地做法（事实上论文作者也推荐直接阅读Event-driven HotStuff）。
简单HotStuff算法如果本节下面的内容理解上有困难可以参考原文对应章节。
视图状态机复制中单次状态转移在HotStuff中以视图(View)的形式出现，leader节点收集网络中其他节点的信息，发送提案并取得共识的整个过程可以看做是一个视图，视图实际上可以类比于状态机的一次转移，其中包含了这次转移需要执行的用户命令。而整个分布式系统，正是通过一次又一次的视图变换(View-Change)，得以逐轮推进运作。
分支直观地看，HotStuff中，每一个副本节点都会在自己的内存中维护一个待提交指令的树状结构。每个树叶子节点都包含了一个待提交的指令，树节点到根节点组成了一个分支。未提交的分支之间互相是竞争关系，一轮中只会有一个分支被节点所共识。
系统中存在一个唯一的leader被其他所有节点所公认，这个leader会尝试将包含“待执行指令”的提议附加到一个已经被个副本投票支持的分支。并尝试就新的分支与其他副本达成共识，共识成功后，整个系统所有节点都会提交并执行这些新的附加操作指令。
【值得注意的是HotStuff并不关心leader的选取过程，因此在后续算法中，我们需要默认leader已经由其他模块指定。】
仲裁证书HotStuff中的投票使用密码学中的仲裁证书(Quorum Certificate, QC)，每一个视图都会关联一个仲裁证书，仲裁证书表明该视图是否获得了足够多副本的认可。仲裁证书本质是副本节点通过自己的私钥签名的一种凭证。
如果一个副本节点认同某一个分支，它会使用自己的私钥对该分支签名，创建一个部分证书发送给leader 。leader收集到个部分证书，可以合成一个仲裁证书，一个拥有仲裁证书的视图意味着获得了多数节点的投票支持。