HotStuff算法详解( 二 ) _HotStuff算法

视图的投票总共分为三个步骤，准备阶段prepare, 预提交阶段pre-commit，提交阶段commit 。每一次投票都会合成一个仲裁证书，不同阶段的证书从含义上稍微有些区别，在后续章节的阅读时需要注意。
算法下面是HotStuff的伪代码，其中算法1是重要函数的伪代码，涉及到到消息创建、投票创建、叶节点创建、仲裁证书创建、消息验证、仲裁证书验证、节点安全性判断这些功能。算法2则是HotStuff的运行流程，在每一个阶段，领导节点leader和所有副本replica（包括leader)都会等待特定类型的消息，并进行处理。下面，我会依次讲解每一个阶段究竟做了什么事情。

文章插图

简单HotStuff涉及函数

文章插图

简单HotStuff算法流程
prepare阶段在视图编号增加时，所有节点都会发送New-View类别的消息给leader节点，消息中捎带当前节点的prepareQC值（这里伪代码没写），leader节点在接收到个New-View消息即可以默认已经有足够多的副本等待接收新的提案。
prepareQC是一个仲裁证书，记录了一个最后获得了个节点投票的已提交分支，leader节点从所有New-View消息捎带的仲裁证书中，选择了一个拥有视图编号最大的仲裁证书highQC，基于highQC对应的节点，创建叶节点拓展待提交的指令curProposal，这样对于leader来说是最安全的。
最后leader节点会将curProposal、highQC封装到prepare类型的消息中发送给副本节点，而副本节点对于接收到的prepare类型消息，进行安全性检测safeNode 。
从算法1中，我们可以看到，安全性判定分为两个规则，安全性规则和活跃性规则。安全性规则检测消息对应的节点是否是仲裁证书的直接子节点，如果是的话，说明副本节点的待提交节点和leader的待提交节点都是同步，中间没有任何步骤缺失。活跃性规则则检测自身的lockedQC的视图编号是否小于仲裁证书的的视图编号，如果小于的话，就说明自己被卡在了一个其他节点早已达成共识的视图，因此可以忽略自身的lockedQC，直接尝试与leader重新同步。
pre-commit预提交阶段当leader节点收到个为当前提案curProposal投票时，将他们合并为prepareQC，此时的prepareQC已经获得了这个副本的投票。而对于副本节点，prepareQC则被赋值为prepare阶段中leader节点的highQC，即最近已提交分支。
commit提交阶段commit阶段类似于pre-commit阶段。当leader接收到个pre-commit投票时，它将它们组合成一个precommitQC，并在commit类型消息中广播它；副本用commit投票来响应它。重要的是，此时通过将副本的lockedQC设置为precommitQC（算法2的第25行），副本将被锁定在precommitQC上。这对于保护提案的安全至关重要，以防提案成为一项协商一致的决定。
decide决定阶段当leader节点收到个commit的选票时，它将它们合并成一个commitQC 。一旦leader节点获得了commitQC，它就会以decide消息的形式将其发送给所有其他副本。在接收到decide消息时，副本将commitQC中包含的提案视图视为已提交的决策，并在已提交的分支中执行命令。副本将增加viewNumber并启动下一个视图。
下一个视图(nextView)中断在所有阶段中，副本都会在viewNumber视图处等待由函数确定的超时时间段。如果中断等待，副本也会增加viewNumber并开始下一个视图。
理解正如代码中蓝色部分所强调的，系统的replica在每一阶段都会维护一个量：

prepareQC，表示该仲裁证书曾经获得过一次majority投票
lockedQC，是一个用于保证安全性的中间量
commitQC，是个表示决策已经成了的凭证，不论之后发生什么样的问题（网络延迟、节点崩溃），只要有个正确节点，这个决定都是会被继续尊重

为什么上述算法是安全的，核心就是证明下面的命题：
如果和是冲突的节点，那么他们不能够同时被某个正确的副本所提交(commit) 。
该命题的证明在文末附录1，如果想要搞清楚lockedQC具体的含义，可以尝试阅读一下证明。接着证明上述算法的活跃性，活跃性的核心是证明下面的命题：
我们首先定义全局稳定时间GST之后，存在一个有界的持续时间，满足如果所有副本在期间仍然在视图中，且视图的leader节点正常运行，那么决定(decision)可以到达。
该命题的证明在文末附录2.
链状HotStuff算法如果本节对应的内容理解有难度，可以参考原文对应章节
。在Basic HotStuff中，不难发现每个阶段都是极其同构且独立的，因此可以进行流水线优化。