团队开发的一条公链共识算法基于 HotStuff，由于旧版实现是三阶段（无 Decide），在高 tps 情况下频繁出现状态分叉，因此需要优化为四阶段的 Chained HotStuff 版本。在撰写技术方案过程中总结了一些个人理解和实现方案。

异步状态下没有人能保证只有一个 leader，共识算法要做的就是，即使异常情况下出现多个 leader，仍然能保证状态的正确性

1. 基础知识：Basic HotStuff 介绍

要理解 Chained HotStuff 方案，需要先对 Basic HotStuff 有所了解。

四阶段提交

Basic HotStuff 为四阶段，其中 NewView 阶段是 Decide 阶段中 replica 收到 commitQC 后或者共识期间出现异常（Timeout）时主动触发的。

NewView 阶段：切换视图，且选出新 Leader，（如果不用切换 leader 可跳过这个阶段，因为旧 Leader 保留了最新的视图状态 ，不需要 Replica 同步），并且保证新 leader 打包的新提案不和大多数节点状态冲突，同时解决部分还未执行 Decide 的状态不一致问题。具体来说，Replica 需要将自己的 prepareQC 和 lockedQC 状态、下一个视图的 curView 号发送给新 leader，新 leader 打包出新的提案，并使用新的 curView 号发布提案。

Prepare 阶段：leader 广播提案供 Replica 校验是否冲突，Leader 收集 > 2/3 的同意 Vote后，生成 prepareQC。

Precommit 阶段： Leader 广播 prepareQC 给 Replica，Replica 设置 prepareQC，拥有 prepareQC 代表承认此提案无冲突，并返回投票，Leader有足够票数后生成 precommitQC。

Commit 阶段：Leader 广播 precommitQC 给 Replica，Replica 设置 lockedQC，拥有 precommitQC(lockedQC) 代表此提案可以随时执行，并返回投票，Leader 有足够的票数后生成 commitQC。设置了 lockedQC 的节点表示最终确认了这个提案，lockedQC 用于和新提案检测是否冲突。

Decide 阶段：Leader 广播 commitQC 给 Replica，拥有 commitQC 表示提案已经执行完毕， Decide 阶段 Replica 收到 Decide 消息或者超时都会发送 NewView 消息选出新 leader。

祭出论文。

基本数据结构

QC: 当 leader 发送给 replica 的某个消息收到 2/3+1 投票时，即认为这个消息产生了一个群体证明（Quorum Certificate）。

视图节点（视图块）：Basic HotStuff 的视图类似于每个要共识的交易块（Block）,当一个新 leader 选出并开始共识该块时，视图变更，或者当某个阶段超时进入视图切换状态时，视图也会发生变更。视图号是单调递增的，且每次都只加 1。

struct ViewBlock {
    int cur_view,
    ViewBlock* parent,
    []Cmd cmds,
    QC prepareQC,
    QC lockedQC,
    QC commitQC,
}
struct QC {
    int view_number,
    Type type,  // prepareQC, lockedQC, commitQC
    Sign sign,
}

视图树：视图节点通过 parent 连接起来，组成一颗视图树，如下图，视图树中不同的节点根据视图号以及是否有 prepareQC, lockedQC, commitQC，分成四种状态。

每个 replica 本地维护视图树，视图树类似于区块链，处于 committed 状态的视图节点（紫色），即为成功出块，视图树可能会分叉，但理论上 committed 状态的节点不会分叉（所有 replica 一致）。

从论文中得知，视图树可以用来检测新的提案是否有冲突。

需要满足以下任意一个条件，replica 就可以给新提案投票：

1. 新提案必须在本地的 lockedQC 的分支上(Safety Rule)
2. 新提案的 qc.view_number > lockedQC.view_number(Liveness Rule)

在下文 Chained HotStuff 方案中会具体介绍这两个条件的作用，以及 Safety 和 Liveness 概念。

2. Chained HotStuff 方案

与 Basic HotStuff 不同，Chained HotStuff 不光是实现了多阶段并行出块，在具体实现上也抽象除了一套具体规则，在对一个提案进行状态确认时，去掉了多个阶段的概念，换之以统计 QC 的数量。

局部变量

每个节点都各自维护三个重要的局部变量，包括

• highQC：目前已知最高的 QC，所谓最高指的是 QC.view_number
• Block: 视图块（视图节点），包含上一个块的群体证明 QC、当前视图号 curView 和打包的交易等
• View：当前视图号，等于 highQC.view_number + 1，只要生成新的 HighQC，View 就会变更。由于 View 永远是 highQC.view_number + 1，可以不用存储。

三个变量互相依赖，关系如下。

Propose & Vote 消息

Basic hotstuff 是一种基本实现，明确阐述了不同的阶段，以及不同阶段产生的 QC，除了第一阶段（Prepare 阶段）会打包新的提案进行验证之外，后续阶段实际上都是使用 2/3+1 的 QC 更换新的 QC，过程十分相似，因此可以进一步抽象两种消息。

