在區(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í)也為未來的世界提供了無限的可能性，正所謂：未來可期，未來以來。
