Castro–Liskov 1999：实用拜占庭容错，不是将军寓言

破除误解#

第二层误解把 PBFT 读成「Paxos 或 Raft 加上加密」。Paxos 的相交多数锁住崩溃与遗漏下的已接受值；议员可缺席，信使可丢信，但不被写成对两名听众交出两份矛盾的已接受记录。Viewstamped Replication 写明故障停止，不是拜占庭。etcd 与 Raft 同样走崩溃容错的复制日志。PBFT 要挡住副本任意偏离算法，因此正常路径多出预准备，认证进入模型，换届也不靠「把某人踢出组」。把三份兑成一套角色名，会把故障模型偷换掉。

第三层误解把「实用」听成「已经在广域网里扛过真实攻击」。论文里可核对的意思有两句。安全不依赖已知的消息延迟上界，因而与 Rampart、SecureRing 那类把同步写进正确性的系统分开。正常路径用消息认证码代替公钥签名，并给出复制库与拜占庭容错 NFS（BFS）的延迟。实验跑在隔离以太网、四台副本、无视图变更的正常路径上。它没有给出注入故障后的存活曲线。

第四层误解把超时、故障检测器与安全捆在一起。Chandra–Toueg 把「谁可能已经停机」写成可查询的预言。论文批评：异步里检测器不可能永远准确；若正确性还要求把被判为故障的副本移出组，延迟就可以让诚实者被排除，直到组内故障越过三分之一。PBFT 从不改写成员集合。超时只进入活性，用来决定何时换主副本。

第五层误解把 $2f+1$ 听成随便一个多数。崩溃模型里多数的力量来自相交；拜占庭模型里交出来的那一票仍可能是任意内容。因此人数先到 $3f+1$，再取 $2f+1$，好让其中至少 $f+1$ 份来自遵守算法的副本。

装置：成员、视图、主副本与仲裁#

系统是异步网络：报文可以丢失、延迟、重复或乱序。故障节点可以任意偏离第 4 节算法，只受计算能力限制。论文假定故障独立，并把不同实现、不同操作系统一类对策写成使该假定可说的条件，而不是部署清单。对手可以协调故障者、延迟通信或延迟正确节点；仍假定不能无限期挡住正确节点，并且（以极高概率）不能伪造未故障节点的签名、不能从摘要还原原文、也不能找出两个相同摘要的不同消息。认证技术见 密码学基础；这里只记下 1999 年文本把这些性质当作前提。

服务是任意确定性复制服务。副本须从同一初态出发。安全被写成（为拜占庭客户改过的）线性化。至多三分之一副本同时故障时，安全不依赖同步。活性——客户终将收到答复——要求延迟不会无限快于超时增长。这是为了绕开 FLP，不是推翻它。分布式计算理论 里那条活性边界仍然立着。

副本集合 $\mathcal{R}$ 取 $|\mathcal{R}|=3f+1$。视图连续编号。视图 $v$ 的主副本是 $p=v \bmod |\mathcal{R}|$，其余是备份。论文写明：Viewstamped Replication 与 Paxos 也用视图加主副本来容忍良性故障；要容忍拜占庭，需要认证、额外的预准备，以及另一套点名主副本的办法。关键一句：本算法的视图变更只选定新的主副本，从不另选一组副本组成新视图。成员名单在运行期间保持已知且固定。

第 3 节的算术是：必须能在只与 $n-f$ 个副本通话后继续；没回答的 $f$ 个也可能没故障，于是回答者里仍可能有 $f$ 个故障；诚实回答仍须多过故障回答，即 $(n-f)-f>f$，故 $n>3f$。取 $n=3f+1$ 时，仲裁是 $2f+1$。客户等待 $f+1$ 份来自不同副本、同一时间戳与同一结果的答复。算法不处理容错隐私：故障副本可以泄露明文状态。

客户把带时间戳的请求发给它所以为的当前主副本。时间戳保证同一客户的请求至多执行一次。收不齐答复则广播给全体；已执行过的只重发上次答复。这些是纸上的角色分工，不是超时配方。

正常路径：预准备、准备、提交#

