← COMP5567 全部讲次
T02 · 第 4 周

T02 HotStuff Part 1:三票成证书,三代成提交

四节点 HotStuff demo 的三个字段怎么一格一格右移,以及故障时为什么只能等。

一句话版

三票凑成一张证书,连着三代都有证书,最老那代才算定了。

先认识这几个词

读之前最好先懂拜占庭容错的基本设定,见 L07a。

词 全称 / 读法 一句人话
HotStuff 一种拜占庭容错共识协议,本讲用它的链式版本 Chained HotStuff 让几个节点对「下一个区块是什么」达成一致,哪怕有节点作恶
n、f 节点总数、最多容忍的故障节点数 本讲 n = 4、f = 1
quorum 法定人数 做决定至少要凑够的票数,这里是 2f + 1 = 3
QC Quorum Certificate,法定人数证书 某个块凑够 3 票后得到的证明
view 视图、轮次 协议按轮推进,每轮有一个编号
leader / 副本 leader / replica 这一轮负责提出新块的节点 / 其余负责投票的节点
提交 commit 块被最终确定,以后不会再被推翻
超时 timeout 这一轮等太久没进展,就放弃并进入下一轮

题目地图

这次 tutorial 是 Project 第一部分的说明会。前五页交代任务,后面二十多页围绕一个网页 demo 讲 Chained HotStuff。demo 可以单步执行:只有四个节点、空区块,每点一次 Next Step 执行一个事件。界面上每个节点显示五个字段:View/Leader、HighQC、LockedQC、Latest block、Commit block。读懂这一讲,就是能说出「走到第几步时这几个字段各是什么、为什么」。

课件内容 容易卡住的地方
项目两部分、n = 4 与 f = 1、安装命令 安装命令里的文件名多打了一个 y
三票门槛、四个设计、五个字段 HighQC 和 LockedQC 分不清
提案、投票、形成 QC、换 leader 收到提案和认证提案是两回事
锁规则、三链提交、checkpoint 表 只数 QC 个数,忘了父子相连
安全三层、超时、两次故障演练 以为少了节点门槛也跟着降
线性通信、demo 的六条简化、提示卡 把 demo 的回放速度当性能数据

项目评分、日期和提交物以第 5 周发布的正式说明为准,本页只讲协议本身。

概念卡

1. 法定人数与交集(Quorum Intersection)

人话定义:它保证同一轮里不会冒出两张互相矛盾的证书。一张证书(QC)要 3 票;四个节点里任意挑两组各 3 人,至少有 2 人重叠。作恶的最多 1 个,所以重叠的人里一定有诚实节点。

四个节点 N1 到 N4 横排,Quorum A 覆盖 N1、N2、N3,Quorum B 覆盖 N2、N3、N4,二者交集是 N2 和 N3 两人,大于故障上限 1,所以交集里至少有一个诚实节点,它在同一个 view 只能投一票,两个冲突 QC 无法同时成立
图片来源:本站据课件 p.7 的表格重绘。

例子:交集下界 = 3 + 3 − 4 = 2 > 1。意思是两组至少重叠 2 人,比作恶上限多。诚实节点每个 view 只投一票。两个冲突的 QC 就得让同一个诚实节点投两次冲突票,这不会发生。

常见误解

以为过半数就够了 → n = 4 时取 2 票,{N1, N2} 和 {N3, N4} 完全不相交,两个冲突块可以各自凑出证书。过半只防分裂投票,防不住作恶节点撒谎,所以门槛是 2f + 1。

回讲义:L10a HotStuff:票交给 leader 攒成一张证书,三轮投票走完一个区块

2. HighQC 与 LockedQC

人话定义:两者分别回答「新块接在哪」和「我能不能投」。HighQC 是「我见过的最新进展」,leader 用它决定新块接在哪。LockedQC 是「我承诺不轻易放弃的分支」,副本用它判断能不能投票。

