L07d OM 的代价与 PBFT 预告:消息一层层乘上去
按层数清 OM(m) 的消息量,看懂 (n−1)(n−2)…(n−k) 和 O(nᵐ) 从哪来;再读 PBFT 的五阶段图,数出 22 条箭头,记住 2f、2f+1、f+1 三个法定人数。
一句话版
OM(m) 每深一层递归,调用次数就要再乘一个人数,消息量是 O(nᵐ),m 稍大就用不起。PBFT 换了一种组织方式,每个阶段最多全员互发一次,消息量降到 O(n²)。
上一页讲了 OM 怎么跑,见 L07c。这一页算账,再预告一个能实际用的协议。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 调用次数 | number of calls | 某一层的小协议一共被跑了几次 |
| O(nᵐ) | n 的 m 次方量级 | 人数一多、叛徒一多,消息量连乘着涨 |
| PBFT | Practical Byzantine Fault Tolerance | 实用拜占庭容错,能在真实网络里跑的 BFT 协议 |
| 副本 | replica | PBFT 里参与共识的服务器,相当于将军 |
| 主节点 | primary | 负责给请求排序号的那个副本 |
| f | faulty | 最多允许几个副本是拜占庭的,对应前面的 m |
| 法定人数 | quorum | 推进到下一步之前,至少要收齐几份一致的消息 |
一个类比:传话游戏的账单
一个班 7 个人玩传话,规定每句话都要让其余人确认一遍。
老师先把话告诉 6 个同学。每个同学再把听到的转告其余 5 人。每个听到转告的人,又要把「谁跟我说了什么」再转告剩下 4 人。
人一多,这张转告的账单越拉越长。叛徒每多一个,就要多套一层转告,账单又得再乘一次。
类比在哪里失效:
- 传话游戏里大家只想传对话,OM 里还要防着有人故意传错。
- 真实的 OM 每条转述都是点对点私发的,不是当众说。
- PBFT 那一套没法用传话游戏类比,它靠的是「收够票再往下走」,下面单独讲。
从零讲起
1. 按层数消息:OM 的账怎么算
它解决什么问题
考试会问「OM 一共发多少条消息」。直接数箭头,n 稍大就数不过来。需要一个按层累加的算法:先算每层跑了几次小协议,再乘上每次发几条。
直觉
OM(m) 的递归像一棵树。最上面一层只有指挥官跑一次 OM(m)。第二层,每位副官各跑一次 OM(m−1)。第三层,每个 OM(m−1) 里的每位接收者又跑一次 OM(m−2)。
每一层的小协议里,当指挥官的人要给剩下所有副官各发一条。剩下几人,每往下一层就少一个。
一步一步看
目标:拿 n = 7、m = 2 按层累加,算出 OM 一共发多少条消息。
-
最上层 OM(2):调用 1 次。指挥官发给 6 位副官,共 1 × 6 = 6 条。
-
第二层 OM(1):每位副官各当一次指挥官,共 6 次。每次发给其余 5 位副官,共 6 × 5 = 30 条。
-
第三层 OM(0):每个 OM(1) 有 5 位接收者,各跑一次 OM(0),共 6 × 5 = 30 次。每次发给剩下 4 人,共 30 × 4 = 120 条。
-
合计 6 + 30 + 120 = 156 条,跑了 3 层,也就是 3 轮。
怎么算
OM(m−k) 被调用的次数:
(n−1)(n−2)…(n−k)
意思是:往下走 k 层,就把 n−1、n−2 一直乘到 n−k,一共乘 k 个数。k = 0 时是空乘积,调用 1 次。
每次 OM(m−k) 发的消息数:
n−1−k
意思是:第 k 层的小协议里,还剩 n−1−k 个人没当过这一路的指挥官,每人收一条。
总消息数 = 把 k 从 0 到 m 的「调用次数 × 每次消息数」全加起来。用 n = 4、m = 1 验算:1 × 3 + 3 × 2 = 9。
常见误解
以为每层的调用次数都是 n−1
只有第二层是 n−1 次。再往下,每次要乘的人数少一个:n−1,再乘 n−2,再乘 n−3。n = 7 时第三层是 6 × 5 = 30 次。
把 n−1−k 写成 n−k
第 k 层的小协议里,已经有 k+1 个人当过这一路的指挥官,剩下 n−1−k 人。k = 0 时就是指挥官发给 n−1 位副官。
试一下
n = 4、m = 1,用按层的方法算出总消息数。
OM(1) 调用 1 次,发 3 条;OM(0) 调用 3 次,每次发 2 条,共 6 条。合计 3 + 6 = 9 条。
2. 为什么是 O(nᵐ)
它解决什么问题
算出具体数字以后,还要能说出它的增长量级。课件把这个量级写成 O(nᵐ),并说它「Expensive → impractical」。这一节解释这个量级从哪来。
直觉
最深一层 OM(0) 的调用次数,是 m 个数连乘:(n−1)(n−2)…(n−m)。每个数都和 n 差不多大,所以连乘起来大约是 n 的 m 次方。
叛徒数 m 出现在指数上。人数翻倍时,消息量要翻 2 的 m 次方倍。
一步一步看
目标:比较三组 n、m 的消息总数,看最深一层怎样决定 O(nᵐ) 的量级。
-
n = 4、m = 1:只有两层,3 + 6 = 9 条。
-
n = 7、m = 2:三层,6 + 30 + 120 = 156 条。
-
n = 10、m = 3:四层,9 + 72 + 504 + 3024 = 3609 条。
-
把三个结果放在一起看:人数从 4 涨到 10,消息量从 9 涨到 3609。
-
每个例子里,最后一层都占了大头:120 占 156 的大部分,3024 占 3609 的大部分。最深一层的调用次数决定量级。
怎么算
老师在课件上写的是:令 k = m,OM(0) 被调用 (n−1)(n−2)…(n−m) 次,约等于 nᵐ。
意思是:只看最深一层就能估出量级。m 个接近 n 的数相乘,约等于 n 的 m 次方。
用 n = 10、m = 3 核对:9 × 8 × 7 = 504 次 OM(0),每次发 6 条,共 3024 条,和 10³ = 1000 同一个量级的几倍。
常见误解
以为 O(nᵐ) 是多项式,所以也还好
m 固定时它是 n 的多项式,但 m 通常跟着 n 一起涨。OM 要求 n ≥ 3m+1,最大的 m 接近 n 的三分之一,此时指数也在变大,增长比任何固定次数的多项式都快。
试一下
n = 10、m = 3 时,OM(1) 被调用几次?每次发几条?
OM(1) 是第 k = 2 层,调用 9 × 8 = 72 次。每次发 10 − 1 − 2 = 7 条,共 504 条。
3. PBFT 预告:五个阶段
它解决什么问题
OM 证明了拜占庭共识可以做到,但消息量太大,还要求同步网络。PBFT 是第一个在真实网络里跑得动的方案,课件在 OM 的代价之后顺带预告它。
从哪来(补充)
PBFT 由 MIT 的 Miguel Castro 和 Barbara Liskov 提出,发表在 OSDI ’99(新奥尔良,1999)。论文摘要说它能在互联网这类异步环境中工作;用它实现的容拜占庭 NFS,只比不复制的 NFS 慢约 3%。出处:USENIX OSDI ’99 论文页。
直觉
PBFT 不再层层转述。它让一个主节点给请求编号,其他副本两轮互相确认这个编号,收够票就执行。
每一轮最多是所有副本互发一次,大约 n² 条。两轮互发加起来还是 n² 量级,所以是 O(n²)。
一步一步看
目标:按课件的图把 PBFT 五个阶段走一遍,数出每个阶段和总共发几条消息。
课件的图是 Castro 和 Liskov 论文里的图 1:客户端 C,副本 0 是主节点,副本 3 出了故障,一条消息都不发。
-
request:客户端 C 把请求发给主节点 0,1 条。
-
pre-prepare:主节点 0 给请求编号,发给副本 1、2、3,3 条。
-
prepare:副本 1、2 各发给其余三个副本,2 × 3 = 6 条。主节点不发 prepare。
-
commit:副本 0、1、2 各发给其余三个副本,3 × 3 = 9 条。
-
reply:副本 0、1、2 各给客户端回一条,3 条。
-
合计 1 + 3 + 6 + 9 + 3 = 22 条。
怎么算
老师在图上标的数法:pre-prepare 是主节点发 n 条;prepare 是每个副本各发 n 条,合起来 n² 条;commit 同理又是 n² 条;reply 是 n 条。
总量 = n + n² + n² + n = O(n²)
意思是:两个全员互发的阶段决定量级,其余阶段只是 n 条,可以忽略。
常见误解
以为 prepare 阶段主节点也要发
主节点已经在 pre-prepare 里发过编号,prepare 只由其余副本发。图里 prepare 是 6 条,正是副本 1、2 各发 3 条。
以为 PBFT 也像 OM 一样依赖同步网络才安全
补充:Castro 与 Liskov 的原文说明,PBFT 的安全性不依赖同步,只有活性需要。网络很慢时它可能暂时推进不了,但不会让忠诚副本认定互相冲突的结果。
试一下
如果副本 3 没有故障、正常参与,五个阶段各有几条箭头?
request 1;pre-prepare 3;prepare 副本 1、2、3 各发 3 条,共 9;commit 副本 0 到 3 各发 3 条,共 12;reply 4。合计 1 + 3 + 9 + 12 + 4 = 29 条。
4. 三个法定人数:2f、2f+1、f+1
它解决什么问题
PBFT 的每个阶段要收够几份一致的消息,才能往下走?收少了,叛徒能凑出假结果;收多了,故障副本不发消息时就永远等不齐。这一节记住三个数。
直觉
PBFT 用 n = 3f+1 个副本,和 OM 的下界一样。
收齐 2f+1 份一致的消息,意味着其中至少 f+1 份来自忠诚副本。任意两组 2f+1 个副本一定有忠诚的人重叠,所以两组不可能认定互相冲突的结果。
一步一步看
目标:以 n = 4 为例,记住 PBFT 三个关口各要收齐几份消息才往下走。
- 定 f:n = 4 时 f = 1。
- prepared:一个副本收齐 pre-prepare,再加 2f 个不同副本的匹配 prepare,就进入 prepared 状态。n = 4 时是 2 个。
- 执行:再收齐 2f+1 个匹配 commit 才执行。n = 4 时是 3 个。
- 回复:客户端等 f+1 个相同回复就采信。n = 4 时是 2 个,至少有一个来自忠诚副本。
| 阶段 | 要收齐几份 | f = 1、n = 4 |
|---|---|---|
| prepared | 2f 个匹配 prepare | 2 |
| 执行 | 2f+1 个匹配 commit | 3 |
| 客户端采信 | f+1 个相同回复 | 2 |
怎么算
两组 2f+1 的重叠:(2f+1) × 2 − (3f+1) = f+1
意思是:两组加起来比总人数多出 f+1 个,这 f+1 个人在两组里都出现了。叛徒最多 f 个,所以重叠里至少有 1 个忠诚副本,它不会对两个冲突的结果都投票。
验算:f = 1、2、3 时 n = 4、7、10,2f+1 = 3、5、7,重叠 = 2、3、4,都 ≥ f+1。
常见误解
以为过半数就够了
拜占庭故障下过半不够。n = 4 时过半是 3,看似等于 2f+1,但 n = 7 时过半是 4,2f+1 是 5。只有 2f+1 能保证两组重叠里有忠诚副本。
试一下
n = 7 时 f 是几?三个法定人数分别是几?
7 = 3 × 2 + 1,f = 2。prepared 要 2f = 4 个 prepare,执行要 2f+1 = 5 个 commit,客户端等 f+1 = 3 个相同回复。
把它们串起来
OM 的消息量按层累加:每往下一层,调用次数再乘一个更小的人数。最深一层是 m 个接近 n 的数连乘,量级 O(nᵐ)。叛徒数在指数上,所以 OM 只能当理论结论。
PBFT 保留了 3f+1 这个副本数,换掉了层层转述。主节点编号,副本两轮互发确认,每轮 n² 量级,总量 O(n²)。每轮收够 2f+1 份一致消息才推进,靠两组之间的忠诚重叠保证不会出现冲突结果。
它的安全性也不再依赖同步网络,这一点和 OM、SM 都不同。完整的 PBFT 在第 9 讲展开。
课件里的坑
- [量级] p.19 写 O(nᵐ),老师旁注「Let k=m: OM(0) called (n−1)(n−2)…(n−m) times ≈ nᵐ」。考试写量级时按最深一层估,不必展开所有层(p.19)。
- [数箭头] p.19 的 PBFT 图里副本 3 打了叉,它一条消息都不发。数箭头时 prepare 是 6、commit 是 9,共 22 条;把副本 3 也算进去会数多(p.19)。
- [补充内容] 2f、2f+1、f+1 三个数课件这一讲没写,来自 Castro 与 Liskov 的原文。第 9 讲会正式讲,本讲答题以课件的 O(n²) 为主(p.19)。
- [同步假设] OM 和 SM 都假设同步网络(p.24);PBFT 的安全性不依赖同步。两者别混(p.19、p.24)。
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先画一张「层 / 被调用 / 每次发 / 小计」的表,把 n = 7、m = 2 填满;再徒手画 PBFT 五条横线,按阶段数出 22 条箭头;最后默写三个法定人数和重叠公式。
必背
- OM(m−k) 被调用 (n−1)(n−2)…(n−k) 次,每次发 n−1−k 条消息,总量 O(nᵐ)
- n = 4、m = 1 共 9 条;n = 7、m = 2 共 6 + 30 + 120 = 156 条、3 轮;n = 10、m = 3 共 3609 条
- PBFT(1999 OSDI)复杂度 O(n²);n = 4、f = 1 时课件图中共 22 条消息
- PBFT 五阶段箭头数:request 1、pre-prepare 3、prepare 6、commit 9、reply 3
- PBFT 法定人数:prepared 要 2f 个 prepare,执行要 2f+1 个 commit,客户端等 f+1 个相同回复;n = 4 时是 2、3、2
- PBFT 的安全性不依赖同步,只有活性需要
课件例题
例 1(课件 p.19):OM 的消息量
p.19 说 OM 的通信代价很高。分别算出 n = 4、m = 1 和 n = 7、m = 2 时 OM 发多少条消息,并说出量级。
提示
按层累加「调用次数 × 每次消息数」。第 k 层调用 (n−1)…(n−k) 次,每次发 n−1−k 条。
解答
n = 4、m = 1:1 × 3 + 3 × 2 = 9 条。n = 7、m = 2:1 × 6 + 6 × 5 + 30 × 4 = 156 条,3 轮。最深一层调用 (n−1)…(n−m) 次,约 nᵐ,所以量级 O(nᵐ),m 稍大就无法实用。
例 2(课件 p.19):PBFT 图里的箭头
p.19 下半页的 PBFT 图中,n = 4,副本 3 出故障。数出每个阶段的箭头数和总数,并说明为什么复杂度是 O(n²)。
提示
副本 3 不发任何消息。prepare 由主节点以外的副本发,commit 由所有正常副本发。
解答
request 1、pre-prepare 3、prepare 6、commit 9、reply 3,共 22 条。prepare 和 commit 两个阶段都是副本全员互发,各约 n² 条;老师批注 n² + n² = O(n²)。
完整例题
题目:n = 10、m = 3,用 OM 算法一共发多少条消息?分几轮?如果改用 PBFT,副本数和三个法定人数是多少?
解:
- 门槛:10 = 3 × 3 + 1,OM 刚好能容忍 3 个叛徒。
- OM(3):调用 1 次,每次发 9 条,共 9 条。
- OM(2):调用 9 次,每次发 8 条,共 9 × 8 = 72 条。
- OM(1):调用 9 × 8 = 72 次,每次发 7 条,共 72 × 7 = 504 条。
- OM(0):调用 9 × 8 × 7 = 504 次,每次发 6 条,共 504 × 6 = 3024 条。
- 合计 9 + 72 + 504 + 3024 = 3609 条,递归 4 层,即 m+1 = 4 轮。
- PBFT:n = 3f+1 = 10,f = 3。prepared 要 2f = 6 个 prepare,执行要 2f+1 = 7 个 commit,客户端等 f+1 = 4 个相同回复。两组 7 个副本的重叠是 7 × 2 − 10 = 4 = f+1。
一句话结论:同样容忍 3 个拜占庭节点,OM 要 3609 条消息,PBFT 每阶段最多约 n² = 100 条。
答题格式:先检查门槛,再画「层 / 调用次数 / 每次发 / 小计」表逐行算,最后写合计和轮数。
变式题(先自己做)
(1) n = 5、m = 1,OM 一共发多少条消息?
(2) n = 7,用 PBFT,f 最大是几?如果有一个副本故障不发消息,prepare 阶段有几条箭头?
提示
(1) 按层算两层。(2) 先由 n = 3f+1 定 f;prepare 由主节点以外的正常副本发,每个发给其余 n−1 个副本。
判分点与答案(非官方评分标准)
判分点:① 写出每层的调用次数和每次消息数;② PBFT 部分要先定 f,再说明主节点不发 prepare、故障副本不发消息。
(1) OM(1) 调用 1 次发 4 条;OM(0) 调用 4 次各发 3 条,共 12 条。合计 4 + 12 = 16 条。
(2) 7 = 3 × 2 + 1,f = 2。主节点以外有 6 个副本,其中 1 个故障,剩 5 个,每个发给其余 6 个副本,共 5 × 6 = 30 条。
闪卡自测
1. OM(m−k) 被调用几次?每次发几条?
(n−1)(n−2)…(n−k) 次,每次 n−1−k 条(p.19)。
2. n = 7、m = 2 时 OM 共发多少条消息?分几轮?
6 + 30 + 120 = 156 条,m+1 = 3 轮(p.19、p.30)。
3. OM 的消息量是什么量级?为什么?
O(nᵐ)。最深一层 OM(0) 被调用 (n−1)(n−2)…(n−m) 次,m 个接近 n 的数相乘约等于 nᵐ(p.19)。
4. PBFT 是哪年、在哪发表的?复杂度多少?
1999 年 OSDI,O(n²)(p.19)。
5. 课件 PBFT 图里五个阶段各有几条箭头?
request 1、pre-prepare 3、prepare 6、commit 9、reply 3,共 22 条;副本 3 故障,不发消息(p.19)。
6. PBFT 中 n = 4、f = 1,prepared 要几个 prepare?执行前要几个 commit?客户端等几个相同回复?
2f = 2;2f+1 = 3;f+1 = 2(补充,来源 Castro & Liskov 1999)。
7. 为什么两组 2f+1 一定有忠诚副本重叠?
(2f+1) × 2 − (3f+1) = f+1,重叠至少 f+1 个,叛徒最多 f 个,所以至少 1 个忠诚(补充)。
8. PBFT 的安全性依赖同步网络吗?
不依赖,只有活性需要(补充,来源 Castro & Liskov 1999)。
下一讲
回到本讲的主线。OM 之外,课件还给了第二种解法:让消息带上签名,叛徒没法冒充别人,人数门槛也会降下来。见 L07e。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。