三阶段原子多播。预准备与准备在同一视图内排好全序，即使提出排序的主副本是故障的。准备与提交让已经提交的请求在视图之间仍保持同一全序。主副本给请求 $m$ 分配序号 $n$，多播带视图、序号与摘要的预准备；请求正文另附，好让预准备在换届时能当证物却不必携带大报文。备份接受预准备，仅当签名与摘要对得上、自己在该视图、尚未对同一序号接受过另一摘要、且序号落在水位之间。水位随稳定检查点推进，用来挡住极大序号，不是现场调参表。

备份若接受，就多播准备。谓词 $\mathrm{prepared}(m,v,n,i)$ 为真，当且仅当 $i$ 的日志里已有请求、$v$ 与 $n$ 上的预准备，以及来自不同备份、相符的 $2f$ 条准备。相符指同一视图、序号与摘要。不变量：若该谓词为真，则任何未故障副本都不会对同一 $(v,n)$ 为另一不同请求准备成功。因为 $3f+1$ 加上已准备意味着至少 $f+1$ 个未故障者曾为该位置发言；另一摘要若也准备成功，其中必有未故障者发出过冲突的两份。

副本在已准备时多播提交。$\mathrm{committed}(m,v,n)$ 为真，当且仅当某个含 $f+1$ 个未故障副本的集合里人人已准备。$\mathrm{committed\text{-}local}$ 为真，当且仅当自己已准备且已接受 $2f+1$ 条相符提交（可含自己）。不变量：未故障副本上本地提交为真，则 $\mathrm{committed}$ 为真。本地提交且更小序号都已执行之后，才执行并答复客户。报文不必按序到达；日志留到能够按序号执行的那一刻。

检查点截断日志。每隔常数个序号（文中举例 100，实验取 128）产生检查点，多播序号与状态摘要。收齐 $2f+1$ 份同一摘要的检查点后，该检查点稳定，更早的三阶段消息可以丢弃。低水位等于最近稳定检查点。确定性是硬条件：NFS 的「上次修改时间」若各读本地钟，状态会分叉。论文让主副本提出该值并走完三阶段，使未故障者对「请求加这个值」锁定同一序号。

第 5 节把大多数数字签名换成消息认证码，公钥运算留给很少发送的视图变更与新视图。理由写给 Rampart 的瓶颈：当时 200 MHz Pentium Pro 上，1024 位模数 RSA 签名与一次短消息认证码相差约三个数量级。认证码不能向第三人证明发送者，于是改用「未故障副本不会在同一视图同一序号上为两份不同请求完成准备」这类已证不变量来补足。普通消息携带面向其他副本的认证码向量。这是已发表的性能取舍，不是伪造步骤。

视图变更：换主，不改成员#

备份在收到合法请求却尚未执行时等待。计时器在视图 $v$ 到期，则停止接受普通消息（检查点、视图变更、新视图除外），多播针对 $v+1$ 的视图变更。报文携带最近稳定检查点、证明它的 $2f+1$ 条检查点，以及其后已准备请求的证物：有效预准备（不含客户原文）外加 $2f$ 条相符准备。新主副本收齐其他副本的 $2f$ 条有效视图变更后，多播新视图。

新预准备的填法印在纸上。取出这组报文里最新稳定检查点序号 $\mathrm{min}\text{-}s$ 与准备证物里最高序号 $\mathrm{max}\text{-}s$，为两者之间每个序号写一条新视图里的预准备。有准备证物则采用其中视图号最高的摘要；没有则填空请求。空请求照样走三阶段，执行是空操作。论文注明 Paxos 用过类似填缝。已准备的请求被带到新视图，缺口被空请求填上，成员集合不变。

活性有三句约束：发出视图变更后先凑齐 $2f+1$ 条再等待，下一次等待加倍；若已见 $f+1$ 条针对更高视图的变更，则跟到其中最小者；故障者不能单靠自己一条报文造成换届，主副本按模轮转也不能连续占据无限个视图。除非延迟无限快于超时期增长，活性成立。这仍是弱同步。Rampart 与 SecureRing 要把故障者移出组才能推进，垃圾回收也依赖故障检测器；异步里一次误判就可以破坏三分之一上界。PBFT 从不把副本排除出组。这也与 Viewstamped Replication 里「视图是当时能够通信的伙伴、且必须含多数」分开：这里的视图不是一张随分区收缩的出席名单。

