拜占庭将军：分布式领域的幽灵

你可能听说过Paxos、Raft这类分布式一致性算法，也在工作中使用过ZooKeeper、etcd等工具来解决一致性问题。但你可能不知道，这些算法和工具解决的并不是一致性中最难的问题，通过精心的设计你甚至可以让这些算法和工具失效。什么是最难的问题呢？要讨论这个最难的问题，这就要追溯到Leslie Lamport 1982年发表的著名论文 《拜占庭将军问题》（The Byzantine Generals Problem ）上了。

拜占庭将军问题，通过比喻的方式来描述分布式一致性中一类最难的问题，这里大致叙述一下：

拜占庭帝国派出多支军队去围攻一支敌军，每支军队有一个将军，但由于彼此距离较远，他们之间只能通过信使传递消息。敌方很强大，固而必须有超过半数的拜占庭军队一同参与进攻才可能击败敌人。在此期间，将军们彼此之间需要通过信使传递消息并协商一致后，在同一时间点发动进攻。

三将军的难题

首先把问题简化一下，假设只有三个拜占庭将军，分别为A、B、C，他们要讨论的只有一件事情：明天是进攻还是撤退。为此，将军们需要依据“少数服从多数”原则投票表决，只要有两个人意见达成一致就可以了。

举例来说，A和B投进攻，C投撤退：

1. 那么A的信使传递给B和C的消息都是进攻；
2. B的信使传递给A和C的消息都是进攻；
3. 而C的信使传给A和B的消息都是撤退。

如此一来，三个将军就都知道进攻方和撤退方二者占比是2 : 1了。显而易见，进攻方胜出，第二天大家都要进攻，三者行动最终达成一致。

这一切，看上去都平淡无奇，非常简单。但是，如果稍微做一个改动：三个将军中出了一个叛徒呢？叛徒的目的是破坏忠诚将军间一致性的达成，让拜占庭的军队遭受损失。

假设A和B是忠诚将军，A投进攻，B投撤退，如果你是C这个叛徒将军，那么你该做些什么，才能在第二天让两个忠诚的将军做出相反的决定呢？

进攻方和撤退方现在是1 : 1，无论C投哪一方，都会变成2 : 1，一致性还是会达成。但是，作为叛徒的C，你必然不会按照常规出牌，于是你让一个信使告诉A的内容是你“要进攻”，让另一个信使告诉B的则是你“要撤退”。

至此，A将军看到的投票结果是：进攻方：撤退方=2 : 1，而B将军看到的是1 : 2 。第二天，忠诚的A冲上了战场，却发现只有自己一支军队发起了进攻，而同样忠诚的B，却早已撤退。最终，A的军队败给了敌人。

叛徒的策略

讲到这里，你有没有发现，明明大多数将军都是忠诚的，却被少数的叛徒耍得团团转？实质上，“拜占庭将军”问题的可怕之处，恰恰在此。

可以看到，在一致性达成的过程中，叛徒将军（恶意节点）甚至不需要超过半数，就可以破坏占据多数的正常节点一致性的达成。

然而，我们在最初提到的Paxos和Raft算法要成立都是建立在一个前提下的：不存在恶意节点，才能达成一致。否则，这些著名的算法会随之失效。而叛徒“拜占庭将军”问题就像幽灵一样，扰乱了所有正常节点保持一致性的可能。

谁是叛徒？

接下来的这个问题，可能就会让你有些气愤了，你可能不相信甚至无法接受这样的一种结果：在大多数将军都是忠诚的情况下，却无法抓出这个为所欲为的叛徒。

那么此刻，就让我来给你讲一下忠臣是怎么抓叛徒的，以及叛徒又是如何隐藏自己并没被暴露的。不过，在整个“抓捕”的过程中啊，需要我带着你进行一步步严密的推理，我想会很“烧脑”吧，所以呢你必须打起十二分的精神来。在此之前，你可以先停下来几分钟想想你的解决方法。

还是上面的例子，假设A与B是忠诚的将军，C是叛徒将军。忠诚的将军经历了上次战役的失败，就已经发觉他们中出现了叛徒，但是并不知道具体是谁。依旧是上面投票的例子，A投进攻，B投撤退，C传递给A和B两种不同的消息。

现在，我们从忠诚将军A的视角来看一下，他是如何做决策的。

A现在知道另外两人中可能有一个是叛徒，他收到了B的撤退消息和C的进攻消息，他应该如何分辨呢？

于是，A打算问一下B，“我从C那儿收到的是进攻，你从C那儿收到的是什么？”因为B是忠诚的将军，他不会伪造信息，B会告诉A收到的是撤退。C发送了两条不同的消息，A现在也发现了这个问题，但是A现在就可以判断C是叛徒了么？

