← COMP5567 全部讲次
L10e · 第 10 周

L10e Chained HotStuff:每个新块顺手推进前面三个块

从零讲 Chained HotStuff:每个新块带上一块的 QC,三轮投票叠成流水线;One-Chain、Two-Chain、Three-Chain 三条规则分别对应存证据、上锁、提交,视图失败时看父子链接而不是视图号。

一句话版

基本 HotStuff 每个块要走三轮投票,Chained HotStuff 让每轮投票同时服务好几个块:新块带着上一块的 QC,这张 QC 既是新块的 Prepare 票,也是更早那些块的下一轮票。稳定运行时,每来一个新块,就有一个更早的块被提交。

这是第 10 讲的最后一页。前面 L10a 讲四个阶段,L10c 讲为什么要三轮,这一页把三轮叠成流水线。

先认识这几个词

词 全称 / 读法 一句人话
Chained HotStuff 链式 HotStuff 把三轮投票叠成流水线的 HotStuff
genericQC 通用 QC 链式版里最新见到的 QC,相当于 prepareQC
One-Chain 一链 一个块有了 QC
Two-Chain 二链 两个块首尾相连、都有 QC,此时上锁
Three-Chain 三链 三个直接父子块都有 QC,此时提交最前面的块
直接父子 direct parent 子块的 QC 恰好指向它的父块
空块 dummy block 视图失败时补的占位块,让高度等于视图号

一个类比:流水线洗车

一辆车要经过冲水、打泡沫、擦干三个工位。老办法是一辆车三个工位走完,下一辆才进场。

流水线洗车让工位同时开工:第一辆在擦干时,第二辆在打泡沫,第三辆刚冲水。每过一个节拍,三辆车各前进一格,出口就开走一辆。

Chained HotStuff 的「节拍」是一个视图。每个视图只做一轮投票,这轮票同时推进链上好几个块。

类比在哪里失效:

  • 洗车的车互相独立,链上的块是父子关系,前一块没 QC,后面的块就推进不了它。
  • 洗车不会有人捣乱,链上可能有视图失败、出不了块,要靠父子链接判断。
  • 洗车的工位固定三个;Chained HotStuff 里一个块到 Decide 要攒够三张连续的 QC。

从零讲起

1. 每个新块带上一块的 QC

它解决什么问题

基本 HotStuff 一个块要 Prepare、Pre-Commit、Commit 三轮投票,每轮的消息格式其实差不多:都是「leader 收票、合成 QC、广播」。既然一样,就让每一轮的票同时给不同的块用。

从哪来(补充)

HotStuff 论文第 5 节(Chained HotStuff)给出这个流水线版本。论文作者 Maofan Yin、Dahlia Malkhi 等,arXiv 第一版 2018 年 3 月提交。

出处:arXiv: HotStuff: BFT Consensus in the Lens of Blockchain

直觉

视图 v 的 leader 提出块 Bv,Bv 里放着上一块的 QC。副本给 Bv 投票,投出的票合成 QCv。

QCv 对 Bv 来说是 Prepare 票。Bv 的父块早一轮有了 QC,现在多了一张,相当于进入下一阶段。再往前一块,又多一张。所以一张新 QC 同时推进三个块。

一步一步看

目标:跟着 B1 走四个视图,看每来一张新 QC,它怎样往前推进一个阶段。

课件练习的设定:n = 4(R1–R4),f = 1,视图 1–4 的 leader 依次是 R1–R4,B1 含交易 X。

  1. 视图 1,R1 提出 B1。B1 还没有任何 QC。

    第 1 步:视图 1,R1 提出 B1(含交易 X),链上只有 B1,B1 处在 Prepare,lockedQC 还没动,已执行为无

  2. 视图 2,B2 带着 QC1。B1 有了第一张证书,进入 Pre-Commit。

    第 2 步:视图 2,B2 带着 QC1,链上有 B1、B2,箭头从子块指回父块,B1 进入 Pre-Commit,lockedQC 还没动

  3. 视图 3,B3 带着 QC2。B1 ← B2 成为 Two-Chain,B1 进入 Commit,lockedQC 指向 B1。

    第 3 步:视图 3,B3 带着 QC2,链上有 B1、B2、B3,B1 进入 Commit,状态栏用青绿标出 lockedQC 指向 B1

  4. 视图 4,B4 带着 QC3。B1 ← B2 ← B3 是直接父子的 Three-Chain,执行 B1。lockedQC 前移到 B2。

    第 4 步:视图 4,B4 带着 QC3,链上有 B1 到 B4,B1 进入 Decide 并被执行,lockedQC 往前挪一格指向 B2,B2、B3 还不执行

  5. 把四个视图摆在一行看,就是一条流水线。

    四个区块 B1 到 B4 依次由视图 1 到 4 的 leader R1 到 R4 提出,B2 带 QC1、B3 带 QC2、B4 带 QC3,下方一行是 B1 从 Prepare 到 Decide 的状态变化

