image

接触区块链的同学，多少都听说过拜占庭将军问题，经常看到或听到：某某区块链使用某某算法解决了拜占庭将军问题，那么究竟什么是拜占庭将军问题呢?《区块链100讲》今天和大家说说什么是拜占庭将军问题。

1

拜占庭将军问题

这个问题是莱斯利·兰伯特（Leslie Lamport）等在论文The Byzantine Generals Problem论文提出的，部分原文如下：

We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement.

它是描述分布式系统一致性问题的著名例子。通过直译这个论文来理解这个问题还是比较困难，可以适当的补充或者添加一些说明来更好地解读。

设想在中世纪，拜占庭帝国拥有巨大的财富，周围邻邦垂诞已久。但拜占庭高墙耸立，固若金汤，没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败，同时也有可能自身被其他邻邦入侵。拜占庭帝国防御能力如此之强，至少要有一半以上邻邦同时进攻，才有可能攻破。

然而，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛，那么入侵者可能都会被歼灭。于是每一方都小心行事，不敢轻易相信邻国。（其实这与原文所描述有些偏差，但这样说更易于理解）

在拜占庭问题里，各邻国最重要的事情是：所有将军如何能过达成共识去攻打拜占庭帝国。

image

达成共识并非坐下来开个会那么简单，有的将军心机深不可测，口是心非，如果有叛徒，可能会出现各种问题：

• 叛徒可能欺骗某些将军自己将采取进攻行动。

• 叛徒可能怂恿其他将军行动。

• 叛徒可能迷惑其他将军，使他们接受不一致的信息，从而感到迷惑。

我们这里假设：

有A、B、C三位将军，当A发出进攻命令时，B如果是叛徒，他可能告诉C，他收到的是“撤退”的命令。这时C收到一个“进攻”，一个“撤退“，于是C被信息迷惑，而无所适从。

如果A是叛徒。他告诉B“进攻”，告诉C“撤退”。当C告诉B，他收到“撤退”命令时，B由于收到了“进攻”的命令，而无法与C保持一致。

叛徒发送前后不一致的进攻提议，被称为“拜占庭错误”，而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。

相信大家已经可以明白这个问题的复杂性了。

正由于上述原因，在只有三个角色的系统中，只要有一个是叛徒，即叛徒数等于1/3，拜占庭问题便不可解。

2

拜占庭将军问题的实质

回顾问题，一群将军想要实现某一个目标（一致进攻或者一致撤退），但是单独行动行不通，必须合作， 达成共识；由于叛徒的存在，将军们不知道应该如何达到一致。

注意，这里“一致性”才是拜占庭将军问题探讨的内容，如果本来叛徒数量就已经多到了问题不可解的地步，这个就是“反叛”的问题了；同时，我们的目标是忠诚的将军能够达成一致，对于这些忠诚的将军来说，进攻或者撤退都是可以的，只要他们能够达成一致就行。

但是，光靠“一致”就可以解决问题吗？考虑一下，如果万事俱备，客观上每个忠诚的将军只要进攻了就一定能够胜利，但是却因为叛徒的存在他们都“一致的”没有进攻；反之，条件不利，将军们不应该进攻，但是却因为叛徒的存在所有人都“一致的”进攻了。

可以发现，只有“一致性”是不足以解决拜占庭将军问题的，我们还需要提出一个“正确性”要求。这个要求是值得斟酌的，因为如果客观来看或许会有“绝对正确的”判断，但是针对每一个将军，大家的判断或许都不相同，我们如何定义“正确”呢？我们或许可以简单地说，正确就是每个忠诚的将军都正确的表达了自己的意思，不会因为叛徒让别的将军认为忠诚的将军是叛徒而不采用他传达的消息。

至此，我们将拜占庭将军问题简化成了，所有忠诚的将军都能够让别的将军接收到自己的真实意图，并最终一致行动；而形式化的要求就是，“一致性”与“正确性”。

如果将问题推广开来，可以发现针对一致性和正确性的算法并不要求命令必须是“进攻/撤退”或是“1/0”，而可以是“发送消息1/发送消息2/待机”或“x/y/z/w”，这意味着拜占庭将军问题算法可以为多种分布式系统提供启发，比如电力系统或网络系统。

由此可见，这个问题说到底是一个关于一致性和正确性的算法问题，这个算法是针对的是忠诚的将军，因为叛徒可以做出任何超出约定的判断。我们就是要在有叛徒的干扰下，找到一个抗干扰的算法。

3

中本聪的解决方案

这个问题困扰了科学家们数十年，直到区块链的出现。

现在让我们想象一下，给每个将军配备一台电脑（相当于分布式的节点），降低信息流通成本，让信息在极短的时间同步到各位将军。

同时，为了避免信息混乱，一段时间内只能有一位将军发送信息。

怎么来确定哪位将军发送信息呢？区块链系统一般通过工作量证明（POW）来确定谁先发言。（工作量证明将在后续文章介绍）

我们可以想象这是一个数独游戏，哪个将军最先解出来，谁就有权先发送信息。一般，数独的行与列可以增删，通过难度的调整保证这个一段时间是一个比较确定的数值。在比特币系统上，这个数字就是10分钟，也就是说比特币平均约每10分钟产生一个区块。

当某个节点发出统一进攻或者撤退的消息后，各个节点收到发起者的消息必须签名盖章，确认各自的身份。比特币在这里引用现代非对称加密技术为这个信息签名。

这个过程就像一位将军A在向其他的将军（B、C、D…）发起一个进攻提议一样，将军B、C、D…看到将军A签过名的进攻提议书，如果是诚实的将军就会立刻同意进攻提议，而不会发起自己新的进攻提议。

非对称加密算法的加密和解密使用不同的两个密钥，这两个密钥就是我们经常听到的公钥和私钥。一般公钥是公开的，用于加密。而私钥是用来解密公钥获取信息的。比如，将军A想给将军B发送消息，为防止消息泄露，将军A只需要使用B的公钥对信息加密，加密的信息只能用B私钥解密。（非对称加密算法将在后续文章介绍）

除了加密信息外，同时，信息经过每个节点都将进行备份，每个节点都保存了相同的完整数据，以防止少数叛徒篡改。

好了，我们再来重新走下一下整个过程：

每个将军分配了一台电脑，A将军第一个解出数独游戏拥有了第一个发言权，A发出攻打的信息，并立即广播至所有将军，所有人可以根据A的公钥来验证A的身份，确保信息的可信性，并发出自己赞成或反对的选票，在全网验证后得出结果。

于是，一个不可信的信息传递，就变成了一个分布式的可信网络，参与者都有权发表意见，并在一件事上达成一致。

拜占庭将军问题也就得到了解决，文章开头的问题相信你也已经有了答案。本期就讲到这里，下期继续。

本文内容来源于：百度百科、巴比特、币行观察等

活动推荐

主题：Blockathon，挑战区块链开发，敢不敢来！（点击了解详情）

5月25-27日，Blockathon2018北京站，招募100名开发者一起挑战区块链开发。

开发者免费，报名需审核。识别下图二维码或点击“阅读原文”即可报名参加。

image

点击“阅读原文”即可报名。