比特币解决拜占庭将军问题@刘教链

丢失的拜占庭将军问题之谜

众所周知,比特币作为一个开放的、分布式的点对点网络,所需要克服的一个非常关键的问题就是拜占庭将军问题,也就是关于分布式共识的问题。

共识机制,也是区块链领域一个非常热门的创新点。各种项目层出不穷,热衷于向大家推销的卖点之一,一定是弃用了比特币的所谓浪费能量的PoW共识算法,替换成了某种不费电的XXX共识算法。甚至有些项目,还要堂而皇之的把自己要从PoW“升级”(我给升级打了引号)成其他共识算法作为重要的技术路线图。

拜占庭两军问题详解图解算法

拜占庭两军问题详解图解算法

很多人讲比特币,也会选择从分布式共识这个角度切入,先讲拜占庭将军问题,然后引出比特币的分布式记账,进而展开比特币的整个设计。

按照这样的叙事逻辑,就要从1982年Leslie Lamport的《拜占庭将军问题》讲起。然后讲到1985年Fischer, Lynch, Paterson的论文《有一个错误进程即不可能达成分布式共识》及其中证明的“FLP不可能定理”。FLP不可能定理基本上可以看作是通过严格的理论证明,把异步网络下解决拜占庭将军问题的可能性给枪毙了。

所以Leslie Lamport后来提出的BFT(Byzantine Fault Tolerant)也就是拜占庭错误相容的共识算法,基本上就是乖乖地在FLP不可能定理画地为牢的框框里求生存,把同步性假设作为解题的前提条件了。毕竟,异步性假设下无解已经被理论严格证否了,就没有必要再去尝试了。

后来到了90年代,互联网兴起。互联网消除了拜占庭将军问题,通过把网络从开放网络变成封闭网络的方法。互联网公司建立了防火墙,对自己运维的服务器严防死守,极力避免黑客渗透到自己的网络里面。这样一来,就可以对网络做安全假设,假设系统里所有的节点都是“好”的,只会出现故障,而不会主动作恶。

安全假设消除了,或者说回避了,拜占庭将军问题。因为所谓拜占庭将军问题,就是假设网络是开放网络,节点不仅会出现故障,而且有可能主动作恶,攻击系统,请问在这种“坏”节点存在的情况下,一个分布式系统如何才能经过有限的时间(而不是无限拖延)即达成共识?

这个假设好处多多。最大的好处就是,可以通过互联网公司中心化的控制和协调,让分布在世界各地的节点达到高度精确的时间同步性。比如谷歌的Spanner系统,甚至用上了卫星授时和原子钟技术。使用Paxos共识算法,十几个节点的Spanner就可以达到十几万TPS(每秒交易数)。

按理说,比特币作为首个在开放网络下克服拜占庭将军问题,实现分布式共识的系统,中本聪至少应该在比特币白皮书中提及一下这个问题。但是非常成谜的是,翻遍整个比特币白皮书,没有一个字儿提到这个事情,更别说在参考文献里引用Leslie Lamport的开创性论文,或者FLP不可能定理相关的论文了。

是中本聪不知道拜占庭将军问题吗?2008年的中本聪不知道上世纪80年的BFT?我不知道这是拿中本聪当傻子,还是拿炒币者当傻子。以至于每当我看到某某大牌项目,又号称自己多么牛逼的改进了中本聪共识算法,定睛一看,原来是PBFT、*BFT或者改头换面的某种BFT算法,我就忍不住觉得太逗了:这不就是打中本聪的脸,说中本聪是傻X么?

比如2018年红极一时的EOS,DPoS投票选出21个超级节点之后,超级节点之间就是使用PBFT算法作为共识出块的机制。

伪三段论推理一下:
大前提:中本聪不是傻X。
小前提:某项目说中本聪是傻X。
结论:某项目是傻X。

犹记当年中本聪在论坛里怒怼EOS的创始人BM(真名Daniel Larimer):“如果你听不懂或者不相信我,我没有时间说服你,抱歉。”(中本聪,2010年7月29日,bitcointalk论坛发言)

你说中本聪可能不知道拜占庭将军问题么?他当然知道。证据就是,早在2008年11月3号的邮件里,中本聪就明确的写道:“工作量证明链就是拜占庭将军问题的解。”

请注意中本聪的表达。并不是PoW是拜占庭将军问题的解,而是采用了PoW的区块链,是拜占庭将军问题的解。解决方案是区块链,而且是采用了PoW的区块链。

去掉了PoW,区块链就不能解决拜占庭将军问题。不能解决拜占庭将军问题的区块链,还是区块链么?至少,在异步网络假设下不能,因为FLP不可能定理的约束。

而如果做了同步性网络假设,就需要借助于外部中心对网络节点的时钟进行控制和协调。那就为系统引入了隐含的中心化。

所以,这里只有三条路可以走。第一条,中心化;第二条,解决不了,放弃;第三条,采用PoW。没有其他路可以走。

没有了PoW的区块链,一定会走到第一条路上去。这是由理论证明和约束了的。无解。

中本聪的解题思路是非常具有突破性的,是真正的think out of the box(跳出框框外思考)。

当我们面对“异步网络中的拜占庭将军问题不可解”这样一个命题的时候,大多数人,包括提出拜占庭将军问题的分布式系统专家Leslie Lamport,都把着眼点放在了“拜占庭将军问题”本身上,为此不惜先默默地通过同步性假设绕开FLP不可能定理,然后研究有作恶节点的情况下如何实现共识的算法。

中本聪却异乎寻常地把着眼点放在了“异步网络假设”上。如果我们能够发明一个去中心化的、自动运行、自动协调的全局计时器,是不是拜占庭将军问题就迎刃而解了?

不同于以往的,中本聪不是通过假设外部有人来搞定同步时钟问题,从而回避这个问题,因为这个问题关乎中心化还是去中心化的根本。他把发明一种方法,在去中心化的情况下实现时钟同步,作为重点考虑。这个解决方案就是比特币白皮书中提到的时间戳服务器。

然后我们就惊讶的发现,当这个问题被解决以后,拜占庭将军问题就不复存在了。节点只需要就最长链达成一致即可,根本就不再需要任何什么拜占庭错误相容的共识算法。所以,就可以直接跳过整个环节。

简单的讲,有一个很困难的问题P,需要发明A算法来解决。但是有人证明了,当B条件不满足时,能够解决P问题的A算法是不存在的。

在中本聪之前呢,所有人的解题思路都是,先假设B条件满足,让题目变得简单一点儿,然后研究有什么样的A算法可以用。

中本聪一来呢,就把B从待满足的“条件”变成了待解决的“问题”,然后他发明了一个C,把B条件不满足的问题给克服了。这样一来,A算法也不需要了。C直接就可以解决P。

比特币违反了FLP不可能定理了吗?并没有。中本聪只是把解决这个问题,转换成了解决另一个问题。

不得不说,中本聪的洞察力和思维转换是令人惊叹的。以至于直到比特币白皮书公布13年后的今天,大家仍然没有完全理解,中本聪到底是怎样解决问题的。

不管怎样,A不需要了。也就没有必要在比特币的白皮书中提及了。

这就是比特币白皮书中为什么对于拜占庭将军问题只字未提的秘密。

(公众号:刘教链。知识星球:公众号回复“星球”)
(免责声明:本文内容均不构成任何投资建议。加密货币为极高风险品种,有随时归零的风险,请谨慎参与,自我负责。)

刘教链
微信号
blockcoach
功能介绍
加密货币和区块链研究者、投资者,前北航软件学院特聘教授,《比特币史话》作者。