可悲的事情发生了，尽管忠诚的B说了实话，但是A反而对他产生了怀疑。因为从A的视角来看，B和C的说法不一致，他无法判断：

1. 到底是第一次发送了两条不同消息的C是叛徒呢?
2. 还是明明C初次告知了B的是进攻，B却和A说C告知的是撤退，B是叛徒呢?

在三个将军中最多有一个叛徒的前提下，A现在唯一能明确的是，他们中间确实出了一个叛徒，但却无法信赖两个人中的任何一个。同样的情况，也出现在B身上，两个忠诚的将军彼此间产生了隔阂。而可以任意进行信息造假的叛徒C，此时只需要再次进行消息伪造：和A说“B告知我的消息是进攻”，和B说“A告知我的消息是撤退”，如此一来，就可以进一步把信息搞混，从而隐藏了自己是叛徒的真相。

综上所讲，我们不得不得出一个令人沮丧的结论：在拜占庭三个将军中出现一个叛徒，并且叛徒可以任意伪造消息的情况下，只要叛徒头脑清醒，他就始终无法被发现，甚至还能造成整个系统的信任危机。

理论上的证明，可以参考另一篇论文Reaching agreement in the presence of faults。目前，我们只需要理解在三个将军的情况下，只要叛徒策略得当，从忠诚的将军视角看其他两个将军的行为并无差异。并且理论上来讲，忠诚的将军们也就无法辨别出到底谁是叛徒。

根据这一结论进一步推导可以得出一个更通用的结论，如果存在 m 个叛徒将军，那么当将军总数小于或等于 3m 时（n <= 3m，m代表叛徒将军个数)，叛徒便无法被发现，整个系统的一致性也就无法达成。（具体的证明过程下一讲我会和你详细聊聊）

从上面的结论，可以看出，忠诚将军的人数是叛徒人数 2 倍的时候，依然不能找出叛徒，那么再多一个忠诚的将军呢？我来带领你看一看在这种情况下正义是否能战胜邪恶。

为了简化问题，接下来假设有 4 个拜占庭将军，分别是A、B、C、D，其中有一个是叛徒。我们依然秉承找出叛徒的关键，即判断哪个将军发送了不一致的消息。也就是说，接下来就是和其他接收到消息的将军进行信息的同步判断：是否收到的消息不一致。

现在，将问题再进一步简化，暂不需要考虑整个投票的过程，只需要考虑一个将军向其他三个将军各发送了一条命令，忠诚将军能否对这个命令达成一致的情况，为了区分发送命令的将将军和接收消息的将军，我们将发送命令的将军称为发令将军，将接收命令的将军称为副官。考虑下面两个问题：

1. 那么剩下的三个副官能不能通过相互间的信息同步找到叛徒？
2. 或者所有忠臣间达成一致，不让叛徒的分裂想法得逞呢？

这时候就出现了两种情况：

• 发令将军是叛徒 ；
• 副官里有叛徒。

对于第一种情况（发令将军是叛徒），假设D是叛徒，向A和B发送了进攻，向C发送了撤退。现在，我再次和你切入到A的视角。

为了判断D没有发送不同的消息，副官之间开始开会，A问B和C，我从D那里收到的消息是进攻，你从D那里收到的是什么呢？B说是进攻，C说是撤退。此时，从A的视角来看，C和D对同一条消息的说法是不一致的，那么他们两个人中肯定有一个是叛徒，但是A无法判断的是：

• D给不同人发送了不一致的消息；
• 还是C伪造了D的消息。

好在，由于A知道最多只有一个叛徒存在，那么根据反证法，如果B也是叛徒，就有两个叛徒存在，那么B肯定不是叛徒。那么A和B至少在D发送的是进攻这一消息上，达成了一致，两者选择都是进攻。B也是同样的情况，现在A和B彼此建立了信任，而同样是忠诚副官的C，最终则和真正的叛徒D被一同怀疑。

接下来，再切入到C的视角。

C在得知A与B两者从D那里收到的都是进攻消息时，就判断出了D是叛徒。很快D又惊恐地发现自己已经被A和B怀疑，自己却没有办法辩解，因为他即便再说什么A和B都无法相信了。但是C所能做的，就是保持自己的决策同A与B是一致的，当知道A和B收到的消息都是D采取的策略是进攻，那么他也这样认为了，至此，就和A、B、C三个忠臣在这条消息上达成了一致。尽管，叛徒依然没有被抓到，但是忠臣们的行动保持了一致，没有被叛徒分裂。