例子:STEP 13 时 HighQC 在 B2、LockedQC 在 B1;STEP 20 时分别在 B3、B2。

常见误解

把「LockedQC 总比 HighQC 落后一格」当成定律 → 这只是正常连续路径上的现象。STEP 0 和 1 两者都在 B0,故障或跳 view 时差几格不固定。

回讲义:L10c 为什么非得三轮投票:锁早了卡死,锁晚了分叉

3. 锁规则(safeNode)

人话定义:它决定副本收到提案后投不投票。副本每个 view 最多投一票,先过基本检查,再满足两个安全条件之一:新块扩展了自己锁定的块,或新块带来的 QC 比自己锁定时的更新。

例子:本地锁在 QC(B1),view 1。

  • 扩展 B1 的提案:接受。
  • 与 B1 冲突,且 QC 的 view ≤ 1:拒绝。
  • 与 B1 冲突,但带着 view 2 的有效 QC:接受。
常见误解

以为锁就是永不改变 → 锁只拒绝「没有依据的切换」。没有第二个条件,一个锁在旧分支上的节点会永远拒绝别人的提案,系统可能卡死。原论文把第一个条件叫 safety rule(安全规则),第二个叫 liveness rule(活性规则,保证系统能继续往前走)。

回讲义:L10c 为什么非得三轮投票:锁早了卡死,锁晚了分叉

4. 三链提交(Three-Chain Commit)

人话定义:它回答「一个块什么时候才算定了」。一个块要攒三级证据:自己拿到 QC 是被认证(certified),儿子拿到 QC 成为锁定依据,孙子拿到 QC 才提交。三个块要父子直接相连。

一条块链 B0 到 B3,下面三行对应 STEP 6、13、20 三个检查点,HighQC、LockedQC、Commit 三列每形成一个 QC 就一起右移一格,到 STEP 20 时分别指向 B3、B2、B1

例子:B1 在 view 1 提出,view 3 形成 QC(B3) 时才提交,demo 里是 STEP 20。

常见误解

只数 QC 个数 → 原论文要求三层都是直接父子关系。这个约束保证了安全证明里的高度关系,放宽它可能让两条冲突分支都被提交。demo 的正常路径上,三个块恰好来自连续的 view 1、2、3。

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

逐题拆解

正常路径(Demo 0–4)。Reset 后四个节点完全一样:view 1,leader N1,三个证书字段都指向 B0。

  • 点一次 Next Step 到 STEP 1,Latest block 变成 B1,HighQC 还在 B0。块收到了,还没有任何证书为它背书。
  • STEP 2–5 是 N1 到 N4 依次投票。STEP 6 形成 QC(B1),三个证书里只有 HighQC 动了。
  • STEP 7 进入 view 2,leader 按公式轮到 N2,STEP 8 是新提案。
  • STEP 13 形成 QC(B2)。这说明 B2 被认证、B1 有了后继证书,于是 HighQC 到 B2、LockedQC 到 B1。
  • STEP 20 形成 QC(B3),三格整齐错开:B3 / B2 / B1,B1 第一次被提交。

checkpoint 表里只有 STEP 6、13、20 改变证书字段,提案和换 view 都不动它们。这对应课件那句「demo 在收到 QC 时更新状态」。相邻两个 QC 隔 7 步:进入新 view、提案、四票、形成 QC,共七步。稳态以后每个 view 提交一个块,开头那段等待是一次性的。

Demo 5:leader 崩溃。Reset 后点 Crash Leader,推进到 STEP 11。截图里 N1 标着 CRASHED,停在 view 1,四个字段全是 B0。N2、N3、N4 已在 view 2,HighQC 是 B1(标 v2),LockedQC 是 B0,界面显示 QC(B1) formed、Live nodes agree。N1 的 Latest block 还是 B0,说明它崩溃前没发出 B1。B1 是 N2 在 view 2 提出并凑齐三票的,所以证书属于 view 2。剩下三个节点恰好是 quorum。崩溃节点不会被移出成员表,大家只是不再等它。

