← COMP5567 全部讲次
L09a · 第 9 周

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 的每种消息都带着这两样东西。

直觉

摘要像一条消息的指纹。消息改一个字,指纹就完全变样;两条消息指纹相同,就当它们是同一条。

签名像盖章。章只在发送者自己手里,别人拿到消息也盖不出同样的章,所以内鬼没法冒充老实分行说话。

一步一步看

目标:看两个副本只交换摘要就能发现手里不是同一笔,以及签名怎样挡住冒充。

  1. R2 收到 transfer(Alice → Bob, $1),用哈希函数算出摘要 h,课件写的例子是 0x9a4f 开头的一串值。

    摘要示意:R2 收到 transfer(Alice → Bob, $1) 算出摘要 h = 0x9a4f…,R3 收到只改了收款人的 transfer(Alice → Cindy, $1) 算出另一串摘要 h’,用青绿标出两串指纹不一样

  2. R3 收到的是被改过的 transfer(Alice → Cindy, $1),算出的摘要 h’ 跟 h 完全不同。

  3. 两个副本交换的只是 h 和 h’。一比,不一样,马上知道两人手里不是同一笔。

  4. 每条消息还带发送者的签名。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 个回复时,诚实的为什么仍占多数。

  1. 设 n = 4、f = 1。最多 1 个副本可能永远不回,等它就会卡死,所以只敢等 n − f = 3 个回复。

    3f+1 推导第 1 步:四个副本 R1 到 R4,R1、R2、R3 回了,R4 画成灰色虚线表示没回、可能只是慢,所以只敢等 3 个回复

  2. 没回的 R4 也许只是网络慢,真叛徒可能混在回了的人里,比如 R3。

    3f+1 推导第 2 步:R3 也画成灰色虚线标注可能是叛徒,R4 仍是没回,说明回了的 3 个里最坏仍有 1 个是假的

  3. 回了的 3 个里,诚实的有 3 − 1 = 2 个,比叛徒的 1 个多。听多数的,结果就是对的。

    3f+1 推导第 3 步:R1、R2 用青绿标成诚实的回复,R3 是可能的叛徒,R4 没回,诚实回复 2 个多过叛徒 1 个

  4. 换成 n = 3、f = 1 对照:只敢等 2 个,其中 1 个可能是叛徒,诚实 1 个对叛徒 1 个,听谁的都说不清。

    3f+1 推导对照:只有三个副本 R1、R2、R3,R1 是诚实回复,R2 可能是叛徒,R3 没回,诚实和叛徒各 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 种消息各属于哪一套。

  1. 分行场景里,Alice 是客户端,她要做两笔转账:op1 给 Bob $1,op2 给 Cindy $1。请求先交给主节点 Branch-I。

    分行场景的角色与消息:左边 Alice 是客户端,请求交给青绿标出的主节点 Branch-I,下面 Branch-II、III、IV 是 backup;右边三组消息,正常操作 Request、Pre-prepare、Prepare、Commit、Reply,视图切换 View change、New view,检查点 Checkpoint

  2. Branch-I 给请求排号,再和 Branch-II、III、IV 一起走投票流程。四家都是副本,各存一份交易日志。

  3. 一切正常时跑正常操作,五个阶段各一种消息。主节点出故障时跑视图切换,两种消息。定期跑检查点,一种消息。

  4. 每种消息的格式、谁发给谁、谁签名,列成下表:

    消息 发送方 → 接收方 格式 属于
    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⌋ 的换算表;再背出三个子协议各用哪几种消息;然后对着完整例题把一笔转账的消息字段填一遍,最后做变式题。

必背

  1. PBFT(Castro & Liskov 1999):3f+1 个副本容忍 f 个拜占庭故障,消息量 O(n²)
  2. 三个设计目标:Consistency(两个诚实副本不会提交不同结果)、Availability、Fault Tolerance
  3. n 个副本最多容忍 f = ⌊(n − 1)/3⌋ 个拜占庭副本:4、5、6 个都只扛 1 个,7 个扛 2 个
  4. 3f+1 的来历:只能等 n − f 个回复,其中仍可能有 f 个是假的,诚实的 n − 2f 个要多过 f 个
  5. 三个子协议:正常操作(Request → Pre-prepare → Prepare → Commit → Reply)、视图切换(View change → New view)、检查点
  6. 8 种消息:5 种属于正常操作,2 种属于视图切换,1 种属于检查点
  7. 摘要 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。带着问题读:副本要凑几票才敢执行,为什么偏偏是这个数?

下一讲 →
L09b L09b PBFT 正常操作:五个阶段、三道门槛,凑不满票就停

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