再来看第二种情况，副官中有叛徒的情况。

假设C是叛徒，D给三个副官都发送了进攻，那么叛徒C应该怎样同步D的消息，才能分裂忠诚的发令将军和忠诚副官间的关系呢？如果将D的消息原样转发出去，那么这一想法实施后也就无法再去当叛徒了。如果给A与B均发送和D相反的撤退消息，那么就回到了前文所讲的第一种情况，A和B认为D发送的是进攻，发送消息的D也认为自己发送的消息是进攻，忠臣们行动上又一次达成了一致。

然而，为了给系统增加更多的混乱，叛徒C决定再次发送不一致的消息，告诉B自己从D收到的是进攻，告诉A自己从D收到的是撤退。这种情况下，B看到所有人都认为D是进攻，会傻傻地认为大家是个团结一致的集体，没有叛徒。而A会发现C和D中出现了一个叛徒，不过A也再次可以确认B是自己人。此时，A决定再和B同步一轮消息，看看C是不是说了两个不一致的消息，这种情况下，叛徒C就完全暴露了。

由此可见，在多了一个忠臣的情况下，叛徒不能为所欲为了，在忠臣的紧密合作下，叛徒需要处处小心，注意自己的行为，才能避免被发现。与此同时，忠臣们即便在存在混乱信息的情况下，行动上也依旧达成了一致。根据类似的推理步骤，我们可以推导出一个结论：当忠臣的个数为2m + 1时，他们可以容忍m个叛徒产生的破坏。

针对分布式一致性领域最为困难的问题，还有着更多的变种，例如如果信使有限，每个将军只能和部分将军进行通信能容忍几个叛徒？如果叛徒将军假装失联，不发送消息会对一致性产生怎样的影响？为了限制叛徒任意伪造消息的能力，将军们之间采用签名信件来传递消息又会怎样？想要更深入地了解这些“幽灵们”，你可以翻看 Leslie Lamport 的最初论文The Byzantine Generals Problem ，细细来体会。

总结

至此，拜占庭将军问题的基础版本就讲解完了。 你应该已经知道了m个可以任意伪造消息的叛徒能够破坏规模最大为3m个将军的一致性。你也已经了解了叛徒是如何通过发送不一致的消息来制造混乱，以及忠诚将军又如何通过交换信息在混乱中保持一致的。

那么接下来让我们跳出拜占庭将军的比喻回到计算机的世界中。如果三个节点中有一个异常节点，那么最坏情况下两个正常节点之间是无法保证一致性的。那么你之前听说过的etcd这样的系统可以保证三个节点有一个宕机的情况下依然可以对外提供一致性服务是问什么呢？因为这类系统并没有考虑拜占庭故障，在他们的假设里故障节点可能会停止服务，可能会超时，但是不会发送异常消息。

尽管拜占庭的“幽灵”很恐怖，但在我们实际工作中，却并不需要过分去考虑它，因为对于大多数系统来说，内部环境里，硬件故障导致消息错误的概率本身就很低，还要按照拜占庭叛徒的策略来处理故障就更困难了。对于黑客来说，最主要的目的是攻克系统拿到数据，而不是读懂系统间交互的协议，而自己实现一套交互把自己作为一个叛徒来的事情给系统制造混乱，这对他们来说成本太高且受益又太低。Lamport 最初提出这个问题，其实是为了应对一致性要求最高的场景，例如导弹发射系统和核弹引爆系统，只有这种应用场景下去考虑拜占庭故障，才会具有比较现实的意义。

而Lamport没想到的是，现在真的出现了一个每个人都可以进行消息伪造，且伪造消息成功时能够受益的巨大系统——区块链。因此，如何解决拜占庭故障也成为了区块链算法要解决的一个核心问题。我想，这大概是Lamport发表论文时并没有预想到的。

思考题

读至此处，你的心情应该好一些了吧，虽然忠诚的将军们没有抓到叛徒，但是他们还是在混乱中认可了一致的消息。但，问题还远远没有结束……

经过上面的讲解，你已经知道了在三个忠诚将军一个叛徒时，尽管忠诚将军无法抓住叛徒，但是已经可以保持一致性不被叛徒破坏。那么再增加一个忠诚将军，四个忠诚将军中一个叛徒的情况，忠诚将军们能不能根据多出来的这个伙伴判断出到底谁是叛徒？忠诚将军的策略应该是怎样的？叛徒隐藏自己的策略又该是怎样的呢？

原文链接： https://mp.weixin.qq.com/s/LXDHZDH_FZBJxhtqF8CvFA