Demo 6:一票被扣。下拉框选 Node 4 withholds votes,推进到 STEP 6。QC(B1) 的投票者是 N1、N2、N3,恰好三票。正常路径里四票有一票是多余的,这里拿掉它系统刚好还能走。

容错边界。全部正常 4 票,QC 形成;一个扣票 3 票,QC 照样形成。一个崩溃再加一个扣票,只剩 2 票,没有 QC,反复超时。门槛不会因为在线节点少了就降低。证据不够就等,系统停住,但不提交冲突的块。

超时。view 卡住的原因有三种:leader 不发提案、票不够三张、QC 没被广播。超时后进入下一个 view、换 leader,副本保留 HighQC 和 LockedQC。超时只决定什么时候换人,不碰证书,所以超时长短只影响速度,不影响正确性。demo 的超时是三个逻辑 tick(模拟出来的时间单位)。

课件里的坑

  • ⚠️ p.5 安装命令拼错:课件写 pip install -r requirements.txty,同页仓库截图里的文件名是 requirements.txt,照抄会找不到文件。
  • [读图提醒] p.5 的两种准备方式不一致:第一行说可以只复制 serve.py,第三行却运行 backend/main.py,截图的根目录里也没有 serve.py,直接 clone 整个仓库更稳妥。
  • [补充] p.26 的「保守的教学规则」课件没解释:原论文实现版的提交条件只检查三层父子关系,demo 在收到 QC 时检查连续三链。推测 demo 比论文实现更严,可能让一些块多等,不会多提交,以实际代码为准。
  • [补充] p.22 的 B1 是谁提出的:页脚只说 N2 在 view 2 形成 QC(B1)。从 N1 的 Latest block 仍是 B0 可以推断 B1 由 N2 在 view 2 提出,块号按出块顺序编。
  • 页码:p.10–28 的页脚数字比 PDF 页序小 4,例如 Demo 0 页脚印 06,本页引用的都是 PDF 页序。

课后 10 分钟:考点复习

这 10 分钟怎么用:先遮住下面的必背,自己画一遍 STEP 0 / 1 / 6 / 7 / 13 / 20 的三列状态表;再做完整例题和变式题;最后用闪卡查漏。

必背

  1. n = 4、f = 1 时 quorum q = 2f + 1 = 3;任意两个 quorum 交集 ≥ 3 + 3 − 4 = 2 > f,加上每 view 一票,同一 view 不可能有两个冲突 QC
  2. 投票的两个安全条件是「或」:提案扩展自己锁定的块,或携带的 QC 的 view 严格高于 LockedQC 的 view;前者保安全,后者防卡死
  3. HighQC 管 leader 往哪接,LockedQC 管副本能不能投,Commit block 是已经最终确定的祖先,三者是不同的状态
  4. 三链提交:块自己有 QC 是 certified,儿子有 QC 成为锁定依据,孙子有 QC 才提交,三个块必须父子直接相连
  5. 正常路径每个 view 七步,STEP 6 / 13 / 20 的 (HighQC, LockedQC, Commit) 依次是 (B1, B0, B0)、(B2, B1, B0)、(B3, B2, B1)
  6. Leader(view) = ((view − 1) mod 4) + 1;超时只换 leader,副本保留 HighQC 和 LockedQC
  7. 故障不降低法定人数:只剩 2 票时没有 QC,系统反复超时等待
  8. demo 用节点 ID 代替签名、用中心队列和逻辑 tick 计时,只演示状态转移,不证明安全性,也不构成性能结论

完整例题

