拜占庭将军问题
简介
拜占庭问题最早由 Leslie Lamport 等学者于 1982 年在论文《The Byzantine Generals Problem》中正式提出，是用来解释异步系统中共识问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将向不同的将军发送不同的消息，试图干扰共识的达成。这种情况十分类似于分布式系统中多个节点达成共识的问题。
拜占庭问题即讨论在此情况下，如何让忠诚的将军们能达成行动的一致。
拜占庭问题（Byzantine Problem）又叫拜占庭将军（Byzantine Generals Problem）问题，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的如何达成共识问题。拜占庭容错（Byzantine Fault Tolerant，BFT）讨论的是容忍拜占庭错误的共识算法。
拜占庭问题之前，学术界就已经存在两将军问题的讨论（《Some constraints and tradeofis in the design of network communications》，1975 年）：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失或伪造），如何达成一致？根据 FLP 不可能原理，这个问题无通用解。
拜占庭问题的解决
拜占庭问题，假设节点总数是N，叛徒将军数为F，则当 N 》= 3F+1 时，问题才有解，共识才能达成，这就是Byzantine Fault Tolerant（BFT）算法。
FLP定理（Fischer-Lynch-Paterson定理）最早发表于JACM'85[1]，从理论上证明了在纯异步环境下不可能存在一种确定性的共识协议。后世的研究者们为了绕过这个定理，不得不在两个方向上进行妥协：要么加强对网络的假设，要么引入随机源。
问题说明
为了更加深入的理解拜占庭将军问题, 我们以三将军问题为例进行说明. 当三个将军都忠诚时, 可以通过投票确定一致的行动方案, 图2展示了一种场景, 即General A, B通过观察敌军军情并结合自身情况判断可以发起攻击, 而General C通过观察敌军军情并结合自身情况判断应当撤退. 最终三个将军经过投票表决得到结果为进攻:撤退=2:1, 所以将一同发起进攻取得胜利. 对于三个将军, 每个将军都能执行两种决策(进攻或撤退)的情况下, 共存在6中不同的场景, 图2是其中一种, 对于其他5中场景可简单地推得, 通过投票三个将军都将达成一致的行动计划.
上图三个将军均为忠臣的场景
当三个将军中存在一个叛徒时, 将可能扰乱正常的作战计划. 图3展示了General C为叛徒的一种场景, 他给General A和General B发送了不同的消息, 在这种场景下General A通过投票得到进攻:撤退=1:2, 最终将作出撤退的行动计划; General B通过投票得到进攻:撤退=2:1, 最终将作出进攻的行动计划. 结果只有General B发起了进攻并战败.
上图为2忠臣一个叛徒的场景
想要总能达到一致的行动方案是不可能的. 详细的证明可参看Leslie Lamport的论文. 此外, 论文中给出了一个更加普适的结论: 如果存在m个叛将, 那么至少需要3m+1个将军, 才能最终达到一致的行动方案.
解决方案
Leslie Lamport在论文中给出了两种拜占庭将军问题的解决方案, 即口信消息型解决方案(A solution with oral message)和签名消息型解决方案(A solution with signed message).
口信消息型解决方案
首先对于口信消息（Oral message）的定义如下：
- 任何已经发送的消息都将被正确传达
- 消息的接受者知道谁发送了消息
- 消息的缺席可以被检测
基于口信消息的定义, 我们可以知道, 口信消息不能被篡改但是可以被伪造
为加深理解, 我们将利用3个忠将1个叛将的场景对口信消息型解决方案进行推导. 在口信消息型解决方案中, 首先发送消息的将军称为指挥官, 其余将军称为副官. 对于3忠1叛的场景需要进行两轮作战信息协商, 如果没有收到作战信息那么默认撤退.
下图是指挥官为忠臣的场景，在第一轮作战信息协商中, 指挥官向3位副官发送了进攻的消息; 在第二轮中, 三位副官再次进行作战信息协商, 由于General A, B为忠将, 因此他们根据指挥官的消息向另外两位副官发送了进攻的消息, 而General C为叛将, 为了扰乱作战计划, 他向另外两位副官发送了撤退的消息. 最终Commanding General, General A和B达成了一致的进攻计划, 可以取得胜利.
下图是是指挥官为叛将的场景, 在第一轮作战信息协商中, 指挥官向General A, B发送了撤退的消息, 但是为了扰乱General C的决定向其发送了进攻的消息. 在第二轮中, 由于所有副官均为忠将, 因此都将来自指挥官的消息正确地发送给其余两位副官. 最终所有忠将都能达成一致撤退的计划.
如上所述, 对于口信消息型拜占庭将军问题, 如果叛将人数为m, 将军人数不少于3m+1, 那么最终能达成一致的行动计划. 值的注意的是, 在这个算法中, 叛将人数m是已知的, 且叛将人数m决定了递归的次数, 即叛将数m决定了进行作战信息协商的轮数, 如果存在m个叛将, 则需要进行m+1轮作战信息协商. 这也是上述存在1个叛将时需要进行两轮作战信息协商的原因.
签名消息型解决方案
同样, 对签名消息的定义是在口信消息定义的基础上增加了如下两条:
- A4. 忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现;
- A5. 任何人都能验证将军签名的真伪.
基于签名消息的定义, 我们可以知道, 签名消息无法被伪造或者篡改. 为了深入理解签名消息型解决方案, 我们同样以3三将军问题为例进行推导. 下图是忠将率先发起作战协商的场景, General A率先向General B, C发送了进攻消息, 一旦叛将General C篡改了来自General A的消息, 那么General B将将发现作战信息被General C篡改, General B将执行General A发送的消息.
上图是叛将率先发起作战协商的场景, 叛将General C率先发送了误导的作战信息, 那么General A, B将发现General C发送的作战信息不一致, 因此判定其为叛将. 可对其进行处理后再进行作战信息协商.
总结
在分布式系统领域, 拜占庭将军问题中的角色与计算机世界的对应关系如下:
- 将军, 对应计算机节点;
- 忠诚的将军, 对应运行良好的计算机节点;
- 叛变的将军, 被非法控制的计算机节点;
- 信使被杀, 通信故障使得消息丢失;
- 信使被间谍替换, 通信被攻击, 攻击者篡改或伪造信息.
如上文所述, 拜占庭将军问题提供了对分布式共识问题的一种情景化描述, 是分布式系统领域最复杂的模型. 此外, 它也为我们理解和分类现有的众多分布式一致性协议和算法提供了框架. 现有的分布式一致性协议和算法主要可分为两类:
- 一类是故障容错算法(Crash Fault Tolerance, CFT), 即非拜占庭容错算法, 解决的是分布式系统中存在故障, 但不存在恶意攻击的场景下的共识问题. 也就是说, 在该场景下可能存在消息丢失, 消息重复, 但不存在消息被篡改或伪造的场景. 一般用于局域网场景下的分布式系统, 如分布式数据库. 属于此类的常见算法有Paxos算法, Raft算法, ZAB协议等.
- 一类是拜占庭容错算法, 可以解决分布式系统中既存在故障, 又存在恶意攻击场景下的共识问题. 一般用于互联网场景下的分布式系统, 如在数字货币的区块链技术中. 属于此类的常见算法有PBFT算法, PoW算法.
