【拜占庭将军问题】VIP专享VIP免费

了解过比特币和区块链的人，多少都听说过拜占庭将军问题，或听说过比特币（或区块链）的一个重要成就正是解决了拜占庭将军问题。但真正明白这个问题的人并不多，甚至知道这个问题实质的人都很罕见。本文是一篇技术科普，将重点提供了拜占庭将军问题本身对本质及经典算法的解析，并探讨与之相关的一些问题。笔者参考了不少文献，夹杂了大量私货，但并没有提出解决该问题的新算法，这也不是本文的目的。:拜占庭将军问题是什么拜占庭将军问题是一个共识问题首先由年提出，被称为与另外两人在或者。核心描述是军中可能有叛徒，却要保证进攻一致，由此引申到计算领域，发展成了一种容错理论。随着比特币的出现和兴起，这个著名问题又重入大众视野。拜占庭将军问题场景关于拜占庭将军问题，一个简易的非正式描述如下：拜占庭帝国想要进攻一个强大的敌人，为此派出了支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御支常规拜占庭军队的同时袭击。基于一些原因，这支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问。已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，我们已经假定了信道是没有问题的，并在这个前提下，去做一致性和容错性相关研究。如果需要考虑信道是有问题的，这涉及到了另一个相关问题：两军问题。与拜占庭将军相关问题：两军问题正如前文所说，拜占庭将军问题和两军问题实质是不一样的。国内大量解释拜占庭将军问题的文章将两者混为一谈，其实是混淆了两个问题的实质，由此造成了两军问题的根本问题在于信道的不可许多误解。这两个问题看起来的确有点相似，但是问题的前提和研究方向都截然不同。如图所示，白军驻扎在沟渠里，蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大，但是蓝军若能同时合力进攻则能够打败白军。他们不能够远程的沟通，只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议，这就是两军问题。看到这里您可能发现两军问题和拜占庭将军问题有一定的相似性,但我们必须注意的是，通信兵得经过敌人的沟渠，在这过程中他可能被捕，也就是说，两军问题中信道是不可靠的，并且其中没有叛徒之说，这就是两军问题和拜占庭将军问题的根本性不同。由此可见，大量混淆了拜占庭将军问题和两军问题的文章并没有充分理解两者。反过来说，如果传递消息的信道是可靠的，两军问题可解。然而，并不存在这样一种信道，所以两军问题在经典情境下是不可解的，为什么呢？倘若号蓝军（简称）向号蓝军（简称）派出了通信兵，若要知道是否收到了自己的信息，必须要求给自己传输一个回执，说“你的信息我已经收到了，我同意你提议的明天早上点分准时进攻”。然而，就算已经送出了这条信息，也不能确定就一定会在这个时间进攻，因为发出的回执并不一定能够收到。所以，必须再给发出一个回执说“我收到了”，但是也不会知道是否收到了这样一个回执，所以还会期待一个的回执。的三次握手也面临类似问题。虽然看似很可笑，但在这个系统中永远需要存在一个回执，这对于两方来说都并不一定能够达成十足的确信。更要命的是，我们还没有考虑，通信兵的信息还有（图：两军问题图B-可能被篡改。由此可见，经典情形下两军问题是不可解的，并不存在一个能使蓝军一定胜利的通信协议。不幸的是，两军问题作为现代通信系统中必须解决的问题，我们尚不能将之完全解决，这意味着你我传输信息时仍然可能出现丢失、监听或篡改的情况。但我们能不能通过一种相对可靠的方式来...