最近重新翻到 Pease、Shostak 和 Lamport 在 1980 年发表的这篇《Reaching Agreement in the Presence of Faults》越读越觉得有意思。这几年分布式系统、区块链、共识算法的文章铺天盖地但很多人一上来就聊 PBFT、Raft、HotStuff却很少有人回头看看最底层的那个问题在节点可能撒谎的前提下我们到底能不能达成一致又需要多少轮通信、多少消息冗余才能做到这篇论文给出的答案就是 EIGExponential Information Gathering指数信息收集算法。我在工程里落地过类似的一致性协议也在模拟环境里写过小规模的拜占庭场景测试所以这篇论文笔记不打算按摘要、引言、结论的顺序平铺直叙而是想从“为什么要设计成这样”的角度把 EIG 的树构建、信息交叉验证、多数决策这三板斧拆开讲清楚。如果你正准备做分布式一致性相关的项目或者只是想搞明白拜占庭将军问题为什么有这么多的衍生算法这篇笔记应该能帮你跳过不少弯路。1. 问题域在什么前提下“达成一致”才是一个可解的问题1.1 故障假设不只是进程崩溃平时我们写分布式系统默认的故障模型是“崩溃故障”节点挂了就不回复消息丢了就重传。这个模型友好得像一个说好要交作业但突然生病请假的同学你至少知道他会不会交、什么时候交。但如果换一个场景节点不一定是挂了而是被攻破、被恶意控制、或者干脆就是一个故障的传感器在乱报数据问题就变成了“拜占庭故障”——进程还会持续运行但它的行为完全不可预测甚至可能对不同节点发送不同的消息。1980 年这篇论文处理的就是后一种情况。它把故障节点描述为“行为任意”比如可能发送冲突消息、可能选择性沉默、可能伪造来源。这个假设放在今天来看非常实用区块链里的恶意验证者、跨机房同步时的脑裂节点、物联网中被劫持的终端本质都是拜占庭故障。所以你可以把这篇论文看成一切非崩溃容错共识的理论起点。拜占庭故障带来的核心困难在于你接收到一条消息无法判断它是不是“真的”。一个诚实节点报告“我看到的值是A”另一个节点报告“我听到它说的是B”你没有办法直接确定哪一个才是事实只能靠节点之间的冗余信息相互验证。EIG 算法的整个设计都是围绕这个“无法直接判断真伪”的困境展开的。1.2 同步网络假设一切结论都有前提论文开篇实际上隐藏了一个很容易被忽略的前提通信是同步的。所谓同步指的是消息在一个有界延迟内必然到达也就是说我们知道一轮消息最晚什么时候该到齐超过这个时间没到就可以判定对方有问题。这个假设非常重要因为 EIG 算法的轮次结构依赖“f1 轮之后所有诚实节点的信息量一致”这个性质。如果消息延迟无界你根本无法判断“还没收到”到底是对方故障还是网络慢后续的多数决策也就失去了基准。当然今天的工程系统很少能给出严格的同步承诺。Raft 和 PBFT 实际上利用的是部分同步假设系统在某个未知的全局稳定时间GST之后进入同步状态。但 EIG 的意义在于它在最严格的同步模型下给出了确定性的可解证明后来的异步 BFT 算法很多都是在这个结论之上放宽条件的结果。我建议初学者先把同步 EIG 吃透再去碰异步情况下的 FLP 不可能结论。1.3 一个反直觉结论3f1 个节点才能容忍 f 个拜占庭故障论文给出了一个看起来很反直觉的结论如果总节点数为 n拜占庭故障节点数为 f那么只有当 n 3f 时问题才可解。这个结论我最早看到的时候觉得过于保守毕竟在崩溃故障模型下 n 2f 就够了。为什么多了一个 f 的冗余用一个非常朴素的例子解释。假设 n3f1也就是三个节点中有一个是叛徒。诚实节点 A 和 B 各自汇报自己的值叛徒 C 对 A 说“我的值是 0”对 B 说“我的值是 1”。这时候 A 和 B 各自听着两个不同的版本没人知道该信谁。表面上看如果 A 和 B 多交流一轮似乎可以交叉验证 C 的谎言。但问题是即使它们交流A 会对 B 说“C 告诉我它是 0而我自己是 x”B 会对 A 说“C 告诉我它是 1而我自己是 y”。由于 A 和 B 无法确认 C 到底对谁说了真话它们依然会陷入僵局。这个例子的本质是在 n3, f1 时诚实节点无法在信息上形成“交集”无法排除故障节点制造的矛盾。要打破僵局必须让任何一个故障节点在任意一条信息路径上出现次数不超过一次这样多数投票才有意义。这直接引出了 n 3f 的约束。了解这个边界很重要因为我见过不少项目在只有两台或三台机器的情况下就去实现“拜占庭容错”最后发现只是在处理崩溃恢复根本没有真正解决恶意节点问题因为他们没搞懂理论边界。2. EIG 树构建指数信息收集Exponential Information Gathering到底在收集什么2.1 消息传递流程EIG 的核心思路非常直白让每个节点不仅广播自己的值还要广播“它收到了谁的值”以及“它收到了谁转述的谁的值”。这样经过多轮之后每个节点都会拥有一棵记录传播路径的树树的每条路径就代表一条完整的信息链。具体流程分轮进行。第 1 轮每个节点把自己的初始值广播给所有节点包括自己。节点收到后把发件人和收到的值记录在树的第一层。第 2 轮每个节点把第 1 轮收到的所有信息原样转播出去同时附带上“这是谁发给我的”这个来源信息。节点再把这些转发消息记录在树的第二层。依此类推经过 f1 轮每个节点的树上就会有从根到叶长度为 f1 的完整路径。我最初理解这个流程时有一个误区以为每一轮大家广播的是“自己的值”那只要 f1 轮之后所有人不就都知道所有人的值了吗事实不是这样。每一轮广播的核心不是原始值而是“我看到的视图”。也就是第 2 轮广播的实际上是“节点 A 告诉我了它的初始值节点 B 告诉我了它的初始值……”这样一条视图消息接收者根据“谁在转发”来区分这些视图来自哪条路径。正是因为消息里携带了路径信息树结构才能反映出某个节点在某条路径上的“二次转述”后续的决策阶段才能针对性地剔除故障节点。2.2 路径与“你自己告诉你”的区分EIG 树的每个节点用一个序列号或者标签标记这个标签其实就是消息传播经过的节点序列。比如根节点代表初始值标号是空序列根的第 i 个子节点代表“节点 i 在第 1 轮直接广播给我的值”再往下路径 (i, j) 代表“节点 j 转述了它从节点 i 那里听到的值”。这里有一个非常关键的细节路径中不能出现重复节点。换句话说一条路径不会出现 (i, i)因为节点 i 没有必要把“自己听到的自己的值”再转述一遍。所以树的高度等于 f1但每一层可用的节点数在减少。更准确地说整棵树的节点总数是 n 加上 n(n-1)再加上 n(n-1)(n-2)直到 n 的阶乘级别的路径数。这正是“指数信息收集”这个名字的由来——系统的总消息量随着轮数指数膨胀。理解这个路径设计就能明白一条重要性质任意两条不同路径的交集最多只有 f 个共同节点。换句话说如果一条路径里混入了故障节点最多也只能跟另一条路径在 f 个节点上产生交集这为后面“保留诚实信息、排除故障信息”的多数决策提供了结构保证。2.3 在最小案例 n4, f1 中构建树我们用最小的可解案例来走一遍完整流程。系统里有 A、B、C 三个诚实节点分别持有初始值 x_A、x_B、x_C还有一个故障节点 D。按照 n 3f4 个节点最多允许 1 个拜占庭节点所以 f1需要运行 2 轮。第 1 轮结束后每个节点都会收到来自全部 4 个节点的初始值广播。以诚实节点 A 为例它的树第一层记录了A 自己广播的 x_AB 广播的 x_BC 广播的 x_CD 广播的某个值 d_A注意 D 可能对每个节点都发送不同的值这里 d_A 表示 A 收到的版本。第 2 轮A 会把“我收到 x_B、我收到 x_C、我收到 d_A”这些信息打包然后广播给 B、C、DB 和 C 也会做同样的事情。这一轮结束后A 的树第二层就会多出大量路径。比如路径 (B, C) 表示“C 转述了它从 B 那里收到的值”路径 (D, C) 表示“C 转述了它从 D 那里收到的值”。注意A 本身不需要转述自己收到的 D 消息因为它自己就站在路径的末端但 A 可以通过比较“我直接从 D 收到的值”和“B 转述的 D 给 B 的值”以及“C 转述的 D 给 C 的值”来判断 D 是不是在撒谎。现在有了完整的树决策阶段就可以开始。如果 D 是故障节点它可能在两个诚实节点面前表现得不一样但 A、B、C 之间的两轮信息交换必然会让 D 的矛盾暴露出来。树中某些路径上的值会产生冲突这些冲突恰恰是识别故障节点的依据。3. 决策规则与正确性论证多数投票为什么在这里是真的可行3.1 从叶子上“修剪”故障节点拿到一棵完整的 EIG 树之后怎么得出最终决定论文给出的规则可以拆成两部分。第一部分是“一致性校验”。节点 A 需要检查树中的每条路径看看是否存在“同一节点在不同路径上说了互相矛盾的话”。例如A 直接收到 D 的值是 d_A但 B 转述说“D 告诉 B 的值是 d_B”而 d_A ≠ d_B那么 A 基本可以断定 D 是一个故障节点。此时 A 会丢弃所有包含节点 D 的路径也就是从第三层往下把它从树里剪掉。关键是这一步并不是“判断 D 是否故障”的绝对证明因为一个故障节点可能在某些路径上表现得完全一致也可能一个诚实节点因为某个异常流程被误判。但 EIG 的巧妙之处在于它不要求每个节点对“谁故障”达成一致观点它只是用这种剪枝操作把明显冲突的信息从决策池中排除出去。第二部分是“多数决策”。剪枝之后每个节点对它树中“顶层各分支”的值做多数投票。具体规则是从叶子往上递归计算如果一个节点的所有子树都持有相同值这个值就向上传导如果不一致就取子树中的多数值如果没有多数值则采用故障处理下的默认值。递归到根节点时得出该节点认为的系统一致性值。这里的多数投票跟普通的数据备份多数投票完全不同。普通投票只需要大多数节点在线即可EIG 的投票则是建立在“每一条路径的独立性”之上。因为故障节点最多 f 个而任意两条通往叶子的路径交集不超过 f 个节点所以一旦某个值在叶子层形成了多数这个多数的结论就必然会传递到所有诚实节点的根节点。换句话说这个多数不是统计意义上的“大多数而是信息冗余意义上的一种“不可能被伪造的利益联合体”。3.2 正确性证明的关键引理教科书上通常用两个引理来证明 EIG 算法的正确性我用大白话复述一下。引理一是两个诚实节点的树在经过了 f1 轮信息交换之后对于任意一条不包含故障节点的路径它们记录的值是相同的。原因很简单因为这条路径上的每个节点都是诚实的它们的转述不会篡改信息所以无论从哪个诚实节点去看这条路径得到的结果都是一致的。引理二是如果故障节点试图在两条包含它的路径上分别传递不同的值那么这两条路径必然会被某个诚实节点的剪枝操作识别出来即使没有识别出来多数投票也会把那个被篡改的分支淹掉。这个结论要归功于路径交集的上限故障节点出现的次数有限它不可能同时压过所有诚实节点汇合而成的信息主流。这个证明思路对我最大的启发是它不是去证明“每个节点都能准确识别出故障节点”而是证明“即便某些故障节点没有被识别出来多数决策的结果也完全一致”。这种从“结果一致性”出发的证明思路在工程上非常实用。因为现实项目中我们很少能精确定位哪台机器出了故障很多时候只能确定“这群数据里混了脏数据”但只要我们能在输出层面达成一致系统照样可以对外提供正确服务。3.3 同步假设与 f1 轮的实际意义为什么恰好是 f1 轮而不是 f 轮或者 f2 轮可以从两个方向理解。从信息传播的角度看每一轮都让每个节点的“视野”向外扩展一层。要做到所有诚实节点的视图足够交叠必须让每条消息有足够的时间穿过由诚实节点组成的“信息骨干”。f 个故障节点最多可以沿路径打断 f 次所以需要 f1 次传播才能确保至少存在一条完整的诚实路径把某个值从发起者传到每个诚实节点的视图中。从异步边界来看如果只看 f 轮故障节点有可能在最后一轮之前一直保持沉默让所有诚实节点都以为它不存在然后在最后一轮突然向部分节点发送不同的消息造成混乱。f1 轮就保证了一个故障节点制造的矛盾即使发生也有剩余轮次被诚实节点的交叉验证暴露出来。工程上做超时设置的时候也可以参考这个概念如果容忍一次故障至少需要两个有效的通信来回才能让系统稳定地达成一致。4. EIG 的代价与现实世界的取舍4.1 消息量是指数级的不是开玩笑EIG 的完整运行需要多少消息粗略估算一下每轮每个节点都要向其余 n-1 个节点广播自己当前树中的全部路径信息而树中的路径数量随着轮数指数增长。在 f1 轮结束时总消息量大约在 O(n^(f1)) 级别确切说是指数级复杂度。对于 f1n4 的小案例这个数字还勉强能接受但如果系统有 100 个节点、需要容忍 10 个拜占庭故障消息量就会膨胀到天文数字这在实际网络里完全不可行。这就是为什么 1980 年论文给出了一个理论上漂亮的算法但工程上很少直接实现 EIG。现代 BFT 算法比如 PBFT会把通信复杂度降到多项式级别核心手段是引入“视图”和“主节点”让每一轮不再广播整棵树路径而是广播摘要和签名。但 PBFT 的正确性论证里依然有 EIG 的影子——只不过它把“指数路径冗余”换成了“多项式多轮交互 数字签名”。如果你在做教学或者仿真实验我建议还是先实现一遍 EIG。它的代码量不大但能很直观地看到拜占庭故障对共识过程的搅动作用。我在自己的测试环境里用 Python 写过 n5、f1 的 EIG 模拟最后生成的树结构信息非常清晰比直接看 PBFT 的论文实现容易理解得多。4.2 EIG 与区块链共识的关系很多人问既然 EIG 这么古老跟现在区块链里的共识算法有什么关系其实关系非常大。中本聪共识工作量证明本质上是通过算力投票来替代拜占庭节点之间的交互验证它能在开放网络里工作是因为“计算资源”约束取代了“故障节点上限”约束。而在联盟链或许可链里PBFT 类算法动辄要求 n 3f这正是从这篇论文继承下来的基础结论。哪怕以太坊的 Casper FFG 这类基于权益证明的共识也无法绕开对拜占庭节点比例的严格假设。从另一个角度看EIG 的信息收集思想在“跨链验证”和“轻节点验证”中也有应用。很多跨链协议要求中继链对目标链的状态进行多路采样验证实际上就是不同路径上的节点分别汇报自己看到的状态摘要而合约根据多数一致的结果做出最终判断。这和 EIG 树中从多个路径汇聚信息再多数投票的逻辑是相通的。4.3 什么时候 EIG 是“划算”的虽然指数级消息复杂度很吓人但 EIG 有个常被人忽略的优势它不需要数字签名。该算法只依赖多轮交互和路径交叉就解决了拜占庭问题这在 1980 年是一个非常大的贡献因为当时的密码学开销被认为非常昂贵。如果你的应用场景满足以下条件EIG 反而可能是一个值得考虑的方案节点数量很小比如 4 到 8 个故障轮次很少通常只需要容忍 1 个故障网络是同步的通信延迟有界开发环境难以引入复杂的密码学或者签名库。在这种极限场景下EIG 比 PBFT 更简单、更容易证明正确性也不需要维护视图切换逻辑。我自己试过在一个低功耗嵌入式采集系统里模拟过类似流程节点之间用共享内存通信最后的一致性效果非常稳定代码量也控制在几百行以内。5. 从 1980 年的论文到现代工程我读 EIG 的四个实际收获5.1 故障越“聪明”方案越要依赖结构而不是技巧早期我也尝试过用启发式规则来识别拜占庭故障比如“如果某个节点的值连续多次与其他节点不同就标记为故障”。这种思路在故障节点行为固定的时候有效但只要故障节点稍微聪明一点轮流对 A 撒谎、对 B 说实话、对 C 沉默启发式规则就会被绕过。EIG 给了一个彻底的方法论转向不要试图猜谁在撒谎而是通过让信息沿着不相交的路径汇聚使得撒谎行为在数学上不可能不被多数淹没。这就像审计账目时不靠肉眼辨别哪张发票是假的而是强制要求同一笔交易必须经多个独立渠道交叉验证假发票自然就被结构隔离出来了。这个思路对架构设计有很强的指导性——与其强化单点检测不如设计信息冗余的结构。5.2 同步假设不是理论家的玩具而是系统的兜底每次我跟团队讨论系统设计时都会反复强调延迟上界timeout和轮次设计。在无界延迟的网络里任何确定性共识算法都不可能同时满足安全性和活性这是 FLP 定理的结论。EIG 虽然是 1980 年的论文但它已经把“同步假设”作为整个协议运行的前提你能在最原始的版本里看到一个概念的最纯粹形态。现代工程中我们常用超时和重试来近似同步假设但要记住超时设置的背后就是 f1 轮思想的实践。如果超时太短诚实节点被误判为故障节点如果超时太长系统活性受损。理解了 EIG 对轮数的敏感性你在调参的时候至少能意识到这不是单纯“拍脑袋定 10 秒”的问题。5.3 多数决策之前必须先有“可比较的信息视图”很多人写一致性协议时直接就对各节点的上报值做多数投票但别忘了投票的前提是大家投票的对象一致。EIG 树的第一个作用其实是“对齐信息视图”经过 f1 轮交换之后每个诚实节点都有了一棵结构相同的树差异只在于具体路径上的值可能被故障节点污染。这为后面的多数投票建立了一个公共坐标系。我在实际项目里踩过一个坑两个数据中心各自维护一个本地状态版本号然后试图在它们之间做“多数投票”决定哪个版本应该保留。结果发现两个中心看到的节点列表都不一样投票根本没法进行。后来我引入了一个虚拟的公共历史结构相当于 EIG 树的简化版先让所有节点对齐自己的视图再做多数判断功能才稳定下来。5.4 老论文的数学工具到今天依然可以用EIG 论文里用到的路径、树、交叉验证、多数合并这些工具本质上是一套组合数学方法。今天你在实现 Sharding 分片、数据副本修复、甚至多层联邦学习聚合的时候都会遇到类似的“信息来自多个源头需要融合确认”的问题。一个人如果只懂得用最终一致性或者 Paxos 这类现成协议遇到新的场景大概率会抓瞎反过来如果掌握了 EIG 的这种树状信息收集和路径冲突识别框架自研一个轻量级拜占庭容错协议并不是难事。我读这篇论文的最大感受是它把“共识”这个看似抽象的问题转化成了“树的构造与树的修剪”这种非常具象的算法问题。如果你愿意动手实现建议从 n4、f1 的无签名版本开始把树的层次打印出来逐步观察故障节点在树上制造的分歧。把这张图看明白之后再去看 PBFT、Tendermint、HotStuff都会觉得顺理成章。最后再分享一个小技巧做论文笔记时不要只摘抄结论尽量把每一轮的消息示例手动走一遍。EIG 这种轮次型算法亲手在纸上画一遍树胜过读十遍证明。你一旦理解了“路径”和“交集”这两个概念整个分布式系统里的拜占庭问题就再也不会绕晕你了。