L10b HotStuff 换 leader:新 leader 只挑最高的那张 QC
从零讲 HotStuff 的 view change:PBFT 换 leader 为什么要 O(n³),HotStuff 的新 leader 怎样只收 n−f 份 New-View、挑视图号最高的 QC 接着往下提块。
一句话版
leader 坏了就换下一个人。HotStuff 的新 leader 不翻任何人的日志,只收 n−f 份「我手里最高的 QC 是这张」,挑出视图号最高的一张,从它指向的块接着往下提新块。
这一页讲换 leader 这一件事。正常流程的四个阶段见上一页 L10a,先把 QC、prepareQC、视图这几个词弄清楚再往下读。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| view change | 视图切换 | leader 出问题时换下一个人当 leader |
| 超时 | timeout | 副本等太久没进展,就认定这个 leader 不行了 |
| New-View | 新视图消息 | 副本告诉新 leader「我手里最高的 QC 是这张」 |
| justify | 依据 | 新提案附带的那张 QC,说明新块从哪个块往下接 |
| 视图号 | viewNumber | QC 上写着的视图编号,越大说明越新 |
| primary | 主节点 | PBFT 里对 leader 的叫法 |
一个类比:交接班看盖章单据
还是班长代收签名的那个班。这回班长失联了,要换下一个人接班。
PBFT 式的交接,要每个同学把自己经手的所有单据复印给全班每个人,大家互相核对完才放新班长上任。人一多,复印件堆成山。
HotStuff 式的交接,新班长只请每人交一张自己手里最新的盖章证明。他收够多数人的就开始干活,挑出日期最新的那张,从那里接着往下办。
一张盖章证明本身就代表多数人签过字,所以新班长不用再去核对每个人的完整记录。
类比在哪里失效:
- 同学交证明时可能故意藏起最新那张,协议靠「凑够 n−f 张里必有诚实的人」来兜底,这一点在 L10c 细讲。
- 真实交接有人监督,协议里新 leader 也可能是坏人,只能靠投票规则约束他。
- 盖章能伪造,门限签名不能:凑不够部分签名,就合成不出能通过验证的 QC。
从零讲起
1. PBFT 换 leader 为什么贵
它解决什么问题
要理解 HotStuff 省下了什么,先得算清 PBFT 换一次 leader 花多少消息。这一节就是记账:一次换主多少,最坏要换几次。
从哪来(补充)
PBFT(Practical Byzantine Fault Tolerance)由 Miguel Castro 和 Barbara Liskov 在 1999 年提出,是上一讲的主角,也是 HotStuff 拿来对比的基准。
出处:Wikipedia: Practical Byzantine fault tolerance
直觉
PBFT 换主时,每个节点都要把 view-change 消息广播给所有节点,消息里还要带上自己的状态证明。一次换主就是「每人对每人」,平方级。
更糟的是坏 leader 可能一个接一个。第一个坏了换第二个,第二个也是坏的再换第三个。每换一次都要付一次平方级的账。
一步一步看
目标:算清 PBFT 换一次 leader 要多少消息、最坏要连换几次,总账是什么量级。
-
课件的例子:Replica 0 是 primary,它崩溃了。视图从 0 变成 1,Replica 1 接任新 leader。
-
这一次换主里,n 个节点每个都把 view-change 广播给 n 个节点,约 n × n 条消息。
-
坏 leader 最多 f 个,而 f 约为 n/3。最坏情况它们排在一起,要连续换约 n/3 次,量级记作 O(n)。
-
每次 n² 条,连换 O(n) 次,总账再乘一个 n。
-
对照一下 n = 4 时的数:一次换主约 4 × 4 = 16 条量级的消息,f = 1,最坏换 1 次;n 变大时,次数也跟着变多。
怎么算
一次 view change:每个节点广播给所有节点,O(n²)
连续出错的 leader 数:最多 f 个,f ≈ n/3,即 O(n)
合计 = O(n²) × O(n) = O(n³)
意思是:一次换主是平方级,最坏要换线性多次,两者相乘就是立方级。
课件用的是这种「单次乘次数」的推法。原论文的表格按签名数算,口径不一样:
| 协议 | leader 正确 | 单次 view change | f 次 leader 失败 |
|---|---|---|---|
| PBFT | O(n²) | O(n³) | O(fn³) |
| HotStuff | O(n) | O(n) | O(fn) |
意思是:论文把单次 PBFT 换主就记作 O(n³),因为每条 view-change 消息里还装着一堆签名。考试按课件推法写。
常见误解
以为 O(n³) 是一次 view change 的消息数
课件的推法是一次 O(n²) 乘连续 O(n) 次。原论文按签名数算,单次就记作 O(n³)。两种算法结论一致:PBFT 换 leader 很贵。答题写课件的推法,并说清是哪两项相乘。
以为坏 leader 只会出现一次
坏节点最多有 f 个,它们完全可能排在相邻的几个视图里轮流当 leader。算最坏情况时要按连续 f 个算。
试一下
如果连续出错的 leader 只有 1 个,课件推法下 PBFT 换 leader 的代价是多少?
只换一次,O(n²)。
n = 7 时,最坏要连续换几次 leader?
7 = 3 × 2 + 1,f = 2,最坏连续 2 个坏 leader,要换 2 次。
2. 换主的时间线:谁先发现、发什么、发给谁
它解决什么问题
副本得先知道「该换 leader 了」,再知道把什么交给谁。这一节把换主的消息按先后排一遍,弄清楚每条消息的方向。课件的时间线图画法有几处容易看错,这里按原论文的流程讲。
直觉
副本手里有个计时器。leader 迟迟不发提案、或者凑不齐票,计时器一到,副本就认定这个视图失败,自己进入下一个视图。
进了新视图,副本做的第一件事和正常流程一样:发 New-View 给这个视图的 leader,里面装着自己见过的最高 prepareQC。新 leader 收够 n−f 份,就带着最高的那张 QC 发 Prepare,之后照常走三轮投票。
一步一步看
目标:按先后看换主时每条消息由谁发给谁、里面装着什么。
-
旧 leader 出问题,副本迟迟等不到它的消息。
-
副本超时,各自把视图号加一,进入新视图。新视图的 leader 按 v mod N 算出来。
-
每个副本把 New-View 发给新 leader,里面放自己手里最高的 prepareQC。
-
新 leader 收到 n−f 份就动手,不等最慢的那几份。
-
新 leader 挑出最高的 QC,带着它广播 Prepare。
顺序 谁 → 谁 消息 内容 1 副本自己 超时 认定旧视图失败 2 副本 → 新 leader New-View 自己最高的 prepareQC 3 新 leader → 全体 Prepare 新块 + justify = 最高 QC 4 副本 → 新 leader Prepare-Vote 部分签名
怎么判断
画换主时间线或读别人的图时,检查三件事:
- New-View 的箭头方向是副本 → 新 leader。
- 新 leader 发的第一条广播是 Prepare,里面带着最高 QC。
- 生命线的条数等于 n,旧 leader 和新 leader 都是这 n 个节点里的成员。
意思是:只要这三条对得上,图就画对了。课件这一页的图三条都有出入,见下面「课件里的坑」。
常见误解
以为 New-View 是新 leader 发给副本的
方向反了。New-View 是副本发给新 leader,告诉它「我手里最高的 QC 是这张」。新 leader 发给副本的是 Prepare。
以为换主时还要像 PBFT 那样转发所有证明
HotStuff 的 New-View 里只放一张 QC。新 leader 收 n−f 份、选一张、广播一次,所以换主的消息数是线性的。
试一下
n = 4,新 leader 至少要收到几份 New-View 才能发 Prepare?
n−f = 4 − 1 = 3 份。
新 leader 发出的 Prepare 里,justify 字段放什么?
放它收到的 New-View 里视图号最高的那张 QC。
3. 新 leader 只挑最高的那张 QC
它解决什么问题
新 leader 收到几张 QC,指向的块可能不一样。它得决定新块接在哪个块后面,才不会把别人已经认可过的块甩掉。HotStuff 的规则只有一句:挑视图号最高的那张。
直觉
视图号越大,说明这张 QC 是越晚形成的,它指向的块是系统最新一次凑够 2f+1 票的成果。从它往下接,就不会丢掉已经被多数人认可的进度。
新 leader 不需要信任交 QC 的那个人。QC 上的门限签名验得过,就说明确实有 2f+1 个节点投过票,坏节点伪造不出来。
一步一步看
目标:看新 leader 收到几张指向不同块的 QC 时,新块该接在哪个块后面。
课件的例子:n = 4,新 leader 是 D,A 是拜占庭节点。
-
A、C、D 的 New-View 先到,B 的还在路上。D 收够 3 份就往下走。
-
D 比较 3 张 QC 的视图号。A、D 报的旧 QC 指向 X 的父块,C 报的 prepareQC(X) 视图号最高。D 先验证这张 QC 的门限签名。
-
D 广播 Prepare(Y, justify = prepareQC(X))。Y 以 X 为父块,链变成 Parent → X → Y。
-
之后照常走三轮投票。整个换主只用了 n−f 条 New-View 加一次广播。
怎么判断
拿到一组 New-View,按下面的顺序判断新 leader 该怎么做:
- 份数够不够 n−f。不够就继续等。
- 每张 QC 的门限签名验不验得过。验不过的丢掉。
- 在验得过的 QC 里挑视图号最大的,作为 justify。
- 新块的父块,就是这张 QC 指向的块。
意思是:新 leader 的判断只依赖 QC 上的视图号和签名,不依赖谁说了什么。
常见误解
以为 Y 是和 X 冲突的块
课件左栏确实写了「conflicting block Y」,但同页右侧写 Y 延伸 X。按规则,Y 的父块就是 X,两者在同一条链上,不冲突。
以为新 leader 要收集所有副本的完整日志
那是 PBFT 的做法,所以贵。HotStuff 里一张 QC 就能证明一个块被 2f+1 个节点认可过,新 leader 只要一张最高的,消息是线性的。
试一下
上面的例子里,如果 D 只收到 A 和 D 的 New-View,能开始提案吗?
不能。n = 4 时要收齐 n−f = 3 份,只有 2 份就继续等。
如果 B 的 New-View 也及时到了,报的是一张视图 3 的 QC,D 的选择会变吗?
不变。C 那张是视图 5,比 3 高,D 仍然选 prepareQC(X)。
把它们串起来
上一页讲了一切顺利时的正常流程,这一页处理 leader 出事的情况。
PBFT 换 leader 要每人对每人地转发证明,一次就是平方级。坏 leader 最多 f 个,可能一个接一个,再乘一个 n,最坏是立方级。
HotStuff 换主时,副本超时进入新视图,各自只交一张最高的 prepareQC。新 leader 收够 n−f 份,验签名、比视图号,挑最高的一张作 justify,新块从它指向的块往下接。一张 QC 本身就代表 2f+1 个节点的意见,所以不用再搬运整套证明,消息数是线性的。
还有一个问题没回答:如果有人已经锁在某个块上,新 leader 挑的 QC 会不会把他晾在一边?这要看「什么时候上锁」,是下一页的内容。
课件里的坑
- [课件有误] 换 leader 例子的左栏写「D proposes conflicting block Y」,同页右侧又写 Y 延伸 X。应为:Y 以 X 为父块,和 X 不冲突(p.14)。
- [读图提醒] 换 leader 时间线画了 5 条生命线(Leader、R1–R3、New leader),n 却是 4;超时的旧 leader 还在发 view change;leader 发给副本的箭头标成「New view」。按原论文,New-View 是副本发给新 leader 的,新 leader 再带最高 QC 发 Prepare(p.15)。
- [口径提醒] 课件按「一次 O(n²) × 连续 O(n) 次」推出 PBFT 换 leader 是 O(n³)。原论文表格把单次 PBFT 换 leader 就记作 O(n³)、f 次失败记作 O(fn³)。考试按课件推法写(p.13)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先合上页面,用一句话说出 PBFT 换主的 O(n³) 是哪两项相乘;再画一遍 p.14 的例子,标出 D 收到的三张 QC 和最后的链;然后做完整例题和变式题。
必背
- PBFT 换 leader 贵:一次 view change 广播 O(n²),最坏连续 O(n) 个 leader 出错,合计 O(n³)
- leader 出问题时副本超时进入新视图,把自己最高的 prepareQC 放进 New-View 发给新 leader
- HotStuff 换 leader:新 leader 收 n−f 个 New-View,选视图号最高的 QC 作 justify,延伸它指向的块
- p.14 例子:C 报 view 5 的 prepareQC(X) 最高,D 广播 Prepare(Y, justify = prepareQC(X)),Y 延伸 X、不冲突
- 新 leader 不转发全部证明,只用一张 QC 当依据,换 leader 的消息数是线性的
课件例题
例 1(课件 p.12–13):PBFT 换 leader 的代价
Replica 0 是 primary 并崩溃,Replica 1 接任,视图从 0 变 1。一次 view change 是什么量级?为什么最坏是 O(n³)?
提示
先数一次切换里谁发给谁,再想坏 leader 最多能连续出现几个。
解答
一次 view change 每个节点都广播给所有节点,O(n²)。最坏情况连续 O(n) 个 primary 出错(f 约为 n/3),每个都要切换一次,O(n²) × O(n) = O(n³)。
例 2(课件 p.14):新 leader D 选父块
见下方完整例题。
例 3(课件 p.15):HotStuff 换 leader 的时间线
leader 超时后,副本和新 leader 之间依次发生什么?新 leader 要等多少条消息?
提示
先确定 New-View 的箭头方向。
解答
副本超时进入新视图,把自己最高的 prepareQC 放进 New-View 发给新 leader。新 leader 收齐 n−f 条,选最高的 QC,带着它发 Prepare,之后照常走三轮投票。消息数是线性的。
完整例题
题目:n = 4,f = 1。新 leader D 收到 A、C、D 的 New-View,B 的迟到。A、D 报的 QC 指向 X 的父块,C 报的是 view 5 的 prepareQC(X)。D 选哪个块当父块?广播什么?Y 和 X 是什么关系?(课件 p.14)
约定:父块 X 之前的那个块叫 Parent。
解法:
第一步,数份数。n−f = 3,D 已经收到 A、C、D 三份,够了,不等 B。
第二步,验签名。三张 QC 都要验门限签名,假设都验得过。
第三步,比视图号。A、D 的 QC 指向 Parent,视图号比 5 小;C 的 prepareQC(X) 是 view 5,最高。
第四步,定父块。最高 QC 指向 X,所以新块 Y 的父块是 X。
第五步,广播 Prepare(Y, justify = prepareQC(X))。链是 Parent → X → Y。
要点:Y 延伸 X,两者不冲突。课件左栏「conflicting」的写法是错的。
答题格式:份数够不够 → 哪张 QC 最高 → 父块是谁 → 广播什么 → 链长什么样。
变式题(先自己做)
1. 还是 p.14 的设定,但拜占庭节点 A 在 New-View 里谎称自己有一张 view 7 的 QC,指向另一个块 Z。D 会选 Z 吗?(改编自课件 p.14)
提示
D 选 QC 之前先做什么?A 一个人能凑出 3 份部分签名吗?
判分点与答案(非官方评分标准)
不会。D 先验证 QC 的门限签名。一张真的 QC 要 2f+1 = 3 份部分签名合成,A 一个坏节点凑不出来,伪造的 QC 验不过,D 把它丢掉。剩下的 QC 里 C 的 view 5 最高,D 仍然选 prepareQC(X),广播 Prepare(Y, justify = prepareQC(X))。判分点:说出「先验签名」;说出伪造需要 2f+1 份部分签名;结论仍选 X。
2. 自编情境:n = 7,新 leader 至少收几份 New-View?如果收到的 5 份里视图号分别是 2、4、4、6、3,它选哪一张?
提示
先算 f,再挑最大的视图号。
判分点与答案(非官方评分标准)
f = 2,n−f = 5,至少收 5 份。最大视图号是 6,选那一张作 justify,新块从它指向的块往下接。判分点:份数 5;按视图号挑最大,不按多数票挑。
闪卡自测
1. 课件里 PBFT 换 leader 的例子是谁换成谁?
Replica 0 崩溃,Replica 1 成为新 leader,视图从 0 变成 1(p.12)。
2. 课件怎样推出 PBFT 换 leader 是 O(n³)?
一次 view change O(n²),最坏连续 O(n) 个 primary 出错,两者相乘(p.13)。
3. 原论文表格里,单次 view change 的复杂度 PBFT 和 HotStuff 各是多少?
PBFT O(n³),HotStuff O(n)(p.13 对照论文 Table 1)。
4. 新 leader 收几份 New-View 才能提案?挑哪张 QC?
n−f 份,挑视图号最高的那张(p.14)。
5. p.14 的例子里 Y 和 X 是什么关系?
Y 以 X 为父块,延伸 X,不冲突(p.14)。
6. New-View 的方向是谁发给谁?
副本发给新 leader(p.15,按原论文)。
7. 课件 p.15 的时间线画了几条生命线?对吗?
5 条,但 n = 4,多画了一条(p.15)。
8. HotStuff 换 leader 为什么是线性的?
每个副本只交一张 QC,新 leader 收 n−f 份、广播一次,不用转发全部证明(p.14–15)。
下一讲
下一页是 L10c 为什么非得三轮投票:锁上得太早会卡死,锁上得太晚会分叉,三轮怎样两头都顾上。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。