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

6. 实现

HotStuff是用于构建高效SMR系统的实用协议。 由于其简易性,我们可以轻松地将算法3转换为事件驱动的形式,该形式几乎等同于我们的实现原型。

HotStuff is a practical protocol for building efficient SMR systems. Because of its simplicity, we can easily turn Algorithm 3 into an event-driven-style specification that is almost like the code skeleton for a prototype implementation.

如算法4所示,可以进一步简化代码,方法是将活跃性相关机制简化并泛化成为一个独立的模块,该模块我们称之为pacemaker。一般来说,下一个leader需要在generic阶段末尾等待genericQC,再开始它的“统治”,这些工作都被丢给Pacemaker模块。 稳定的leader可以略过此步骤,并流水线化处理多个不同高度的提案。 此外,在维护最高genericQC和lockedQC的过程中,我们放宽了直接父亲的约束,同时仍然保留了有效节点中的QC始终引用其祖先的要求。 正确性的证明与Chained HotStuff类似,我们也将其推迟到附录中。

As shown in Algorithm 4, the code is further simplified and generalized by extracting the liveness mechanism from the body into a module named Pacemaker. Instead of the next leader always waiting for a genericQC at the end of the generic phase before starting its reign, this logic is delegated to the Pacemaker. A stable leader can skip this step and streamline proposals across multiple heights. Additionally, we relax the direct parent constraint for maintaining the highest genericQC and lockedQC, while still preserving the requirement that the QC in a valid node always refers to its ancestor. The proof of correctness is similar to Chained HotStuff and we also defer it to the appendix of [50].

数据结构 任意的副本u持续追踪下列的核心状态变量:

  • V[\cdot] 将节点映射到投票
  • vheight 最近投票节点的高度
  • b_{lock} 被锁定的节点(和lockedQC相似)
  • b_{exec} 最后执行的节点
  • qc_{high} 由Pacemaker维护的最高的已知QC(与genericQC相似)
  • b_{leaf} 由Pacemaker维护的叶节点

同时维护一个常量 b_0 , 一个系统共享的的创世纪节点,被所有副本所公认,用于系统的启动。b_0 包含了一个通过硬编码指向自身的QC, b_{lock} , b_{exec} , b_{leaf} 都初始化为 b_0 , 且 qc_{high} 包含 b_0的QC .

Data structures. Each replica u keeps track of the following main state variables:

  • V[\cdot] mapping from a node to its votes.
  • vheight height of last voted node.
  • b_{lock} locked node (similar to lockedQC).
  • b_{exec} last executed node.
  • qc_{high} highest known QC (similar to genericQC) kept by a Pacemaker.
  • b_{leaf} leaf node kept by a Pacemaker.

It also keeps a constant b_0 , the same genesis node known by all correct replicas. To bootstrap, b_0 contains a hardcoded QC for itself, b_{lock} , b_{exec} , b_{leaf} are all initialized to b_0 , and qc_{high} contains the QC for b_0 .

起搏器(Pacemaker) Pacemaker是这样一个机制,保证GST之后一定会取得进展,通过下面两种机制保证的。

第一个是“同步”,同步会将所有正确的副本和唯一的leader节点带入一个共同高度的视图,持续足够长的时间。 文献[25、20、15]中通常使用的同步机制是使副本在更大的高度的视图上增加等待Δ的次数,直到取得进展。 常用的选取leader的方法是使用轮换leader方案,其中所有正确的副本都保留一个预先确定的leader时间表,并在转移leader时轮换到时间表中下一个leader。

Pacemaker. A Pacemaker is a mechanism that guarantees progress after GST. It achieves this through two ingredients.

The first one is “synchronization”, bringing all correct replicas, and a unique leader, into a common height for a sufficiently long period. The usual synchronization mechanism in the literature [25, 20, 15] is for replicas to increase the count of ∆’s they spend at larger heights, until progress is being made. A common way to deterministically elect a leader is to use a rotating leader scheme in which all correct replicas keep a predefined leader schedule and rotate to the next one when the leader is demoted.

其次,Pacemaker需要为leader提供一种选择提案的方式,以保证选择的提案将得到正确副本的支持。 如算法5所示,在视图更改后,新领导者在onReceiveNewView中收集副本通过onNextSyncView发送的新视图消息,以发现最高的仲裁证书,以满足onReceiveProposal中第二个条件的要求(算法4的第18行) )。 但是,在同一视图中,现任leader会将新节点链接到自己最后提出的叶的末尾,在此不需要新视图消息。 基于某些特定于应用程序的启发式方法(例如,等到先前提出的节点获得QC之后),当前领导者调用onBeat提出一个新节点,该节点携带要执行的命令。

Second, a Pacemaker needs to provide the leader with a way to choose a proposal that will be supported by correct replicas. As shown in Algorithm 5, after a view change, in onReceiveNewView, the new leader collects new-view messages sent by replicas through onNextSyncView to discover the highest QC to satisfy the second part of the condition in onReceiveProposal for liveness (Line 18 of Algorithm 4). During the same view, however, the incumbent leader will chain the new node to the end of the leaf last proposed by itself, where no new-view message is needed. Based on some application-specific heuristics (to wait until the previously proposed node gets a QC, for example), the current leader invokes onBeat to propose a new node carrying the command to be executed.

值得注意的是,即使不良的Pacemaker任意调用onPropose或任意选择父级和QC,并且在任何计划延迟的情况下,也始终可以确保安全性。 因此,仅通过算法4保证的安全性就可以与算法5的任何可能活跃性实现完全脱钩。

It is worth noting that even if a bad Pacemaker invokes onPropose arbitrarily, or selects a parent and a QC capriciously, and against any scheduling delays, safety is always guaranteed. Therefore, safety guaranteed by Algorithm 4 alone is entirely decoupled from liveness by any potential instantiation of Algorithm 5.

两阶段HotStuff变型 为了进一步说明HotStuff框架的灵活性,算法6显示了HotStuff的两阶段变体。 仅执行更新过程,需要Two-Chain才能做出提交决定,而One-Chain确定锁定。 如上所述(第4.4节),此两阶段变型失去了乐观响应能力,类似于Tendermint / Casper。 好处是更少的阶段,而活跃性可以通过在Pacemaker中加入基于最大网络延迟的等待来解决。 参见第7.3节进一步讨论。

Two-phase HotStuff variant. To further demonstrate the flexibility of the HotStuff framework, Algorithm 6 shows the two-phase variant of HotStuff. Only the update procedure is affected, a Two-Chain is required for reaching a commit decision, and a One-Chain determines the lock. As discussed above (Section 4.4), this two-phase variant loses Optimistic Responsiveness, and is similar to Tendermint/Casper. The benefit is fewer phases, while liveness may be addressed by incorporating in Pacemaker a wait based on maximum network delay. See Section 7.3 for further discussion.

发表评论

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

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