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,R1 提出 B1。B1 还没有任何 QC。
-
视图 2,B2 带着 QC1。B1 有了第一张证书,进入 Pre-Commit。
-
视图 3,B3 带着 QC2。B1 ← B2 成为 Two-Chain,B1 进入 Commit,lockedQC 指向 B1。
-
视图 4,B4 带着 QC3。B1 ← B2 ← B3 是直接父子的 Three-Chain,执行 B1。lockedQC 前移到 B2。
-
把四个视图摆在一行看,就是一条流水线。
怎么算
看 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 往回数。
-
b* 的 QC 指向 b’‘:b’’ 有了 QC,One-Chain,genericQC 更新为它。
-
b’’ 的 QC 指向 b’:b’ ← b’’ 是 Two-Chain,lockedQC 设为 b’‘.justify,也就是指向 b’。
-
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 执行 -
「直接父子」的检查:每一段都要满足子块的 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。
-
视图 2 没出块,超时后换到视图 3。
-
视图 3,B3 带 QC1,直接延伸 B1。B1 进入 Pre-Commit,视图号跳了一格,父子链接没断。
-
视图 4,B4 带 QC3。B1 ← B3 是 Two-Chain,锁 B1。
-
视图 5,B5 带 QC4。B1 ← B3 ← B4 是直接父子的 Three-Chain,提交 B1,lockedQC 前移到 B3。
-
按论文的空块规则:高度 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 失败」的变式题。
必背
- Chained HotStuff:每个新块带上一块的 QC;One-Chain 更新 genericQC,Two-Chain 设 lockedQC,直接父子的 Three-Chain 提交最前面的块
- p.26 练习:B1 在 View 2/3/4 依次进入 Pre-Commit/Commit/Decide;处理 B3 时锁 B1;收到 B4 时执行 B1
- 收到 B4(带 QC3)时 B2 ← B3 成为 Two-Chain,lockedQC 前移指向 B2;B2、B3 尚未执行
- 提交看直接父子链接(b*.justify.node = b*.parent),不看视图号是否连续
- 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。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。