它量了什么，没有量什么#

安全要保证未故障副本对本地提交的序号达成一致。同一视图内，准备不变量禁止两个不同请求占同一序号。跨视图时，本地提交意味着 $f+1$ 个未故障者已经准备，合法新视图又携带 $2f+1$ 份视图变更；两组在 $3f+1$ 下相交于至少一名未故障者。细节在 MIT/LCS/TM-590。它没有证明异步崩溃共识的全称终止，见 FLP。它没有证明与 Paxos 形式等价，没有给出 etcd 与 Raft 那种工程日志，也没有把 $3f+1$ 说成开放账本的本质。共识算法 总览里的后裔，用来标明对象停在哪里。

第 7 节量正常路径延迟。隔离网络，一台客户两个中继，四台副本，可容忍一个拜占庭故障。机器是相同的 DEC 3000/400 Alpha：133 MHz、128 MB、Digital Unix 4.0，10 Mbit/s 以太网。检查点间隔 128。空操作微基准：读写型 $0/0$ 为 3.35 毫秒，相对直接 UDP 未复制实现高 309%；只读优化后 1.62 毫秒，高 98%。与 Rampart 的对照是间接估计，不是同一机房对打。

Andrew 基准比较 BFS、去掉复制的 BFS-nr，以及内核 NFS V2。十次均值。BFS 严格语义 64.48 秒，BFS-nr 为 51.07 秒，相对自身未复制慢 26%。NFS-std 为 62.52 秒，于是 BFS 只慢 3%。把 lookup 改成只读后 61.07 秒，比 NFS-std 快 2%；论文写明这违反严格 Unix 语义。同步操作多的阶段里，NFS-std 靠写盘求稳定，BFS 靠复制求稳定，后者可以更快。复制库当时没有实现视图变更与重传；论文说第 7 节数字因此仍有效，因为其余算法已实现，完整协议已形式化。量到的是无换届、隔离局域网、四副本、正常路径。没有量到视图变更延迟、广域延迟、同时故障大于一、把任意故障写进 Andrew 轨迹、成员变更，以及容错隐私。独立故障也没有用多版本实现去核对。结论里提到一次只在部分副本上出现的软件错误，算法仍给出正确服务；这是作者观察，不是「所有软件错误都能被掩盖」。发生在全部副本上的错误，这套方法掩盖不了。

2002 年 TOCS 长文讨论主动恢复：在时间窗口内保持少于三分之一故障，从而使寿命内可承受超过 $f$ 次故障。那是另一份对象，不要读回 OSDI 的实验表。

跨域连接#

• 认识论：预准备只是主副本的公开提议；$\mathrm{prepared}$ 是「我与足够多备份已对同一摘要发出相符证词」；$\mathrm{committed\text{-}local}$ 是「我还看见 $2f+1$ 份提交，因而知道至少 $f+1$ 个未故障者已经准备」。客户等待的 $f+1$ 份相同答复，把「至少一名诚实副本执行了同一结果」收成可对外引用的知识。认证信道把「我听到主副本这么说」升级为可核验的绑定，仍不能单独证明第三人也会抽出同一序号。换届必须携带检查点证明与准备证物，正因为本地日志里的信念不能直接当成公共知识。把主副本内存里尚未准备成功的排序说成全组已锁定的历史，就是把私有观察误认为知识。
• 可靠性工程：故障单元不是「这一台还能不能 ping 通」，而是「至多 $f$ 个副本可以任意偏离算法，且故障被假定独立」。崩溃模型里 $2f+1$ 往往已经够选值；这里先升到 $3f+1$，再取 $2f+1$ 仲裁，好让沉默与撒谎同时被算术盖住。论文把「先标成故障再移出组」写成危险的正确性依赖：异步里慢与坏分不开，排除诚实者会直接破坏三分之一上界。可用性被钉在固定成员上的换主，而不是动态收缩的出席名单。独立故障、计算上受缚的对手、弱同步只服务活性，都是指标成立的前提。隐私被明确排除在指标之外。
• 立法机构：视图像连续编号的会期，主副本像这一届被点名主持的人，但出席名单不随缺席缩短。$2f+1$ 的仲裁像必须到场才能锁定一条已编号的决议；客户的 $f+1$ 份相符答复像会后向外人出示的同一份纪要摘要。换届要带着上一届已经准备成功的证物和稳定检查点证明开场，空请求填没有证物的序号，以免同一编号被另一条文案占用。比喻能讲清届次、法定人数和纪要，不能把故障副本读成反对党，也不能把协议读成可采购的议事规则。议会有议程、修正案与除名；这份对象既不评价请求好坏，也不把任何人移出议会。
• 集合论：整份正确性几乎不谈毫秒，只谈有限集上的相交。$n=3f+1$ 的全集上，任意两个 $2f+1$ 子集至少交出 $f+1$ 个元素；其中必有未故障者，因为故障至多 $f$ 个。准备集合与新视图所依赖的视图变更集合，正是用这一刀切出「至少一名诚实者同时属于两边」，从而把旧视图里已经准备的摘要送进新视图。水位与稳定检查点把无限可能的序号收成当前窗口里的有限前缀。把这些集合画成机柜拓扑，会把外延对象误认成布线图；它们是证明里的子集，不是分区方案。

