请选择 进入手机版 | 继续访问电脑版
高级搜索 关闭

区块链最大的一个特性就是去中心化,但形成去中心化的网络,不是各搭各的台,各唱各的戏,而是要保证各个节点可以形成统一的决定,用区块链的术语,就是如何达成共识。

小到人和人之间的人际关系,大到国家和国家之间的外交关系,达成共识可以说是头等大事,人缘差、没有国家战略伙伴,肯定会影响个人幸福和国家稳定。

微软的首席研究员莱斯利·兰伯特在2013年获得了有着“计算机界诺贝尔奖”之称的图灵奖,他是计算机分布式问题专家,在他最著名的一篇文章中,他提出了著名的拜占庭将军问题。在这篇文章的摘要中,他风趣的提到了迪杰斯特拉的“哲学家就餐问题”,迪杰斯特拉是1972年的度“图灵奖”得主。兰伯特调侃道,因为创作了“就餐问题”,迪杰斯特拉获得了超出预想的关注。兰伯特此时正在解决NASA的一个计算机容错系统,考虑的问题是“如何保证分布式系统的可靠性”,所以也萌生了创作一个有趣小故事的想法。

在分布式计算领域中,两军问题,或者称作“中国将军问题”,是很有名的。兰伯特受此启发,创作了拜占庭将军问题。这里还有个小插曲,一开始兰伯特的故事叫做“阿尔巴尼亚将军问题”,同事提醒他换个名字,他才换成了“拜占庭将军问题”。

先来看下给了兰伯特启发的“两军问题”:两支驻扎在不同地点的军队分别由一名将领指挥,如果两个将军必须通过传令兵传递消息,才能达成共同进攻或撤退的决定。两军合力才可以战胜敌人,否则只有失败或撤退。问题出在传令兵上,一方派往另一方的传令兵可能永远到达不了,一种可能是被敌军捉住,另一种可能是被险恶的地形困住。学者们已经证明在通信受阻的情况下,除非是巧合,这两位将军是不可能达成一致的。他们二人只能凭借对另一人战略战术的了解,做出猜测,才能做出决定。

关于猜测,在刘慈欣的科幻小说《三体》中,大刘也分析了宇宙文明间存在的猜疑链。大刘通过主人公罗辑,阐述了宇宙的两条公理:一、生存是文明的第一需要;二、文明不断增长和扩张,但宇宙中的物质总量保持不变。然后又道出了宇宙的秘密:宇宙就是一座黑暗森林,每个文明都是潜行于林间的持枪猎人。林中到处是这样的猎人,如果一个文明发现了另外一个文明,他只有一个选择,将其消灭。

为什么宇宙的秘密如此黑暗呢?咱们可以假想一个最基本的模型,假设地球探测到火星内部有一个高度发达的文明,在没有交流之前,我们是无法判断火星人是否具有善意。假如人类向这个文明发出了邀请函。收到邀请函的火星文明同样也会犯难,他们也无法判断地球人是否真的怀有善意。这样在两者之间就形成了猜疑链,无法形成信任。

猜疑链正是阻挡两方达成合作共识的罪魁祸首。双方彼此之间的猜测,是一个典型的博弈过程,双方都想将自己的利益最大化,结果造成任何一方都会成为猎物。博弈论的创始人是大名鼎鼎的冯·诺依曼,他不仅是博弈论的创始人,也是现代计算机结构的发明人,同时也是一位卓越的数学家,还参与过曼哈顿工程,研究过原子弹。后人在冯诺依曼的理论基础上开发出了多种模型,其中之一是广为流传的“囚徒困境”:两名犯人接受隔离审问,犯人被告知,如果一人坦白,另一人不坦白,坦白的人就会无罪释放,不坦白的人就判5年;两人都坦白,各判3年;两人都不坦白,各判1年。可以设身处地的从一名囚犯的角度进行考虑:他的判决结果完全取决于另一人是否坦白,如果另一人选择坦白,他为了避免5年的最大惩罚,最好也选择坦白;如果另一人不坦白,那么为了能无罪释放,最好也选择坦白。两名囚犯都这么思考,结果两人都轻易坦白了。这就是典型的在存在猜疑的情况下,个人的理性选择,造成了集体的非理性。

拜占庭将军问题的参与者要多于前面的例子:拜占庭帝国是东罗马帝国的别称,因为首都君士坦丁堡位于希腊城邦拜占庭的旧址,所以又被成为拜占庭帝国。帝国后期内乱不断,一群将军领兵围困了一座敌城。与两军问题类似,他们也必须靠传令兵传递信息,才能达成统一的行动:要么一起进攻,要么一起撤退。假设传令兵一定能将信息送达,但是将军中可能存在一个或多个叛徒,叛徒会派传令兵发送假信息,从而人为地制造猜疑。叛徒向其他将军发送的信息是不一样的,有进攻的提议,也有撤退的提议,这时不能达成一致的错误,叫做“拜占庭错误”。如果叛徒发送了假信息,传令系统仍能达成一致性,则称该系统具备“拜占庭容错”。

接下来,我们讨论下两军问题和拜占庭将军问题在不同条件下,是否存在解决方法,可以破解猜疑和信任的难题。

两军问题在无法实现两军通讯的情况下是无解的。如果添加一些条件,是否可以破解两军问题和囚徒困境呢?对于两军问题,假如国王宣布两个将军只能前进不能后退,后退者杀无赦,就可以保证两军在指定时刻同时进攻;对于囚徒困境,假如黑帮老大立下了规矩,谁要是坦白了,就会受到黑帮内部最严厉的惩罚,也可以保证两名囚犯都守口如瓶,这样两人都只要坐一年牢就行了。

对于拜占庭将军问题,可以分为口头通讯和书面通讯。

如果采用口头通讯,拜占庭将军问题有解的条件是将军的总数要大于叛徒总数的三倍。因为达成共识的原则是少数服从多数,那么最小模型的将军总数是3。假设有3个将军甲乙丙,三人中有一人是叛徒:当甲发出“进攻”命令时,乙如果是叛徒,他可能告诉丙,他收到的是“撤退”的命令。这时丙收到一个“进攻”,一个“撤退“,于是丙无法判断真实命令;如果甲是叛徒,他告诉乙“进攻”,告诉丙“撤退”。当丙告诉乙,他收到“撤退”命令时,乙由于收到了甲“进攻”的命令,而无法与丙保持一致。

在符合有解的条件下,每位将军只要根据收到的口信,根据多数原则做决策就行了。

如果拜占庭帝国的国王给每个将军发了一个不同的印章,将军们可以利用印章确定通信中的将军身份,将军可以对其它人的印章进行验证。有了这些印章,每位将军分别给其他将军发送书信,并在书信上附上自己盖印;其他将军收信后,附上自己的印章后再发给所有其他将军;最终,每位将军根据收到的书信进行决断。这样就能杜绝叛徒给每个人发送不同信息。但是对于这种书面信息,实物的印章是靠不住的,伪造发生的可能性很高;国王的存在实际是一个高度可信的第三方,不符合去中心化的特征。最好这可以用一个客观的理论代替印章和国王,实现真正的分布式共识。这个理论具备数学公理般牢不可破的特性,比国王更让人信任。


回复

使用道具 举报

级别:韭菜
发表于 2020-1-16 18:07:41 | 显示全部楼层
沙发
区块链去中心化的好处
回复

使用道具 举报

级别:老韭菜
发表于 2020-1-16 18:23:44 | 显示全部楼层
板凳
感谢科普
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版规则