L09b PBFT 正常操作:五个阶段、三道门槛,凑不满票就停
主节点没出事时,一笔请求走 Request、Pre-prepare、Prepare、Commit、Reply 五步;副本两次凑满 2f+1 个匹配票才执行,客户端等 f+1 个相同回复;票凑不满就停住,保安全性、暂丢活性。
一句话版
主节点给请求排号,所有副本两轮互相投票,每轮凑满 2f+1 个一致的票才往下走,客户端收到 f+1 个一样的回复就采信。票凑不满,大家就停在原地,不会记错账。
先认识这几个词
读之前最好先懂上一页的 3f+1、摘要和 8 种消息。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 匹配票 | matching messages | 视图号、序号、摘要三项都一样的消息,才算投给同一件事 |
| prepared | 读「准备好了」 | 某副本已凑满 2f+1 个匹配 prepare,确认这个序号上就是这个操作 |
| 法定人数 | quorum | 一个决定至少要凑齐几票,PBFT 里是 2f+1 |
| 投票交集 | quorum intersection | 任意两组法定人数里必然有共同成员 |
| 安全性 | safety | 坏事永远不发生,比如两个诚实副本记了不同的账 |
| 活性 | liveness | 好事终究会发生,比如请求最后会被执行 |
| O(n²) | 读「n 方量级」 | 消息数大约跟副本数的平方成正比 |
一个类比:两轮电话会
四家分行要把 Alice 的转账记成一样的账,其中一家可能是内鬼。
值班经理一分行把这笔编为「第 n 笔」,通知其他三家。其他分行不直接照记,每家先给所有人打一轮电话:「我收到的第 n 笔是 Alice 转 Bob,你那边呢?」凑够 3 家说法一致(含自己),这家才把它写进预备栏。
预备栏还不算数。每家再打第二轮电话:「我的预备栏写好了。」又凑够 3 家,才正式入账,给 Alice 发回执。
Alice 也不全信。四张回执里只要有 2 张内容一样,她就知道至少一张来自老实分行。
要是有一家沉默、另一家又乱说,谁都凑不够 3 家,那就干脆不记,等下一轮再说。
类比在哪里失效:
- 电话是一对一打的,协议里每一轮是所有副本同时群发,人一多消息量涨得很快。
- 类比里的经理是固定的,协议里经理不干活会被换掉,那是下一页的内容。
从零讲起
1. 五个阶段:一笔请求怎么走完
它解决什么问题
主节点没出事时,要让所有诚实副本按同一顺序执行同一个操作。难点在于主节点自己也可能是叛徒,它能给不同副本发不同内容;backup 里也可能藏着叛徒。
直觉
主节点只管排号。排完号,副本们要两次「对口供」:第一次确认大家收到的是同一件事,第二次确认大家都已经确认过了。两次都过了才动手执行。
一步一步看
目标:看一笔请求怎样走完五个阶段,有一个叛徒时诚实副本是否仍执行同一个操作。
f = 1,四个副本。Alice 是客户端,R1 是主节点,R2、R3 诚实,R4 是叛徒。
-
Request:Alice 把操作 X 发给主节点 R1。
-
Pre-prepare:R1 给 X 排上序号 n,把 PRE-PREPARE 群发给 R2、R3、R4。这一阶段只有主节点在发。
-
Prepare:每个副本向其他所有副本群发 PREPARE。R1、R2、R3 投 Yes,R4 投 No。诚实副本各数到 3 个匹配票,进入 prepared。
-
Commit:再全员群发一轮 COMMIT。诚实副本各收到 3 个 Yes、1 个 No,凑够 3 票,执行 X。
-
Reply:各副本把结果回给 Alice。R1、R2、R3 结果相同,R4 回了个错的;Alice 收到 2 个相同的就采信。
怎么算
数一轮 Prepare 有多少条消息。每个副本都要发给其余所有副本:
- 发消息的副本:n 个
- 每个副本发给:n − 1 个
- 一轮总数:n(n − 1)
- n = 4 时:4 × 3 = 12 条
意思是:副本数翻一倍,每轮消息数大约翻两番,所以量级写成 O(n²)。Commit 轮同样是 n(n − 1) 条。
上一讲的 OM 算法消息量随叛徒数指数增长,PBFT 的 n² 涨得慢得多,这正是名字里「实用」的来由。
常见误解
误解:主节点发了 pre-prepare,副本照着执行就行
主节点自己可能就是叛徒,它能给不同副本发不同内容。副本要先在 Prepare 轮互相对一遍摘要,确认大家收到的是同一件事,才敢往下走。
误解:课件说主节点也发 PREPARE,原论文也这么写
原论文里主节点不发 PREPARE,副本的条件是「pre-prepare 加 2f 个来自不同 backup 的匹配 prepare」。两种数法都是凑满 2f+1 票,结论一样。答题按课件写,被问原论文细节写后一种。
试一下
五个阶段里,哪一个阶段只有主节点在发消息?n = 7 时一轮 Prepare 最多几条消息?
Pre-prepare。Request 由客户端发,Prepare 和 Commit 是全员互发,Reply 是各副本发给客户端。n = 7 时 7 × 6 = 42 条。
2. 为什么门槛是 2f+1:投票交集
它解决什么问题
副本要凑几票才敢相信「这个序号上就是 X」?票数太少,叛徒能拉出两伙人,一伙认 X、一伙认 Y。门槛要高到两伙人不可能同时凑齐。
直觉
两组人只要有共同成员,而共同成员里至少有一个老实人,就不可能各认一个值。老实人对同一个序号只投一票,他不会既投 X 又投 Y。
所以门槛要让任意两组的交集里,扣掉所有叛徒之后还剩至少一个人。
一步一步看
目标:看门槛定在 2f+1 时,任意两组投票者为什么不可能各认一个值。
-
f = 1,四个副本。R2 手上数票:R1 的 pre-prepare、自己、R3 的 PREPARE(X, h) 都匹配,R4 投 No 不算。
-
3 票够 2f+1 = 3,R2 进入 prepared。
-
换个角度看为什么够。设一组是 {R1, R2, R3},另一组是 {R2, R3, R4},两组重叠 R2、R3 两个。
-
叛徒最多 1 个,重叠的 2 个里至少 1 个诚实,它不会同时投 X 和 Y。所以两组不可能各认一个值。
-
换成更大的 f,规律不变:
f 副本数 3f+1 门槛 2f+1 两组至少重叠 扣掉 f 个叛徒还剩 1 4 3 2 1 2 7 5 3 1 3 10 7 4 1
怎么算
两组各 2f+1 个人,塞进 3f+1 个位置里,至少有多少人被数了两次:
- 两组人数相加:2(2f+1) = 4f + 2
- 总共只有:3f + 1 个副本
- 至少重叠:(4f + 2) − (3f + 1) = f + 1
- 扣掉最多 f 个叛徒:(f + 1) − f = 1
意思是:两组的交集里永远至少有 1 个诚实副本,冲突的两个值凑不齐两组。
常见误解
误解:VR 的过半交集已经够用了
VR 里两个过半集合只保证共享 1 个节点。崩溃故障下它会如实报告;有叛徒时,这一个可能正好是叛徒,它对两组各说一套,两组就能各认一个值。PBFT 把门槛抬到 2f+1,就是为了让交集里多出一个诚实的人。
误解:凑满 2f+1 个 PREPARE 就可以执行了
prepared 只说明在当前视图里,大家对这个序号没有分歧。主节点一换,这个结论可能丢。多走一轮 COMMIT 是为了让已执行的操作在换主节点后还在,后面专门用反例讲。
试一下
f = 4 时副本数和门槛各是几?两组至少重叠几个?
副本 3 × 4 + 1 = 13 个,门槛 2 × 4 + 1 = 9。两组至少重叠 2 × 9 − 13 = 5 个,扣掉 4 个叛徒还剩 1 个诚实。
3. 客户端只等 f+1 个相同回复
它解决什么问题
客户端收到好几个回复,有的可能是叛徒伪造的。它要判断什么时候可以相信结果,又不想傻等所有人。
直觉
副本之间已经凑过两轮 2f+1,结果本身是靠得住的。客户端只需要确认「这个结果至少有一个老实人背书」。
叛徒最多 f 个,最多造出 f 张一样的假回执。只要凑到 f+1 张一样的,里面一定混着真的。
一步一步看
目标:看客户端为什么凑到 f+1 张相同回复就能采信,不必等所有人。
-
f = 1,四个副本都给 Alice 回复。R1、R2、R3 回 r,R4 回了个错的 r’。
-
R1、R2 的回复先到,两张一样,凑够 f+1 = 2 张。
-
叛徒最多 1 个,两张一样的回复里至少一张来自诚实副本,Alice 采信 r。
-
R3 的回复晚到也没关系;R4 的 r’ 只有一张,凑不成 2 张,被忽略。
怎么算
- 最多的假回复:f 张
- 需要的相同回复:f + 1 张
- f + 1 张里诚实的至少有:(f + 1) − f = 1 张
意思是:客户端的门槛比副本之间低,因为它只要一个老实人背书,不用防两伙人分歧。f = 1 等 2 张,f = 2 等 3 张。
常见误解
误解:客户端也要等 2f+1 个回复
2f+1 是副本之间防分歧用的门槛。客户端只问一件事:这个结果有没有诚实副本背书。f+1 个相同回复已经能保证这一点。
试一下
f = 2,客户端已经收到 3 张回复:两张 r、一张 r'。能采信吗?
不能。f + 1 = 3,相同的只有 2 张。两张 r 可能都来自叛徒,得再等一张 r。
4. 凑不满就停:安全性与活性
它解决什么问题
前面讲的都是票凑得够的情况。要是有副本沉默、又有叛徒捣乱,票凑不够,协议怎么办?硬着头皮往下走可能记错账,停下又可能一直卡住。PBFT 需要一个明确的取舍。
从哪来(补充)
安全性(safety)和活性(liveness)这两个词由 Lamport 在 1977 年的论文《Proving the correctness of multiprocess programs》里提出,借自 Petri 网理论。1985 年 Alpern 和 Schneider 给出了形式定义。一句话记:安全性是「坏事不发生」,活性是「好事终会发生」。
出处:Wikipedia: Safety and liveness properties
直觉
两种性质会打架。一直等下去,账永远不会记错,可是请求可能永远办不完;不等就往下走,请求办完了,账却可能记错。
PBFT 选前者:凑不满就停。停住只是暂时丢了活性,换主节点或重传之后还能接着走;记错的账可就改不回来了。
一步一步看
目标:看一轮里票凑不满时 PBFT 怎么处理,安全性和活性各自保没保住。
-
f = 1,四个副本。R1 发出 PRE-PREPARE 后,R2 发了匹配的 PREPARE(X, d),R3 沉默,R4 发了摘要冲突的 PREPARE(X, d’)。
-
以 R1 为例,匹配 (X, d) 的只有自己的 pre-prepare 和 R2 的 prepare,2 票不到 3,进不了 prepared。
-
进不了 prepared,就不发 COMMIT,也不回复客户端。这一轮停住。
-
结果对照:
性质 这一轮 原因 安全性 保住 没有任何副本执行 X,自然不会有人记错 活性 暂时丢失 请求没办完,要靠重传或视图切换继续
怎么判断
判断一轮会不会停住:数「没投对票的副本」有几个。沉默的和乱投的都算。
- 不超过 f 个:诚实的票还够 2f+1,照常往下走
- 超过 f 个:凑不满 2f+1,停住,安全但不前进
意思是:f 是协议能容忍的「坏票预算」,一个诚实副本沉默也会占用这份预算。
常见误解
误解:R3 是诚实的,它沉默不该算故障
协议分不清「沉默」是因为叛变还是网络慢,只看收到几票。R3 沉默加上 R4 乱投,两个副本没投对,超出了 f = 1 的预算,所以停住。
误解:停住说明协议出错了
停住是协议故意的选择,账一笔都没记错。PBFT 宁可暂时不前进,也不提交错的。
试一下
f = 1,R4 是叛徒乱投,R2、R3 都按时投了匹配票。这一轮会停吗?
不会。没投对的只有 R4 一个,没超出 f = 1。R1、R2、R3 三票正好是 2f + 1 = 3。
把它们串起来
主节点排号之后,副本们走两轮全员群发:Prepare 确认大家收到的是同一件事,Commit 确认大家都确认过了。每轮门槛都是 2f+1。
这个门槛来自投票交集。两组 2f+1 在 3f+1 个副本里至少重叠 f+1 个,叛徒最多 f 个,交集里总有一个老实人,冲突的值凑不齐两组。
客户端站在最外面,只要 f+1 个相同回复,确认有老实人背书就行。两轮全员互发的代价是 O(n²) 条消息,比 OM 的指数增长省得多。
票凑不满时,副本停在原地,安全性保住,活性暂时丢掉。主节点自己作恶或宕机导致的停顿,要靠下一页的视图切换解决。
课件里的坑
- [与原论文口径不同] p.13 写每个副本(含主节点 R1)都发 PREPARE,凑满 2f+1 个匹配 prepare 就 prepared。Castro & Liskov 原论文里主节点不发 PREPARE,条件是「pre-prepare + 2f 个来自不同 backup 的匹配 prepare」。两种数法都是凑满 2f+1 票,答题按课件写,被问原论文细节写后者(p.13)。
- [符号不一致] p.14 的 PREPARE(X, d) 和 PREPARE(X, d’) 里,d 是消息摘要,和 p.12 消息格式里的 h 同义;p.11 却把 d 定义成签名(p.11、p.14)。
- [读图提醒] p.13 Reply 一栏写「客户端等 f+1 个结果相同的回复」,图里是 4 个回复里的 2 个。2 是 f+1,不是过半(p.13)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先合上页面,默写五个阶段和三道门槛(f = 1 时各是几);再用两组投票的交集讲清为什么是 2f+1;然后对着完整例题画一遍四个副本的消息流,最后做变式题。
必背
- 正常操作五个阶段:Request → Pre-prepare → Prepare → Commit → Reply,只有 Pre-prepare 由主节点单独群发
- 三道门槛:2f+1 个匹配 prepare 才 prepared,2f+1 个匹配 commit 才执行,客户端等 f+1 个相同回复;f = 1 时是 3、3、2
- 两组 2f+1 在 3f+1 个里至少重叠 f+1 个,其中至少 1 个诚实,所以冲突的值凑不齐两组
- Prepare、Commit 两轮全员互发,每轮最多 n(n − 1) 条,量级 O(n²)
- 客户端等 f+1 个相同回复:最多 f 个是假的,f+1 个里至少 1 个来自诚实副本
- 票凑不满就停住不提交:丢活性、保安全性
- 5 个节点撑不住 f = 2:要么凑不够 5 票卡死,要么降门槛后交集只剩 1 个、可能出错;至少要 7 个
课件例题
例 1(课件 p.13):f = 1 时的正常操作
见下方完整例题。
例 2(课件 p.14):凑不够 2f+1 个匹配 PREPARE
f = 1,4 个副本。R1 发出 PRE-PREPARE 后,R2 发了匹配的 PREPARE(X, d),R3 沉默,R4 发了摘要冲突的 PREPARE(X, d’)。R1 能进 prepared 吗?这一轮结果如何?
提示
只数摘要都是 d 的票,主节点自己的 pre-prepare 也算一票。
解答
以 R1 为例,匹配 (X, d) 的只有自己的 pre-prepare 和 R2 的 prepare,2 票,不到 2f+1 = 3。进不了 prepared,Commit 也进不去,本轮不回复客户端,可能要重传或视图切换。
一个诚实副本沉默,加上一个叛徒捣乱,相当于两个副本没投对票,超出了 f = 1 的预算。系统停住,但没有出错:安全性保住,活性暂时丢失。
例 3(课件 p.20,Exercise 2):5 个节点能扛 f = 2 吗
5 个节点,R4、R5 是拜占庭副本,主节点 R1 已把 PRE-PREPARE 发给 R2 到 R5。PBFT 能正常执行吗?
提示
先查 3f+1 够不够;再分别试 2f+1 门槛和「去掉 f 个后剩下的人数」这个更低的门槛。
解答
f = 2 要 3f+1 = 7 个,5 < 7,前提不满足;5 个节点最多扛 ⌊(5 − 1)/3⌋ = 1 个。
照 f = 2 的门槛,每轮要 2f+1 = 5 票,等于全员。R4、R5 只要有一个不投或乱投,诚实的 R1、R2、R3 最多 3 票,永远进不了 prepared,客户端也等不到 f+1 = 3 个相同回复:活性丢失。
把门槛降到 n − f = 3:两组 3 个在 5 个里只保证重叠 2 × 3 − 5 = 1 个,它可能就是 R4 或 R5,两组能认定冲突的值:安全性丢失。所以 5 个节点要么卡死,要么可能出错。
完整例题
题目(课件 p.13):f = 1,4 个副本。Alice 是客户端,R1(Branch-I)是主节点,R2、R3 诚实,R4 是拜占庭副本,在 Prepare 轮投反对票。按五个阶段写出消息流,标出每道门槛凑到几票,并算出 Prepare 一轮最多有几条消息。
解:
第一步 Request。Alice 把操作 X 发给 R1:⟨REQUEST, o, t, c⟩。
第二步 Pre-prepare。R1 给 X 分配序号 n,把 ⟨⟨PRE-PREPARE, v, n, h⟩, m⟩ 多播给 R2、R3、R4。
第三步 Prepare。每个副本(课件口径含 R1)向其他所有副本多播 ⟨PREPARE, v, n, h, i⟩。R1、R2、R3 投 Yes,R4 投 No。每个诚实副本手上有 3 个匹配的 prepare,正好 2f+1,进入 prepared。
第四步 Commit。每个副本多播 ⟨COMMIT, v, n, h, i⟩。诚实副本各收到 3 个 Yes、1 个 No,3 = 2f+1,执行 X。课件页底红字:正确副本只有收到 2f+1 个匹配的 COMMIT 后才执行。
第五步 Reply。各副本把 ⟨REPLY, r, i⟩ 发给 Alice。R1、R2、R3 结果相同,Alice 收到其中 2 个(f+1)就采信,R4 的错回复被忽略。
消息量:Prepare 轮每个副本发给另外 3 个,n(n − 1) = 4 × 3 = 12 条;Commit 轮同样 12 条。两轮都是全员互发,量级 O(n²)。
一句话结论:一个叛徒最多拉走 1 票,剩下 3 票正好够 2f+1,三道门槛 3、3、2 全部照常通过(p.13)。
变式题(先自己做)
1. 7 个副本跑 PBFT,R1 是主节点,R6、R7 是拜占庭副本。(a) Prepare、Commit、Reply 三道门槛各是几?(b) 如果诚实的 R5 又因网络故障沉默,这一轮还能执行吗?(改编自课件 p.14、p.20)
提示
先由 7 = 3f+1 求出 f;(b) 只数诚实且在线的副本。
判分点与答案(非官方评分标准)
(a) 7 = 3 × 2 + 1,f = 2。Prepare、Commit 各要 2f+1 = 5 个匹配票,客户端等 f+1 = 3 个相同回复。判分点:先求出 f,三个数各对一个。
(b) 在线的诚实副本只剩 R1 到 R4 共 4 个,R6、R7 不投或乱投,匹配票最多 4 < 5,进不了 prepared,本轮不执行、不回复。判分点:数出 4 票并和 5 比较,说出「停住但不出错」。这和例 2 一样是丢活性、保安全性,要等 R5 回来、重传或视图切换才能继续。
闪卡自测
1. 五个阶段的顺序?
Request → Pre-prepare → Prepare → Commit → Reply(p.9、p.13)。
2. f = 1 时 prepare、commit、reply 三道门槛各是几?
3、3、2(p.13)。
3. 为什么两组 2f+1 不能各自认定冲突的值?
两组在 3f+1 个里至少重叠 f+1 个,其中至少 1 个诚实,诚实副本对同一序号只投一个值(p.13)。
4. 客户端为什么只等 f+1 个相同回复?
最多 f 个回复是假的,f+1 个相同回复里至少 1 个来自诚实副本(p.13)。
5. 例 2 里 R1 为什么进不了 prepared?
R3 沉默、R4 摘要冲突,匹配的只有自己和 R2 两票,不到 3 票(p.14)。
6. 票凑不满时,丢的是安全性还是活性?
活性。停住不提交,安全性保住(p.14)。
7. 5 个节点最多能扛几个拜占庭副本?
1 个;扛 2 个至少要 7 个节点(p.20)。
8. PBFT 的消息量是什么量级?为什么?
O(n²):Prepare、Commit 两轮都是每个副本发给其他所有副本(p.13、p.23)。
下一讲
下一页是 L09c PBFT 视图切换:主节点靠不住就换人,Commit 保证换届不丢账。带着问题读:prepared 已经能防同一视图里的分歧,为什么还要多走一轮 Commit?
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。