拜占庭将军问题与区块链

通证观察局  2019-05-15  新手入门/区块链知识栏目  

  用通俗有趣的语言

  带你了解通证经济

  这是通证观察局的第7篇原创文章

   ◡

  它开拓了未来的想象空间,通过它可以把一组全新的事物从实体世界映射到数字世界。                                ——赵胜

  “全文共3902字,读完约7分钟”

  图片来自网络,侵删

  这两年,区块链似乎一下子成为热词,被各个大佬高举“去中心化”、“不可篡改”的旗帜,乍一听好像还特别高大上(反动),尤其是频频出现在知乎和百度问答这种地方。但是小六悲催的发现,看完了那些个长长短短的回答,我好像还是不知道区块链是干什么

  A

  大佬,大佬,什么是区块链呀?

  简单来说,区块链就是一个分布式账本。

  B

  A

  那什么是分布式账本呢?

  分布式账本就是区块链啊!

  B

  A

  可是我还是不知道区块链是啥啊?!

  A

  哎呀,区块链就是一群高技术、高智商的技术人员和科学家搞出来的,涉及到很高深的密码学知识等,说了你也不懂。总之你只需要跟我念:

  安全透明无风险,账本透明都可查。

  人人共享去中心,你的安全小管家。

  技术大牛都说好,民主国家全用它。

  互联之初不努力,徒管马云叫爸爸。

  如今天降中本聪,信区块链保全家。

  B

  A

  这怎么听起来……有点像传销啊

  呵呵,你这水平也就当一辈子韭菜了。我勉为其难再跟你科普一遍,你听好了啊~~~

  区块链就是比特币加密货币的基本技术,一个分布式账本,它在交易史形成了分布式共识。它具有去中心化,交易公开透明、不可篡改、可溯源……

  B

  图片来自网络,侵删

  其实,对于那些大部分问 “区块链是什么”的人来说,他们并不想听到定义上的答案(因为会绝望的发现还是听不懂)。毕竟大部分人是真的不懂什么叫分布式,什么是密码学…….

  所以小六觉得,对于区块链的科普,我们都陷入了一个误区:与其一开始问区块链是什么,不如先搞明白它是怎么用的更为重要。

  So,在接下来的日子里,小六希望用通俗易懂的语言,从区块链背后的技术入手,为大家介绍它是怎么用的(如果写的不好,各位看官一定多多批评)。

  下面进入主题

   图片来自网络,侵删

  通俗来说,区块链就像一个“你有我有大家都有”的小账本,在每笔交易过程中,大家都会把帐给记下来,达成共识。每一笔交易都可以看作是一个加密的标识过的信息,为了让区块链网络上的每个节点验证交易的合法性,所有交易都通过P2P网络广播

  然而简单的交易广播,并不是一种完美的解决方式。当网络处于传播延迟,或节点处于联机或脱机状态时,每个节点将无法保存交际记录的相同副本。要想解决这个问题——也就是达到分布式共识,首先就必须了解拜占庭将军问题

  什么是拜占庭将军问题?

  

  图片来自网络,侵删

  简单的说,拜占庭将军问题就是指三个将军,如何在其中一个是叛徒的情况下,通过互相之间派信使传令的方式,让两个诚实的将军达成共识。这个问题最早是由图灵奖得主——分布式系统的奠基人之一 Leslie Lamport ,在1982年和他的两个同事一起提出的。

  当时的拜占庭罗马帝国,位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于帝国国土辽阔,而整个国家的军力又非常有限,为了防止周边国家的进攻,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。 

  如果想要对周边某个国家发动战争,拜占庭军队内所有正义的将军必须达成一致的共识,决定是否去攻打敌人的阵营。但是,由于军队内有叛徒的存在,将会干扰将军们的决定,使他们无法达成一致。

  在已知有叛徒的情况下,其余忠诚的将军如何能不受叛徒的影响,成功达成一致的协议,这就是拜占庭问题的实质。

  图片来自网络,侵删

  我们先把三个将军分别按照分成两类:

  1.按照忠奸:有一个将军是叛徒,另两个将军是忠诚的;

  2.按照身份地位:有一个将军是指挥官(即发令者),另两个是副官。

  他们三个之间的信息交流如下:

  指挥官下达命令,副官接受命令,副官再相互传达命令。

  由于叛徒的存在,正义的将军既无法从另两个将军那里接收到相同的指令,又无法识别出来谁是叛徒。这就导致2个正义的将军之间,无法成功达成共识,也就是所谓的拜占庭失效。下面小六将详细解释,为什么正义的将军会如此悲催?

  首先我们先把叛徒分为两个段位,说慌和沉默。

  1.1说谎的叛徒

  假设指挥官A是正义的,那么叛徒就会存在B、C(2个副官)之间,这里可以先暂定C为叛徒。如果A传达给B、C的命令为进攻,此时B、C接到命令:进攻。因为B是正义的,所以B给C的指令是进攻;同时由于C是叛徒,所以C给B的信息为撤退。

  这时候B就蒙圈了,因为他接收到的两个指令不一致,A让他进攻敌方防御塔,B让他猥琐发育别浪。他能怎么办,他也很绝望啊!因此他就无法和A达成共识,此时也就是拜占庭失效

  我们再来看一下,当指挥官A为叛徒时,将会是怎样的一种情况。

  假设A为叛徒,那他传达给B、C的指令是不同的。如果A告诉B进攻,那么就会同时告诉C撤退。当A、B将得到的指令互换后,发现彼此交换的信息和自己从A那边接受到的信息不一致,B、C同时蒙圈了。因此,在这种情况下,将军们也无法达成共识,再次出现拜占庭失效。

  这个时候,可能有些吃瓜群众觉得:既然A是叛徒,那他直接向B、C同时下达错误的命令,战争不久也就失败了吗,为什么还要下达不同的命令呢。是的,同时下达错误的命令,战争确实也是失败了。

  但是拜占庭将军问题,最终讨论的不是到底是进攻还是防守,而是正义的两个将军如何达成共识。

  这个时候,我们就不得不说 Leslie Lamport 当初提出这个问题的背景了。

  很多人都知道 Leslie Lamport 是图灵奖获得者,也是分布式算法的奠基人之一。但不知道的是,当 Lamport 提出拜占庭将军问题的时候,他正在SRI,为NASA做关于航天飞机航电系统的研究。同样,也很少有人知道,他不仅仅是分布式系统的奠基人,更是数字签名的先驱。

  所以,当初 Lamport 写下拜占庭将军问题这篇论文的初衷,是想要说明刚刚诞生不久的RSA和数字签名的作用,而并没有考虑到异步拜占庭将军问题。因此在 Lamport 随后发表此论文中,解决的是说慌情况下的拜占庭将军问题。

  那么 Leslie Lamport 是如何解决这一问题的呢?答案就是加入签名。一旦在指令中加入签名,即便全世界只有两个将军是诚实的,其它将军都是叛徒,这两个将军之间也能达成共识。下面让我们来具体分析一下,指令中加入签名后将会产生什么效果。

  假设A依然下达进攻的指令,此时B、C收到A签过名的消息:“A说进攻”。因为B是正义的,所以B会向C传达 :“A说进攻”;同时又因为C是叛徒,所以会篡改A的命令,向B传达:“C说撤退” 。

  在这里有些吃瓜群众可能又想问,为什么C不直接告诉B说:“A说撤退”呢?这是因为:命令可以伪造篡改,但是签名是无法伪造篡改的。所以当C一旦篡改了指令,那么这条指令的签名,也会相应的变成C,而不是A。

  加了签名之后:B还蒙圈吗?答案是不会。因为B接收到的命令为:“A说进攻,C说撤退。”有些吃瓜群众可能又会问:为什么呀,俺不懂,你再解释解释。那么就让小六用数学上的反证法,再给你们证明一下,正义将军B为什么不再蒙圈了吧。

  假设C是正义的,那么C不会篡改A的命令,所以他只会将A的命令再转述给B。那么B收到的命令将为:“A说进攻”&“A说进攻”,这与上文B接收到的命令:“A说进攻”&“C说撤退”相矛盾,所以假设不成立,即C是叛徒。聪明的B经过这一番分析之后,不但很开心的与A达成了共识,并且还发现了C是个叛徒。

  前方十级套路预警!!!

  同理可证,当指挥官是叛徒的时候,上述结论仍成立。

  不知道大家有没有发现,在上述问题中,不管是叛徒还是忠诚的将军,大家都积极的参与其中:没有挂机,没有掉线,我们称其为同步系统。但是在现实生活中,情况往往没有这么简单。

  比如我们和别人共同协作一个任务,如果有几个人不负责任,他们可能看到通知后也不会及时回复,这就会拖慢整个任务的进度。根据生活经验我们知道,再这种系统之下,我们所面临的问题非常棘手。但不幸的是,我们往往就处在这样的一个异步网络系统之中,

  1.2沉默的叛徒

   之前我们提到, Leslie Lamport 在写下拜占庭将军问题这篇论文的时候,他并没有考虑到异步拜占庭将军的问题。所以当沉默的叛徒出现时,原来的大招已经不管用了。

  在异步拜占庭将军问题中,叛徒拥有了更大的能力,他可以假装自己是失效节点,从而导致B再次蒙圈。

  假设A仍旧下达进攻的指令,此时两个副官接到指令:“A说进攻”。然后正义将军B就会像向叛徒C传达:”A说进攻”。由于C是一个沉默的叛徒,所以他将不会给B传达任何指令。

  但这时候,B的内心戏是非常复杂的!!!为什么C不回我消息?不是说好做彼此的天使吗??为什么不理我了???由此,因为B没有收到C的命令,并且B也不敢只轻信A,所以我们再次得出结论,正义将军B又将无法与A达成共识。

  其实,异步拜占庭问题,才是我们在现实应用中最经常遇到的情况。而异步拜占庭系统,异步分布式系统,通过网络传输的消息可能丢失延迟重复或者乱序,恶意节点将会利用这些特征对正义节点造成干扰,导致拜占庭失效。

  现在让我们总结一下:在叛徒说谎时,任何一个将军——无论是指挥官还是副官,由于签名的存在,谎言一定会被识破;而在叛徒沉默的情况下,由于有人故意不说话,所以终究无法达成共识。

  看完上面的文章,有没有很绝望?发现看了那么久,拜占庭将军问题仍旧无法彻底解决?

  其实小六在刚开始研究拜占庭将军问题的时候,也很蒙圈。看了一些大V的解释和文章,但由于学识有限,所以小六目前还无法站在专业的角度,来分析拜占庭将军问题。故只能从数学这一层面,去解释一下拜占庭将军问题。

  其实在拜占庭将军问题因为区块链而大火之前,它更像是一个数学问题(小六在这里绝对没有贬低BFT算法的意思)。

  虽然随着互联网的普及,我们生活中的分布式系统已经随处可见,但由于它的应用场景非常有限,所以在共识算法中,采用BFT的少之又少。但是如今但凡提到区块链,BFT绝对是一个绕不开的话题。

  所以在下一篇文章中,小六依旧从数学的角度,给大家继续解释拜占庭将军问题,并将浅析BFT与区块链的前世今生。

  /  END  /

  写在后面

  通证观察局 是由一群区块链爱好者自发组织成立的通证内容平台,我们希望通过研究金融、历史和社会等多方面领域的知识,共同探讨通证未来的发展。

  如果你对这篇文章感兴趣,欢迎扫描下方二维码添加作者微信,一起进行交流探讨:)            

  作者介绍

  小六

  一个爱吃薯片的区块链粉丝

版权信息
作者:小六
来源:通证观察局

关于我们

联系我们

作者进驻

手机版

Copyright © 2013 比特巴 www.btb8.com
始建于2013年,提供比特币 区块链及数字货币新闻、技术教程、测评、项目周报、人物等资讯
本页面提供的是新手入门教程资讯,提供入门级的比特币知识、区块链知识以及各类数字货币知识,是数字货币爱好者入门、精通的好导师。