【拜占庭将军问题】

《【拜占庭将军问题】》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、了解过比特币和区块链的人，多少都听说过拜占庭将军问题，或听说过比特币（或区块链）的一个重要成就正是解决了拜占庭将军问题。但真正明白这个问题的人并不多，甚至知道这个问题实质的人都很罕见。木文是一篇技术科普，将重点提供了拜占庭将军问题本身对本质及经典算法的解析，并探讨与之相关的一些问题。笔者参考了不少文献，夹杂了大量私货，但并没有提出解决该问题的新算法,这也不是本文的目的。PART1：拜占庭将军问题是什么拜占庭将军问题是一个共识问题：首先由LeslieLamport与另外两人在1982年提出,被称为TheByzantineGenerals

2、Problem或者ByzantineFailureo核心描述是军中可能有叛徒，却要保证进攻一致，由此引申到计算领域，发展成了一种容错理论。随着比特币的出现和兴起，这个著名问题又重入大众视野。1.1.拜占庭将军问题场景关于拜占庭将军问题，一个简易的非正式描述如下：拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同吋袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭

3、击才能攻下敌国。他们分散在敌国的四周，依靠通信兵和互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问。LamportB经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，我们已经假定了信道是没

4、有问题的，并在这个前提下，去做一致性和容错性相关研究。如果需要考虑信道是有问题的，这涉及到了另一个相关问题：两军问题。1.2•与拜占庭将军相关问题：两军问题正如前文所说，拜占庭将军问题和两军问题实质是不一样的。国内人量解释拜占庭将军问题的文章将两者混为一谈，其实是混淆了两个问题的实质，由此造成了许多误解。这两个问题看起来的确有点相似，但是问题的前提和研究方向都截然不同。BlueVBlueBarmyBarmy#1#2（图1：两军问题图不）如图1所示，口军驻扎在沟渠里，蓝军则分散在沟渠两边。口军比任何一支蓝军都更为强大，但是蓝军若能同时合

5、力进攻则能够打败白军。他们不能够远程的沟通，只能派遗通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议，这就是两军问题。看到这里您可能发现两军问题和拜占庭将军问题有一定的相似性，但我们必须注意的是，通信兵得经过敌人的沟渠，在这过程中他可能被捕，也就是说，两军问题屮信道是不可靠的，并且其中没有叛徒Z说，这就是两军问题和拜占庭将军问题的根本性不同。由此可见，大量混淆了拜占庭将军问题和两军问题的文章并没有充分理解两者。两军问题的根本问题在于信道的不可靠，反过来说，如果传递消息的信道是可靠的，两军问题可解。然而，并不

6、存在这样一种信道，所以两军问题在经典情境下是不可解的，为什么呢？倘若1号蓝军（简称1）向2号蓝军（简称2）派出了通信兵，若1要知道2是否收到了自己的信息，1必须要求2给自己传输一个回执，说“你的信息我已经收到了，我同意你提议的明天早上10点9分准时进攻”o然而，就算2已经送岀了这条信息，2也不能确定1就一定会在这个吋间进攻，因为2发出的回执1并不一定能够收到。所以，1必须再给2发岀一个回执说“我收到了”，但是1也不会知道2是否收到了这样一个回执，所以1述会期待一个2的回执。TCP的三次握手也面临类似问题。虽然看似很可笑，但在这个系统中

7、永远需要存在一个回执，这对于两方来说都并不一定能够达成十足的确信。更要命的是，我们还没有考虑，通信兵的信息还有可能被篡改。由此可见，经典情形下两军问题是不可解的，并不存在一个能使蓝军一定胜利的通信协议。不幸的是，两军问题作为现代通信系统中必须解决的问题，我们尚不能将之完全解决，这意味着你我传输信息时仍然可能岀现丢失、监听或篡改的情况。但我们能不能通过一种相对可靠的方式来解决大部分情形呢？这需要谈到TCP协议。事实上，搜索“两军问题与三次握手”，您一定可以找到大量与TCP协议相关的内容。若您是通信方而的专家，权当笔者是班门弄斧，这里仅用

8、最浅显易懂的方式科普TCP协议的原理和局限，可能存在一些毛刺，请多包涵。SendSYN(㈣=x)ReceiveSYN(seq=x)ReceiveSYN(seq划ACK=x*1)SendACK(ack=y*1

9、Receiv