复制KV若只容忍崩溃，三副本取两票就能承受一台停机。节点一旦可以对不同接收者发送互相矛盾的消息，这个证明立即失效：两个两票集合可能只交在作恶节点上。PBFT（Practical Byzantine Fault Tolerance）增加的不只是一个副本，还包括认证消息、分阶段证书、换主证明和状态恢复规则。

分布式系统（32）：事件时间、水位线与状态恢复

同一份KV需求对应两种故障模型

需求固定为线性一致的 Put/Get、确定性状态机和最多一个故障。crash fault模型允许节点停止、重启或暂时不可达，但节点运行时仍遵守协议。三副本的两票集合至少交一个节点；交点不会为同一日志位置确认两个值，因此多数派交集有用。

Byzantine fault允许故障节点沉默、伪造自身状态、选择性转发、串谋，还能向不同接收者发送冲突消息。这样的行为称为equivocation。若沿用三副本两票阈值，故障节点B可以同时支持红值和蓝值：

sequenceDiagram
  participant H1 as 正确副本 H1
  participant B as 恶意副本 B
  participant H2 as 正确副本 H2
  B->>H1: vote(red, v, n)
  B->>H2: vote(blue, v, n)
  Note over H1,B: red证书 = {H1,B}
  Note over B,H2: blue证书 = {B,H2}

两个证书的交集只有B。crash证明隐含的“交点不会双投”已经不成立。

模型 容忍f个故障的常见副本数 协议证书阈值 交集里能保证什么
crash fault复制 2f+1 f+1 至少一个成员，且成员只会停机或遵守协议
经典PBFT配置 3f+1 2f+1量级 至少f+1个成员，其中至少一个正确

PBFT配置在 n=3f+1 时，任意两个 2f+1 集合至少相交 f+1 个副本。最多只有f个恶意节点，所以交集至少含一个正确副本。这个算术仍不是完整证明；还要规定正确副本在相同 (view, sequence) 上不为冲突摘要投票，并让换主继承旧view已经形成的证明。

系统模型先于消息流程

经典PBFT讨论固定成员的复制状态机，最多f个副本拜占庭故障，服务操作必须确定。副本间消息带认证器，请求和协议消息绑定客户端、view、sequence number与摘要。正确副本的密钥未泄露，摘要和认证算法满足论文假设。

网络可以延迟、丢失、重复和乱序消息。安全性不需要已知延迟上界：网络长期异步时，正确副本宁可停止提交，也不能执行冲突请求。活性则需要最终出现一段足够稳定的通信期，并最终选到正确primary。永久分区或持续拒绝服务不在活性承诺内。

认证器能阻止攻击者冒充正确副本或静默篡改其消息，却不能阻止故障节点用自己的身份发送两个冲突值。只有两份冲突消息都进入可比较的协议证据时，系统才能归因equivocation。认证也不能替代view、sequence、水位线与重放检查；一份旧的合法消息仍可能被重新发送。

正常路径的四个边界

PBFT把“primary提出顺序”“副本确认看到同一提议”“把该事实传播到换主边界”和“客户端接受结果”分成不同阶段。

sequenceDiagram
  participant C as Client
  participant P as Primary
  participant R1 as Replica 1
  participant R2 as Replica 2
  participant R3 as Replica 3
  C->>P: REQUEST(op, client, t)
  P->>R1: PRE-PREPARE(v,n,d)
  P->>R2: PRE-PREPARE(v,n,d)
  P->>R3: PRE-PREPARE(v,n,d)
  R1-->>R2: PREPARE(v,n,d)
  R2-->>R3: PREPARE(v,n,d)
  R3-->>R1: PREPARE(v,n,d)
  Note over P,R3: prepared条件成立后
  P-->>R1: COMMIT(v,n,d)
  R1-->>R2: COMMIT(v,n,d)
  R2-->>R3: COMMIT(v,n,d)
  R3-->>P: COMMIT(v,n,d)
  P-->>C: REPLY(result)
  R1-->>C: REPLY(result)

PRE-PREPARE由primary把请求摘要d绑定到view v与序号n。backup只有在认证、view、水位范围、摘要以及同槽不冲突等检查都通过时才接受。它不是提交证据。

