在區(qū)塊鏈中,不同節(jié)點(diǎn)為了達(dá)成數(shù)據(jù)一致而按照同一套邏輯處理數(shù)據(jù)。但有時(shí)候,區(qū)塊鏈節(jié)點(diǎn)可能為了自身利益而發(fā)送錯(cuò)誤的信息,也有可能因?yàn)榫W(wǎng)
在區(qū)塊鏈中,不同節(jié)點(diǎn)為了達(dá)成數(shù)據(jù)一致而按照同一套邏輯處理數(shù)據(jù)。但有時(shí)候,區(qū)塊鏈節(jié)點(diǎn)可能為了自身利益而發(fā)送錯(cuò)誤的信息,也有可能因?yàn)榫W(wǎng)絡(luò)中斷而無法傳遞接收信息,這就使區(qū)塊鏈網(wǎng)絡(luò)中的節(jié)點(diǎn)得到不一致的結(jié)果,從而破壞系統(tǒng)一致性。拜占庭將軍問題被認(rèn)為是在分布式系統(tǒng)中達(dá)成共識(shí)的最難解的問題之一,而與之對(duì)應(yīng)的拜占庭容錯(cuò)共識(shí)算法是區(qū)塊鏈網(wǎng)絡(luò)的基礎(chǔ)設(shè)施之一。
1982年,圖靈獎(jiǎng)獲得者萊斯利 · 蘭伯特(Leslie Lamport)發(fā)表了一篇重要的論文《拜占庭將軍問題》(The Byzantine Generals Problem),由此展開了長達(dá)幾十年的、關(guān)于如何在分布式系統(tǒng)中有節(jié)點(diǎn)被故意破壞的情況下達(dá)成共識(shí)的討論。
隨著區(qū)塊鏈技術(shù)的出現(xiàn),這種討論有愈演愈烈的趨勢(shì)。但對(duì)大多數(shù)人來說,直接去啃論文,無異于望梅止渴,并不能很好地理解論文中要表達(dá)的思想。在這篇文章里,我就帶你通俗地學(xué)習(xí)拜占庭將軍問題背后的共識(shí)協(xié)議。
兩個(gè)將軍問題
相關(guān)廠商內(nèi)容
羅輯思維Go語言微服務(wù)改造完整過程
Netflix的未來IT架構(gòu)模型:Serverless
阿里巴巴數(shù)據(jù)處理引擎Blink核心設(shè)計(jì)
谷歌研究院出品:TensorFlow在深度學(xué)習(xí)中的應(yīng)用
破案大獎(jiǎng),五周年細(xì)的不能再細(xì)的攻略
相關(guān)贊助商
首先我們來看一個(gè)比較簡(jiǎn)單的例子,我們姑且就稱之為“兩個(gè)將軍問題”吧,情形是這樣的:
有兩支軍隊(duì)一起攻打一座城市,他們各自由一名將軍領(lǐng)導(dǎo)。兩支軍隊(duì)各自占領(lǐng)城市附近兩個(gè)不同的山谷。兩軍之間隔著一個(gè)山谷,雙方間唯一的通信方式就是派遣信使來往于三個(gè)山谷。不幸的是,中間山谷已被城市保衛(wèi)軍占領(lǐng),也就意味著:信使在通過山谷時(shí)可能會(huì)被捕。
現(xiàn)在兩支軍隊(duì)要協(xié)商進(jìn)攻城市的時(shí)間,因?yàn)橹挥袃芍к婈?duì)一起進(jìn)攻才能獲得戰(zhàn)斗的勝利。所以他們就必須溝通一個(gè)時(shí)間點(diǎn)來發(fā)起進(jìn)攻,并同意就在那時(shí)發(fā)動(dòng)攻擊。大家可以想一想,兩位將軍能就何時(shí)進(jìn)攻達(dá)成一致么?
A1和A2軍隊(duì)需要協(xié)調(diào),但是他們派出的信使有可能被B軍隊(duì)攔截
現(xiàn)在,我來展開介紹這個(gè)過程。
A1將軍寫了封進(jìn)攻信“我們兩支軍隊(duì)凌晨四點(diǎn)一起發(fā)動(dòng)總攻”,并將信交給信使。信使將信帶出去后,A1將軍根本不知道信使是被捕了還是已將信送達(dá)。因此,A1將軍會(huì)猶豫是否發(fā)動(dòng)進(jìn)攻,除非收到了A2將軍的確認(rèn)回信。
假設(shè)信使通過了山谷,將信交給了A2將軍,A2將軍寫了封回信“我同意在凌晨四點(diǎn)發(fā)動(dòng)總攻”,他將回信交給信使之后,A2將軍也不知道信使是否成功將回信交給了A1將軍。因此,A2將軍會(huì)猶豫是否發(fā)動(dòng)進(jìn)攻,除非收到了A1將軍的確認(rèn)回信。
假設(shè)信使又成功地通過了封鎖,將A2將軍的確認(rèn)進(jìn)攻回信交給了A1將軍。為了讓A2將軍放心,A1將軍還得給A2將軍寫封信“我已經(jīng)收到了你的確認(rèn),我們會(huì)取得勝利的”。但是,如果這次的信使被捕了呢?是否A2將軍還得給A1將軍發(fā)信“我確認(rèn)我已經(jīng)收到了你的確認(rèn)消息”?
...
于是,你會(huì)發(fā)現(xiàn)兩位將軍陷入了僵局,因?yàn)樗麄儾荒艽_認(rèn)信使是否將信息傳遞給了對(duì)方。因此,這個(gè)問題是無解的。
無限次重試,永遠(yuǎn)不可能達(dá)成共識(shí)
還有另外一個(gè)例子,是說三個(gè)人在不同房間,進(jìn)行投票的故事。三個(gè)人彼此可以通過電話進(jìn)行溝通,但經(jīng)常會(huì)有人不接電話。比如某個(gè)時(shí)候,A 投票“贊成”,B 投票“反對(duì)”,但是C不接電話。A 和 B 永遠(yuǎn)無法在有限時(shí)間內(nèi)獲知最終的結(jié)果。如果可以重新投票,類似情形也同樣會(huì)再次發(fā)生。
這背后其實(shí)有一個(gè)很著名的定理:“FLP不可能性”,它是指在分布式異步通信中,沒有任何算法能保證一致性。
我們可能會(huì)覺得不可思議,因?yàn)樵诂F(xiàn)在的軟件系統(tǒng)架構(gòu)中,分布式架構(gòu)隨處可見,比如Paxos算法。這里的區(qū)別在于FLP定理是學(xué)術(shù)定理,是遵循嚴(yán)格數(shù)學(xué)證明的,考慮的是最極端的情況,而Paxos算法是工程實(shí)踐,學(xué)術(shù)上的極端性一般情況下很少發(fā)生,即便發(fā)生,多試幾次可能就成功了。
正如第一個(gè)例子所示,不可能每次派出的信使都被B軍隊(duì)攔截,所以A1、A2將軍可以一次性派出100個(gè)信使,只要有1個(gè)信使通過了封鎖,就算是送信成功。而同樣在投票的例子里,ABC每輪都給彼此打多次電話,直至打通,這樣也能達(dá)成共識(shí)。
有句話是這么說的:科學(xué)告訴你什么是不可能的;工程則告訴你,付出一些代價(jià),我可以把它變成可能。這就是工程的魅力。我很贊同。
拜占庭將軍問題
接下來,我們來看拜占庭將軍問題,它相較于兩將軍問題要復(fù)雜得多。萊斯利·蘭伯特在他的論文里是這么描述這個(gè)問題的:
9位拜占庭將軍分別率領(lǐng)一支軍隊(duì)要共同圍困一座城市,因?yàn)檫@座城市很強(qiáng)大,如果不協(xié)調(diào)統(tǒng)一將軍們的行動(dòng)策略,部分軍隊(duì)進(jìn)攻、部分軍隊(duì)撤退會(huì)造成圍困失敗,因此各位將軍必須通過投票來達(dá)成一致策略,要么一起進(jìn)攻,要么一起撤退。
因?yàn)楦魑粚④姺謩e占據(jù)城市的一角,他們只能通過信使互相聯(lián)系。在協(xié)調(diào)過程中每位將軍都將自己投票“進(jìn)攻”還是“撤退”的消息通過信使分別通知其他所有將軍,這樣一來每位將軍根據(jù)自己的投票和其他將軍送過來的投票,就可以知道投票結(jié)果,從而決定是進(jìn)攻還是撤退。
而問題的復(fù)雜性就在于:將軍中可能出現(xiàn)叛徒,他們不僅可以投票給錯(cuò)誤的決策,還可能會(huì)選擇性地發(fā)送投票。假設(shè)9位將軍中有1名叛徒,8位忠誠的將軍中出現(xiàn)了4人投“進(jìn)攻”,4人投“撤退”,這時(shí)候叛徒可能故意給4名投“進(jìn)攻”的將軍投“進(jìn)攻”,而給另外4名投“撤退”的將軍投“撤退”。這樣在4名投“進(jìn)攻”的將軍看來,投票是5人投“進(jìn)攻”,從而發(fā)動(dòng)進(jìn)攻;而另外4名將軍看來是5人投“撤退”,從而撤退。這樣,一致性就遭到了破壞。
還有一種情況,因?yàn)閷④娭g需要通過信使交流,即便所有的將軍都是忠誠的,派出去的信使也可能被敵軍截殺,甚至被間諜替換,也就是說將軍之間進(jìn)行交流的信息通道是不能保證可靠性的。所以在沒有收到對(duì)應(yīng)將軍消息的時(shí)候,將軍們會(huì)默認(rèn)投一個(gè)票,例如“進(jìn)攻”。
以上就是拜占庭將軍問題的簡(jiǎn)單描述,如果將軍們?cè)谟信淹酱嬖诘那闆r下仍然達(dá)成了一致,我們就稱達(dá)到了“拜占庭容錯(cuò)”。那這跟我們?cè)诙嗯_(tái)計(jì)算機(jī)中達(dá)成共識(shí)有什么關(guān)系呢?
其實(shí),我們可以這么看這個(gè)問題,把將軍看做是計(jì)算機(jī);信使就是網(wǎng)絡(luò);信使被截殺,代表著計(jì)算機(jī)間的網(wǎng)絡(luò)不可達(dá);而將軍叛變則代表著程序出錯(cuò)。這么一解釋,有沒有豁然開朗的感覺?
拜占庭將軍問題有解嗎?答案是有的,但有個(gè)前提,那就是叛徒的數(shù)量不能大于等于1/3。
這個(gè)值怎么得出來的呢?這里我們可以用最小化模型來探討,因?yàn)楣沧R(shí)的基礎(chǔ)是要少數(shù)服從多數(shù),那么最小化模型的將軍數(shù)是3。假設(shè)有3個(gè)將軍A、B、C,假設(shè)三人中有一個(gè)是叛徒。
當(dāng)A發(fā)出“進(jìn)攻”命令時(shí),B如果是叛徒,他可能告訴C,他收到的是“撤退”的命令。這時(shí)C收到一個(gè)“進(jìn)攻”,一個(gè)“撤退“,于是C無法判斷真實(shí)命令。
如果A是叛徒,他告訴B“進(jìn)攻”,告訴C“撤退”。當(dāng)C告訴B,他收到“撤退”命令時(shí),B由于收到了A“進(jìn)攻”的命令,而無法與C保持一致。
正由于上述原因,只要有一個(gè)是叛徒,即叛徒數(shù)等于1/3,拜占庭問題便不可解。
既然有解,我們就來看看有哪些解法。
1. 口頭協(xié)定
所謂口頭協(xié)定,就是將軍們使用信使傳遞口頭信息,要滿足以下三個(gè)條件:
被發(fā)送的消息能夠被信使正確傳遞;
接受者知道消息是哪個(gè)將軍發(fā)的;
能夠知道誰沒有發(fā)送消息。
也就是說,信道可信,消息來源可知。消息傳遞一般的步驟如下:
每位將軍都給其他將軍傳遞口信;
每位將軍將自己收到的口信分別轉(zhuǎn)給其他將軍;
每位將軍根據(jù)收到的口信做出決策。
如此來看,每輪下來,每個(gè)將軍都會(huì)收到N(將軍數(shù))條消息,相當(dāng)于每個(gè)將軍都知道了其他將軍手里的投票,如果有一半以上的將軍說“進(jìn)攻”,那么就可以進(jìn)攻。即便是有叛徒,只要聽大部分人的,就可以保證達(dá)成一致。
但是口頭協(xié)定有個(gè)很大的弊端,就是不知道消息的上一個(gè)來源是哪個(gè)將軍發(fā)出來的,就算將軍中間有叛徒,也不能知道誰是叛徒。
2. 書面協(xié)定
不同于口頭協(xié)定的將軍間使用口信傳遞信息,而是使用書信,并且在書信上都要簽上國王發(fā)給將軍們的印章,相比于口頭協(xié)定,又多了兩個(gè)隱含條件:
將軍使用印章對(duì)書信簽名,簽名確定將軍身份,不可偽造,篡改簽名可被發(fā)現(xiàn);
任何將軍都可以驗(yàn)證簽名的有效性。
書面協(xié)定的本質(zhì)就是引入了“簽名系統(tǒng)”,這使得所有消息都可追本溯源。只要采用了書面協(xié)定,忠誠的將軍就可以達(dá)到一致?,F(xiàn)在這種方式下,將軍們按照以下方式發(fā)送消息:
每位將軍分別給其他將軍發(fā)送書信,并在書信上附上自己的簽名;
其他將軍收到書信后,附上自己的簽名后再發(fā)給所有其他將軍;
每位將軍根據(jù)自己收到的書信進(jìn)行決斷。
書面協(xié)定貌似完美解決了拜占庭將軍問題,但是不得不說實(shí)際上的解決是建立在諸多限制條件下的。在現(xiàn)實(shí)的分布式系統(tǒng)中,我們可能會(huì)遇到各種各樣的問題。例如:
沒有考慮信使傳遞消息的時(shí)延問題;
真正可信的簽名體系很難實(shí)現(xiàn),也很難避免簽名造假;
將軍們的印章是國王頒發(fā)的,難以褪去中心化機(jī)構(gòu)的影響。
另外,如果每個(gè)將軍都向其他將軍派遣信使表達(dá)自己的觀點(diǎn),那么一輪信息交流需要90次的信使往來。而且每個(gè)將軍的觀點(diǎn)都可能不一致,在異步通信模式下,幾乎很難達(dá)成一致。而且讓所有將軍都相信中心化的國王簽發(fā)的印章的真實(shí)性,實(shí)際上也違反了整個(gè)問題的前提,那就是將軍們互相不信任,即便是有國王的存在。
區(qū)塊鏈
不難看到,以上兩種解法或多或少都有些瑕疵,不難完美的解決問題。那么有沒有一種趨近完美的解決方案呢?當(dāng)然是有的,那就是中本聰在創(chuàng)造比特幣的時(shí)候提出的區(qū)塊鏈技術(shù)。
拜占庭將軍問題之所以難解,一個(gè)重要的原因就是在任意時(shí)間,系統(tǒng)中可能會(huì)存在多個(gè)提案,也就是問題描述中的每個(gè)將軍都可以給出自己的意見。這樣一來,很難在一個(gè)時(shí)刻對(duì)結(jié)果進(jìn)行一致性確認(rèn)。中本聰創(chuàng)新性地引入PoW共識(shí)算法,解決了兩個(gè)困難。
限制一段時(shí)間內(nèi)提案的個(gè)數(shù),只有擁有對(duì)應(yīng)權(quán)限的節(jié)點(diǎn)(將軍)可以發(fā)起提案。在比特幣里,是通過隨機(jī)哈希計(jì)算分配權(quán)限的,誰第一個(gè)計(jì)算出對(duì)應(yīng)的答案,誰才有權(quán)限發(fā)起提案。
由強(qiáng)一致性放寬至最終一致性。對(duì)應(yīng)一次提案的結(jié)果不需要全部的節(jié)點(diǎn)馬上跟進(jìn),只需要在節(jié)點(diǎn)能搜尋到的全網(wǎng)絡(luò)中的所有鏈條中,選取最長的鏈條進(jìn)行后續(xù)拓展就可以。
同時(shí),區(qū)塊鏈技術(shù)使用非對(duì)稱加密算法對(duì)節(jié)點(diǎn)間的消息傳遞提供簽名技術(shù)支持,每個(gè)節(jié)點(diǎn)(將軍)都有屬于自己的秘鑰(公鑰私鑰),唯一標(biāo)識(shí)節(jié)點(diǎn)身份。使用非對(duì)稱加密算法傳遞消息,能夠保證消息傳遞的私密性,而且消息簽名不可抵賴,不可篡改。
使用公鑰加密的數(shù)據(jù),使用公鑰對(duì)應(yīng)的私鑰進(jìn)行解密;使用私鑰進(jìn)行簽名的消息,只需要使用私鑰對(duì)應(yīng)的公鑰驗(yàn)證簽名即可。比如,A將軍想要給B將軍發(fā)送消息,那么只需要使用B將軍的公鑰加密消息,B將軍收到消息后使用自己的私鑰解密消息即可。而如果A將軍想申明自己的身份,只需要將消息使用自己的私鑰進(jìn)行簽名即可,B將軍收到消息后就可以使用A將軍的公鑰驗(yàn)證消息的來源。這樣就將一個(gè)不信任的網(wǎng)絡(luò)變成了信任網(wǎng)絡(luò)。
在對(duì)區(qū)塊鏈的研究中,經(jīng)常聽到有人說PoW算法浪費(fèi)了大量的電力資源、GPU資源等,是不可取的做法。我認(rèn)為區(qū)塊鏈?zhǔn)褂肞oW共識(shí)算法來保證系統(tǒng)的去中心化,成就可信網(wǎng)絡(luò),凡事都是有得有失,達(dá)成信任這一目標(biāo)不管以何種方式完成,成本永遠(yuǎn)不可能為零。而在以比特幣為首的區(qū)塊鏈網(wǎng)絡(luò)中,電力資源、GPU資源等就是達(dá)成信任需要付出的成本。
在區(qū)塊鏈這樣的分布式網(wǎng)絡(luò)中,我們還是以將軍為例:
每位將軍都保留一份歷史消息賬本;
因?yàn)槊糠菹⒍际沁M(jìn)行過簽名的,所以如果有背叛的將軍,我們很容易就能找出來;
在一輪共識(shí)的流程里,即便有消息不一致,但是只要背叛將軍個(gè)數(shù)不超過1/3,這一輪共識(shí)就能達(dá)成。
這里,我們很清楚地知道,區(qū)塊鏈和拜占庭將軍問題的共性所在了,都是決定由誰發(fā)起消息(提案),以及如何在分布式系統(tǒng)中達(dá)成一致的問題。
總結(jié)
由多門技術(shù)糅合在一起的區(qū)塊鏈技術(shù),它摒棄了口頭協(xié)定與書面協(xié)定的諸多問題,使用非對(duì)稱加密算法、PoW等共識(shí)算法,構(gòu)建了一套分布式系統(tǒng)中大家都準(zhǔn)守的協(xié)議,至善至美的解決了拜占庭將軍問題。同時(shí)也為未來的世界提供了無限的可能性,正所謂:未來可期,未來以來。