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

这是《HotStuff:BFT Consensus in the Lens of Blockchain》论文翻译的第四篇,包含了论文的Basic HotStuff章节。


4. 简化HotStuff协议

HotSuff解决了状态复制机(SMR)问题,在SMR的核心问题,是如何设计一个协议,引导客户端发来的指令自然执行。状态复制机的副本们按照统一的顺序执行请求。一个客户端向所有副本发送一个请求,并等待其中的f+1个副本的回执。在大多数情况下,我们在讨论中省略了客户端这个角色,在有关请求的编号和重复数据消除的问题上,遵循行业标准做法。

HotStuff solves the State Machine Replication (SMR) problem. At the core of SMR is a protocol for deciding on a growing log of command requests by clients. A group of state-machine replicas apply commands in sequence order consistently. A client sends a command request to all replicas, and waits for responses from (f + 1) of them. For the most part, we omit the client from the discussion, and defer to the standard literature for issues regarding numbering and de-duplication of client requests.

算法2给出了简易版HotStuff的解决方案。这个协议在一系列编号单调递增的视图(view)中工作,每一个编号的视图都有唯一的leader节点被其他副本所公认。所有节点都在其内存中储存一个待执行指令树。所有的树节点包括一个客户端提议的指令(command)、协议的关联元数据(metadata)和一个父节点链接。节点的分支路径被定义为从该节点出发,沿着父节点链接走到根节点的整条路径。在协议过程中,单调增长的分支被提交(commited),为了提交分支,leader节点需要提议一个能够获得n-f个副本投票支持的分支,而投票分为三个步骤,准备阶段prepare, 预提交阶段pre-commit,提交阶段commit。

【由于这里介绍的是一个简化版模型,Basic HotStuff里面不存在leader节点的选取细节,leader节点可以看做在运行之初被公认了,后面的文章会提到,leader的选取由一个独立的pacemaker算法实现。同时,视图可以理解为账本变动的最小单位,相同视图中账本内容完全相同,而记账则体现在视图的变化。】

The Basic HotStuff solution is presented in Algorithm 2. The protocol works in a succession of views numbered with monotonically increasing view numbers. Each viewNumber has a unique dedicated leader known to all. Each replica stores a tree of pending commands as its local data structure. Each tree node contains a proposed command (or a batch of them), metadata associated with the protocol, and a parent link. The branch led by a given node is the path from the node all the way to the tree root by visiting parent links. During the protocol, a monotonically growing branch becomes committed. To become committed, the leader of a particular view proposing the branch must collect votes from a quorum of (n - f) replicas in three phases, prepare, pre-commit, and commit.

协议的核心部分是leader节点发起的n-f个副本的投票,这个投票的结果被称为仲裁证书(quorum certificate, QC)。仲裁证书被关联到一个特定的树节点以及视图编号。tcombine函数可以将n-f个被签名的投票合并成一个可进行合法性验证的仲裁证书。

A key ingredient in the protocol is a collection of (n - f) votes over a leader proposal, referred to as a quorum certificate (or “QC” in short). The QC is associated with a particular node and a view number. The tcombine utility employs a threshold signature scheme to generate a representation of (n - f) signed votes as a single authenticator.

下面将首先描述Basic HotStuff协议的各阶段执行逻辑,紧接着是基于伪代码(算法2)更精细的描述。最后用对Basic HotStuff的安全性、活跃性、复杂度分析结束本节。

Below we give an operational description of the protocol logic by phases, followed by a precise specification in Algorithm 2, and conclude the section with safety, liveness, and complexity arguments.

4.1 阶段

准备(prepare)阶段 一个新leader节点的协议过程起始于从n-f个副本中收集NewView消息。副本在进入新的viewNumber时(包括最开始的那个视图),会发送一个NewView消息给leader节点,并且在消息中捎带该副本当前的prepareQC值(如果不存在则发送\perp)。

leader节点选择一个prepareQC最高的分支,这个值被定义为highQC。因为highQCn-f个副本中的最高值,所以没有更高的视图可以做提交决定,因此highQC对应的副本作为leader节点对于该分支来说是最安全的。

收集NewView消息之后,如何选择一个安全的分支这个部分会被当前leader节点忽略,在这里我们简单地选择最高prepareQC作为highQC,为了简便起见,我们将此优化推迟到第6节。在本节中我们仅描述一个单一leader节点的协议。请注意,与类似PBFT的协议不同,我们现在这个单一leader节点协议中,上述步骤是直接跳过的,并强制与协议的其他阶段一样产生相同的线性开销。