PREPARE让副本彼此核对primary是否对同一槽位说了不同的话。原论文的 prepared 谓词有阶段特定的形状：本地日志包含请求和合法pre-prepare，并包含来自不同backup的 2f 个匹配prepare。不能把它粗略改写成“所有阶段都是2f+1张相同票”。

副本在prepared后广播 COMMIT。当本地已经prepared，并收到来自不同副本的 2f+1 个匹配commit时，committed-local 才成立。commit阶段把“足够多副本知道该请求已prepared”的事实扩散开，为跨view保留请求提供交集。

正确副本按sequence顺序执行已committed-local的请求并缓存结果。客户端收到 f+1 个一致reply才接受；这保证至少一份reply来自正确副本。客户端接受与单个副本执行仍是两个状态，超时也不表示请求没有执行。

状态 已知事实 还不能推出什么
accepted pre-prepare primary提出了 (v,n,d) 其他副本是否看到相同值
prepared 本地拥有阶段规定的prepare证据 请求已按序执行、客户端已成功
committed-local 本地拥有prepare与commit证据 任意外部副作用恰好一次
executed 本副本按序更新了确定性状态机 客户端已经收到足够reply
client accepted f+1个reply一致 永久分区期间还能继续服务

安全证明需要跨过view边界

同一view中的核心反证很短。假设两个冲突值都形成合法的 2f+1 证书，它们至少共享 f+1 个副本，其中至少一个正确。正确副本不会在相同 (view, sequence) 为两个摘要投票，因此冲突证书不能同时成立。

flowchart LR
  A[证书A: 3 of 4] --> I[交集至少2个]
  B[证书B: 3 of 4] --> I
  I --> H[至多1个恶意<br/>至少1个正确]
  H --> R[正确副本同槽不双投]
  R --> X[冲突证书不能同时成立]

只写这段交集推理还不够。新view可能由不同primary主持；如果换主丢掉旧view已经prepared的值，新primary就可能在同一sequence提出另一个值。PBFT的view-change消息携带稳定checkpoint和尚未被checkpoint覆盖的prepared证明，新primary收集覆盖 2f+1 副本的材料并构造 NEW-VIEW。其他副本会验证新view选择的pre-prepare是否与这些证明相容。

跨view安全因此依赖一个归纳步骤：旧view中足以形成提交的值，会在view-change法定人数中留下正确副本的证据；新view必须选择该证据约束的值。法定人数交集、正确副本投票规则与new-view选择规则缺一不可。

超时、分区与重试只改变活性

恶意primary可以沉默、拖延或发送冲突pre-prepare。冲突消息可能让请求无法prepared，却不能让两个冲突值都得到合法证书。backup看到请求长期没有进展后触发view change；超时决定何时怀疑primary，不是判断某个值安全与否的依据。

sequenceDiagram
  participant C as Client
  participant P0 as 恶意 Primary v
  participant R as Correct replicas
  participant P1 as Primary v+1
  C->>P0: REQUEST
  P0--xR: 沉默或冲突提案
  Note over R: timer expires
  R-->>P1: VIEW-CHANGE + checkpoint + prepared proofs
  P1-->>R: NEW-VIEW + selected pre-prepares
  C->>R: timeout后向所有副本重发
  R-->>C: 缓存结果或继续协议

在 n=4,f=1 的2+2永久分区中，两侧都拿不到3份commit，正确副本不能达到committed-local。系统保住安全性，但失去活性。若网络恢复，view change和重传可以继续推进；若分区永不恢复，协议没有义务返回成功。

客户端重试必须保留稳定的客户端ID和请求时间戳或序号。已经执行的正确副本返回缓存结果，未执行的副本继续转发请求。把重试包装成新请求会绕过去重边界，外部非确定性调用也不由PBFT自动变成恰好一次。

checkpoint与恢复仍需要证书

协议日志不能无限增长。副本执行到周期性序号后广播checkpoint摘要；收到 2f+1 份同序号、同摘要的checkpoint消息后，该checkpoint才稳定。稳定证书允许丢弃更早的请求和协议消息，并移动低、高水位线。

