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