怎么算

看 B1 在第 k 个视图之后有几张 QC:

B1 的阶段 = 它后面接了几张 QC(1 张 Pre-Commit,2 张 Commit,3 张 Decide)

意思是:B1 后面每多一个带 QC 的子孙块,B1 就前进一个阶段。

常见误解

以为每个块还是要单独走三轮投票

链式版每个视图只投一轮票,这轮票合成的 QC 同时推进链上前面的块。

以为 B4 到来时 B1、B2、B3 都被执行

只执行 B1。B2 还差一张 QC,B3 还差两张。

试一下

视图 5 的 B5 带着 QC4 到来,哪个块会被执行?

B2。B2 ← B3 ← B4 成为直接父子的 Three-Chain。

视图 4 结束时,B3 处在哪个阶段?

Pre-Commit。B3 只有 QC3 一张证书。

2. 一链、二链、三链

它解决什么问题

链式版没有阶段名,副本靠数「连起来的 QC 有几张」决定做什么。这一节把三条规则和基本 HotStuff 的三个阶段对上号。

直觉

基本版的顺序是:存证据、上锁、执行。链式版一一对应:

  • 一个块有了 QC(One-Chain),就是存了证据,更新 genericQC。
  • 两个块首尾相连、都有 QC(Two-Chain),就上锁:lockedQC 指向前面那块。
  • 三个块首尾相连、都有 QC,并且是直接父子(Three-Chain),就提交最前面那块。

规则和上一页讲的「为什么三轮」完全一样,只是换成按链长计数。

一步一步看

目标:看副本从新块的 QC 往回数链长,一链、二链、三链各对应基本版的哪一步。

新块 b* 到来时,副本从它的 QC 往回数。

  1. b* 的 QC 指向 b’‘:b’’ 有了 QC,One-Chain,genericQC 更新为它。

  2. b’’ 的 QC 指向 b’:b’ ← b’’ 是 Two-Chain,lockedQC 设为 b’‘.justify,也就是指向 b’。

  3. b’ 的 QC 指向 b:b ← b’ ← b’’ 是 Three-Chain。如果三段都是直接父子,提交 b。

    链 条件 动作 对应基本版
    One-Chain b’’ 有 QC 更新 genericQC 存 prepareQC
    Two-Chain b’ ← b’’ 设 lockedQC 指向 b’ 上锁
    Three-Chain b ← b’ ← b’’,直接父子 提交 b 执行
  4. 「直接父子」的检查:每一段都要满足子块的 QC 恰好指向它的父块,即 b*.justify.node = b*.parent。

怎么判断

拿到一条链,从最新的块往回看:

  • 每一段都问「子块带的 QC 是不是指向它的父块」。是,就算连上了。
  • 连上一段,最新 QC 指向的块是 One-Chain;连上两段,锁住更前面那块;连上三段,提交最前面那块。
  • 中间有一段没连上(QC 指向的块和父块不是同一个),就从断开处重新数。

意思是:判断只看父子链接和 QC 指向,不看视图号是不是连续。

常见误解

以为 Two-Chain 时锁的是最新那块

锁的是 Two-Chain 里前面那块。B1 ← B2 是 Two-Chain 时,lockedQC 指向 B1。

以为三张 QC 连续就能提交,不用管父子关系

要求是直接父子。QC 指向的块和父块对不上时,就算有三张 QC 也不能提交。

试一下

处理 B3(带 QC2)时,lockedQC 指向谁?为什么?

B1。B1 ← B2 成为 Two-Chain,QC2 证明多数已经存了 QC1。

处理 B4 时,lockedQC 从 B1 挪到了哪里?

B2。B2 ← B3 成为新的 Two-Chain。

3. 视图失败时看父子链接

它解决什么问题

leader 崩溃时,那个视图出不了块,链上的视图号会跳。这一节说明为什么跳号不妨碍提交,以及课件练习第 4 问的两种读法。

直觉

终局性看的是 QC 和父子链接,不看视图号连续。视图 2 失败,视图 3 的块直接延伸 B1,只要 B3 带着 B1 的 QC,B1 ← B3 就连上了。

论文另有一种处理:视图失败时补一个空块,让高度永远等于视图号。两种处理下 B1 都能最终提交,提交时机的说法不同。