leader使用createLeaf方法用一个新的提案扩展highQC.node的尾部。该方法创建一个新的叶节点作为子节点,并在子节点中嵌入父节点的摘要。然后,leader节点使用一个prepare类型消息将新节点发送到所有其他副本。该消息同时包含了highQC以支持后续的安全性验证。

从leader接收到当前视图的prepare类型消息后,副本r使用safeNode谓词函数判断是否接受它。如果被接受,复制品会将带有部分签名(由tsign(r)生成)的prepare类型投票发送给leader节点。

prepare phase. The protocol for a new leader starts by collecting new-view messages from (n - f) replicas. The new-view message is sent by a replica as it transitions into viewNumber (including the first view) and carries the highest prepareQC that the replica received (⊥ if none), as described below.

The leader processes these messages in order to select a branch that has the highest preceding view in which a prepareQC was formed. The leader selects the prepareQCwith the highest view, denoted highQC, among the new-view messages. Because highQC is the highest among (n - f) replicas, no higher view could have reached a commit decision. The branch led by highQC.node is therefore safe.

Collecting new-view messages to select a safe branch may be omitted by an incumbent leader, who may simply select its own highest prepareQC as highQC. We defer this optimization to Section 6 and only describe a single, unified leader protocol in this section. Note that, different from PBFT-like protocols, including this step in the leader protocol is straightforward, and it incurs the same, linear overhead as all the other phases of the protocol, regardless of the situation.

The leader uses the createLeaf method to extend the tail of highQC.node with a new proposal. The method creates a new leaf node as a child and embeds a digest of the parent in the child node. The leader then sends the new node in a prepare message to all other replicas. The proposal carries highQC for safety justification.

Upon receiving the prepare message for the current view from the leader, replica r uses the safeNode predicate to determine whether to accept it. If it is accepted, the replica sends a prepare vote with a partial signature (produced by tsign_r ) for the proposal to the leader.

安全节点(safeNode)谓词函数 safeNode谓词是协议的核心组成部分。它检查带有仲裁证明域(QC)m.justify的消息m,并确定m.node是否可以安全接受。一方面,如果m.node分支是从当前lockedQC.node分支扩展而来,则可以安全的接受提案。另一方面,由活跃性规则保证,如果m.justify的视图高于当前lockedQC,则副本将接受m。只要两个规则中的任何一个成立,谓词函数就返回真。

【我的理解是,safety rule指的是leader在lockedQC.node后面加了一个command节点,对于副本来说,接受这个节点毫无坏处,甚至可以和leader保持同步。liveness rule指的是,当前副本发现自己锁定的副本以及过时了,leader的提案节点的父节点都已经是获得n-f个投票的QC了,自己永远卡在一个奇怪的古老状态毫无意义,所以说也会无条件支持leader。safeNode谓词函数为false意味着副本和leader在lockedQC上有冲突,且位于同一个视图,这个时候,副本不给leader投票】

safeNode predicate. The safeNode predicate is a core ingredient of the protocol. It examines a proposal message m carrying a QC justification m.justify, and determines whether m.node is safe to accept. The safety rule to accept a proposal is the branch of m.node extends from the currently locked node lockedQC.node. On the other hand, the liveness rule is the replica will accept m if m.justify has a higher view than the current lockedQC. The predicate is true as long as either one of two rules holds.

预提交(pre-commit)阶段 当leader节点收到n-f个为当前提案curProposal投票时,将他们合并为prepareQC。leader使用pre-commit类型的消息广播prepareQC。一个副本通过pre-commit投票对leader节点做出响应,并对提案进行签名摘要。

pre-commit phase. When the leader receives (n - f) prepare votes for the current proposal curProposal, it combines them into a prepareQC. The leader broadcasts prepareQC in pre-commit messages. A replica responds to the leader with pre-commit vote having a signed digest of the proposal.

提交(commit)阶段 commit阶段类似于pre-commit阶段。当leader接收到n-f个pre-commit投票时,它将它们组合成一个precommitQC,并在commit类型消息中广播它;副本用commit投票来响应它。重要的是,此时通过将副本的lockedQC设置为precommitQC(算法2的第25行),副本将被锁定在precommitQC上。这对于保护提案的安全至关重要,以防提案成为一项协商一致的决定。

