【论文翻译】HotStuff:BFT Consensus in the Lens of Blockchain – Chained HotStuff

5. Chained HotStuff

上一节讲到的Basic HotStuff里面,leader想要提交一个提案,需要三个步骤。这些步骤除了从副本处收集投票之外,并没有做其他什么有意义的工作,因此从形式上来看非常相似。在Chained HotStuff里面,我们一方面优化了Basic HotStuff的功能,同时对其进行了简化。核心思想是将改变视图的步骤放在prepare阶段完成,每一个提案都会有自己对应的视图。这样做会简化消息的种类个数,并且允许决策的并行化。相似的消息种类简化的思路在Casper算法的文章里也有所提及。

It takes three phases for a Basic HotStuff leader to commit a proposal. These phases are not doing “useful” work except collecting votes from replicas, and they are all very similar. In Chained HotStuff, we improve the Basic HotStuff protocol utility while at the same time considerably simplifying it. The idea is to change the view on every prepare phase, so each proposal has its own view. This reduces the number of message types and allows for pipelining of decisions. A similar approach for message type reduction was suggested in Casper [1].

更具体地说,在Chained HotStuff协议中,prepare阶段的投票由leader收集到一个视图中,储存在状态变量genericQC里。接下来,genericQC被转发给下一个视图的leader,实质上是将下一阶段的职责(这曾经由pre-commit阶段负责的)委托给下一个leader节点。然而,下一位leader实际上并不单独进行pre-commit阶段,而是启动一个新的prepare阶段,添加自己的提议。视图v+1的prepare阶段同时充当视图v的pre-commit阶段。视图v+2的prepare阶段同时充当视图v+1的pre-commit阶段和视图v的commit阶段。这中流水线化的思路是完全可行的,因为Basic HotStuff的所有的阶段都有相同的结构。

More specifically, in Chained HotStuff the votes over a prepare phase are collected in a view by the leader into a genericQC. Then the genericQC is relayed to the leader of the next view, essentially delegating responsibility for the next phase, which would have been pre-commit, to the next leader. However, the next leader does not actually carry a pre-commit phase, but instead initiates a new prepare phase and adds its own proposal. This prepare phase for view v + 1 simultaneously serves as the pre-commit phase for view v. The prepare phase for view v + 2 simultaneously serves as the pre-commit phase for view v + 1 and as the commit phase for view v. This is possible because all the phases have identical structure.

图1描绘了将Basic HotStuff协议的各个阶段流水线化,最终得到Chained HotStuff协议的示例。在Chained HotStuff协议里,视图v_1v_2v_3对于cmd 1来说充当了Basic HotStuff中的prepare, pre-commit, commit阶段。该命令将在v_4结束时提交。视图v_2v_3v_4作为v_2中提议的cmd 2的三个Basic Hotstuff阶段,并在v_5结束时提交。在这些阶段生成的其他提议以类似的方式继续流水线化,用虚线框表示。在图1中,单箭头表示节点bb.parent字段,双箭头表示b.justify.node

The pipeline of Basic HotStuff protocol phases embedded in a chain of Chained HotStuff proposals is depicted in Figure 1. Views v_1 , v_2 , v_3 of Chained HotStuff serve as the prepare, pre-commit, and commit Basic HotStuff phases for cmd 1 proposed in v_1 . This command becomes committed by the end of v_4 . Views v_2 , v_3 , v_4 serve as the three Basic HotStuff phases for cmd 2 proposed in v_2 , and it becomes committed by the end of v_5 . Additional proposals generated in these phases continue the pipeline similarly, and are denoted by dashed boxes. In Figure 1, a single arrow denotes the b.parent field for a node b, and a double arrow denotes b.justify.node.

图1 Chained HotStuff是Basic HotStuff的流水线版本,QC可以同时处于多个阶段。

基于上述的结构,事实上Chained HotStuff只有两种类别的消息—— NewView和GenericPhase消息。一个通用的QC函数在所有的流水线阶段运行。接下来,我们将解释流水线的机制,重点关注锁定lock与提交commit操作,他们对应了Basic HotStuff的commit和decide阶段。

Hence, there are only two types of messages in Chained HotStuff, a new-view message and generic-phase generic message. The generic QC functions in all logically pipelined phases. We next explain the mechanisms in the pipeline to take care of locking and committing, which occur only in the commit and decide phases of Basic HotStuff.

