拜占庭将军问题可不是在讲兵家知识 - 区块链前沿 - BitMere

本文从介绍什么是拜占庭将军问题开始，进而谈到能解决这一问题的算法。最后谈一谈拜占庭将军问题与区块链的关系。

什么是拜占庭将军问题

一个可信的计算机系统，需要在系统有失常组件传递错误信息的情况下，维持系统的正常运作。乍一看，很复杂是不是？所以，大神们都喜欢用编故事的方式去阐释一些晦涩难懂的科学问题（例如，物理史上那只著名的薛定谔的猫）。我们的计算机网路大神Lamport也不例外，为了更生动地描述可信计算机系统需要具备的这种能力，Lamport编了一个情景故事，这个故事就是拜占庭将军问题。

假设现在有一支拜占庭部队，需要攻击一个城市。军队内部的情报沟通仅由传令官进行，将军们则需要在同一份军事行动计划上达成一致。但是，在这个情报体系中，却混入了几个叛徒，他们企图干扰军事情报的准确传递。所以问题来了，我们需要有一个算法来确保忠诚的将军能够达成战术行动的一致，从而取得最终的胜利。而不是让叛徒得逞，让指挥系统陷入混乱，拜占庭战败。

什么样的算法能解决这一问题

这种算法需要确保两件事。

第一，所有忠诚的将军遵循同一行动计划。第二，小部分叛徒不能让忠诚的将军受到误导，从而选择错误的行动计划。

条件一可以通过让将军们用同一套情报收集方法和同一套决策方法来完成（情报相同，分析情报并制定行动计划的方针也相同，那么最终的行动计划自然相同）。条件二则需要行动计划的确定方针有容错机制。

例如，将军可以通过比较收集到的情报的权重来决定最终行动计划，即他收集到五个情报，其中三个是要进攻（正确的指令），两个是要撤退（错误的指令），将军最终选择进攻。在这一案例中，将军在有错误指令的干扰下，最终依旧制定出正确的行动计划，这就是容错机制发挥的作用。只要这两个条件满足，我们就可以说这个算法解决了拜占庭将军问题。

接着，Lamport在他的文章中指出两种不同形式的情报，口述情报和签名情报。口述情报指它的传递形式是口述，这种情况下，情报的传递者对情报的内容拥有绝对控制权，换句话说，叛徒可以在传递过程中更改情报内容，传递假情报，制造混乱。

这种情报代指的是计算机在通常情况下，传递给网络中其他计算机的信息。签名情报则指，情报是通过不可伪造的加密信件传递的，情报内容在传递过程中，只要被更改就会被接收者发现。叛徒的作恶能力因此受到了限制，使情报系统的容错性提高。这种情报代指的是使用了一定加密算法，例如数字签名，HASH来确保信息在传递过程中一旦被篡改，就能被网络中其他计算机识别的信息系统中的信息。

针对这两种形式不同的情报，Lamport设计了两种算法OM（对应口述情报）和SM（对应签名情报）。先举个例子说明OM算法，如下图，四个拜占庭将军，其中Commander是诚实的，将军3是非诚实的。

第1步，Commander发送命令v给其他三个将军。第2步，三个将军广播消息给其他两个将军（上图中只画出了将军2收到的消息），将军3非诚实，发送x给将军2。第3步，将军2收到的消息为[v,v,x]，使用v作为命令,因为多数消息是v。

Lamport使用数学归纳法得出结论，在大于3m个将军中，只要叛徒不超过m，OM（m）算法就能确保之前提到的两个条件（解决拜占庭问题），从而确保情报系统的可靠性。

我们再举个例子说明SM算法。值得一提的是，因为加入了签名，接受者可以知道情报的最初发出者和经手者。

如下图所示，“attatck”：0 表示这条情报是0号（commander）发出来的，“attack”：0:1 则表示这条情报由0号发出，并由1号经手。图中总共3个将军，Commander是不诚实的将军，分别发送“attack”和“retreat”给将军1和将军2。

将军1和将军2从签名的消息发现从Commander发出了“矛盾”的命令，可以断定Commander不诚实。根据Lamport的结论，SM（m）算法可以解决至多m个叛徒的拜占庭将军问题。

统而言之，OM算法能解决拜占庭将军问题的条件是：军队中三分之二以上的将军是忠诚的。SM算法则不管将军中出现了多少叛徒，都能解决拜占庭将军问题。但是，Lamport本人也说了，他提出来的这两种算法，需要消耗大量时间，且对信息量有大量要求。所以，长江后浪推前，后来的大神们，也在他的基础上，提出新的、更优化的、能解决拜占庭问题的算法。

为什么在区块链中很重要

众所周知，区块链的节点网络是去中心化的，从一方面，它意味着节点的申请门槛相比中心化网络要低。这其实是一把双刃剑，好处我们就不说了，大家可以从营销号里看到100种，我们来说说它带来的隐患。节点申请门槛低意味着，对节点的监管能力也相对较弱，网络中出现恶意节点的可能性大大提高。

因此，我们需要在有部分恶意节点发送错误信息至网络中的情况下，确保区块链系统的可靠性。这不正是拜占庭问题么？“拜占庭军队”便是区块链系统，“叛徒”则是混入区块链中的恶意节点。

所以，区块链的核心组件——共识算法，需要解决的核心问题中就包括了拜占庭问题。以比特币和以太坊为代表的POW，EOS为代表的DPOS，解决的是共识节点众多情况下的拜占庭问题，适用于公链中。PBFT则是在共识节点较少的情况下拜占庭问题的一种解决方案，适用于联盟链。