• Propose 消息：生成新 QC，leader 打包消息广播给 replica 进行验证并同步新 QC
• Vote 消息：replica 验证后投票给新的 leader，新 leader 收到 2/3+1 投票即可产生新的 QC。Vote 消息同时也是 NewView 消息，将 replica 当前最新的 QC 同步给新的 leader

超时异常时，会有

• Timeout 消息：当 replica 超时时，会广播 Timeout 消息给所有 replicas，新 leader 收到相同 View 的 2/3+1 的 Timeout 消息后，会重新 Propose

下图是每一次 Propose & Vote 的详细流程。

相比 Basic Hotstuff，这样抽象的好处是：

• 每一次 Propose 都可以打包交易，提案一个新的区块，相当于实现 Basic HotStuff 中的多阶段并行
• 没有阶段的概念，每一次 Propose & Vote 都可以更换一个 leader，提高安全性
• 代码实现难度简化

整个共识流程如下。

如上图，Basic HotStuff 中的四个阶段变成了四次 Propose & Vote 步骤，每一步都会产生一个 QC，同步这个 QC，并增加视图，另外每一步也都会重新打包交易，而不是只有 Prepare 阶段打包交易。

数据结构

视图块结构

注：后面画图的时候省略哈希指针，一般情况下都和 QC 指针一致

struct ViewBlock { // 视图块（或视图节点）
    Hash hash, // 本 view_block hash 值
    Hash parent_hash, // 父节点 hash 值
    Block* block, // 打包的 Block，包含交易
    QC* qc, // 打包的某个块的 QC, 通常是上一个视图块的 QC
    View view, // 视图号, HighQC 决定
}

注意：Block 的视图号是 HighQC 决定的，而不是打包的 QC，Leader 可以打包任意自己有的 QC。

在这种结构下，视图树就变成了这样。

视图树本质，是一个更细化的区块链，每一个块是对 HotStuff 中具体阶段的一次共识（而不只是对 CommittedBlock 的共识）。而我们常规说的区块链就是其中已经提交的紫色的块（不分叉），而最新的尚未 commit 的块（非紫色块）还是有多种可能的（分叉）。

视图块状态

所有的 Proposal 都有 QC，这个 QC 表示该视图块的父节点块收到了群体证明。因此不再有 prepareQC，lockedQC，commitQC，只有一个 QC，视图节点也就只有 Proposal，locked，committed 状态，而判断具体处于什么阶段就变成了一个数 QC 的游戏。如下图

当某个节点后面有连续两个 qc，且哈希值指针也是连续的状态（如 2 ← 3 ← 4），该节点状态为 locked，当出现第三个 qc 指向 4 时（哈希指针不需要连续），2 提交为 committed 状态。

Propose 验证规则

新提案的验证使用论文中 SafeNode 的两个条件（满足任意一个即可），两个条件分别保证了安全性和活性。

Safety：共识的正确性，比如不会出现状态不一致等。

Liveness: 活性，保证无论在什么情况下，系统不会卡住，能够持续产生共识。

HotStuff 将 Safety 和 Liveness 解耦，Safety 由 HotStuff 协议本身实现，Liveness 由业务实现。SafeNode 函数是 Safety 和 Liveness 唯一耦合的地方。

1. node extends from lockedQC.node新的视图块需要和最新的 lockedQC 在同一分支。正常情况下 HotStuff 协议都能保证新的提案在 lockedQC 的分枝上，可以保证 Safety。
2. qc.viewNumber > lockedQC.viewNumber新提案的 qc.view_number > lockedQC.view_number(Liveness Rule)。具体情况见下面「完整演绎一个过程」小节。

此外我们也增加了其他验证规则，

1. Block.View() == Block.QC().View() + 1保证 leader 不能随意设置 Block.View。
2. 校验 leader 是否符合选举规则。leader.ID == LeaderRotation.GetLeader(c.CommittedBlock.Height())

Propose 打包规则

原则上，一个 leader 可以打包任何 QC，任何 View，这部分的安全性由 Replica 验证规则保证，但是考虑到共识效率，我们需要尽量减少多分叉之间的竞争，因此制定打包规则如下：

• 优先打包自己最高 QC，即 highQC。
• 如果有两个相同的 QC，比如 4 和 4'，则优先打包后者，即 qc >= highQC 时更新 highQC

正常情况下 leader 只会打包上一个块对应的 QC，但有些时候会打包以前的 QC，用户恢复系统活性。

比如有一种情况是。

此时，Leader 打包了一个旧的 QC3，但是 block.View() 源于 HighQC()。

这种情况有可能造成恶意节点强行回滚之前的块。因此我们额外屏蔽了这种情况。对 Block.View() 进行约束，保证 Block.View() == Block.QC().View() + 1

视图切换

视图切换就是根据目前的 HighQC.View 变更自己的 CurView。

视图切换过程：

1.每一次 Propose & Vote 都要进行一次视图切换，Vote 消息同时也是 NewView 消息，会触发新 leader 的视图切换。

