HotStuff算法详解( 三 ) _HotStuff算法

文章插图

图1 Chained HotStuff是Basic HotStuff的流水线版本，QC可以同时处于多个阶段。对于节点b，单箭头表示b.parent字段，双箭头表示b.justify.node 。
更具体地说，在Chained HotStuff协议中，prepare阶段的副本的投票由leader节点加以收集，并且储存在状态变量genericQC里。接下来，genericQC被转发给下一个视图的leader，实质上是将下一阶段的职责（这曾经由pre-commit阶段负责的）委托给下一个leader节点。然而，下一位leader实际上并不单独进行pre-commit阶段，而是启动一个新的prepare阶段，添加自己的提议。视图的prepare阶段同时充当视图的pre-commit阶段。视图的prepare阶段同时充当视图的pre-commit阶段和视图
的commit阶段。在实际的实现中，还有一些细节，比如说，当一个leader没有成功获得足够的仲裁证书，那么就可能出现一个节点的justify的视图编号并不连续，如图2所示，这种情况需要通过添加哑结点补齐。

文章插图

图2 v8的父节点没有成功获得仲裁证书
我们按照节点的依次向上访问，可以获得流水线中各个阶段的节点。令,,
。

如果，说明的prepare阶段成功完成，当副本投票给时，还需要执行。需要注意的是，即使，执行上述赋值也是安全的，我们在下一节Event-driven HotStuff中会使用后者。
如果，说明的pre-commit阶段成功完成，需要同步更新。
如果，说明的commit阶段完成，就变成一个已提交的决策。

下面是Chained HotStuff的伪代码，其中略去了很多特殊情况的判断。

文章插图

事件驱动的HotStuff从Chained HotStuff到Event-driven HotStuff也并不困难。最终伪代码涉及了如下的数据结构——

将节点映射到投票
最近投票节点的高度
被锁定的节点（和lockedQC相似）
最后执行的节点
由Pacemaker维护的最高的已知QC（与genericQC相似）
由Pacemaker维护的叶节点

下面两个代码共同组成了一个工程上实现高效的Event-driven HotStuff算法，他们分别描述了安全性相关模块和活跃性相关模块。和Chained HotStuff源码进行对比，不难理解其中各个函数的功能，同时，读者也可以结合网络上公开的实现
进行理解。

文章插图

文章插图

上述的HotStuff是三阶段的，而论文中还介绍了一个两阶段的HotStuff变种算法，其优势是更少的阶段，更快的效率，而劣势则是乐观响应性的损失。

文章插图

附录1. 证明HotStuff安全性证明：如果和是冲突的节点，那么他们不能够同时被某个正确的副本所提交(commit) .
先证明一个特殊情况，假设和的高度相同，上述命题不成立。这其实是很显然的，毕竟副本的提交需要多数节点的投票，而每个副本每个阶段只会投一个提案，不可能出现两个同样深度树节点得票数同时过半的情况。

文章插图

【HotStuff算法详解】w和b高度不同的情况
假设和高度不同，不妨设，，是高度大于且与冲突的，高度最小的那个合法的 prepareQC仲裁证书。即

文章插图

文章插图

和都是合法的commitQC仲裁证书，是一个合法的prepareQC证书。算法29行说明一个commitQC是由个lockedQC组成，而算法13行则说明一个prepareQC需要个副本同时通过safeNode检验。而一个commitQC需要由个lockedQC组成，和一个prepareQC需要的次safeNode检验，一定存在一个公有的，在视图的时候，会设置lockedQC为precommitQC（），当尝试检验safeNode谓词时，就会发现既不满足“extends from”，也不满足“” 。这意味着
甚至根本无法生成，与假设矛盾。反证法的结论就是不可能存在两个冲突的commitQC 。
附录2. 活跃性证明我们首先定义全局稳定时间GST之后，存在一个有界的持续时间，满足如果所有副本在期间仍然在视图中，且视图的leader节点正常运行，那么决定(decision)可以到达。引理如果一个正常运行的副本已经锁定了，且锁定在了，那么至少个副本投票了与匹配的。引理证明如果一些副本锁定了，那么在prepare阶段一定获得了个投票(算法2的第10行)，由于，所以其中至少个是正常运行的副本。活跃性证明从一个新的视图开始，leader节点收集个newView消息，并计算出他们的highQC，最后广播prepare消息。假设在所有副本中（包括leader本身），最高的锁定QC是，通过引理，我们知道了，至少有个正确的副本曾经向一个匹配的投票，并且该值已经被附在NewView消息中，传送给leader节点。在这些New-View消息中，至少有一个会被leader接受，并赋值到highQC中。基于假设条件，所有正确的副本在该视图中处于同步状态(synchronized)，且leader节点是无缺陷的。因此，所有正确的副本都会在prepare阶段投票，由于在函数里面，算法1第27行的条件被满足了（即使节点的消息和副本的冲突，即26行条件不满足）。然后，在leader为这个视图聚合出有效的prepareQC之后，所有副本将在接下来的所有阶段进行投票，从而产生一个新的决策。在GST之后，这些阶段完成的持续时间是有界的。