L09a PBFT 的舞台:为什么要 3f+1 台机器,谁在台上,说哪几种话
PBFT 开场三件事:消息靠摘要和签名防篡改冒名;容忍 f 个会撒谎的副本至少要 3f+1 个;主节点、backup、客户端三类角色,正常操作、视图切换、检查点三个子协议,一共 8 种消息。
一句话版
几台机器各存一份账,其中可能有几台会撒谎。PBFT 先把规矩定好:要扛住 f 个撒谎的,至少摆 3f+1 台;一台当主节点排号,其余投票;大家只用 8 种固定格式的消息说话。
先认识这几个词
读之前最好先懂:上一讲的拜占庭将军问题(叛徒会对不同人说不同的话),以及 VR 里的主节点和视图。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| PBFT | Practical Byzantine Fault Tolerance,实用拜占庭容错 | 在混有叛徒的副本之间达成一致、消息量又不爆炸的复制协议 |
| 拜占庭故障 | Byzantine fault | 节点不只会宕机,还会发假消息、对不同人说不同的话 |
| f | 读「f」,faulty | 最多允许几个副本同时作恶 |
| 副本 / 主节点 / backup | replica / primary | 每个副本存一份账;主节点负责接请求、排号,其余副本叫 backup |
| 摘要 | digest,课件写作 h(有时写 d) | 一条消息算出来的短指纹,比指纹就知道内容是否相同 |
| 签名 | signature | 证明「这条消息确实是某某发的」,别人冒充不了 |
| 子协议 | subprotocol | PBFT 拆成三套流程,不同情况跑不同的一套 |
一个类比:四家分行合记一本账
银行有四家分行,每笔转账都要四家记成一模一样的账。麻烦在于其中一家可能是内鬼,它会对不同分行说不同的话。
先得定几条规矩。第一条,开几家分行才压得住一个内鬼?答案是四家,三家不够,后面会算给你看。
第二条,谁来排号。本周由一分行当值班经理,客户 Alice 的转账先交给它,它编好「第几笔」再通知其他三家。
第三条,说话用固定格式。每条通知都附一串指纹,大家一比指纹就知道收到的是不是同一笔;每条通知都签名,内鬼没法冒充别家说话。
第四条,按情况分三种流程。平常照常记账;值班经理不干活就换人;账记多了,定期封存,旧票据扔掉。
类比在哪里失效:
- 真实的内鬼查出来会被开除;协议不追查谁作恶,只靠人数把它压住。
- 分行之间打电话是一对一的,协议里的消息常常是一个副本同时发给其他所有副本。
从零讲起
1. 先补一块:摘要和签名(补充)
它解决什么问题
副本之间要反复确认「我们说的是同一笔交易」。把整条请求一遍遍转发太占地方,也没法证明是谁说的。
摘要解决「内容是不是同一条」,签名解决「消息是不是这个人发的」。PBFT 的每种消息都带着这两样东西。
直觉
摘要像一条消息的指纹。消息改一个字,指纹就完全变样;两条消息指纹相同,就当它们是同一条。
签名像盖章。章只在发送者自己手里,别人拿到消息也盖不出同样的章,所以内鬼没法冒充老实分行说话。
一步一步看
目标:看两个副本只交换摘要就能发现手里不是同一笔,以及签名怎样挡住冒充。
-
R2 收到 transfer(Alice → Bob, $1),用哈希函数算出摘要 h,课件写的例子是 0x9a4f 开头的一串值。
-
R3 收到的是被改过的 transfer(Alice → Cindy, $1),算出的摘要 h’ 跟 h 完全不同。
-
两个副本交换的只是 h 和 h’。一比,不一样,马上知道两人手里不是同一笔。
-
每条消息还带发送者的签名。R4 想冒充 R2 发一条假消息,签不出 R2 的签名,别人验签就会拒收。
怎么判断
拿到两条消息,判断它们是不是同一条:比摘要。摘要相同就当成同一条,不同就一定不是。
判断一条消息是谁发的:验签名。课件的消息表里每种消息都有「签名者」一栏,客户端签 Request,主节点签 Pre-prepare,其余消息由发送它的副本签。
常见误解
误解:有了签名,内鬼就没法捣乱了
签名只防冒名。内鬼用自己的名字照样能发假内容、对不同的人说不同的话,签名拦不住这个。压住它要靠后面的投票门槛。
误解:课件里 d 一会儿是签名、一会儿是摘要,两个是一回事
两个是不同的东西。课件在变量表里把 d 定义成签名,可是在失败例和检查点公式里又把 d 当摘要用。原论文用 d 表示摘要。读例题时把 d 当成摘要就行。
试一下
R2 和 R3 交换了摘要,结果一样。能说明 R2、R3 都诚实吗?
不能。摘要一样只说明两人手里的消息内容相同。至于这条消息本身对不对、它们后面会不会乱投票,摘要管不了。
2. 3f+1:扛住 f 个叛徒要几台机器
它解决什么问题
PBFT 要在「有副本会撒谎」的情况下照样记对账。第一个问题就是要摆几台机器。摆少了,叛徒能把结果带偏;摆多了,白白多花钱、还更慢。
从哪来(补充)
这个数字比 PBFT 早二十多年。1978 年 Robert Shostak 在 SRI 参与 NASA 的 SIFT 容错计算机项目时,把它形式化成 interactive consistency 问题,证明至少要 3n+1 台才能容忍 n 台出错。1982 年 Lamport、Shostak、Pease 发表《The Byzantine Generals Problem》,用将军和叛徒讲这个问题,名字由此而来。
1999 年 Castro 和 Liskov 的 PBFT 论文沿用 3f+1,并给出一个更直白的推导:等不齐所有人,回了的人里还可能有叛徒。下面的「一步一步看」就是这个推导。
出处:Wikipedia: Byzantine fault;Castro & Liskov 1999, Practical Byzantine Fault Tolerance
直觉
叛徒能干两件坏事:装死不回,或者回一个假的。协议没法分辨「不回的那个是叛徒还是网络慢」,只能把两种坏事都算进预算里。
所以要留出两份 f:一份给可能不回的,一份给回了但撒谎的。剩下的诚实回复还得比撒谎的多,才能多数说了算。
一步一步看
目标:用 n = 4、f = 1 走一遍,看只敢等 n − f 个回复时,诚实的为什么仍占多数。
-
设 n = 4、f = 1。最多 1 个副本可能永远不回,等它就会卡死,所以只敢等 n − f = 3 个回复。
-
没回的 R4 也许只是网络慢,真叛徒可能混在回了的人里,比如 R3。
-
回了的 3 个里,诚实的有 3 − 1 = 2 个,比叛徒的 1 个多。听多数的,结果就是对的。
-
换成 n = 3、f = 1 对照:只敢等 2 个,其中 1 个可能是叛徒,诚实 1 个对叛徒 1 个,听谁的都说不清。
怎么算
推导写成式子:
- 能等到的回复数:n − f
- 其中最坏有 f 个是假的,诚实的有:(n − f) − f = n − 2f
- 诚实的要多过假的:n − 2f > f,也就是 n > 3f
- n 取最小的整数:n = 3f + 1
意思是:机器数要比叛徒数的 3 倍再多 1 台。
反过来,已知有 n 个副本,最多能扛的叛徒数是 f = ⌊(n − 1)/3⌋。⌊ ⌋ 是向下取整,意思是把 (n − 1) 除以 3,小数部分直接扔掉。
| n(副本数) | 计算 | 最多扛几个叛徒 |
|---|---|---|
| 4 | ⌊3/3⌋ = 1 | 1 |
| 5 | ⌊4/3⌋ = 1 | 1 |
| 6 | ⌊5/3⌋ = 1 | 1 |
| 7 | ⌊6/3⌋ = 2 | 2 |
| 10 | ⌊9/3⌋ = 3 | 3 |
PBFT 在这个机器数下追求三个设计目标。Consistency:两个诚实副本永远不会提交不同的结果。Availability:有人作恶时照样能服务。Fault Tolerance:3f+1 个副本最多扛 f 个叛徒。
常见误解
误解:5 个副本总比 4 个多扛一个叛徒
⌊(5 − 1)/3⌋ = 1,5 个和 4 个都只能扛 1 个。想扛 2 个,得一口气加到 7 个。多出来的第 5、6 台只是让系统更慢,容错能力没变。
误解:副本越多越安全,干脆摆 100 台
原论文专门说过,副本多于 3f+1 只会拖慢性能,不提高容错。要多扛叛徒,得同时把 f 定得更大,机器数按 3f+1 跟着涨。
试一下
一个系统有 13 个副本,最多扛几个叛徒?要扛 5 个叛徒,最少要几个副本?
⌊(13 − 1)/3⌋ = 4 个。扛 5 个要 3 × 5 + 1 = 16 个副本。
3. 谁在台上:角色、三个子协议和 8 种消息
它解决什么问题
机器数定了,还要说清楚谁负责什么、出了状况走哪套流程、每一步发什么消息。PBFT 把这些全部写死,副本照章办事,叛徒就很难钻空子。
直觉
台上有三类角色。客户端是来办事的人;主节点是值班经理,接单、排号;backup 是其他分行,负责投票核对。
流程按情况分三套。平常走正常操作;怀疑值班经理坏了,走视图切换换人;账本太长了,走检查点封存旧账。每套流程用自己的几种消息,加起来一共 8 种。
一步一步看
目标:理清台上有哪三类角色、分哪三套流程,以及 8 种消息各属于哪一套。
-
分行场景里,Alice 是客户端,她要做两笔转账:op1 给 Bob $1,op2 给 Cindy $1。请求先交给主节点 Branch-I。
-
Branch-I 给请求排号,再和 Branch-II、III、IV 一起走投票流程。四家都是副本,各存一份交易日志。
-
一切正常时跑正常操作,五个阶段各一种消息。主节点出故障时跑视图切换,两种消息。定期跑检查点,一种消息。
-
每种消息的格式、谁发给谁、谁签名,列成下表:
消息 发送方 → 接收方 格式 属于 Request 客户端 → 主节点 ⟨REQUEST, o, t, c⟩ 正常操作 Pre-prepare 主节点 → 其余副本 ⟨⟨PRE-PREPARE, v, n, h⟩, m⟩ 正常操作 Prepare 副本 → 其余副本 ⟨PREPARE, v, n, h, i⟩ 正常操作 Commit 副本 → 其余副本 ⟨COMMIT, v, n, h, i⟩ 正常操作 Reply 副本 → 客户端 ⟨REPLY, r, i⟩ 正常操作 View change 副本 → 其余副本 ⟨VIEWCHANGE, v+1, n, s, C, P, i⟩ 视图切换 New view 新主节点 → 其余副本 ⟨NEWVIEW, v+1, V, O⟩ 视图切换 Checkpoint 副本 → 其余副本 ⟨CHECKPOINT, n, h, i⟩ 检查点
怎么判断
看到一种消息,先问它属于哪套流程。名字带 PREPARE、COMMIT、REQUEST、REPLY 的是正常操作;带 VIEW 的是视图切换;CHECKPOINT 单独一套。
再看字母。v 是视图号,n 是序号,h 是摘要,i 是发消息的副本,o、t、c 是操作、时间戳、客户端,r 是执行结果。课件例子里 n = 1050 表示系统里第 1050 笔交易,c = Alice123。
视图切换那两条消息的字母多一些。s 是最近的稳定检查点,C 是它的证书,P 是本副本手上的 prepared 证书,V 是新视图的证明,O 是新视图要接着处理的请求。这几个字母后面两页会细讲。
常见误解
误解:主节点权力最大,它说什么大家就记什么
主节点只负责排号。它自己可能就是叛徒,所以其余副本要在 Prepare、Commit 两轮里互相核对,凑够票才执行。主节点不干活,还会被视图切换换掉。
误解:New view 的签名栏写 Replica,所以是普通副本发的
New view 由新主节点发。新主节点本身也是副本,所以签名栏写 Replica。
试一下
⟨PREPARE, v, n, h, i⟩ 里,哪个字母能让收到的人确认「我们说的是同一笔交易」?哪个字母说明是谁投的票?
h 是摘要,比对 h 确认是同一笔。i 是副本标识,说明是谁投的票(再加上签名,别人冒充不了)。
把它们串起来
上一讲的 OM 算法能扛叛徒,可是消息量随叛徒数指数增长,还要求网络同步。VR 消息少,却只防宕机。
PBFT 先借来 3f+1 这个机器数。算法里每一步都只敢等 n − f 个回复,回了的里面还可能有 f 个叛徒,3f+1 保证诚实的永远占多数。
然后它照搬 VR 的骨架:一个主节点排号,坏了就换人。每条消息带摘要和签名,内容改不了,身份冒不了。
最后把所有情况分成三套子协议,用 8 种固定消息说话。下一页讲最常跑的那套:正常操作的五个阶段。
课件里的坑
- [前后不一致] p.10 写「v = 1:第一个当选的主节点」,p.15–17 的第一个视图却是 view 0。按 p.15 的公式 p = v mod n,第一个视图应是 view 0(p.10、p.15)。
- [符号不一致] p.11 把 d 定义为数字签名、h 为哈希,但 p.14 的 PREPARE(X, d) 和 p.18 的 d = H(State₁₀₀) 都把 d 当摘要用,原论文也用 d 表示摘要。读例题时把 d 理解成摘要(p.11、p.14、p.18)。
- [简写] p.12 的 Reply 格式 ⟨REPLY, r, i⟩ 是简化版,原论文是 ⟨REPLY, v, t, c, i, r⟩。p.10 的 m = ⟨t, c, o⟩ 和 p.12 的 ⟨REQUEST, o, t, c⟩ 字段顺序不同,只是写法差异(p.10、p.12)。
- [读图提醒] p.4 把 Hyperledger、Stellar、Ripple、NEO 列为 PBFT 的流行实现。更准确的说法是 PBFT 家族:NEO 用改良版 dBFT,Stellar、Ripple 用各自的共识协议,都不是原版 PBFT(p.4)。
- [历史口径] p.2 写 Paxos 1988 首次提出。常见说法是 1989 年左右写成技术报告、1998 年正式发表,答题写 1998 年正式发表不会错(p.2)。
- [拼写] p.10「Trsanction」应为 Transaction,不影响内容(p.10)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先合上页面,默写 3f+1 的四行推导和 ⌊(n − 1)/3⌋ 的换算表;再背出三个子协议各用哪几种消息;然后对着完整例题把一笔转账的消息字段填一遍,最后做变式题。
必背
- PBFT(Castro & Liskov 1999):3f+1 个副本容忍 f 个拜占庭故障,消息量 O(n²)
- 三个设计目标:Consistency(两个诚实副本不会提交不同结果)、Availability、Fault Tolerance
- n 个副本最多容忍 f = ⌊(n − 1)/3⌋ 个拜占庭副本:4、5、6 个都只扛 1 个,7 个扛 2 个
- 3f+1 的来历:只能等 n − f 个回复,其中仍可能有 f 个是假的,诚实的 n − 2f 个要多过 f 个
- 三个子协议:正常操作(Request → Pre-prepare → Prepare → Commit → Reply)、视图切换(View change → New view)、检查点
- 8 种消息:5 种属于正常操作,2 种属于视图切换,1 种属于检查点
- 摘要 h 保内容一致,签名保发送者身份;课件 p.11 把 d 记作签名,p.14、p.18 又把 d 当摘要用
课件例题
例 1(课件 p.6):n 个副本扛几个叛徒
f = 1、2、3 各要几个副本?反过来,4、5、6、7 个副本各能扛几个拜占庭副本?
提示
正着用 3f+1,反着用 ⌊(n − 1)/3⌋。
解答
f = 1 要 4 个,f = 2 要 7 个,f = 3 要 10 个。反过来,4、5、6 个副本都只扛 1 个,7 个扛 2 个。
例 2(课件 p.7–8):分行场景里的角色
四家分行 Branch-I 到 Branch-IV 各存一份交易日志。Alice 要转账给 Bob,请求先到 Branch-I。谁是客户端、主节点、backup?
提示
主节点负责接请求和排号,其余副本只参与投票。
解答
Alice 是客户端;Branch-I 是主节点(leader replica);Branch-II、III、IV 是 backup。四家都是副本,各存一份交易日志,比如 op1 是 Alice 给 Bob $1,op2 是 Alice 给 Cindy $1。
例 3(课件 p.9、p.12):八种消息各归哪个子协议
Request、Pre-prepare、Prepare、Commit、Reply、View change、New view、Checkpoint 这 8 种消息,各属于哪个子协议?三个子协议各在什么时候运行?
提示
正常操作有五个阶段,每个阶段一种消息。
解答
前 5 种属于正常操作,一切正常时运行;View change、New view 属于视图切换,检测到主节点故障时运行;Checkpoint 属于检查点,定期运行、丢弃旧日志。New view 由新主节点发出,格式是 ⟨NEWVIEW, v+1, V, O⟩。
完整例题
题目(课件 p.10–12 的变量例子):Alice 在 2025-08-04 10:00:00 发起转账 transfer(Alice → Bob, $1),客户端标识 Alice123。主节点 Branch-I 把它排为第 1050 笔,当前视图按 p.15 口径是 view 0。写出 Request、Pre-prepare、Prepare 三条消息的具体内容,并说明每条由谁签名。
解:
第一步,填变量。o = transfer(Alice → Bob, $1),t = 2025-08-04 10:00:00,c = Alice123。请求消息 m 就是这三项打包。主节点对 m 算出摘要 h = SHA256(m),课件例子是 0x9a4f 开头的一串值。
第二步,Request。Alice 发给主节点:⟨REQUEST, transfer(Alice → Bob, $1), 2025-08-04 10:00:00, Alice123⟩,由 Alice 签名。
第三步,Pre-prepare。Branch-I 发给 Branch-II、III、IV:⟨⟨PRE-PREPARE, v = 0, n = 1050, h⟩, m⟩,由主节点签名。外层只带摘要,原请求 m 附在后面。
第四步,Prepare。以 Branch-III 为例,i = Branch-III,它发给其他所有副本:⟨PREPARE, 0, 1050, h, Branch-III⟩,由 Branch-III 签名。收到的人只比 v、n、h 三项,就知道它说的是同一笔。
一句话结论:同一笔转账在三条消息里靠「v、n、h」三项对上号,靠签名分清是谁说的(p.10–12)。
变式题(先自己做)
1. (a) 一个系统要扛 4 个拜占庭副本,至少几个副本?(b) 现有 11 个副本,最多扛几个?再加 1 台变成 12 个呢?(c) 副本 R7 收到一条 ⟨COMMIT, 3, 88, h, R2⟩,说出每个字段的含义。(改编自课件 p.6、p.12)
提示
(b) 两次都按 ⌊(n − 1)/3⌋ 算,看加 1 台有没有用。(c) 对照 8 种消息表的格式。
判分点与答案(非官方评分标准)
(a) 3 × 4 + 1 = 13 个。判分点:用 3f+1,写成 12 扣分。
(b) ⌊10/3⌋ = 3 个;12 个时 ⌊11/3⌋ = 3 个,加 1 台没提高容错,要到 13 个才扛 4 个。判分点:两个数都对,说出「加 1 台没用」。
(c) COMMIT 属于正常操作;3 是视图号 v,88 是序号 n,h 是请求摘要,R2 是发送这票的副本 i。判分点:四个字段各一分。
闪卡自测
1. PBFT 是谁、哪年提出的?
Castro 和 Liskov,1999 年(p.2)。
2. PBFT 的三个设计目标是什么?
Consistency:两个诚实副本不会提交不同结果;Availability:有拜占庭行为时仍可用;Fault Tolerance:3f+1 个副本容忍 f 个拜占庭故障(p.6)。
3. 为什么 3 个副本扛不住 1 个叛徒?
只敢等 2 个回复,其中 1 个可能是叛徒,诚实 1 个对叛徒 1 个,分不出真假。
4. 6 个副本最多扛几个叛徒?
⌊5/3⌋ = 1 个,和 4 个副本一样(p.6)。
5. 三个子协议分别在什么时候运行?
一切正常时跑正常操作;怀疑主节点出故障时跑视图切换;定期跑检查点、丢弃旧日志(p.9)。
6. 8 种消息里哪些属于正常操作?
Request、Pre-prepare、Prepare、Commit、Reply 共 5 种(p.12)。
7. 摘要和签名各防什么?
摘要防内容被改、确认大家说的是同一条;签名防冒名、确认消息是谁发的(p.11)。
8. 分行场景里谁是主节点?
Branch-I,其余三家是 backup,Alice 是客户端(p.8)。
下一讲
下一页是 L09b PBFT 正常操作:五个阶段与三道门槛:主节点没出事时,一笔请求怎样走完 Request 到 Reply。带着问题读:副本要凑几票才敢执行,为什么偏偏是这个数?
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。