分布式一致性算法
拜占庭的将军们没有一个中心化的领导机构,所以,如果他们需要攻击某个城市,所有将军需要对任何将军可能提出的攻击时间达成共识。也就是说,只有所有的将军都达成了共识,在同一个攻击时间攻击,就有非常大的胜率。但是,问题来了。这时,可能会有多个将军同时发出不同的攻击计划,而且这些将军中还有叛徒。那么,将军们怎样达成共识呢?
莱斯利·兰伯特证明,当叛变者不超过 1/3 时,存在有效的算法。不论叛变者如何折腾,忠诚的将军们总能达成一致的结果。如果叛变者过多,则无法保证一定能达到一致性。
拜占庭问题之所以难解,在于任何时候系统中都可能存在多个提案(因为提案成本很低),并且要完成最终的一致性确认过程十分困难,容易受干扰。但一旦确认,即为最终确认。
比特币的区块链网络在设计时使用的 PoW(Proof of Work) 算法思路。一个是限制一段时间内整个网络中出现提案的个数(增加提案成本),另外一个是放宽对最终一致性确认的需求,约定好大家都确认并沿着已知最长的链进行拓宽。
也就是说,如果比特币系统在某一个时刻同时出现了两个都合法的区块,那么两个都承认。于是,区块链上会出现两个合法的分支(术语叫 " 分叉 ")。此时矿工可以选择任何一个分支继续,在某个分支的长度超过了另一个分支时,短的那个分支马上作废。
如果你看过我之前写的《分布式系统架构的本质》系列文章,那么一定知道 Paxos 协议,这也是一种分布式一致性的共识算法。但为什么不用 Paxos 和 Raft 来做区块链的一致性算法的协议呢?这两个算法对资源的消耗比 PoW 要小得多呢。