commit phase. The commit phase is similar to pre-commit phase. When the leader receives (n-f) pre-commit votes, it combines them into a precommitQC and broadcasts it in commit messages; replicas respond to it with a commit vote. Importantly, a replica becomes locked on the precommitQC at this point by setting its lockedQC to precommitQC (Line 25 of Algorithm 2). This is crucial to guard the safety of the proposal in case it becomes a consensus decision.

决定(decide)阶段 当leader节点收到n-f个commit的选票时,它将它们合并成一个commitQC。一旦leader节点获得了commitQC,它就会以decide消息的形式将其发送给所有其他副本。在接收到DECIDE消息时,副本将commitQC中包含的提案视图视为已提交的决策,并在已提交的分支中执行命令。副本将增加viewNumber并启动下一个视图。

decide phase. When the leader receives (n - f) commit votes, it combines them into a commitQC. Once the leader has assembled a commitQC, it sends it in a decide message to all other replicas. Upon receiving a decide message, a replica considers the proposal embodied in the commitQC a committed decision, and executes the commands in the committed branch. The replica increments viewNumber and starts the next view.

下一个视图(nextView)中断 在所有阶段中,副本都会在viewNumber视图处等待由nextView(viewNumber)函数确定的超时时间段。如果nextView(viewNumber)中断等待,副本也会增加viewNumber并开始下一个视图。

nextView interrupt. In all phases, a replica waits for a message at view viewNumber for a timeout period, determined by an auxiliary nextView(viewNumber) utility. If nextView(viewNumber) interrupts waiting, the replica also increments viewNumber and starts the next view.

4.2 数据结构

消息(message) 协议中的消息m由一组固定的字段组成,这些字段使用算法1中所示的Msg()程序填充。m会被自动打上curView标记,即发送者当前的视图编号。每个消息都有一个类型m.type \in \{new view, prepare, pre commit, commit, decide\}m.node包含一个建议的节点(建议分支的叶节点)。有一个可选的字段m.justify。leader节点总是在不同的阶段使用这个域来储存仲裁证书(QC)。副本节点则在新视图消息中使用它来携带最高的prepareQC。以副本角色发送的每个消息都包含部分签名m.partialSig,该值是通过将三元组\langle m.type, m.viewNumber, m.node \rangle通过voteMsg()函数签名获得的。

Messages. A message m in the protocol has a fixed set of fields that are populated using the Msg() utility shown in Algorithm 1. m is automatically stamped with curView, the sender’s current view number. Each message has a type m.type ∈ {new-view, prepare, pre-commit, commit, decide}. m.node contains a proposed node (the leaf node of a proposed branch). There is an optional field m.justify. The leader always uses this field to carry the QC for the different phases. Replicas use it in new-view messages to carry the highest prepareQC. Each message sent in a replica role contains a partial signature m.partialSig by the sender over the tuple hm.type, m.viewNumber, m.nodei, which is added in the voteMsg() utility.

仲裁证书(Quorum certificates) 一个仲裁证书是建立在三元组\langle type, viewNumber, node \rangle之上的,并且组合了该三元组在n-f个副本上的签名。给定一个仲裁证书 qc,我们使用qc.type, qc.viewNumber, qc.node来指示原三元组中的项。

Quorum certificates. A Quorum Certificate (QC) over a tuple \langle type, viewNumber, node \rangle is a data type that combines a collection of signatures for the same tuple signed by (n-f) replicas. Given a QC qc, we use qc.type, qc.viewNumber, qc.node

树(Tree)和分枝(Branches) 每个命令都包装在一个节点中,该节点还包含一个父链接,该父链接可以是父节点的哈希摘要。我们在伪代码中省略了实现细节。在协议期间,副本仅在节点所对应的分支已在其本地树中之后才传递消息。实际上,落后的副本可以通过从其他副本中获取丢失的节点数据来赶上。为简洁起见,伪代码中也省略了这些细节。如果两个分支都不是另一个分支的扩展,那么这两个分支就是冲突的。如果两个节点所对应的分支冲突,则两个节点冲突。

Tree and branches. Each command is wrapped in a node that additionally contains a parent link which could be a hash digest of the parent node. We omit the implementation details from the pseudocode. During the protocol, a replica delivers a message only after the branch led by the node is already in its local tree. In practice, a recipient who falls behind can catch up by fetching missing nodes from other replicas. For brevity, these details are also omitted from the pseudocode. Two branches are conflicting if neither one is an extension of the other. Two nodes are conflicting if the branches led by them are conflicting.

