Byzantine Generals Problem

想象几支部队驻扎在一座城的周围。他们必须一起进攻或一起撤退，行动分裂可能带来灾难。指挥官派人传令，但有人可能背叛，对不同的人讲不同的版本。可靠的参与者怎样才能最终采取相同的行动？这并非真实战役的记载，而是帮助理解计算机如何保持记录一致的思想实验。例如，多台服务器，也就是共同提供服务的计算机，需要一致判断某笔付款是否已经处理。每台机器收到一个答复还不够，这些答复必须能支持共同的决定。 [1] [9]

Leslie Lamport、Robert Shostak 和 Marshall Pease 在1980年关于故障条件下达成一致的研究之后，于1982年7月发表了这个著名表述。故事中的叛徒代表行为已无法预测的系统组件。计算机不一定只是停机：它可能正确回答一个邻居，却错误回答另一个，也可能漏发消息或声称看到了不同内容。原因既可能是攻击，也可能是程序错误。拜占庭故障描述的是其他参与者观察到的行为，而不是设备的意图。BFT (Byzantine Fault Tolerance)，即拜占庭容错，指系统在明确条件下承受此类行为的能力。 [1] [2]

原始问题提出两个条件。IC1要求所有可靠的下属接受同一个命令；IC2补充说，如果指挥官也可靠，他们必须接受指挥官实际发出的命令。缺少第二个条件，“永远撤退”似乎就能解决问题，却会无视诚实的指挥官。计算机系统区分安全性与活性：前者禁止相互矛盾的结果，后者要求系统能够取得结果。另一些规则规定哪些结果才有效。记录一致本身并不能证明输入的说法符合外部世界的事实。 [1] [9]

把指挥官称为A，下属称为B和C。C收到A的进攻命令，但B告诉C，指挥官要求撤退。是B说谎，还是A向两人发了不同命令？如果没有转发后仍可验证的签名，C可能无法区分这两种情况。B也可能遇到同样的困惑。如果他们永远听从指挥官，恶意的A就能让他们分裂；如果永远忽略指挥官，又不满足诚实指挥官应被服从的条件。因此，在三名参与者中可能有一名叛徒的这个问题里，不存在不使用签名却总能成功的程序。障碍在于缺少可区分两种情况的信息，而不是计算机不够快。 [1] [9]

在经典的无签名模型中，要容忍最多m名叛徒，至少需要n ≥ 3m+1名参与者；容忍一名就需要四名。这里n是参与者总数，m是系统需要容忍的最大叛徒数量。这并非增加一票、数一次多数就够了。OM(m)让参与者反复转述自己听到的内容，并按相同规则评估消息；基本情形OM(0)直接采用指挥官的值，或约定的默认值。模型假设参与者已知、两两能够直接通信、已发送的消息正确送达、接收者知道直接发送者是谁，并能识别缺失的消息。所以“无签名”并不是“完全不验证来源”。离开这些假设，四这个数字不保证任何结果。 [1] [9]

有了可验证的数字签名，即Digital Signature，B可以向C出示指挥官实际签署内容的证据。程序用私钥，也就是一个秘密数值，生成签名。其他人用对应的公钥就能验证签名，无须知道私钥。叛徒无法悄悄改掉可靠参与者的命令，也无法仿造其签名。签名消息算法传播已签名的值，并使用共同的选择规则。在该模型中，上述诚实多数的要求不再适用，但签名不可伪造、消息送达和轮次时间条件依然不可少。Dolev与Strong在1983年的研究进一步讨论了所需轮数。即使签名有效，也不能保证内容真实或消息按时送达，更不能证明私钥没有被盗。它证明某条消息的来源，而不是发送者在所有事情上都可信。 [1] [3]

服务器不回复时，其他机器不知道它已经停机，还是连接特别慢。Michael Fischer、Nancy Lynch与Michael Paterson于1985年发表的FLP结果精确刻画了这种不确定性。这里的进程指正在运行的程序。确定性程序在状态和输入相同时，会执行相同的下一步，而不是随机选择。在完全异步、没有已知延迟上限的系统中，只要允许一个进程崩溃停机，确定性程序就无法保证在每一种允许的执行过程中都完成共识。即使消息最终可靠送达，只是延迟没有界限，这个结论仍成立。它并不是说永远无法达成一致。实际系统会加入时间假设、具有合适性质的故障检测器或随机性。网络分区时，等待可能比确认两个不兼容的结果更安全。 [4] [13] [8]

Miguel Castro与Barbara Liskov在1999年提出Practical Byzantine Fault Tolerance，简称PBFT，用于由多个已知副本运行的服务。这些副本在不同服务器上运行，持续处理相同的请求，并不是存放起来的备份文件。基本配置n = 3f+1可容忍f个故障副本。四台服务器里允许一台出现拜占庭故障；任意两个三台服务器的集合至少重叠两台，其中至少一台可靠。协议要求的这类同意集合称为法定人数集合，即quorum。但重叠本身还不够，各阶段和更换主节点的规则也很重要。具体而言，prepared状态要求请求、pre-prepare消息以及来自不同非主副本的2f条匹配prepare消息；本地确认还需要2f+1条commit消息，可以包含自身的一条。来源验证、序号与检查点用于应对伪造、重放和日志无限增长。安全性不依赖时间界限，但持续取得进展需要额外的延迟条件。 [5] [10] [11] [12]

Bitcoin没有事先封闭的服务器名单。如果每个新建账户都有一票，攻击者就能制造多数，这称为Sybil Attack。因此，Proof of Work把出块与计算工作联系起来。区块是加入共同历史记录的一批交易。Full Node是运行软件、独立验证规则的计算机，它先拒绝无效区块，再在有效分支中选择累计工作量最大的分支。Bitcoin并不运行OM或PBFT，临时分叉是其运行的一部分。在诚实算力具有足够优势、通信条件适当时，更多确认会降低历史被改写的风险，但不会产生绝对不可逆性。Bitcoin Backbone研究的正是这些条件：各方历史如何一致、链如何增长，以及诚实参与者能够生成多大比例的区块。 [6] [7]

听到“网络达成共识”时，不妨追问：谁能参与，攻击者控制什么，消息可能延迟多久，决定在什么条件下还能改变？即使Proof of Work也无法消除一切问题。Eclipse Attack让节点与诚实邻居隔绝，审查会排除交易，Selfish Mining则涉及扣留已经挖出的区块。此外仍有软件错误，以及攻击者在优势足够大时改写部分历史的可能。不过，即使拥有多数算力，也不能迫使正常工作的Full Node接受违反其规则的区块。将军的故事教我们审视达成一致的条件，而不是仅凭技术名称就相信保证。 [6] [7] [8]