题:从 n > 3f 推出本 demo 的参数,并说明 n = 4 时为什么 quorum 取 3。

  1. 设 quorum 为 q。活性要求 f 个节点不回票也能凑够:q ≤ n − f。
  2. 安全要求两个 quorum 的交集里至少一个诚实节点:2q − n > f。
  3. 把第 1 式代入第 2 式:2(n − f) − n ≥ 2q − n > f,得 n − 2f > f,即 n > 3f。
  4. f = 1 时最小 n = 4,取 q = 2f + 1 = 3。检查:q ≤ n − f 即 3 ≤ 3,成立;2q − n = 2 > 1,成立。
  5. 若取 q = 2:2q − n = 0,不满足第 2 式,{N1, N2} 与 {N3, N4} 可以各自出证书。

答:n = 4、f = 1、q = 3;q = 2 会破坏交集论证。

变式题

题:本地 LockedQC = QC(B1),view 1。依次收到三个提案:(a) 扩展 B2(B2 是 B1 的儿子),携带 QC(B2),view 2;(b) 与 B1 冲突,携带一份 view 1 的 QC;(c) 与 B1 冲突,携带一份有效的 view 2 QC。三个提案都来自本 view 合法的 leader,副本本 view 还没投过票。问各自能否投票,并说明 (c) 通过后 LockedQC 是否立刻变成 (c) 带来的那份 QC。

提示

先查两个安全条件各满足哪条,再想「能投票」和「改锁」是不是同一个动作。

判分点与答案

(a) 扩展 B1,满足第一条,接受。(b) 冲突,QC 的 view 1 不大于锁的 view 1,两条都不满足,拒绝。(c) 冲突,但 2 > 1,满足第二条,接受。判分点:答出 (c) 只说明锁规则允许投票,LockedQC 按证书链规则另行更新,不会因为投了这一票就直接换成那份 QC。注意每个 view 只能投一票,三个提案若在同一 view 到达,只有第一个合法的能被投。

闪卡自测

1. 项目第一部分要演示哪六个协议动作?

leader proposal、replica voting、QC formation、chained block construction、block commitment、view changes(p.3)。

2. Safety 和 Liveness 各保证什么?

Safety 保证坏事不发生:正确副本不会提交冲突的内容。Liveness 保证好事终会发生:网络稳定后正确的 leader 能收集到足够响应(p.4)。

3. STEP 1 时 Latest block 是 B1,HighQC 为什么还是 B0?

块已经收到,但还没有任何节点为它投票形成 QC,收到提案和认证提案是两件事(p.11)。

4. view 6 的 leader 是谁?

((6 − 1) mod 4) + 1 = 2,是 N2(p.14)。

5. QC(B2) 一个事件为什么能同时推进 HighQC 和 LockedQC?

它说明 B2 被认证,同时说明 B2 的父块 B1 有了后继证书,于是 HighQC 到 B2、LockedQC 到 B1(p.15)。

6. Demo 5 里为什么 QC(B1) 标的是 v2?

N1 崩溃前没发出 B1,B1 由 view 2 的 leader N2 提出并凑齐三票(p.22)。

7. 超时设得太短或太长会破坏安全性吗?

不会。超时只决定什么时候换 leader,不碰证书字段,只影响推进速度(p.21)。

8. 线性通信靠哪两件事?

所有副本只把票发给 leader,leader 用门限签名把票合成一个紧凑签名,每个 view 认证器总量是 O(n)。论文的复杂度表里 PBFT 正常 leader 是 O(n²)(p.25)。

9. 乐观响应在什么前提下成立?

网络稳定(GST 之后)且 leader 正确。此时 leader 等够 n − f 个响应就推进,不必等固定时长(p.25)。

10. demo 的六条简化中,哪一条对安全论证影响最大?

签名只是节点 ID 列表。安全论证依赖投票不可伪造,没有签名,一个节点可以冒充别人投票(p.4、p.26)。

下一步

下一次 Project Introduction 2 讲第二部分:把交易提交、mempool、出块和状态机执行接到这套共识上,带着「共识层到底向区块链层承诺了什么」去听。

下一讲 →
L05a L05a PoW 与 PoS:出块权从烧电换成押币

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