记账变量 副本使用额外的局部变量来记录协议状态:
i) viewNumber,最初为1,通过完成决策或nextView中断实现递增;
ii) lockedQC,最初为⊥,存储副本投票提交的最高QC;
iii) prepareQC,最初为⊥,存储副本投票预提交的QC。
此外,为了增量地执行一个提交的命令日志,副本维护其分支已被执行的最高节点。为了简洁起见,下面省略这一点。

Bookkeeping variables. A replica uses additional local variables for bookkeeping the protocol state: (i) a viewNumber, initially 1 and incremented either by finishing a decision or by a nextView interrupt; (ii) a locked quorum certificate lockedQC, initially ⊥, storing the highest QC for which a replica voted commit; and (iii) a prepareQC, initially ⊥, storing the highest QC for which a replica voted pre-commit. Additionally, in order to incrementally execute a committed log of commands, the replica maintains the highest node whose branch has been executed. This is omitted below for brevity.

4.3 协议规范

算法2中给出的协议被描述为逐视图循环迭代。在每轮视图中,副本根据扮演的其角色(描述为一系列as块)连续执行阶段(注意,副本可以具有多个角色,例如,leader也是一个normal副本)。不同角色的as块的执行可以并行化。每个as块的执行本身则是原子的。nextView中断中止任何as块中的所有操作,并跳到Finally块。

The protocol given in Algorithm 2 is described as an iterated view-by-view loop. In each view, a replica performs phases in succession based on its role, described as a succession of “as” blocks. A replica can have more than one role. For example, a leader is also a (normal) replica. Execution of as blocks across roles can be proceeded concurrently. The execution of each as block is atomic. A nextView interrupt aborts all operations in any as block, and jumps to the “Finally” block.

4.4 安全性、活跃性以及复杂度

安全性(Safety). 我们定义仲裁证书 qc是合法的当且仅当tverify(\langle qc.type, qc.viewNumber, qc.node \rangle, qc.sig)为真。

Safety. We first define a quorum certificate qc to be valid if tverify(\langle qc.type, qc.viewNumber, qc.node \rangle, qc.sig) is true.

引理1. 对于任意合法的qc_1, qc_2,如果有qc_1.type = qc_2.typeqc_1.nodeqc_2.node 冲突,那么我们有qc_1.viewNumber \neq qc_2.viewNumber

Lemma 1. For any valid qc_1, qc_2 in which qc_1.type = qc_2.type and qc_1.node conflicts with qc_2.node, we have qc_1.viewNumber \neq qc_2.viewNumber.

证明. 反证法,假设qc_1.viewNumber = qc_2.viewNumber = v,由于一个合法的仲裁证书只能够通过n - f = 2f + 1个副本投票(部分签名)生成。因此,一定有一个正常工作的副本对v投票了两次,伪代码里面并不允许这个情况出现。

Proof. To show a contradiction, suppose qc_1.viewNumber = qc_2.viewNumber = v. Because a valid QC can be formed only with n - f = 2f + 1 votes (i.e., partial signatures) for it, there must be a correct replica who voted twice in the same phase of v. This is impossible because the pseudocode allows voting only once for each phase in each view.

定理2 如果wb是冲突的节点,那么他们不能够同时被一个正确的副本所提交(commit)。

Theorem 2. If w and b are conflicting nodes, then they cannot be both committed, each by a correct replica.

证明 我们也会用反证法证明这个重要的结论。 令qc_1表示一个合法的commitQC(即q_1.type = commit),此时q_1.node = w,同时qc_2是另一个合法的commitQC,满足q_2.node = b。令v_1 = qc_1.viewNumberv2=qc_2.viewNumber。由引理1我们知道,v_1 \neq v_2,不失一般性,可以假设v_1 < v_2

现在,我们假设v_s是比v_1高的prepareQC里面的最小的仲裁证书。qc_s.type=prepare, qc_s.viewNumber = v_sqc_s.nodew冲突,那么我们可以定义下面的谓词逻辑:

E(prepareQC):=(v_1 < prepareQC.viewNumber \leq v_2 ) \wedge (prepareQC.node\ conflicts \quad with\quad w).

我们现在可以按照下列形式定义出qc_sqc_s可以看做是“冲突”的起始位置:

