← COMP5567 全部讲次
L07d · 第 7 周

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 一共发多少条消息。

  1. 最上层 OM(2):调用 1 次。指挥官发给 6 位副官,共 1 × 6 = 6 条。

  2. 第二层 OM(1):每位副官各当一次指挥官,共 6 次。每次发给其余 5 位副官,共 6 × 5 = 30 条。

  3. 第三层 OM(0):每个 OM(1) 有 5 位接收者,各跑一次 OM(0),共 6 × 5 = 30 次。每次发给剩下 4 人,共 30 × 4 = 120 条。

  4. 合计 6 + 30 + 120 = 156 条,跑了 3 层,也就是 3 轮。

    按层数消息的表格:OM(2) 被调用 1 次、每次发 6 条、小计 6;OM(1) 被调用 6 次、每次发 5 条、小计 30;OM(0) 被调用 30 次、每次发 4 条、小计 120;右下角青绿框写着合计 156

怎么算

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ᵐ) 的量级。

  1. n = 4、m = 1:只有两层,3 + 6 = 9 条。

  2. n = 7、m = 2:三层,6 + 30 + 120 = 156 条。

  3. n = 10、m = 3:四层,9 + 72 + 504 + 3024 = 3609 条。

  4. 把三个结果放在一起看:人数从 4 涨到 10,消息量从 9 涨到 3609。

    三根横条:n 等于 4、m 等于 1 时 9 条;n 等于 7、m 等于 2 时 156 条;n 等于 10、m 等于 3 时 3609 条,最长一根描成青绿;条长按对数画

  5. 每个例子里,最后一层都占了大头: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 出了故障,一条消息都不发。

  1. request:客户端 C 把请求发给主节点 0,1 条。

  2. pre-prepare:主节点 0 给请求编号,发给副本 1、2、3,3 条。

  3. prepare:副本 1、2 各发给其余三个副本,2 × 3 = 6 条。主节点不发 prepare。

  4. commit:副本 0、1、2 各发给其余三个副本,3 × 3 = 9 条。

  5. reply:副本 0、1、2 各给客户端回一条,3 条。

    PBFT 五阶段消息图:五条横线自上而下是客户端 C、副本 0 主节点、副本 1、副本 2、副本 3,副本 3 线头打叉;request 一条,pre-prepare 三条,prepare 六条和 commit 九条用青绿高亮,reply 三条

  6. 合计 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 三个关口各要收齐几份消息才往下走。

  1. 定 f:n = 4 时 f = 1。
  2. prepared:一个副本收齐 pre-prepare,再加 2f 个不同副本的匹配 prepare,就进入 prepared 状态。n = 4 时是 2 个。
  3. 执行:再收齐 2f+1 个匹配 commit 才执行。n = 4 时是 3 个。
  4. 回复:客户端等 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 条箭头;最后默写三个法定人数和重叠公式。

必背

  1. OM(m−k) 被调用 (n−1)(n−2)…(n−k) 次,每次发 n−1−k 条消息,总量 O(nᵐ)
  2. n = 4、m = 1 共 9 条;n = 7、m = 2 共 6 + 30 + 120 = 156 条、3 轮;n = 10、m = 3 共 3609 条
  3. PBFT(1999 OSDI)复杂度 O(n²);n = 4、f = 1 时课件图中共 22 条消息
  4. PBFT 五阶段箭头数:request 1、pre-prepare 3、prepare 6、commit 9、reply 3
  5. PBFT 法定人数:prepared 要 2f 个 prepare,执行要 2f+1 个 commit,客户端等 f+1 个相同回复;n = 4 时是 2、3、2
  6. 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²)。

PBFT 正常流程时序图:五条水平线自上而下是客户端 C 和副本 0、1、2、3,虚线把时间分成 request、pre-prepare、prepare、commit、reply 五段。副本 3 在最左侧画着叉号,表示故障、全程不发消息;C 发一条请求到 0,0 向 1、2、3 发 pre-prepare,1、2 在 prepare 段互相并向其他副本发箭头,0、1、2 在 commit 段全员互发,最后 0、1、2 各回一条 reply 给 C
图片来源:COMP5567 Lecture_7-BFT.pdf, p.19
提示

副本 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,副本数和三个法定人数是多少?

解:

  1. 门槛:10 = 3 × 3 + 1,OM 刚好能容忍 3 个叛徒。
  2. OM(3):调用 1 次,每次发 9 条,共 9 条。
  3. OM(2):调用 9 次,每次发 8 条,共 9 × 8 = 72 条。
  4. OM(1):调用 9 × 8 = 72 次,每次发 7 条,共 72 × 7 = 504 条。
  5. OM(0):调用 9 × 8 × 7 = 504 次,每次发 6 条,共 504 × 6 = 3024 条。
  6. 合计 9 + 72 + 504 + 3024 = 3609 条,递归 4 层,即 m+1 = 4 轮。
  7. 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。

下一讲 →
L07e L07e 签名消息算法 SM:叛徒没法冒充别人

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。