拜占庭将军问题

破除误解：不是崩溃，也不是一次真实的围城#

第一层误解把题目当成历史。论文里的将军、信使与城池是叙事装置，用来把「没有上帝视角、却必须一致行动」讲成可想象的现场。兰波特后来说明，早先标题曾用「阿尔巴尼亚将军」，匿名审稿人觉得不妥，才改成拜占庭，取其宫廷倾轧的联想，而不是考证公元六世纪的战史。读者若去对君士坦丁堡的年表，会走错书架。

第二层误解把拜占庭故障与崩溃故障捆成一个词「容错」。崩溃模型里，出错的进程安静停机，不再发言；口头消息模型里，叛徒可以在同一轮里向不同副将送达不同内容。兼职议会与 Paxos 与 etcd 的 Raft 处理的是前一种：信使可以迟到、丢失、重复，但不被写成「伪造别人的已接受记录」。把 1982 年的定理直接说成键值集群的正确性证明，等于把故障模型偷换成另一个对象。

第三层误解把 $3f+1$ 听成一条与消息类型无关的工程常数。论文的关键对照恰恰是：口头消息下，少一个将军就可能让忠诚者无法分辨「司令在撒谎」与「同僚在撒谎」；一旦忠诚者的签名不可伪造、改动可被察觉，同样的交互一致性可以在弱得多的人数条件下成立。数字跟着假设走，不是一条可以贴在机柜上的万能配额。

第四层误解把这篇论文读成实用拜占庭协议或开放账本的起源章。Castro 与 Liskov 1999 年的 PBFT，以及后来开放成员网络里的各种账本协议，都改了同步假设、认证方式、成员是否事先已知。后裔用来限定对象停在哪里，不能把 TOPLAS 文本扩成一份产品编年。第五层误解则把本题与「两将军问题」混为一谈：后者问的是两条不可靠信道上两个忠诚者能否确认对方已收到；本题假定送达正确、发送者身份可知、缺席可被察觉，难处在叛徒而不是邮路。

装置：司令、副将、交互一致性#

论文把 $n$ 名将军写成一名司令与 $n-1$ 名副将。司令发出进攻或撤退一类的命令，副将互相转告自己听到了什么。目标不是评哪份命令更明智，而是让所有忠诚的副将服从同一条命令；并且，若司令本人忠诚，这条命令必须就是他发出的那一条。文中把这两句叫作交互一致性的 IC1 与 IC2。有效性藏在 IC2 里：忠诚司令的命令不能被叛徒改写成另一份公共决议。

口头消息的三条假设把装置钉死。每一封被送出的消息都被正确投递；收信人知道信是谁写的；该来而没来的消息，其缺席可以被察觉。第三条尤其要紧：它把模型放进能够侦测「超时未至」的同步世界，而不是稍后 FLP 定理那种完全异步、崩溃与延迟不可区分的世界。见 分布式计算理论 对那条活性边界的陈述。叛徒的能力被写成模型里的许可，而不是一份攻击步骤：他可以对不同收信人给出不同内容，也可以在该发言时保持沉默。

忠诚者不会伪造他人的口头身份。发送者可知，意味着「这封口头信来自谁」对收信人不是谜。装置还有一处常被滑过的几何：论文默认任意两名将军之间都有直达信使，通信图是完全图。后来的文献会问更稀疏的网络里界限如何移动，那是另一份对象。1982 年文本证明的，是在这套完全连接、缺席可察、口头或带签名的信道上，忠诚者要满足 IC1 与 IC2，人数与轮次必须怎样。把完全图读成机房布线清单，会把思想实验误认成部署图。

口头消息：三个将军为何不够#

口头消息下最干净的不可能性，发生在三名将军、一名叛徒。忠诚副将面对两份互相冲突的报告：一份声称来自司令，一份声称来自另一名副将。他无法用口头信道证明「我听到的就是原文、未被改写」。若司令是叛徒，他可以对两名副将下达相反命令；若一名副将是叛徒，他可以对另一名副将谎报司令的话。对剩下那名忠诚副将，这两种世界给出的证据形状可以相同。

他若按一种解释行动，就会在另一种解释里破坏 IC1 或 IC2。人数太少，不是因为「投票不够热闹」，而是因为两套叙事无法被第三份独立的忠诚证言拆开。把 $m$ 个叛徒、$n$ 名将军一般化，论文证明：口头消息下，若 $n \le 3m$，则不存在满足 IC1 与 IC2 的解。直觉是忠诚者必须在去掉至多 $m$ 份任意证词之后，仍能压住叛徒同时编织的两套故事。

少一名忠诚者，证明里可以把剩余忠诚者分到两个无法用第三份独立证词互相否证的箱子里。这里的划分是集合论对象，不是一份把活系统拆成隔离区的操作说明。$3m+1$ 是让「多数在去掉 $m$ 个任意声音后仍然成其为多数」的算术下限，不是经验调参。可能性方向由递归算法 OM($m$) 给出。OM($0$) 里司令把值发给每一名副将，副将就采用自己收到的值。