qc_s := argmin_{prepareQC} \{prepareQC.viewNumber | prepareQC\quad is\quad valid \wedge E(prepareQC)\} .

注意,基于之前的假设,这样的qc_s必须存在;例如,在最坏情况,qc_s可以是在视图v_2中形成的prepareQC。

一个正确的副本,会发送部分签名的结果tsign_r(\langle qc_1.type, qc_1.viewNumber, qc_1.node \rangle)给leader节点,令r成为对于tsign_r(\langle qc_s.type, qc_s.viewNumber, qc_s.node\rangle)有贡献的第一个副本;这样的r必须存在,否则,qc_1.sigqc_s.sig其中一个就不能创建。在视图v_1期间,副本r在算法2的第25行使用precommitQC更新它的lockedQC,对应树节点w。由于v_s的最小化定义,副本r上曾经在w处生成的lockedQC在qc_s形成之前不会改变。否则r一定看到了其他一些低视图的prepareQC,因为第17行在第25行之前,与最小值相矛盾。现在考虑副本r在视图v_s的准备阶段调用safeNode,其中消息m包含m.node=qc_s.node。假设m.nodelockedQC.node冲突,因此算法1第26行的判断为false。此外,m.justify.viewNumber>v_1将违反v_s的最小值的假设,因此算法1第27行中的判断也是false的。因此,safeNode必须返回false,而r不能针对v_s的观点进行prepare投票,发现矛盾,证毕。

Proof. We prove this important theorem by contradiction. Let qc_1 denote a valid commitQC (i.e., qc_1.type = commit) such that qc_1.node = w, and qc_2 denote a valid commitQC such that qc_2.node = b. Denote v_1 = qc_1.viewNumber and v_2 = qc_2.viewNumber. By Lemma 1, v_1 \neq v_2 . W.l.o.g. assume v_1 < v_2 .

We will now denote by v_s the lowest view higher than v_1 for which there is a valid prepareQC, qc_s (i.e., qc_s.type = prepare) where qc_s.viewNumber = v_s , and qc_s.node conflicts with w. Formally, we define the following predicate for any prepareQC:

E(prepareQC):=(v_1 < prepareQC.viewNumber \leq v_2 ) \wedge (prepareQC.node\ conflicts\ with\ w).

We can now set the first switching point qc_s :

qc_s := argmin_{prepareQC} \{prepareQC.viewNumber | prepareQC\ is\ valid \wedge E(prepareQC)\} .

Note that, by assumption such a qc_s must exist; for example, qc_s could be the prepareQC formed in view v_2 .

Of the correct replicas that sent a partial result tsign_r(\langle qc_1.type, qc_1.viewNumber, qc_1.node \rangle), let r be the first that contributed tsign_r(\langle qc_1.type, qc_1.viewNumber, qc_1.node \rangle); such an r must exist since otherwise, one of qc_1.sig and qc_s.sig could not have been created. During view v_1 , replica r updates its lock lockedQC to a precommitQC on w at Line 25 of Algorithm 2. Due to the minimality of v_s , the lock that replica r has on the branch led by w is not changed before qc_s is formed. Otherwise r must have seen some other prepareQC with lower view because Line 17 comes before Line 25, contradicting to the minimality. Now consider the invocation of safeNode in the prepare phase of view v_s by replica r, with a message m carrying m.node = qc_s.node. By assumption, m.node conflicts with lockedQC.node, and so the disjunct at Line 26 of Algorithm 1 is false. Moreover, m.justify.viewNumber > v_1 would violate the minimality of v_s , and so the disjunct in Line 27 of Algorithm 1 is also false. Thus, safeNode must return false and r cannot cast a prepare vote on the conflicting branch in view v_s , a contradiction.

活跃性(Liveness). 前面的叙述中,缺少了两个函数,leader和nextView。他们的定义与协议的安全性无关,但和协议的活跃性有关。在给出候选定义之前,我们首先定义GST之后,存在一个有界的持续时间T_f,满足如果所有副本在T_f期间仍然在视图v中,且视图v的leader节点正常运行,那么决定(decision)可以到达。之后的叙述中,我们定义qc_1qc_2匹配(match)当且仅当qc_1qc_2是合法的,且qc_1.node = qc_2.node,且qc_1.viewNumber = qc_2.viewNumber