2.视图切换时，leader 根据目前已知的 HighQC，更新 view_number = highQC.View + 1，leader 收集到 2/3+1 NewView 后，更新 HighQC 和 view_number，基于 highQC 创建一个新的 QC 再 Propose 给 replicas。

视图切换基本原理：连续两个阶段中，一定有一个诚实节点同时参与了两个阶段的投票。

上图中，生成一个 qc 时需要 2f+1 节点，那么其中诚实节点数量最少为 f + 1，在 NewView 阶段如果成功选出新 leader，需要另一个 2f + 1，其中诚实节点数量为 f + 1，则两个阶段拥有的诚实节点数量一共为 2f + 2，这就意味着一定至少有一个诚实节点，同时参与两次投票过程。所以新 leader 从 2f + 1 的 qc 中，选择最新的 qc 的话，这个 qc 一定就是真实的最新的 qc。新 leader 即可恢复上一次共识的最新状态。

Chained HotStuff 中，qc 不必区分 lockedQC, prepareQC, commitQC，新 leader 要的是最新的 qc，论文中发送 prepareQC 是因为论文中默认从 prepare 阶段开始恢复，即使有更新的 lockedQC 和 commitQC，也会被覆盖。但如果想从任意一个阶段开始恢复，只需要发送最新的 qc 即可。

完整共识流程

下图具体描述了共识时局部变量的变化。

过程描述：

从创世块开始，GenesisBlock 即 Block0，View = 1，手动创建创世块的 QC，QC = 0。然后开始共识循环。

1.从 Propose 开始。Propose 会打包 Block1，同步给 replicas，此时 Block1 如下。

Block1 = ViewBlock {
    QC: QC0,
    View: 1,
    ...
}

2.replica 同步 Block1 后保存 Block1(replica 中包含新 leader)，更新 HighQC，并且进行视图切换，将 View 改变为 HighQC + 1 = 1，投票给新 leader。

3.新 leader 收到 2/3+1 的投票后，生成针对 Block1 的 QC1，然后再次进行视图切换（防止刚才切没有收到消息），将 View

更新为 HighQC + 1 = 2，之后打包提案 Block2，如下

Block1 = ViewBlock {
    QC: QC1,
    View: 2,
    ...
}

以此类推进行共识。

超时恢复

当发生超时，超时的 replica 需要将本节点的 highQC（View 由 highQC 决定）广播给其他 replica，其他 replica 如果发现收到更高的 highQC，则会进行视图切换，更新到更高的 QC，当新 leader 收到超过 2/3 replica 的超时信息（必须是同一个 View），则重新打包一个包含 HighQC 的视图节点，发起 Propose。举两个例子。

情况一：1/2 节点率先超时。剩余节点下一视图超时

这种情况也可以看出来，当发生超时时不广播 HighQC 而只发送给 leader 是不行的，因为两部分 replica 的 highQC 不一致，导致 View 不一致。永远无法在同一个 View 上凑够 2/3+1 的 TimeoutMsg。

情况二：2/3+1 超时

一个例子：新分叉赶超过程

下述过程呈现了一个新的分叉是如何赶超并最终替换老的分叉的。

所有节点初始状态为 Block.View = 4, HighQC.View = 3, View = 4，此时 leader 生成新 QC.View = 4，并提案 Block{View: 5, QC4} 给 Replicas。然而超过 2/3+1 的节点没有收到这次 Propose。

此时 2/3 + 1 节点 TimeoutMsg 给新 leader，发送当前的 HighQC = 3。新 leader 重新打包 Block = {View: 4', QC3} 并广播，收到消息后所有节点的视图树状态如下图。

新 Leader 选择

必须保证所有 replica 的新 leader 的一致性。

每一组 Propose & Vote 之后都会轮换 leader，leader 的轮换规则如下

leader = random(latest_commitQC.view_number + now_timestamp / 30s) % leaders_num

使用 replica 当前最新 commitQC.view_number(或 committedBlock.height)随机一个 leader，为了防止新 leader 不作为而导致的情况，额外增加一个 30s 周期的随机性。之所以要用 commitQC 是因为 commitQC 不会分叉，能够保证所有节点状态一致。当然某些节点最新的 commitedQC 可能由于延迟还没有同步过来，从而导致无法选出 leader，因此依赖块同步逻辑，块同步是个周期性的同步逻辑，会定期检测并从邻居节点同步 committedBlock。

黑名单

每个 replica 维护一个 leader 黑名单，当某个节点无法生成一个 QC 时（即对某个阶段的状态复制无法达成共识），replica 将 leader 加入黑名单，黑名单中的阶段无法成为新 leader，而当该节点参与投票了某个 QC 的签名时，replica 将该节点从黑名单删除。

3. 参考资料

Hotstuff 论文.pdf

HotStuff Presentation.pdf

https://github.com/relab/hotstuff

【Westar】Hotstuff 共识算法完全详解及区块链架构_哔哩哔哩_bilibili