OM($m$) 里司令先发送；每名副将再以司令身份，在规模更小的实例 OM($m-1$) 里，把自己收到的值转给其余副将；每名副将最后对自己收集到的那一向量取多数。递归深度对应叛徒数上界：每一层用多数把至多 $m$ 份谎言摊薄。算法要求 $n \ge 3m+1$，并且要跑 $m+1$ 轮口头交换。它是存在性证明的构造，不是实现手册：没有超时毫秒，没有报文格式，也没有教人如何在真实网络里注入矛盾内容。

多数在这里仍然不是社会选择里的偏好加总。向量里的每一格是「某人声称司令说了什么」，多数只是从互相污染的转述里抽出一个可被所有忠诚者同样抽出的值。若司令忠诚，所有忠诚副将收到的第一跳相同，后续谎言不够改写多数。若司令是叛徒，IC2 不再约束命令内容，IC1 仍要求忠诚副将抽出同一个值。OM($m$) 保证的是后一句在口头模型里仍能成立，只要人数过线。

签名消息：同一问题，另一条界限#

书面或签名消息给装置加上第四条假设：忠诚者的签名不可伪造，对已签名内容的改动可被察觉，任何人都能核验签名是否属于声称的那名将军。叛徒仍可对自己的话签字，也可选择不签；他不能把一名忠诚者从未签发的命令，做成看起来由那名忠诚者签发的证据。口头模型里「我转述他的话」没有证物；签名模型里，证物可以随信转发，忠诚者看见的是同一份不可抵赖的文本链，而不是两套无法对质的口述。

算法 SM($m$) 让司令发出带自己签名的命令；副将把尚未见过的、签名链合法的命令集合继续签上自己的名字并转发。收集在 $m+1$ 轮后停止。每名忠诚副将看到的，是同一类可核验证据：哪些命令曾经被哪些人签发过。若司令忠诚，伪造不了的签名把 IC2 钉死；若司令是叛徒，忠诚副将比较的是同一份可转发的签名集合，而不是互相矛盾且无法出示原文的口头转述。

论文摘要的表述是：书面不可伪造消息下，问题对任意将军数与任意叛徒数可解。后文构造 SM($m$) 时，通常还需要至少两名忠诚者，以免「一致服从」在只剩一人时变成空句子；教科书因此常写成 $n \ge m+2$。口头情形没有这种空转：三分之二是硬界限。这条移动不是「同样证明里多写一句加密」，它改的是证据的可转移性。口头消息里，甲对乙说「丙告诉我进攻」，乙无法把这句话变成对丙的质询凭证；签名消息里，乙拿到的是丙的签名件，可以出示给别人。

下界因此不再需要用人数去对冲「同一句话的两个版本」。把 SM($m$) 读成部署公钥基础设施的步骤，或读成教人如何伪造证书，都离开对象。需要记住的只是：认证改变的是模型，模型改变的是可能与不可能的分界。签名假设本身也有边界。它不自动提供同步；缺席可察仍然来自口头模型里那条假设。它也不处理「谁算一名将军」尚未确定的开放成员网络，那是后来账本协议另加的身份与资源问题。1982 年文本里的签名是思想实验里的不可伪造记号，不是某家证书机构的产品保证。

它证明了什么，没有证明什么#

它证明了：在送达正确、发送者可知、缺席可察的口头消息模型里，交互一致性可解当且仅当忠诚者严格多于三分之二，构造性算法是 OM($m$)；在加上不可伪造签名之后，同一条交互一致性可以在弱得多的人数条件下求解，构造性算法是 SM($m$)。它把「撒谎」从日常道德词改写成一种故障：同一轮、同一发送者、对不同接收者给出不相容内容。忠诚者必须对行动达成一致，而不是对叛徒的内心达成一致。

1980 年三人先在 Journal of the ACM 以更短、更形式的「存在故障时达成一致」发表核心数学。1982 年这篇 TOPLAS 论文是把同一核心写成围城装置、并清楚分开口头与书面两条信道的那一篇。对象停在后一篇的叙事与定理，不把前一篇吞掉，也不把后裔协议算进正文。它没有证明异步崩溃共识是否可能。1985 年 Fischer、Lynch 与 Paterson 的 FLP 结果，假定的是完全异步加上一次干净停机；口头拜占庭模型里「缺席可察」已经引入时间。两条不可能性切的是不同的前提，不能互相当引理。

它也没有证明 兼职议会与 Paxos 的安全声明。Paxos 的相交多数锁住的是崩溃与遗漏下的已接受值，不处理口头矛盾证词。它更没有给出复制日志如何变成键值存储，见 etcd 的 Raft；也没有给出开放网络里如何定义一票。把 $3m+1$ 说成「区块链的数学本质」，会跳过成员已知、信道认证、同步与激励这些后来才进入模型的句子。实用拜占庭状态机复制属于 分布式共识算法 的后续文献，不是 1982 年文本的缺页。

