拜占庭将军问题与EIG算法：分布式共识的边界与工程启示

做分布式系统的人大概率都绕不开拜占庭将军问题系统里有一批节点它们需要针对某个值达成一致但其中一部分节点不但可能宕机还可能故意作恶、伪造消息、发送互相矛盾的信息。这类问题在文献里被统称为 Reaching agreement in the presence of faults而解决思路中最有代表性、也最常被写进教科书的就是 EIG 算法。这篇论文笔记基于 Pease、Shostak 和 Lamport 的经典论文结合我自己手动推演和写代码模拟的经验把 EIG 的完整思路、运行过程、边界条件一次讲清楚。适合正在啃分布式系统教材、准备面试、或想真正理解拜占庭容错底层的朋友。很多人第一次看到 EIG 这个名字以为又是什么新的分布式框架。其实它就是 Exponential Information Gathering指数信息收集。名字很直白算法通过指数级增长的信息量让诚实节点在充满谎言的信道里找到真相。论文给出的结论和证明方式深刻影响了后来几十年的共识协议设计。我当年读这篇论文的时候最痛苦的不是看不懂结论而是教材里的形式化描述太抽象树和多数投票很容易绕晕。所以这篇文章我会用“带数字的例子”把整个过程走一遍再谈它对现代系统的影响。1. 论文到底在解决什么问题1.1 故障模型不只是节点崩溃在分布式系统里最常见的故障假设是节点宕机或网络分区。这类故障很好处理因为一个节点要么有响应要么永远没有响应诚实节点可以靠超时机制把问题节点隔离掉。但拜占庭故障要恶劣得多故障节点可以做出任意行为包括向我们发送看似合理但实际被篡改的消息甚至在不同节点面前说不同的话。这种模型并不是为了刁难人。在真实系统中一台被入侵的服务器、一个被恶意植入硬件后门的交换机、一个写错了却仍然返回成功的客户端都可能表现出类似拜占庭的行为。更常见的情况是我们拿到的数据来自多个不可信来源比如不同传感器、不同供应商的接口、不同参与者提交的交易其中可能有来源在撒谎。所以论文研究的是一个非常现实的问题当系统里存在 f 个会“骗人”的节点时如何让所有诚实节点仍然就某个值达成一致。这里要先澄清一点论文讨论的是“同步系统”。也就是说消息延迟有一个已知上界节点之间通过点对点信道通信每个诚实节点都能在有限时间内收到其他诚实节点发送的消息。这个假设很重要因为同步系统里可以使用“轮次”的概念算法可以按照固定轮次推进不需要担心无限等待。如果放到异步系统情况会复杂很多这也是 FLP 不可能结论的另外一个故事。1.2 一致性、有效性和终止性达成一致意味着什么在拜占庭容错问题里“达成一致”不是简单地说大家输出同一个数。至少需要满足三个性质一致性所有诚实节点的输出值必须相同。有效性如果所有诚实节点的初始值都是同一个值 v那么它们的输出值也必须是 v。终止性所有诚实节点必须在有限轮次内完成计算不能无限阻塞。有效性的存在很关键。如果我们只是要求“输出相同”那让所有节点永远输出 0 也算“一致”但这明显没有意义。有效性保证了输出结果和输入相关故障节点不能通过发送虚假消息强制诚实节点接受一个凭空捏造的值。论文的核心结论就是在“口头消息”也就是没有数字签名、发送者身份可以被冒充模型下如果系统里最多只有 f 个拜占庭故障节点那么节点总数 n 必须满足 n 3f。换句话说至少要 3f 1 个节点才能保证三个性质同时成立。这个边界不仅是一个必要条件论文还构造了一个满足条件的算法也就是 EIG 算法证明这个边界同时是充分条件。很多初学者会问为什么不是 2f 1直觉上看诚实节点有 n - f 个只要 n - f f即 n 2f诚实节点就占多数为什么还不够问题在于拜占庭节点可以对不同诚实节点发送不同的消息而每个诚实节点只能看到自己的视图。如果 n 2f 1拜占庭节点可以给一半诚实节点说“初始值是 0”给另一半说“初始值是 1”导致诚实节点手里的信息无法互相印证。只有当诚实节点数量大于故障节点数量的两倍时任何一份被怀疑的消息都能找到足够多的独立来源来“投票洗清嫌疑”。所以我个人习惯把 3f 1 理解为“必须让真相的来源至少是谎言来源的两倍再加一”。2. EIG 算法用树结构把消息历史摊开2.1 信息收集树的结构EIG 的核心数据结构是一棵有根树每个节点用一串进程编号作为标签。根节点的标签是空序列比如空字符串。根节点的子节点标签是单个进程编号比如 A、B、C。下一层子节点标签是长度为 2 的序列比如 A-B表示“发送者 A 的消息经过了节点 B 到达当前节点”。标签序列里不会出现重复的进程编号这是协议硬性规定因为一条消息不可能由同一个节点转发两次后仍然保留原始语义。整个树的深度固定为 f 1。为什么是这个深度这其实和“消息最多可能经过多少个诚实的转发者才能被验证”有关。在 f 轮转发之后任何消息路径里如果包含 f 1 个不重复的节点那么即使其中存在 f 个拜占庭节点也至少有一个诚实节点在这条路径上出现过。这个诚实节点可以作为信任锚点帮我们过滤掉一些虚假消息。更深层地说f 1 的深度保证了每个诚实节点都能采集到足够冗余的信息让最终投票时有确定的多数。树里的每个节点都存储一个值。根节点存的是当前节点自己的初始输入其他节点存的信息来自某个消息路径。举例来说节点 C 维护的树里标签为 A-B 的子节点存的值代表节点 C 从节点 B 那里听到的“节点 A 的初始输入值”。因为 B 可能诚实也可能撒谎所以这个值未必是 A 的真实输入但 C 会把它原样记录下来。整个信息收集阶段就是不断往树里填充这些中间值。2.2 两阶段算法先收集再投票EIG 算法可以清晰分成两个阶段信息收集阶段和多数裁决阶段。信息收集阶段严格按照轮次推进总共有 f 1 轮。第一轮每个节点把自己的初始值发送给所有其他节点。当某个节点收到来自节点 X 的消息时它就在自己树里标签为 X 的位置记录这个消息的值。第二轮每个节点把自己第一轮收到的所有值再转发给所有其他节点但不能把这个值发回给标签中已经出现过的节点。具体来说如果当前消息标签序列是 X那么发送给所有不在 X 序列里的节点。收到者会把它记录到新标签 X-Y 下面这里 Y 是自己收到的发送方编号。这个过程一直重复直到树深度达到 f 1。每一轮的信息量都在膨胀因为每个节点都会收到来自其他 n - 1 个节点的、关于上一轮所有标签的信息。这也是“指数信息收集”名字的由来。可以想见这个算法的通信量巨大不是任何实际系统的首选但作为理论构造和教学工具它极其优雅。信息收集完成后进入多数裁决阶段。每个节点从树的叶子层开始向上计算如果当前节点是叶子它的值就保持原样。如果当前节点是内部节点它的值取所有子节点值中的多数。如果子节点值无法形成严格多数就给它赋一个默认值通常是特殊值“未知”或 0。这个计算会递归执行最终根节点得到一个值这个值就是该节点的输出。由于树的结构是固定的而且所有诚实节点执行同样的投票规则最终它们一定能得到相同的输出值。下面是一个简化版的 EIG 核心流程伪代码用于辅助理解。真实运行会涉及网络层的收发但核心逻辑就是这样# 注意这里只展示单个节点的视角忽略网络传输细节 def eig_phase_one(initial_value, node_id, peers, f): tree {(): initial_value} # 第一轮广播初始值给所有人并接收别人的初始值 send_to_all(peers, ((), initial_value)) for sender, value in receive_all(): tree[(sender,)] value # 第2轮到第 f1 轮 for depth in range(2, f 2): for label, value in tree.copy().items(): if len(label) depth - 1: for target in peers: if target not in label and target ! node_id: send(target, label (node_id,), value) for sender, label, value in receive_all(): if sender not in label: tree[label (sender,)] value return tree def eig_phase_two(tree, peers, f): max_depth f 1 for depth in range(max_depth, -1, -1): for label in [lab for lab in tree if len(lab) depth]: children [tree[label (p,)] for p in peers if label (p,) in tree] if children: tree[label] majority(children) return tree[()]这段伪代码其实已经能跑出一个节点内部的树计算但缺少网络消息传递的并发控制。真正理解它的最好方式还是找一个具体场景手动推演一遍。3. 4 个节点、1 个叛徒的手工推演3.1 构建信息收集树从一个拜占庭节点开始假设系统里有 4 个节点分别是 A、B、C、D。其中只有 A 是拜占庭节点它想破坏共识B、C、D 都是诚实节点。三个诚实节点的初始值都是 0。A 的初始值可以是 1但它真正的目的是让诚实节点输出错误值所以它可以任意发送消息。第一轮开始诚实节点 B、C、D 向所有其他节点发送自己的初始值 0。A 呢它为了捣乱可以向 B、C、D 都发送一个虚假的初始值 1。这样第一轮结束后B 的树里有根节点值为 0还有三个子节点 A、C、D值分别是 1、0、0。C 的树类似子节点 A、B、D值分别是 1、0、0。D 的树同理子节点 A、B、C值分别是 1、0、0。第二轮开始前每个节点需要把第一轮收到的值转发给其他节点。我们只看 B 的视角。B 需要把第一轮收到的三个值转发给 A、C、D但不能把“A 的值”发回给 A因为标签 A 里已经有 A 了。于是 B 会向 C 和 D 发送“A 的值是 1”向 A 发送“C 的值是 0”和“D 的值是 0”向 C 发送“D 的值是 0”向 D 发送“C 的值是 0”。由于 C 和 D 是诚实节点它们也会做同样的事。所以 B 最终会收到来自 C 和 D 的关于 A 的值C 告诉 B“A 说它的初始值是 1”D 也告诉 B“A 说它的初始值是 1”。B 把这些值记录下来填入树中的 A-C 和 A-D 节点。同样的B 还会收到 A 发来的各种消息。但 A 是拜占庭节点它可以给 B 发送任意垃圾数据。比如 A 可以给 B 发送“C 的值是 1”但这不会影响最终结果因为后面投票时C 节点的孩子节点里还有其他诚实来源的信息。只看 B 的树关键节点大致如下标签值的来源B 存储的值根节点B 自己的初始值0AB 从 A 收到的初始值1CB 从 C 收到的初始值0DB 从 D 收到的初始值0A-CB 从 C 处听到的 A 的值1A-DB 从 D 处听到的 A 的值1C-AB 从 A 处听到的 C 的值可能为 0 或 1C-DB 从 D 处听到的 C 的值0D-AB 从 A 处听到的 D 的值可能为 0 或 1D-CB 从 C 处听到的 D 的值0到这里B 的信息收集树就建完了。注意树里有很多节点但核心可以用“路径的多样性”来理解每一层值都有多个独立来源。3.2 自底向上投票多数值如何压倒谎言接下来是多数裁决。从树的叶子层开始。深度为 2 的节点都是叶子保留原值。深度为 1 的节点 A 有两个孩子A-C 和 A-D。这两个孩子都存储了值 1所以无论 A 在其他孩子节点里塞了什么垃圾A 这个内部节点的多数值都是 1。再看深度为 1 的节点 C。C 的孩子包括 C-A 和 C-D可能还有一个 C-B。如果 B 不允许给自己发消息那么 C 的孩子就是 C-A 和 C-D。C-A 是 A 告诉 B 的 C 的值A 可能发 0 也可能发 1但 C-D 是 D 告诉 B 的 C 的值D 是诚实的它告诉 B 的值一定是真实值 0。假设 A 发了恶意值 1那么 C 的孩子是 {1, 0}没有严格多数。按照算法如果形成不了多数这个节点会被赋默认值比如 0。这样一来 C 节点的值大概率是 0。同理D 节点的值也是 0。现在根节点的孩子是 A、C、D对应值分别是 1、0、0。三个值中 0 出现两次是多数所以根节点的值被更新为 0。B 最终输出 0。我们再看 C 节点的视角。C 的树里A 的孩子包括 A-B 和 A-D。B 和 D 都诚实B 告诉 C“A 的值是 1”D 告诉 C“A 的值是 1”所以 A 节点的多数值也是 1。B 和 D 的孩子节点也类似最终根节点的孩子值还是 A1、B0、D0因为它们都是按照同样的转发规则收集来的。根投票结果仍然是 0。所以即便 A 在第一轮和第二轮都发送了故意伪造的值四个节点中三个诚实节点依然能通过多数投票得到一致的正确输出。这就是 EIG 算法的核心魅力不是试图识别哪一个节点在撒谎而是用冗余的信息和多数逻辑让谎言失去决定性作用。3.3 如果只有 3 个节点问题出在哪现在我们尝试把节点数减少到 3 个A 是拜占庭节点B 和 C 是诚实节点诚实节点的初始值都是 0。A 给 B 发送初始值 1给 C 发送初始值 0。第一轮结束后B 树里 A 的值是 1C 的值是 0C 树里 A 的值是 0B 的值是 0。第二轮结束后B 树里 A-C 的值是 C 告诉 B 的 A 的值C 诚实C 说 A 的值是 0。C 树里 A-B 的值是 B 告诉 C 的 A 的值B 诚实B 说 A 的值是 1。投票阶段B 树中节点 A 的孩子只有 A-C值是 0。根的孩子是 A0、C0投票结果是 0。C 树中节点 A 的孩子只有 A-B值是 1。根的孩子是 A1、B0没有严格多数如果默认值是 0C 也输出 0。如果默认值恰好是 0这个例子似乎也能“蒙对”。但问题在于如果诚实初始值不是 0或者拜占庭节点变化策略B 和 C 的输出就可能会不同。更关键的是B 和 C 永远无法区分以下两种情况情况一A 是叛徒它对 B 说 1对 C 说 0 情况二A 是诚实的初始值确实是 1但 C 是叛徒它故意告诉 B“A 说的是 0”。在这两种情况下B 看到的视图完全一样但正确输出应该不同。如果是情况一正确输出是 0如果是情况二正确输出是 1。单个节点无法做出正确判断这就是 3f 1 边界在直观层面上的解释。4. 从论文到工程EIG 的边界与替代方案4.1 消息复杂度和同步假设带来的现实警示EIG 算法在理论上很漂亮但直接实现它做真实系统是不现实的。第一个问题就是消息复杂度。每个诚实节点都需要维护深度为 f 1 的树树里每个节点都要有足够的子节点冗余整体通信量呈指数级增长。具体来说总消息量大约是 n 的 f 1 次方级别。当 f 1 时还算勉强但 f 3 时即便 n 10消息量也会爆炸。所以在工程界EIG 更多被当作“可证明边界”的构造而不是直接落地实施的协议。第二个限制是同步假设。EIG 要求每一轮都在已知的超时内完成如果某个诚实节点因为网络延迟没有及时收到消息算法可能就会卡住或者误判。真实公网环境里严格同步是很难做到的。这也是为什么后来的拜占庭容错算法往往需要引入“同步视图轮换”或“锁定机制”来模拟同步环境。但研究 EIG 仍然很有价值。它让我们看到拜占庭共识的理论下界不是凭空而来的而是由信息传播的冗余要求决定的。理解了这个道理再去看 PBFT 这类工程协议就会明白为什么它们把精力花在“减少冗余消息数量”上而不是试图跳过根本性的多数投票。4.2 认证消息为什么能改变界限前面我一直强调“口头消息”模型即消息没有数字签名发送者身份可以伪造。如果允许使用数字签名情况会变得不一样。在认证消息模型里每个节点都有私钥消息带有签名任何节点都无法伪造另一个节点发出的消息。这样一来拜占庭节点的撒谎能力被大大削弱。论文中讨论了这种模型结论是有认证消息时只要 n 2f也就是 2f 1 个节点就足够达成一致。理解这个变化的关键在于签名让“消息来源”变得不可否认。如果 B 收到一条带有 A 签名的消息说“初始值是 1”那么 B 可以确定这个消息一定来自 A哪怕之后 C 告诉 B 一些矛盾的信息B 也知道 C 是在撒谎。这样就不再需要额外一个诚实节点来验证 A 的声明冗余从“三个来源”降到了“两个来源”。下面这个表整理了我认为最核心的模型差异模型节点数下界消息复杂度典型算法口头消息无签名3f 1指数级EIG、OM(m)认证消息有签名2f 1通常多项式级Signed EIG、PBFT 相关思路异步系统故障节点确定性 ≥ 2不存在确定性算法FLP 不可能性这个表格也解释了为什么很多现代区块链共识协议都是基于签名消息的。大家平时接触的 PBFT、Tendermint、HotStuff都是在认证消息模型下做优化所以节点数要求通常是 3f 1但消息复杂度和轮次数比 EIG 友好得多。4.3 从 EIG 到 PBFT再到区块链共识我在读 EIG 论文的时候最大的感受是PBFT 本质上就是 EIG 思想的一次“工程压缩”。PBFT 引入了 Primary 节点来简化信息收集用 prepare 和 commit 两阶段把指数级广播收敛到多项式级但核心逻辑仍然是让诚实节点收集足够多的冗余备份再通过多数投票过滤拜占庭节点。区块链领域里常见的 BFT 共识也延续了同样的套路。节点之间需要交换多轮消息每个节点需要看到 2f 1 个签名消息才能前进。这样即使有 f 个节点作恶诚实节点依然拥有足够的信息来证明自己“看过足够多真实数据”。你可以把 EIG 树里的深层次节点投票理解成一种“分布式证据链”。每一层新增的节点都是在为上层决策增加可信证据。EIG 只是把所有证据无脑收集而现代算法则通过签名、哈希和视图切换来精确地选择关键证据。今天做区块链共识的人可能不会直接实现 EIG但面试和系统设计讨论里经常会碰到类似问题“为什么拜占庭容错最少需要 3f 1”“为什么有些协议在签名模型下只要 2f 1”如果能把 EIG 的边界论证和投票逻辑讲清楚很多问题都能迎刃而解。5. 学习 EIG 常见的坑与自检方法5.1 概念混淆清单我第一次读相关论文时踩过不少坑这里列一个避坑清单。混淆 EIG 和 OM(m) 算法。OM(m) 是 Lamport 在拜占庭将军论文里给出的递归算法EIG 则是对这类树形信息收集算法的更一般表述。很多教材把两者混着用但核心思想是一样的只是树表示更直观。认为 3f 1 是“诚实节点数量至少是故障节点的三倍”。正确理解是“总节点数至少是故障节点的三倍再加一”因为诚实节点是 n - f在这个条件下诚实节点数量约为 2f 1是故障节点数量的两倍多。以为只要有签名就能完全消除故障影响。签名能减少节点数下界但并不能解决所有问题因为拜占庭节点仍然可以产生自己的合法消息并破坏一致性只是无法伪造他人消息而已。忽略“默认值”的处理。在多数投票时如果子节点数量不够或者平票必须有一个既定规则。这个规则虽然看起来只是实现细节但会直接影响性质证明。把 EIG 当异步算法。EIG 依赖严格的同步轮次在异步系统里直接使用会挂掉。5.2 实现与推演时的注意事项如果自己动手写 EIG 模拟我建议注意以下几点标签序列里不能有重复节点。这不仅是协议规定也是信息循环传播的天然限制。实现时一定要在收消息前检查 sender 是否已经在 label 里否则树会长歪。收到的消息可能会缺失。拜占庭节点可以拒绝发送任何消息所以树里有些节点可能不存在。投票时如果子节点缺失不能简单跳过要给学生留一个默认值否则多数计算会出错。每一轮广播时消息体本身要携带完整路径标签而不是只携带值。因为接收者需要知道这条信息经过了哪些节点才能把它放到正确的树节点下。自底向上投票时要先处理深层节点再处理浅层节点。如果不按深度排序内部节点的子节点值可能还未更新结果就会乱套。模拟时建议先固定 f 1n 4打印每一轮每个节点收到的消息确认树结构和预期一致再逐步增加节点数。这样做能很快发现代码中的路径拼接错误。5.3 推荐的学习路径如果你刚接触这个领域我建议先不要急着读论文原文。可以先做三件事用纸笔手动推演 n 4f 1 的例子画出 B 节点的树检查每个节点值。再看 n 3f 1 的例子体会为什么无法同时满足一致性和有效性。自己写一个小模拟把 2.2 的伪代码补全观察不同拜占庭策略下输出是否稳定。完成这三步之后再回头读论文你会发现论文里的那些定理和证明突然变得特别自然。因为 EIG 的所有设计都是为了应对“消息可以被篡改、来源可以被伪造、节点可以撒谎”这三个最恶劣的现实约束。关于这篇论文我个人的体会是它教给我们的不是某个可以直接上线的协议而是一种看待“可信冗余”的方式。真正需要做高可靠系统的时候你会发现大量设计都在重复 EIG 的底层逻辑让关键信息出现在足够多的独立视图中然后用多数来压制异常。把这篇论文吃透再看后来的拜占庭容错研究会顺畅很多。