虚拟节点 在某些视图viewNumber中,leader使用的genericQC不能直接引用前一个视图的提议(viewNumber-1)。原因是之前视图的leader未能获得QC,要么是因为有冲突的提议,要么是因为节点的崩溃。为了简化树结构,createLeaf将genericQC.node扩展为空白节点,直到提议视图的高度(节点分支上父链接的数量),因此视图编号与节点高度相等。这样就会导致,嵌入在节点b中的仲裁证书QC不能正确引用其父节点,即b.justify.node不能等于b.parent(图2中的最后一个节点)。

Dummy nodes. The genericQC used by a leader in some view viewNumber may not directly reference the proposal of the preceding view (viewNumber −1). The reason is that the leader of a preceding view fails to obtain a QC, either because there are conflicting proposals, or due to a benign crash. To simplify the tree structure, createLeaf extends genericQC.node with blank nodes up to the height (the number of parent links on a node’s branch) of the proposing view, so view-numbers are equated with node heights. As a result, the QC embedded in a node b may not refer to its parent, i.e., b.justify.node may not equal b.parent (the last node in Figure 2).

图2 节点v4,v5,v6组成了Three-Chain,节点v8没有成为一个合法的One-Chain。

一链(One-Chain),二链(Two-Chain)和三链(Three-Chain) 当节点b^*带有和父节点相同的QC时,即b^∗.justify.node = b^∗.parent,我们说它形成了一个One-Chain。 令b''=b^∗.justify.node,如果除了形成单链外,还满足b''.justify.node = b''.parent,那么节点b^∗形成Two-Chain。 如果b''已经是Two-Chain了,那么b^*将形成Three-Chain。

One-Chain, Two-Chain, and Three-Chain. When a node b^∗ carries a QC that refers to a direct parent, i.e., b^∗ .justify.node = b^∗ .parent, we say that it forms a One-Chain. Denote by b'' = b^∗ .justify.node. Node b^∗ forms a Two-Chain, if in addition to forming a One-Chain, b''.justify.node = b''.parent. It forms a Three-Chain, if b'' forms a Two-Chain.

查看链b = b'.justify.node, b'= b''.justify.node, b'' = b^∗ .justify.node,祖先空缺可能发生在任何一个 节点。 这些情况类似于Basic HotStuff的leader未能完成三个阶段中的任何一个阶段,并被nextView中断到下一个视图。

Looking at chain b = b'.justify.node, b'= b''.justify.node, b'' = b^∗ .justify.node, ancestry gaps might occur at any one of the nodes. These situations are similar to a leader of Basic HotStuff failing to complete any one of three phases, and getting interrupted to the next view by nextView.

如果b^*形成One-Chain,则b''的prepare阶段是成功的。 因此,当副本对b^∗投票时,它应该记录了genericQC \leftarrow b^∗.justify。 我们需要注意,即使One-Chain不是直接的,只要它高于当前的genericQC,也可以安全地更新genericQC。 在第6节中描述的实现代码中,在这种情况下,我们确实更新了genericQC

If b^∗ forms a One-Chain, the prepare phase of b'' has succeeded. Hence, when a replica votes for b^∗ , it should remember genericQC \leftarrow b^∗.justify. We remark that it is safe to update genericQC even when a One-Chain is not direct, so long as it is higher than the current genericQC. In the implementation code described in Section 6, we indeed update genericQC in this case.

如果b^*形成两链,则b'的pre-commit阶段成功。 因此,副本应更新lockedQC \leftarrow b''.justify。 再次注意,即使Two-Chain不是直接的,也可以更新该锁(安全不会中断),而实际上,这在第6节的实现代码中已给出。

If b^* forms a Two-Chain, then the pre-commit phase of b 0 has succeeded. The replica should therefore update lockedQC \leftarrow b''.justify. Again, we remark that the lock can be updated even when a Two-Chain is not direct—safety will not break—and indeed, this is given in the implementation code in Section 6.

最后,如果b^*形成Three-Chain,则b的commit阶段成功,并且b成为已提交的决策。

Finally, if b ∗ forms a Three-Chain, the commit phase of b has succeeded, and b becomes a committed decision.

算法3显示了Chain HotStuff的伪代码。 附录A中定理5给出的安全性证明与Basic HotStuff的证明相似。 我们要求在有效节点中的仲裁证书(QC)引用其祖先。 为简便起见,我们假设约束始终成立,并且省略了代码中的检查。

Algorithm 3 shows the pseudocode for Chained HotStuff. The proof of safety given by Theorem 5 in Appendix A is similar to the one for Basic HotStuff. We require the QC in a valid node refers to its ancestor. For brevity, we assume the constraint always holds and omit checking in the code.

算法3 Chained HotStuff协议

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据