它也不证明真实立法或选举应当怎样计票。IC1 与 IC2 要求忠诚者服从同一命令，并不比较命令的好坏，也不把叛徒映射成政治反对派。社会选择理论问的是如何把许多排序加总成社会排序，那是另一条不可能定理家族。围城寓言有效，是因为它让「证据不能被忠诚地出示给第三人」变得可想象；寓言失效，一旦有人把忠诚与叛徒读成道德谱系，或把算法轮次读成作战计划。概念证据到此为止：不提供节点清单，不提供可用区拆法，也不把伪造签名或隔离通信写成步骤。

跨域连接#

• 社会选择理论：阿罗定理问如何把许多人的排序加总成社会排序，并证明几条温和公理不能同时成立。拜占庭将军问题问的不是偏好加总，而是在有人提交不相容证词时，忠诚者如何锁定同一条已发出的命令。两边都出现「多数」，机制却不是同一个。社会选择的多数是福利判断的聚合规则，可以循环、可以被议程操纵；口头消息算法里的多数是从被污染的转述向量里抽出一个可被所有忠诚者同样抽出的值。把 OM($m$) 读成少数服从多数的民主算法，会把 IC2（忠诚司令的命令必须被服从）错认成对命令内容的评价。论文不比较进攻好不好，只保证忠诚者不会各执行一份互相矛盾的命令记录。
• 认识论：口头模型的核心困难是证言的不可转移。副将甲告诉副将乙「司令说进攻」，乙得到的是甲的证言，不是司令的证物。签名把证言升级为可出示的证据：同一份文本可以在忠诚者之间转发而不失去与签发者的绑定。这不是怀疑主义练习，而是把「听过」与「能够向第三人证明自己听过」拆开。知识论里内在确证与公共可检验性的区分，在这里变成信道假设。工程事故常发生在把本地听到的值当成已被全体忠诚者共享的公共知识；论文的 IC1 要求的正是后一种，且只对忠诚者承诺。
• 集合论：口头下界 $3m+1$ 的内容几乎不谈延迟数字，只谈有限集上的划分。$n$ 名将军、其中至多 $m$ 名任意坏掉，剩下的忠诚集必须大到：去掉任何 $m$ 个位置后，多数关系仍然把忠诚者粘在同一值上。口头不可能性证明的几何，是叛徒可以把忠诚者分到两个无法用第三份独立证词沟通的箱子里。签名模型改变的不是集合大小的算术本身，而是元素上可携带的标签：签名让「来自某忠诚者的值」成为可在集合间移动的对象。把这些集合画成机柜拓扑，会把外延对象误认成布线图。
• 立法机构：真实议会用记录、唱名与鉴证防止会后改口，用法定人数防止空场立法。《拜占庭将军问题》把「记录可否被第三人核验」写成信道类型：口头相当于不可出示的转述，签名相当于不可伪造的会议纪要。寓言有效，是因为立法机构本来就担心同一议长对两院说出两套决议。差别同样硬：议会有党派、修正案与议程控制；论文里的忠诚者没有偏好，只有一致性义务。制度比喻能讲清证物，不能把政治过程塞进 OM($m$) 的递归。
• 时间哲学：缺席可察把「现在」偷偷送进模型。口头消息的一轮有截止：该到而未到的信，被当成一个可检测的事件，而不是可能仍在路上的延迟。这与完全异步里「慢与死不可分」相反，也与日常那种人人共用一个薄薄「此刻」的时间观不同。选定发生在有限轮次的交换之后，先后由轮次与消息因果给出。把超时写成墙上时钟校准，会把同步假设绑到误差上；论文绑定的是「缺席是可观察对象」。FLP 后来证明，拿掉这层可观察的缺席，连一次崩溃都能挡住确定性终止——那是另一条时间与知识的边界。

参考文献#

• Leslie Lamport, Robert Shostak & Marshall Pease, "The Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems 4(3), 1982, pp. 382–401. DOI: 10.1145/357172.357176. —— 本文对象：口头与书面消息下的交互一致性。
• M. Pease, R. Shostak & L. Lamport, "Reaching Agreement in the Presence of Faults", Journal of the ACM 27(2), 1980, pp. 228–234. DOI: 10.1145/322186.322188. —— 同一核心数学的更短形式陈述，用以限定 1982 年叙事装置所依附的定理。
• Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985, pp. 374–382. DOI: 10.1145/3149.214121. —— 异步崩溃模型的活性边界，用以说明本文对象没有证明什么。
• Miguel Castro & Barbara Liskov, "Practical Byzantine Fault Tolerance", OSDI, 1999. —— 后续实用状态机复制，对象页见 PBFT；用来标明 1982 年论文不是产品史。

延伸阅读#

• 与 莱斯利·兰波特 对读：逻辑时钟处理事件偏序，本篇处理口头矛盾证词下的一致行动，不要收成同一个「时间」故事。
• 与 分布式计算理论 对读：先分清口头拜占庭的同步假设与 FLP 的异步崩溃，再看 $3m+1$ 数字从哪一条前提长出来。
• 崩溃容错的决议对象见 兼职议会与 Paxos；复制日志的工程路径见 etcd 的 Raft，都不是本篇的缺页补丁。