「区块链从入门到精通」:拜占庭将军问题 | 第8讲

区块链从入门到精通热度: 93288
为什么宇宙的秘密如此黑暗呢?咱们可以假想一个最基本的模型,假设地球探测到火星内部有一个高度发达的文明,在没有交流之前,我们是无法判断火星人是否具有善意。

在上节课中,我们共同学习了区块链的三大特性,第一点就是区块链的去中心化特性。但形成去中心化的网络之后,不是各搭各的台,各唱各的戏,而是要保证各个节点可以形成统一的决定,用区块链的术语,就是如何达成共识。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

两军问题和拜占庭问题,体现了去中心化组织为了达成共识所碰到的困境。内部原因和外部原因都可能造成无法达成共识。虽然在特定条件下有对应的解决方案,但会破坏去中心化的特征。作为集大成者,比特币吸收了前人在密码学、分布式系统上的经验,它是如何解决区块链网络节点的共识难题的呢?关于共识算法,欢迎收听下一讲的内容。恭喜你完成《区块链入门到精通》第8讲的学习。

「区块链从入门到精通」:从玄武门之变到分叉和算力攻击 | 第7讲

声明:本文为入驻“火星号”作者作品,不代表火星财经官方立场。
转载请联系网页底部:内容合作栏目,邮件进行授权。授权后转载时请注明出处、作者和本文链接。 未经许可擅自转载本站文章,将追究相关法律责任,侵权必究。
提示:投资有风险,入市须谨慎,本资讯不作为投资理财建议。
免责声明:作为区块链信息平台,本站所提供的资讯信息不代表任何投资暗示,本站所发布文章仅代表个人观点,与火星财经官方立场无关。鉴于中国尚未出台数字资产相关政策及法规,请中国大陆用户谨慎进行数字货币投资。
语音技术由科大讯飞提供
最近更新
本文来源:区块链从入门到精通
原文标题:
24H热门新闻
暂无内容

评论0