Blockchain

接触区块链，多少会听到「某某算法解决了拜占庭将军问题」。它其实是分布式系统一致性（distributed consensus）领域一个很经典的抽象问题，由 Leslie Lamport（2013 年图灵奖得主，分布式系统领域奠基人之一，逻辑时钟、Paxos、LaTeX 的作者）与 Robert Shostak、Marshall Pease 在 1982 年的论文 《The Byzantine Generals Problem》 中提出。 什么是拜占庭将军问题 它也被叫作「拜占庭容错问题」。用一个比喻来描述： 拜占庭帝国派出 10 支军队去包围一个敌人。这个敌人能抵御 5 支常规军队的同时袭击，所以至少要有 6 支军队（过半）同时进攻才能取胜。这些军队分散在敌国四周，只能靠通信兵骑马互相传递消息来约定「进攻意向」和「进攻时间」。 麻烦在于：将军中可能有叛徒。叛徒会擅自篡改进攻意向或时间。那么，在可能存在叛徒的情况下，忠诚的将军们要如何达成一致、保证有多于 6 支军队在同一时间发起进攻？ 需要注意，这个问题里假定信道本身是可靠的（消息不会丢失、不会被截获）。至于「在可能丢消息的不可靠信道上，靠消息传递达成一致是不可能的」，那是另一个经典结论——两将军问题（Two Generals’ Problem），由 Akkoyunlu 等人在 1975 年提出并证明无解、Jim Gray 1978 年将其命名，是第一个被证明无解的计算机通信问题。它常被误记为 Lamport 的成果，其实和拜占庭将军问题是两回事：前者讲「信道不可靠」，后者讲「节点会作恶」。所以拜占庭将军问题把信道问题排除在外，焦点放在「节点（将军）本身可能作恶」上。 问题分析 先看没有叛徒的情况：将军 A 提一个进攻提议（「明天下午 1 点进攻，你加入吗？」），通过通信兵告诉其他将军。如果他收到 6 个以上将军的同意，就能发起进攻。但如果其他将军同时也在发不同的提议（2 点、3 点……），由于消息到达有时间差，不同将军收到并认可的提议可能不一样，于是出现 A 提议 3 票、B 提议 4 票、C 提议 2 票这种分裂局面。 再加入叛徒就更复杂了：一个叛徒会向不同的将军发出不同的提议（告诉 A 是 1 点、告诉 B 是 2 点），也可能同时同意多个互相冲突的提议。 叛徒发送的这种前后不一致、互相矛盾的信息，就叫「拜占庭错误（Byzantine fault）」。 ...