flowchart TD
  S[执行到checkpoint序号] --> D[计算状态摘要]
  D --> M[广播CHECKPOINT]
  M --> Q{收到2f+1个<br/>同序号同摘要?}
  Q -->|否| W[继续保留旧日志]
  Q -->|是| C[stable checkpoint]
  C --> G[回收旧协议记录]
  C --> T[为落后副本提供state transfer锚点]

恢复副本不能因为“磁盘里有一份状态”就重新获得信任。它要从稳定checkpoint与后缀日志追赶，并验证状态摘要。经典PBFT还假设故障总数不超过f；若同一软件漏洞或同一泄露密钥同时控制超过f个副本，协议证明不再适用。

本地实验：多数派反例与证书交集

1
2
3
4
5
mkdir -p examples/distributed-systems/.build/pbft33/tmp
export TMPDIR="$PWD/examples/distributed-systems/.build/pbft33/tmp"
export TMP="$TMPDIR" TEMP="$TMPDIR" PYTHONDONTWRITEBYTECODE=1
python3 -B examples/distributed-systems/pbft33/check.py \
  --output examples/distributed-systems/.build/pbft33/observations.json

Python 3.12.3有限模型枚举三节点两票crash法定人数，再让节点0等价冲突，得到 {0,1} 与 {0,2} 两个冲突证书。对四节点三票集合，模型逐一把0、1、2、3设为唯一故障节点；任意证书对都没有“交集里只剩恶意节点”的情况，最小交集为2。

模型的 certificate_quorum=3 只抽象同一view、同一sequence上的集合交叠，不等同于原论文prepared谓词的消息清单。认证边界和超时用途列在输出中，但没有执行密码学、网络、view change、checkpoint或性能测试。

完整输出见结构化观察，研究和运行证据见实验证据，边界见验证说明。

安全性、活性与工程成本

PBFT的安全性要求故障副本不超过f、正确副本遵守投票与换主规则、认证与摘要假设成立、状态机确定。活性还需要最终同步、足够副本互通、正确primary最终出现，以及客户端请求最终送达正确副本。

成本或边界 PBFT为何需要它 不覆盖的情况
3f+1副本 让证书交集含正确副本 超过f个恶意或相关故障
prepare与commit全体传播 建立同view与跨view证据 经典正常路径消息关系为二次量级
认证器、摘要与密钥轮换 防冒充、篡改和旧消息混入 合法身份用自己的密钥说谎、密钥失陷
view-change证明 保留旧view的prepared值 永久分区、持续DoS
stable checkpoint与state transfer 回收日志并恢复落后副本 不受控的非确定性外部副作用

四台机器若运行同一份含后门的镜像、共享同一把泄露密钥或处在同一管理域，不能自动算作四个独立故障域。部署成本来自独立性，而不只是服务器数量。后来的BFT协议会优化通信、换主或广域延迟；这些改进不能反向当作PBFT本身已经提供的保证。

两个推演练习

把容错提高到f=2。 n=7、证书阈值5时，两个证书最少相交多少副本？阈值4为什么不够？

两个5元素集合的交集至少有3个副本；最多2个恶意，因此至少有1个正确。两个4元素集合只保证交1个，该交点可能正是恶意节点，不能阻止冲突证书。

四副本发生2+2分区。 primary位于左侧，客户端请求也到达左侧。请求能否达到prepared、committed-local和客户端成功？

左侧只有两个副本，不能取得PBFT所需的完整prepare/commit证据，正确副本不能committed-local或执行。恶意副本可以伪造一份reply，但客户端需要 f+1=2 份一致reply，其中必须有正确副本；因此不能得到合法成功。分区恢复后可通过view change继续。

工程结论

法定人数设计先问“故障节点还能做什么”，再计算交集。crash quorum依赖交点成员遵守协议；PBFT把集合扩大到即使所有恶意节点都落在交集里，仍至少留下一个正确副本，并用prepare、commit与view change把这条约束保持到后续view。

下一篇把前面各篇的复制、分片、迁移与恢复约束装进一个有界结课系统，并用固定工作负载检查它明确覆盖和没有覆盖的故障。

参考资料