参考文献#

• Castro, M. & Liskov, B. Practical Byzantine Fault Tolerance. Proc. 3rd USENIX OSDI, New Orleans, February 1999, pp. 173–186. DOI: 10.5555/296806.296824.（本文对象：已知成员、认证信道、视图、三阶段与 BFS 测量）
• Castro, M. & Liskov, B. Practical Byzantine Fault Tolerance and Proactive Recovery. ACM Transactions on Computer Systems 20(4), 2002, pp. 398–461. DOI: 10.1145/571637.571640.（支撑：主动恢复与更完整陈述；不把 OSDI 实验表改写）
• Castro, M. & Liskov, B. A Correctness Proof for a Practical Byzantine-Fault-Tolerant Replication Algorithm. MIT/LCS/TM-590, 1999.（I/O 自动机上的安全与活性证明）
• Lamport, L., Shostak, R. & Pease, M. The Byzantine Generals Problem. ACM TOPLAS 4(3), 1982, pp. 382–401.（口头与签名消息下的交互一致性；用以限定本文不是 1982 年寓言）
• Fischer, M. J., Lynch, N. A. & Paterson, M. S. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32(2), 1985, pp. 374–382.（完全异步下确定性共识的活性边界；论文用弱同步绕开而非推翻）
• Oki, B. M. & Liskov, B. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. Proc. 7th ACM PODC, 1988, pp. 8–17.（良性故障下的视图与主副本；论文用来对照「换届是否改成员」）
• Herlihy, M. & Wing, J. Linearizability: A Correctness Condition for Concurrent Objects. ACM TOPLAS 12(3), 1990, pp. 463–492.（安全口径所本的线性化；论文声明对拜占庭客户作了修改）
• Reiter, M. K. The Rampart Toolkit for Building High-Integrity Services. Theory and Practice in Distributed Systems (LNCS 938), 1995.（同步假设写入正确性、并用故障检测器移出成员的对照系统）

延伸阅读#

• Castro, M. & Liskov, B. Authenticated Byzantine Fault Tolerance Without Public-Key Cryptography. MIT/LCS/TM-589, 1999.（把认证码向量写进协议不变量的技术备忘；非操作单）
• Schneider, F. B. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys 22(4), 1990, pp. 299–319.（状态机复制框架；确定性与同一初态）
• Chandra, T. D. & Toueg, S. Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM 43(2), 1996, pp. 225–267.（会犯错的怀疑预言；用来对照「检测器加排除成员」不是本协议的安全路径）
• 与 拜占庭将军问题 对读：那一篇是同步口头/签名模型里的交互一致性；本篇是异步认证信道上的状态机复制。
• 与 Paxos、Viewstamped Replication、etcd 与 Raft 对读：前两份与后一份处理崩溃与遗漏；本篇多出预准备、认证与固定成员上的换主。
• 与 共识算法、FLP 对读：总览标明后裔停在何处；FLP 标明活性假设从哪里进来。