一步一步看

目标:看视图 2 失败、视图号跳了一格后,B1 为什么仍能提交,又在哪个视图提交。

设定:视图 2 的 R2 崩溃,没出块。按练习的字面模型,B3.parent = B1。

  1. 视图 2 没出块,超时后换到视图 3。

    第 1 步:视图 2 的 R2 崩溃,高度 2 空着,用暗色块表示,链上只有 B1,B1 处在 Prepare

  2. 视图 3,B3 带 QC1,直接延伸 B1。B1 进入 Pre-Commit,视图号跳了一格,父子链接没断。

    第 2 步:视图 3,B3 带 QC1 直接延伸 B1,链上有 B1、B3,B1 进入 Pre-Commit,视图号跳了一格但父子链接没断

  3. 视图 4,B4 带 QC3。B1 ← B3 是 Two-Chain,锁 B1。

    第 3 步:视图 4,B4 带 QC3,链上有 B1、B3、B4,B1 进入 Commit,状态栏用青绿标出 lockedQC 指向 B1

  4. 视图 5,B5 带 QC4。B1 ← B3 ← B4 是直接父子的 Three-Chain,提交 B1,lockedQC 前移到 B3。

    第 4 步:视图 5,B5 带 QC4,链上有 B1、B3、B4、B5,B1 进入 Decide 并被执行,lockedQC 前移指向 B3

  5. 按论文的空块规则:高度 2 放一个空块,B3 的父块是空块。B3 提交时,B1 作为祖先一起执行,因为 Decide 会按顺序执行所有未执行的祖先。

怎么判断

视图失败的题目,按两步答:

  • 先定父子关系:失败视图之后的块延伸谁?题目没说就按字面模型,直接延伸最后一个有 QC 的块。
  • 再按直接父子数链:数到 Three-Chain 的那个视图,就是提交时刻。

如果题目问的是论文规则,补上空块后再数,并说明祖先会一起执行。

意思是:两种读法都能证明 B1 最终会提交,答题时写清自己用的是哪种模型。

常见误解

以为视图号跳了,B1 就永远不能提交

提交只看父子链接。视图 2 失败后,B1 ← B3 ← B4 照样能组成 Three-Chain。

以为空块里也有交易

空块只占位置,让高度等于视图号,里面没有交易。

试一下

字面模型下,视图 2 失败时 B1 在哪个块到来时提交?

带 QC4 的 B5,此时 B1 ← B3 ← B4 是直接父子的 Three-Chain。

字面模型下,B5 到来时 lockedQC 指向谁?

B3。B3 ← B4 成为新的 Two-Chain。

把它们串起来

基本 HotStuff 让一个块走三轮投票,每轮都是 leader 收票、合成 QC、广播。Chained HotStuff 发现每轮格式相同,就让新块带上一块的 QC,一张 QC 同时推进前面三个块。

副本按链长做事。一链存证据,二链上锁,直接父子的三链提交最前面的块,和 L10c 讲的「先存证据、再上锁、再执行」一一对应。稳定运行时每个视图都会有一个更早的块被提交,吞吐量比一块一块走三轮高。

leader 崩溃导致视图号跳了,判断仍然只看 QC 和父子链接。字面模型下延后一个视图提交,论文用空块把高度补齐,祖先在后代提交时一起执行。

课件里的坑

  • [读图提醒] 练习第 4 问说视图 2 失败,没给 B3 的父块。按字面模型 B3 直接延伸 B1,B1 在 B5(带 QC4)到来时提交;论文会在高度 2 放空块,B3 提交时 B1 作为祖先一起执行(p.26)。
  • [读图提醒] 练习只问 B1 的阶段,没提处理 B4 时 lockedQC 会从 B1 前移到 B2,答锁的问题时注意问的是哪个时刻(p.26)。
  • [课件没单列] 「直接父子」的检查 b*.justify.node = b*.parent 课件没写出来,是从论文第 5 节补的(p.26)。

课后 10 分钟:考点复习

这 10 分钟怎么用:先合上页面,画出 B1 到 B4 的链,在每个视图下面写 B1 的阶段和 lockedQC;再做完整例题的四问;最后做「视图 3 失败」的变式题。

