L10a HotStuff:票交给 leader 攒成一张证书,三轮投票走完一个区块
从零讲 Basic HotStuff 的正常流程:为什么要 3f+1 个节点、每轮等 2f+1 票,leader 怎样把票合成 QC 再广播,四个阶段各做什么,leader 怎样轮换。
一句话版
HotStuff 让所有副本只把票交给 leader。leader 攒够 2f+1 张票,就合成一张证书再发回去。一个区块要走三轮这样的投票才算定下来。
这一页只讲一切顺利时的正常流程。leader 坏了怎么换人、为什么非得三轮、证书里的签名怎么合成,后面几页分别讲。读之前最好先懂 PBFT,见 L09a。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| BFT | Byzantine Fault Tolerance,拜占庭容错 | 有节点会撒谎、乱发消息,系统照样不出错 |
| f 与 n | failures 与节点总数 | 最多 f 个坏节点,总共要 n = 3f+1 个节点 |
| leader | 领导者,每个视图一个 | 负责提区块、收票、发证书的那个节点 |
| 视图 | view | 一个 leader 的任期,编号从小到大往上数 |
| QC | Quorum Certificate,法定人数证书 | 一张证明「已有 2f+1 个节点投了赞成票」的凭据 |
| 门限签名 | threshold signature | 凑够指定人数的部分签名,就能合成一个完整签名 |
| 部分同步 | partial synchrony | 网络有时乱,但最终会稳定下来,消息能在有限时间内送到 |
一个类比:班长代收签名
一个班要表决一件事,全班 4 个人,其中可能有 1 个人捣乱。
上一讲 PBFT 的做法,像每个人都给其他所有人打电话说「我同意」。人一多,电话数按人数的平方涨。
HotStuff 换了个办法。班长坐在中间,每个人只把签了名的小纸条交给班长。班长凑够 3 张,就把它们合成一张盖了章的证明,复印发给全班。大家看到证明,就知道多数人已经同意了,不用再互相打电话。
这样的表决要走三轮。第一轮大家把证明收好,第二轮按证明「定下来」,第三轮才真正执行。班长每次换人轮流当。
类比在哪里失效:
- 真实班长可能是坏人,协议靠「凑不够票就造不出证明」来防他,不靠信任他。
- 纸条一眼能看出谁签的,协议里要靠密码学的签名来验证。
- 班里的人能面对面确认,节点之间只能发消息,消息还可能迟到。
从零讲起
1. 为什么是 3f+1 个节点、每轮等 2f+1 票
它解决什么问题
要在有坏节点的网络里投票,先得回答两件事:一共要几个节点,每一轮等几张票才往下走。等得太少,坏节点能凑数骗人;等得太多,坏节点一沉默,大家就永远等不齐。
直觉
坏节点最多 f 个,它们可以一张票都不投。所以每轮最多只能等 n−f 张,多等就可能等不到。
另一边,两次投票各凑够 n−f 张,这两组人里必须至少有一个诚实节点是重叠的。诚实节点不会前后说两样话,重叠的那个人就把两次投票拴在一起,坏人没法让两组人各自同意两件冲突的事。
把这两个要求一起算,节点数最少就是 3f+1,每轮等 2f+1 张票。
一步一步看
目标:用 f = 1 的四个节点数一遍,看任意两组 2f+1 票为什么至少重叠一个诚实节点。
-
取最小的情况 f = 1,节点数 n = 3 × 1 + 1 = 4,记作 R1 到 R4。
-
每轮等 n−f = 4 − 1 = 3 张票。坏节点就算一张不投,剩下 3 个诚实节点也凑得齐。
-
随便取两组 3 票,比如第一组 R1、R2、R3,第二组 R2、R3、R4。
-
两组重叠的是 R2、R3,共 2 个,正好是 f+1。坏节点最多 1 个,重叠里至少还剩 1 个诚实节点。
-
换几个 f 再算一遍,规律不变:
f n = 3f+1 每轮票数 2f+1 两组至少重叠 1 4 3 2 2 7 5 3 3 10 7 4
怎么算
两组票各有 2f+1 张,节点一共 3f+1 个。两组加起来的人数减去总人数,就是至少重叠的人数:
(2f+1) + (2f+1) − (3f+1) = f+1
意思是:任意两组票至少有 f+1 个共同成员。坏节点最多占其中 f 个,所以至少剩 1 个诚实节点在两组里都投了票。
反过来,如果节点只有 3f 个,每轮最多等 3f − f = 2f 张。两组 2f 张的重叠是 2f + 2f − 3f = f 个,可能全是坏节点,拴不住。这就是不能少于 3f+1 的原因。
常见误解
以为凑够过半就行
4 个节点的过半是 3,碰巧一样。7 个节点时 f = 2,过半是 4,但要等 5 张。HotStuff 要的是超过三分之二,这样任意两组票才保证有诚实节点重叠。课件 QC 那一页写成「majority」,答题时写 2f+1。
以为每轮要等全部 n 个节点都回复才安全
等全部回复,坏节点只要有一个不投,系统就永远卡住。安全性来自两组票的重叠,不来自人到齐。
试一下
n = 7 时 f 是几?每轮等几张票?
7 = 3 × 2 + 1,f = 2,每轮等 2 × 2 + 1 = 5 张。
n = 10 时,两组票至少重叠几个节点?里面至少几个诚实?
f = 3,每组 7 票,重叠至少 7 + 7 − 10 = 4 个。坏节点最多 3 个,至少 1 个诚实。
2. QC 与星形拓扑:票只交给 leader
它解决什么问题
PBFT 里每个节点把票发给所有节点,每人都自己数票。节点一多,消息数按平方涨。星形拓扑想办法让每轮的消息数只跟节点数成正比。
从哪来(补充)
HotStuff 出自 Maofan Yin、Dahlia Malkhi、Michael K. Reiter、Guy Golan Gueta、Ittai Abraham 的论文「HotStuff: BFT Consensus in the Lens of Blockchain」。论文 2018 年挂上 arXiv,短版本发表在 PODC 2019。摘要里的两句卖点是:正确的 leader 按实际网络延迟推进,通信量和副本数成线性。
后来 Libra 区块链(后改名 Diem)用的共识 LibraBFT,白皮书里写明它基于 HotStuff。
出处:arXiv 1803.05069、LibraBFT 白皮书
直觉
把数票这件事交给 leader 一个人。大家只把票交给他,他数够 2f+1 张就合成一张证书 QC,再发给所有人。别人拿到 QC,验一下上面的签名,就知道多数人投过票了,不用自己再挨个收票。
QC 能做到「一张顶 2f+1 张」,靠的是门限签名:每张票是一个部分签名,凑够 2f+1 份就能合成一个和普通签名一样大的完整签名。具体怎么合成在 L10d 讲。
一步一步看
目标:看票只交给 leader、由 leader 合成 QC 后,一轮的消息怎样比 PBFT 两两互发少得多。
还是 n = 4,R1 当 leader,R2、R3、R4 是副本。走一轮投票:
-
R1 把提案发给 3 个副本,提案里附着它手里最高的那张 QC。
-
3 个副本各自把票交给 R1,票里是自己的部分签名。副本之间不互相发消息。R1 自己也算一票。
-
R1 凑够 3 份部分签名,合成一张 QC,再发给所有副本。
-
把整轮的消息画在一起,和 PBFT 对比:左边两两互发,右边全部经过 leader。
怎么算
先看两条消息的格式。
QC = type + viewNumber + sig
意思是:一张 QC 写着这是哪一阶段的证书、属于哪个视图,再加一个由 n−f 个部分签名合成的门限签名。
VoteMSG = type + node + partialSig
意思是:一张票写着投的是哪一阶段、投票人是谁、投票人的部分签名。
再数一轮的消息。PBFT 每个节点发给其余 n−1 个,n = 4 时是 4 × 3 = 12 条。HotStuff 是 3 张票交给 leader,leader 再发 3 份 QC,3 + 3 = 6 条,约 2n。
意思是:PBFT 一轮约 n² 条,记作 O(n²);HotStuff 一轮约 2n 条,记作 O(n)。课件的总结口径是正常流程 O(n²) → O(n),换 leader O(n³) → O(n²)。
常见误解
以为 QC 就是把 3 个签名打包在一起
打包也能证明,但验证要验 3 次,体积随人数增长。门限签名合成后只有一个签名,验一次就够,这是消息能做到线性的关键。
以为星形拓扑只是省了几条消息,没什么本质区别
节点多了以后差距很大。平方级和线性级的比值本身随 n 增长,节点上百时差几十倍。换 leader 时的通信量也跟着降了一个量级。
试一下
节点从 4 个增加到 8 个,PBFT 和 HotStuff 每轮的消息数大约各变成原来的几倍?
PBFT 是 8 × 7 = 56 条,约是 12 条的 4 倍多;HotStuff 是 7 + 7 = 14 条,约是 6 条的 2 倍多。按量级说,平方级约 4 倍,线性级约 2 倍。
门限签名里「2-of-3」是什么意思?
一共 3 份密钥碎片,任意 2 份合作就能签出完整签名,只有 1 份不行。
3. 四个阶段:存证据、上锁、执行
它解决什么问题
一张 QC 只说明「多数人对某件事投了票」。一个区块要被所有诚实节点安全地执行,HotStuff 让它连拿三张 QC,每拿一张,副本就多做一件事。这一节讲这几个阶段的先后。
直觉
一个视图里,leader 广播一样东西,副本投票回来,leader 凑够票合成 QC,进入下一阶段。这样来回三次,副本手里依次多出三样东西:先是证据,再是锁,最后才执行。
为什么要分三步、少一步会怎样,在 L10c 用反例讲。这里先把每步做什么记住。
一步一步看
目标:看一个区块在一个视图里依次拿到三张 QC,副本每拿一张多做哪件事。
-
New-View:副本把自己手里最高的 prepareQC 发给这个视图的 leader。
-
Prepare:leader 提出区块 B,附上收到的最高 QC 作为依据,叫 justify。副本投票,得到 prepareQC。
-
Precommit:leader 广播 prepareQC,副本把它存下来。副本再投票,得到 precommitQC。
-
Commit:leader 广播 precommitQC,副本把 lockedQC 指向 B,也就是上锁。副本再投票,得到 commitQC。
-
Decide:leader 广播 commitQC,副本执行 B 和它还没执行的祖先块。
课件用一张星形时间线把这几步画在一起:
怎么判断
看一个阶段时问两件事:leader 这一步广播的是什么,副本收到后改了自己的什么状态。
| 阶段 | leader 广播 | 副本做什么 |
|---|---|---|
| Prepare | 提案 B + justify | 检查后投票 |
| Precommit | prepareQC | 存下 prepareQC,再投票 |
| Commit | precommitQC | 设 lockedQC 指向 B,再投票 |
| Decide | commitQC | 执行 B 及未执行的祖先 |
投票只发生在前三步之后,一共三轮:Prepare-Vote、Precommit-Vote、Commit-Vote。Decide 不再投票。
常见误解
以为 Precommit 阶段副本就上锁了
Precommit 只是把 prepareQC 存起来当证据。上锁发生在 Commit 阶段,执行发生在 Decide 阶段。三步的先后顺序就是安全性的来源。
以为 New-View 只在换 leader 时才发
课件对比页确实这么写,但时间线里每个视图的第一步都是 New-View。按原论文,副本每进入一个新视图都发,包括第一个视图。
试一下
副本在哪个阶段设置 lockedQC?在哪个阶段执行区块?
Commit 阶段设置 lockedQC,Decide 阶段执行。
一个视图里一共有几轮投票?分别换来哪张 QC?
三轮。Prepare-Vote 换来 prepareQC,Precommit-Vote 换来 precommitQC,Commit-Vote 换来 commitQC。
4. leader 轮换与乐观响应
它解决什么问题
所有票都经过 leader,leader 的权力就很大。他要是坏人,可以故意不发提案、拖着不动。轮换让每个人只当一个视图的 leader,坏 leader 最多拖慢一个视图。乐观响应回答另一件事:leader 每轮该等多久。
直觉
轮换像值日表:按视图编号排,轮到谁就是谁,大家不用商量就知道这一轮该听谁的。
乐观响应是说 leader 不等固定时间。最先到的 n−f 张票一到,马上往下走。网络快,协议就快;网络慢,协议才跟着慢。
一步一步看
目标:看 leader 怎样按 v mod N 轮流当,坏 leader 为什么最多拖慢一个视图。
-
4 个节点编号 0 到 3,N = 4。
-
按 v mod N 排出几个视图的 leader:
视图 v v mod 4 leader 4 0 0 号 5 1 1 号 6 2 2 号 9 1 1 号 -
假设 2 号是坏节点。视图 6 轮到它,它不发提案,大家等到超时。
-
进入视图 7,7 mod 4 = 3,换成 3 号当 leader,系统继续往前走。
-
视图 7 里,3 号收到最先到的 3 张票就合成 QC,不用等剩下那一张。
怎么算
第 v 个视图的 leader 编号 = v mod N
意思是:用视图号除以节点数,余数就是这一轮 leader 的编号。视图号一直往上加,leader 就在所有节点之间一圈一圈轮下去。
乐观响应的等待条件:收到的回复数 ≥ n−f 就走
意思是:leader 等的是「够数」,不等「到点」。
常见误解
以为乐观响应是指 leader 等一个固定的超时时间
固定超时是同步协议的做法,网络再快也要等满。乐观响应只要凑够 n−f 个就走,网络快时协议就快。超时只在 leader 出问题、迟迟凑不齐票时才用来触发换人。
以为 Chain Quality 的规则就是固定轮数强制换 leader
课件写了「每 3 轮」强制换一次,但原论文没有这条规则,只说 leader 频繁轮换有助于 chain quality。考试按课件写,自己心里知道这一条口径存疑。
试一下
N = 4,视图 9 的 leader 是几号?
9 mod 4 = 1,是 1 号节点。
N = 7,视图 15 的 leader 是几号?
15 mod 7 = 1,是 1 号节点。
把它们串起来
上一讲的 PBFT 已经能在有坏人时达成共识,问题是太吵,每个人都要和所有人说话。
HotStuff 先沿用 3f+1 个节点、每轮 2f+1 票的规矩,这保证任意两组票里都有诚实节点重叠。然后把「大家互相确认」换成「大家交给 leader,leader 出一张证明」。这张证明就是 QC,门限签名让它只有一个签名那么大,于是每轮消息从平方级降到线性级。
一个区块要拿到三张 QC 才算定下来:先存证据,再上锁,最后执行。leader 每个视图按 v mod N 轮换,坏 leader 只能拖慢一个视图;好 leader 凑够票就走,速度跟着实际网络走。
还剩几个问题:leader 坏了,新 leader 怎样接手;为什么非得是三轮;门限签名怎么合成。下面几页依次讲。
课件里的坑
- [读图提醒] QC 页写「recognized by a majority」。实际要 n−f = 2f+1 个,超过三分之二,比「过半」更严(p.6)。
- [读图提醒] 对比页写「New-view only happens in view-change phase」,和时间线图里每个视图第一步都是 New-View 矛盾。原论文是每进入一个新视图(包括第一个)都发 New-View(p.8,对照 p.4、p.9)。
- [口径存疑] 创新页写 Chain Quality 是「每 3 轮强制换一次 leader」。原论文没有这条规则,只说 leader 频繁轮换有助于 chain quality。考试按课件写(p.3)。
- [口径提醒] 课件写换 leader 从 O(n³) 降到 O(n²)。原论文表格里单次换 leader 是 PBFT O(n³)、HotStuff O(n);O(n²) 是连续多个 leader 出错时的口径。考试按课件写(p.2、p.13)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先合上页面,默写四个阶段和每阶段副本做的事;再算一遍 n = 4 时每轮几张票、消息几条;然后读完整例题,最后做变式题。
必背
- HotStuff:BFT 状态机复制,部分同步,n = 3f+1,每轮等 n−f = 2f+1 票
- QC = type + viewNumber + sig,sig 是 n−f 个部分签名合成的门限签名;VoteMSG = type + node + partialSig
- 星形拓扑:票只发给 leader,leader 广播 QC;正常流程 O(n²) → O(n),换 leader O(n³) → O(n²)(课件口径)
- 四阶段:New-View → Prepare → Precommit(存 prepareQC)→ Commit(设 lockedQC)→ Decide(执行 B 及未执行祖先),三轮投票
- leader 轮换:第 v 个视图的 leader = v mod N;收到最先到的 n−f 个响应就往下走(Optimistic Responsiveness)
课件例题
例 1(课件 p.4–5):n = 4 的星形时间线
f = 1,n = 4。按时间线写出一个视图里每个阶段谁发给谁、副本做什么,quorum 是几?
提示
奇数步是 leader 发给全体,偶数步是副本投票给 leader。
解答
quorum = 2f+1 = 3。New-View:副本把最高 prepareQC 发给 leader。Prepare:leader 发提案 B。Prepare-Vote:副本投票。Precommit:leader 发 prepareQC,副本存下。Precommit-Vote:投票。Commit:leader 发 precommitQC,副本设 lockedQC。Commit-Vote:投票。Decide:leader 发 commitQC,副本执行 B 及未执行的祖先。
例 2(课件 p.9):R1 当 leader 的四阶段
R1 是 leader,R2–R4 是副本。每个阶段 R1 要等几张票才能进入下一阶段?票里装的是什么?
提示
看 VoteMSG 的三个字段。
解答
每阶段等 3 张(可以含 R1 自己的一票)。每张票是一条 VoteMSG,含类型、投票节点编号和部分签名。R1 把 3 个部分签名合成该阶段的 QC 再广播。
例 3(课件 p.10–11):Replica 3 恶意时的一个视图
见下方完整例题。
例 4(课件 p.24):两种消息模式对比
PBFT 和 HotStuff 每阶段的消息模式和复杂度各是什么?
提示
想一下每张票发给几个人。
解答
PBFT 全员互发,每阶段 O(n²)。HotStuff 票交给 leader、leader 广播 QC,每阶段 O(n)。
完整例题
题目:f = 1,n = 4,Replica 3 是恶意节点,从头到尾不投票。leader 能否完成这个视图?写出每阶段的票从哪来。(课件 p.10–11)
约定:leader 自己也投一票;课件里的副本叫 Replica 1、Replica 2、Replica 3。
解法:
第一步,New-View。副本把各自最高的 prepareQC 发给 leader,leader 选出最高的作为 justify。
第二步,Prepare。leader 广播提案。leader 自己一票,加 Replica 1、Replica 2 各一票,共 3 票,合成 prepare_QC。Replica 3 没投,不影响。
第三步,Precommit。leader 广播 prepare_QC,副本存下。Replica 3 仍然不回,另外 3 票照样凑齐,得到 pre-commit_QC。
第四步,Commit。leader 广播 pre-commit_QC,副本上锁,再凑 3 票得到 Commit_QC。
第五步,Decide。leader 把 Decide(commit_QC) 发给所有人,副本执行区块。
要点:每轮只要 n−f = 3 票,一个坏节点沉默拖不住进度。
答题格式:先写 f、n、quorum 三个数,再按阶段逐行写「谁投票 → 几票 → 得到哪张 QC」,最后一句结论。
变式题(先自己做)
1. n = 7,Replica 5 和 Replica 6 都不投票,leader 是 0 号。每轮要几张票?这个视图能走完吗?如果再多一个节点不投呢?(改编自课件 p.10–11)
提示
先由 n = 3f+1 求 f,再看诚实且在线的节点够不够 2f+1。
判分点与答案(非官方评分标准)
7 = 3 × 2 + 1,f = 2,每轮要 5 票。剩下 5 个节点(含 leader)正好凑够,能走完。再多一个不投就只剩 4 票,凑不出 QC,视图卡住,超时后换 leader。卡住不会出错,只是暂时不前进(p.4、p.10–11)。
2. 自编情境:N = 4,2 号节点是坏人,每次轮到它就不发提案。从视图 4 走到视图 11,一共有几个视图被它拖住?
提示
用 v mod 4 = 2 找出轮到 2 号的视图。
判分点与答案(非官方评分标准)
视图 4 到 11 里,v mod 4 = 2 的是视图 6 和视图 10,共 2 个。其余 6 个视图由别的节点当 leader,正常推进。判分点:会用 v mod N 算 leader;说出坏 leader 只拖慢自己那个视图。
闪卡自测
1. HotStuff 假设什么网络模型?
部分同步:网络最终会稳定,消息能在有限时间内送到(p.2)。
2. 容忍 f 个拜占庭节点要几个节点?每轮等几票?
n = 3f+1 个节点,每轮等 n−f = 2f+1 票(p.2、p.4)。
3. QC 有哪几个字段?
type、viewNumber、sig,sig 是 n−f 个部分签名合成的门限签名(p.6)。
4. 投票消息 VoteMSG 有哪几个字段?
type、node、partialSig(p.7)。
5. 课件说的 HotStuff 三项创新是什么?
线性换 leader(Linear View Change)、乐观响应(Optimistic Responsiveness)、Chain Quality(p.3)。
6. Precommit、Commit、Decide 三个阶段副本各做什么?
Precommit 存 prepareQC,Commit 设 lockedQC,Decide 执行区块和未执行的祖先(p.4–5)。
7. 第 v 个视图的 leader 怎么算?
v mod N(p.8)。
8. 正常流程的消息复杂度从多少降到多少?
PBFT 的 O(n²) 降到 HotStuff 的 O(n)(p.2、p.24)。
9. 为什么任意两组 2f+1 票里一定有诚实节点?
两组至少重叠 (2f+1) + (2f+1) − (3f+1) = f+1 个,坏节点最多 f 个(p.4、p.6)。
下一讲
下一页是 L10b 换 leader:新 leader 只挑最高的那张 QC:leader 坏了,新 leader 怎样不翻日志、只看 QC 就接着干。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。