Liveness. There are two functions left undefined in the previous section: leader and nextView. Their definition will not affect safety of the protocol, though they do matter to liveness. Before giving candidate definitions for them, we first show that after GST, there is a bounded duration T_f such that if all correct replicas remain in view v during T_f and the leader for view v is correct, then a decision is reached. Below, we say that qc_1 and qc_2 match if qc_1 and qc_2 are valid, qc_1.node = qc_2.node, and qc_1.viewNumber = qc_2.viewNumber.

引理3 如果一个正常运行的副本已经锁定了,且锁定在了lockedQC = precommitQC,那么至少f+1个副本投票了与lockedQC匹配的prepareQC

Lemma 3. If a correct replica is locked such that lockedQC = precommitQC, then at least f+1 correct replicas voted for some prepareQC matching lockedQC.

证明 如果一些副本r锁定了precommitQC,那么prepareQC在prepare阶段一定获得了(n-f)个投票(算法2的第10行),其中至少f+1个是正常运行的副本。

Proof. Suppose replica r is locked on precommitQC. Then, (n - f) votes were cast for the matching prepareQC in the prepare phase (Line 10 of Algorithm 2), out of which at least f + 1 were from correct replicas.

定理4 在GST之后,存在一个时间界限T_f,满足如果所有副本在T_f期间仍然在视图v中,且视图v的leader节点是正确的,那么决定(decision)可以在T_f结束时到达。

Theorem 4. After GST, there exists a bounded time period T_f such that if all correct replicas remain in view v during T_f and the leader for viewv is correct, then a decision is reached.

证明 从一个新的视图开始,leader节点收集(n-f)个newView消息,并计算出他们的highQC,最后广播prepare消息。假设在所有副本中(包括leader本身),最高的锁定QC是lockedQC = precommitQC^*,通过引理, 我们知道了,至少有f+1个正确的副本曾经向一个匹配precommitQCprepareQC投票,并且该值已经被附在NewView消息中,传送给leader节点。在这些New-View消息中,至少有一个会被leader接受,并赋值到highQC中。基于假设条件,所有正确的副本在该视图中处于同步状态(synchronized),且leader节点是无缺陷的。因此,所有正确的副本都会在prepare阶段投票,由于在函数safeNode里面,算法1第27行的条件被满足了(即使节点的消息和副本的lockedQC.node冲突,即26行条件不满足)。然后,在leader为这个视图聚合出有效的prepareQC之后,所有副本将在接下来的所有阶段进行投票,从而产生一个新的决策。在GST之后,这些阶段完成的持续时间T_f是有界的。

Proof. Starting in a new view, the leader collects (n - f) new-view messages and calculates its highQC before broadcasting a prepare messsage. Suppose among all replicas (including the leader itself), the highest kept lock is lockedQC = precommitQC^∗ . By Lemma 3, we know there are at least f+1 correct replicas that voted for a prepareQC^∗ matching precommitQC^∗ , and have already sent them to the leader in their new-view messages. Thus, the leader must learn a matching prepareQC^∗ in at least one of these new-view messages and use it as highQC in its prepare message. By the assumption, all correct replicas are synchronized in their view and the leader is nonfaulty. Therefore, all correct replicas will vote in the prepare phase, since in safeNode, the condition on Line 27 of Algorithm 1 is satisfied (even if the node in the message conflicts with a replica’s stale lockedQC.node, and so Line 26 is not). Then, after the leader assembles a valid prepareQC for this view, all replicas will vote in all the following phases, leading to a new decision. After GST, the duration T_f for these phases to complete is of bounded length.

协议是乐观响应性的,因为没有严格的“等待\Delta时间”的步骤,并且使用三步骤的逻辑,让我们可以通过safeNode的判断覆盖过时的锁。

The protocol is Optimistically Responsive because there is no explicit “wait-for-∆” step, and the logical disjunction in safeNode is used to override a stale lock with the help of the three-phase paradigm.

我们现在为leader和nextView提供简单的构造,以确保GST之后,最终将到达一个视图,在该视图中leader节点是正确的,并且所有正确的副本将在此视图中保留T_f的时间。对于leader来说,一个特定的从视图号到副本的映射就已经足够了,最终leader的选择在所有副本之间进行旋转。nextView的一个可能的解决方案是利用一种exponential back-off机制来保持超时时间间隔。然后在进入每个视图时设置一个计时器。当计时器在没有做出任何决定的情况下结束,副本将间隔加倍,并调用nextView来推进视图。由于每次间隔都是原来的两倍,所有正确副本的等待间隔最终都会有至少T_f的共同重叠,在此期间,leader可以驱动决策。