必背

  1. Chained HotStuff:每个新块带上一块的 QC;One-Chain 更新 genericQC,Two-Chain 设 lockedQC,直接父子的 Three-Chain 提交最前面的块
  2. p.26 练习:B1 在 View 2/3/4 依次进入 Pre-Commit/Commit/Decide;处理 B3 时锁 B1;收到 B4 时执行 B1
  3. 收到 B4(带 QC3)时 B2 ← B3 成为 Two-Chain,lockedQC 前移指向 B2;B2、B3 尚未执行
  4. 提交看直接父子链接(b*.justify.node = b*.parent),不看视图号是否连续
  5. p.26 第 4 问:View 2 失败时按字面模型 B3.parent = B1,B1 在 B5(带 QC4)到来时提交;按论文空块规则,B1 作为 B3 的祖先一起执行

课件例题

例 1(课件 p.26):Chained HotStuff 练习

见下方完整例题。

完整例题

题目:n = 4(R1–R4),f = 1,QC = 3 票。视图 1–4 的 leader 依次是 R1–R4,B1 含交易 X。每个视图 v 的 leader 提出 Bv,Bv 携带上一块的 QC。回答四问:(1) B1 在各视图处于什么阶段?(2) lockedQC 何时指向 B1?(3) B1 何时被执行?(4) 若视图 2 失败,B1 还能提交吗?(课件 p.26)

解法:

(1) 视图 2 的 B2 带 QC1,B1 进入 Pre-Commit;视图 3 的 B3 带 QC2,B1 进入 Commit;视图 4 的 B4 带 QC3,B1 进入 Decide。

(2) 处理视图 3 的 B3(带 QC2)时,B1 ← B2 成为 Two-Chain,lockedQC 指向 B1。QC2 证明 2f+1 个副本已存 QC1,冲突分支拿不到更高的 QC 而不与之相交。收到 B4 时 lockedQC 前移到 B2。

(3) 收到 B4(带 QC3)时,B1 ← B2 ← B3 是直接父子的 Three-Chain,执行 B1 及其祖先。B2、B3 尚未执行。

(4) 能。终局性看 QC 和父子链接,不要求视图号连续。按字面模型 B3.parent = B1,B1 在处理带 QC4 的 B5 时提交(B1 ← B3 ← B4)。按论文空块规则,高度 2 放空块,B3 提交时 B1 作为祖先一起执行。

要点:每一问都从「新块带的 QC 指向谁」往回数链。

答题格式:写出每个视图的新块和它带的 QC → 数链长 → 对应动作。

变式题(先自己做)

1. 同样设定,改成视图 3 失败(R3 崩溃),R4 的 B4 嵌入 QC2、直接延伸 B2。lockedQC 何时指向 B1?B1 何时提交?(改编自课件 p.26)

提示

B4 带的是 QC2,指向 B2;往回数时看每段是不是直接父子。

判分点与答案(非官方评分标准)

处理 B4 时出现 Two-Chain B1 ← B2,lockedQC 指向 B1。B5(视图 5,嵌入 QC4)到来时 B1 ← B2 ← B4 是直接父子的 Three-Chain,提交 B1。判分点:锁的时刻是 B4;提交时刻是 B5;理由用父子链接,不用视图号。

2. 自编情境:稳定运行到视图 6,B6 带着 QC5。此时哪个块刚被提交?lockedQC 指向谁?

提示

从 B6 带的 QC5 往回数三段。

判分点与答案(非官方评分标准)

QC5 指向 B5,B3 ← B4 ← B5 是直接父子的 Three-Chain,提交 B3。B4 ← B5 是 Two-Chain,lockedQC 指向 B4。判分点:提交 B3;锁 B4;说出每个视图提交一个更早的块。

闪卡自测

1. Chained HotStuff 里新块带着什么?

上一块的 QC(p.26)。

2. One-Chain、Two-Chain、Three-Chain 各做什么?

更新 genericQC;设 lockedQC;提交最前面的块(论文第 5 节)。

3. B1 在视图 2、3、4 分别处于哪个阶段?

Pre-Commit、Commit、Decide(p.26)。

4. 处理哪个块时 lockedQC 指向 B1?

B3(带 QC2)(p.26)。

5. 收到 B4 时执行哪些块?

只执行 B1,B2、B3 尚未执行(p.26)。

6. 收到 B4 时 lockedQC 指向谁?

B2(p.26)。

7. 提交看视图号连续吗?

不看,看直接父子链接 b*.justify.node = b*.parent。

8. 视图 2 失败时,字面模型下 B1 在何时提交?

带 QC4 的 B5 到来时(p.26)。

下一讲

第 11 讲换到一条真实在跑的公链 Solana:它用 PoS 排出 leader 轮值表,用哈希链当时钟,再用带锁定的投票 Tower BFT 敲定区块,投票门槛同样是三分之二。见 L11a。

下一讲 →
L11a L11a Solana 总览:两种最终性和 PoS + PoH + Tower BFT

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。