5. Chained HotStuff
上一节讲到的Basic HotStuff里面，leader想要提交一个提案，需要三个步骤。这些步骤除了从副本处收集投票之外，并没有做其他什么有意义的工作，因此从形式上来看非常相似。在Chained HotStuff里面，我们一方面优化了Basic HotStuff的功能，同时对其进行了简化。核心思想是将改变视图的步骤放在prepare阶段完成，每一个提案都会有自己对应的视图。这样做会简化消息的种类个数，并且允许决策的并行化。相似的消息种类简化的思路在Casper算法的文章里也有所提及。
It takes three phases for a Basic HotStuﬀ 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 HotStuﬀ, we improve the Basic HotStuﬀ 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 .
更具体地说，在Chained HotStuff协议中，prepare阶段的投票由leader收集到一个视图中，储存在状态变量genericQC里。接下来，genericQC被转发给下一个视图的leader，实质上是将下一阶段的职责（这曾经由pre-commit阶段负责的）委托给下一个leader节点。然而，下一位leader实际上并不单独进行pre-commit阶段，而是启动一个新的prepare阶段，添加自己的提议。视图的prepare阶段同时充当视图的pre-commit阶段。视图的prepare阶段同时充当视图的pre-commit阶段和视图的commit阶段。这中流水线化的思路是完全可行的，因为Basic HotStuff的所有的阶段都有相同的结构。
More speciﬁcally, in Chained HotStuﬀ 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 simultaneously serves as the pre-commit phase for view . The prepare phase for view simultaneously serves as the pre-commit phase for view and as the commit phase for view . This is possible because all the phases have identical structure.
图1描绘了将Basic HotStuff协议的各个阶段流水线化，最终得到Chained HotStuff协议的示例。在Chained HotStuff协议里，视图、、对于cmd 1来说充当了Basic HotStuff中的prepare, pre-commit, commit阶段。该命令将在结束时提交。视图、、作为中提议的cmd 2的三个Basic Hotstuff阶段，并在结束时提交。在这些阶段生成的其他提议以类似的方式继续流水线化，用虚线框表示。在图1中，单箭头表示节点的字段，双箭头表示。
The pipeline of Basic HotStuﬀ protocol phases embedded in a chain of Chained HotStuﬀ proposals is depicted in Figure 1. Views , , of Chained HotStuﬀ serve as the prepare, pre-commit, and commit Basic HotStuﬀ phases for cmd 1 proposed in . This command becomes committed by the end of . Views , , serve as the three Basic HotStuﬀ phases for cmd 2 proposed in , and it becomes committed by the end of . Additional proposals generated in these phases continue the pipeline similarly, and are denoted by dashed boxes. In Figure 1, a single arrow denotes the ﬁeld for a node , and a double arrow denotes .
基于上述的结构，事实上Chained HotStuff只有两种类别的消息—— NewView和GenericPhase消息。一个通用的QC函数在所有的流水线阶段运行。接下来，我们将解释流水线的机制，重点关注锁定lock与提交commit操作，他们对应了Basic HotStuff的commit和decide阶段。
Hence, there are only two types of messages in Chained HotStuﬀ, 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 HotStuﬀ.
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).
一链(One-Chain)，二链(Two-Chain)和三链(Three-Chain) 当节点带有和父节点相同的QC时，即，我们说它形成了一个One-Chain。 令，如果除了形成单链外，还满足，那么节点形成Two-Chain。 如果已经是Two-Chain了，那么将形成Three-Chain。
One-Chain, Two-Chain, and Three-Chain. When a node carries a QC that refers to a direct parent, i.e., , we say that it forms a One-Chain. Denote by . Node forms a Two-Chain, if in addition to forming a One-Chain, . It forms a Three-Chain, if forms a Two-Chain.
查看链, , ，祖先空缺可能发生在任何一个 节点。 这些情况类似于Basic HotStuﬀ的leader未能完成三个阶段中的任何一个阶段，并被nextView中断到下一个视图。
Looking at chain , , , ancestry gaps might occur at any one of the nodes. These situations are similar to a leader of Basic HotStuﬀ failing to complete any one of three phases, and getting interrupted to the next view by nextView.
如果形成One-Chain，则的prepare阶段是成功的。 因此，当副本对投票时，它应该记录了。 我们需要注意，即使One-Chain不是直接的，只要它高于当前的，也可以安全地更新。 在第6节中描述的实现代码中，在这种情况下，我们确实更新了。
If forms a One-Chain, the prepare phase of has succeeded. Hence, when a replica votes for , it should remember . We remark that it is safe to update even when a One-Chain is not direct, so long as it is higher than the current . In the implementation code described in Section 6, we indeed update in this case.
如果形成两链，则的pre-commit阶段成功。 因此，副本应更新。 再次注意，即使Two-Chain不是直接的，也可以更新该锁（安全不会中断），而实际上，这在第6节的实现代码中已给出。
If forms a Two-Chain, then the pre-commit phase of b 0 has succeeded. The replica should therefore update . 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.
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 HotStuﬀ的证明相似。 我们要求在有效节点中的仲裁证书(QC)引用其祖先。 为简便起见，我们假设约束始终成立，并且省略了代码中的检查。
Algorithm 3 shows the pseudocode for Chained HotStuﬀ. The proof of safety given by Theorem 5 in Appendix A is similar to the one for Basic HotStuﬀ. 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.