We now provide simple constructions for leader and nextView that suffice to ensure that after GST, eventually a view will be reached in which the leader is correct and all correct replicas remain in this view for T_f time. It suffices for leader to return some deterministic mapping from view number to a replica, eventually rotating through all replicas. A possible solution for nextView is to utilize an exponential back-off mechanism that maintains a timeout interval. Then a timer is set upon entering each view. When the timer goes off without making any decision, the replica doubles the interval and calls nextView to advance the view. Since the interval is doubled at each time, the waiting intervals of all correct replicas will eventually have at least T_f overlap in common, during which the leader could drive a decision.

HotStuff两阶段变种的活跃性 现在,我们将展示一个“两阶段”HotStuff的无限非决定性场景。这解释了在Casper和Tendermint中引入同步延迟的必要性,并因此放弃(乐观的)响应。

在HotStuff的两阶段变种中,我们删除pre-commit阶段,直接到commit阶段。一个副本在投票prepareQC的时候即锁定。假设在视图v,一个leader发起提议b。当完成prepare阶段时,一些副本r_v向prepareQC投票,得到qc,满足qc.node=b。因此r_v都会锁定qc,一个异步的网络调度使得其余的副本在没有接收qc的情况下直接进入下一个视图v+1

现在,我们重复无穷多次这个单视图脚本。最开始,我们在视图v+1中,副本r_v持有系统中最高的prepareQC(如qc)。新的leaderl从除了r_v之外的2f+1个副本中收集了NewView消息。在这些节点中最高的prepareQCqc',对应了视图v-1b'=qc'.node,与b矛盾。l进一步提议基于b'的提案b'',对于这个来说,2f个诚实的副本提供了投票。但是副本r_v拒绝了这个提案,因为他已经被锁定在了qc上面。b''b是冲突的,qc'qc要低,最终,2f个副本放弃向下一个视图的转换。就在这个时候,一个崩溃的副本回应了l的提议,l合并了一个prepareQC(v+1, b''),并且一个副本r_{v+1}表示会投票给这个提议,并且锁定了他。

Livelessness with two-phases. We now briefly demonstrate an infinite non-deciding scenario for a “two-phase” HotStuff. This explains the necessity for introducing a synchronous delay in Casper and Tendermint, and hence for abandoning (Optimistic) Responsiveness.

In the two-phase HotStuff variant, we omit the pre-commit phase and proceed directly to commit. A replica becomes locked when it votes on a prepareQC. Suppose, in view v, a leader proposes b. It completes the prepare phase, and some replica r_v votes for the prepareQC, say qc, such that qc.node = b. Hence, r_v becomes locked on qc. An asynchronous network scheduling causes the rest of the replicas to move to view v + 1 without receiving qc.

We now repeat ad infinitum the following single-view transcript. We start view v + 1 with only r_v holding the highest prepareQC (i.e. qc) in the system. The new leader l collects new-view messages from 2f + 1 replicas excluding r_v . The highest prepareQC among these, qc' , has view v-1 and b' = qc'.node conflicts with b. l then proposes b'' which extends b' , to which 2f honest replicas respond with a vote, but r_v rejects it because it is locked on qc, b'' conflicts with b and qc' is lower than qc. Eventaully, 2f replicas give up and move to the next view. Just then, a faulty replica responds to l’s proposal, l then puts together a prepareQC(v+1, b'') and one replica, say r_{v+1} votes for it and becomes locked on it.

复杂度 在HotStuff的每个阶段,只有leader向所有副本广播,而副本则用部分签名向发送者回复一次以完成投票。在leader的消息中,仲裁证书由先前收集到的(n-f)张选票组成,这些选票可以通过一个阈值签名进行编码。在副本的响应中,来自该副本的部分签名是唯一的身份验证程序。因此,在每个阶段中,总共接收到O(n)个验证器(authenticators)。由于有固定数量的阶段,每个视图的总体复杂性为O(n)

Complexity. In each phase of HotStuff, only the leader broadcasts to all replicas while the replicas respond to the sender once with a partial signature to certify the vote. In the leader’s message, the QC consists of a proof of (n-f) votes collected previously, which can be encoded by a single threshold signature. In a replica’s response, the partial signature from that replica is the only authenticator. Therefore, in each phase, there are O(n) authenticators received in total. As there is a constant number of phases, the overall complexity per view is O(n).

发表评论

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

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