「區塊鏈從入門到精通」：拜占庭將軍問題 | 第8講

在上節課中，我們共同學習了區塊鏈的三大特性，第一點就是區塊鏈的去中心化特性。但形成去中心化的網路之後，不是各搭各的台，各唱各的戲，而是要保證各個節點可以形成統一的決定，用區塊鏈的術語，就是如何達成共識。

小到人和人之間的人際關係，大到國家和國家之間的外交關係，達成共識可以說是頭等大事，人緣差、沒有國家戰略夥伴，肯定會影響個人幸福和國家穩定。

微軟的首席研究員萊斯利·蘭伯特在2013年獲得了有著「計算機界諾貝爾獎」之稱的圖靈獎，他是計算機分散式問題專家，在他最著名的一篇文章中，他提出了著名的拜占庭將軍問題。在這篇文章的摘要中，他風趣的提到了迪傑斯特拉的「哲學家就餐問題」，迪傑斯特拉是1972年的度「圖靈獎」得主。蘭伯特調侃道，因為創作了「就餐問題」，迪傑斯特拉獲得了超出預想的關注。蘭伯特此時正在解決NASA的一個計算機容錯系統，考慮的問題是「如何保證分散式系統的可靠性」，所以也萌生了創作一個有趣小故事的想法。

在分散式計算領域中，兩軍問題，或者稱作「中國將軍問題」，是很有名的。蘭伯特受此啟發，創作了拜占庭將軍問題。這裡還有個小插曲，一開始蘭伯特的故事叫做「阿爾巴尼亞將軍問題」，同事提醒他換個名字，他才換成了「拜占庭將軍問題」。

先來看下給了蘭伯特啟發的「兩軍問題」：兩支駐紮在不同地點的軍隊分別由一名將領指揮，如果兩個將軍必須通過傳令兵傳遞消息，才能達成共同進攻或撤退的決定。兩軍合力才可以戰勝敵人，否則只有失敗或撤退。問題出在傳令兵上，一方派往另一方的傳令兵可能永遠到達不了，一種可能是被敵軍捉住，另一種可能是被險惡的地形困住。學者們已經證明在通信受阻的情況下，除非是巧合，這兩位將軍是不可能達成一致的。他們二人只能憑藉對另一人戰略戰術的了解，做出猜測，才能做出決定。

關於猜測，在劉慈欣的科幻小說《三體》中，大劉也分析了宇宙文明間存在的猜疑鏈。大劉通過主人公羅輯，闡述了宇宙的兩條公理：一、生存是文明的第一需要；二、文明不斷增長和擴張，但宇宙中的物質總量保持不變。然後又道出了宇宙的秘密：宇宙就是一座黑暗森林，每個文明都是潛行於林間的持槍獵人。林中到處是這樣的獵人，如果一個文明發現了另外一個文明，他只有一個選擇，將其消滅。

為什麼宇宙的秘密如此黑暗呢？咱們可以假想一個最基本的模型，假設地球探測到火星內部有一個高度發達的文明，在沒有交流之前，我們是無法判斷火星人是否具有善意。假如人類向這個文明發出了邀請函。收到邀請函的火星文明同樣也會犯難，他們也無法判斷地球人是否真的懷有善意。這樣在兩者之間就形成了猜疑鏈，無法形成信任。

猜疑鏈正是阻擋兩方達成合作共識的罪魁禍首。雙方彼此之間的猜測，是一個典型的博弈過程，雙方都想將自己的利益最大化，結果造成任何一方都會成為獵物。博弈論的創始人是大名鼎鼎的馮·諾依曼，他不僅是博弈論的創始人，也是現代計算機結構的發明人，同時也是一位卓越的數學家，還參與過曼哈頓工程，研究過原子彈。後人在馮諾依曼的理論基礎上開發出了多種模型，其中之一是廣為流傳的「囚徒困境」：兩名犯人接受隔離審問，犯人被告知，如果一人坦白，另一人不坦白，坦白的人就會無罪釋放，不坦白的人就判5年；兩人都坦白，各判3年；兩人都不坦白，各判1年。可以設身處地的從一名囚犯的角度進行考慮：他的判決結果完全取決於另一人是否坦白，如果另一人選擇坦白，他為了避免5年的最大懲罰，最好也選擇坦白；如果另一人不坦白，那麼為了能無罪釋放，最好也選擇坦白。兩名囚犯都這麼思考，結果兩人都輕易坦白了。這就是典型的在存在猜疑的情況下，個人的理性選擇，造成了集體的非理性。

拜占庭將軍問題的參與者要多於前面的例子：拜占庭帝國是東羅馬帝國的別稱，因為首都君士坦丁堡位於希臘城邦拜占庭的舊址，所以又被成為拜占庭帝國。帝國後期內亂不斷，一群將軍領兵圍困了一座敵城。與兩軍問題類似，他們也必須靠傳令兵傳遞信息，才能達成統一的行動：要麼一起進攻，要麼一起撤退。假設傳令兵一定能將信息送達，但是將軍中可能存在一個或多個叛徒，叛徒會派傳令兵發送假信息，從而人為地製造猜疑。叛徒向其他將軍發送的信息是不一樣的，有進攻的提議，也有撤退的提議，這時不能達成一致的錯誤，叫做「拜占庭錯誤」。如果叛徒發送了假信息，傳令系統仍能達成一致性，則稱該系統具備「拜占庭容錯」。

接下來，我們討論下兩軍問題和拜占庭將軍問題在不同條件下，是否存在解決方法，可以破解猜疑和信任的難題。

兩軍問題在無法實現兩軍通訊的情況下是無解的。如果添加一些條件，是否可以破解兩軍問題和囚徒困境呢？對於兩軍問題，假如國王宣布兩個將軍只能前進不能後退，後退者殺無赦，就可以保證兩軍在指定時刻同時進攻；對於囚徒困境，假如黑幫老大立下了規矩，誰要是坦白了，就會受到黑幫內部最嚴厲的懲罰，也可以保證兩名囚犯都守口如瓶，這樣兩人都只要坐一年牢就行了。

對於拜占庭將軍問題，可以分為口頭通訊和書面通訊。

如果採用口頭通訊，拜占庭將軍問題有解的條件是將軍的總數要大於叛徒總數的三倍。因為達成共識的原則是少數服從多數，那麼最小模型的將軍總數是3。假設有3個將軍甲乙丙，三人中有一人是叛徒：當甲發出「進攻」命令時，乙如果是叛徒，他可能告訴丙，他收到的是「撤退」的命令。這時丙收到一個「進攻」，一個「撤退「，於是丙無法判斷真實命令；如果甲是叛徒，他告訴乙「進攻」，告訴丙「撤退」。當丙告訴乙，他收到「撤退」命令時，乙由於收到了甲「進攻」的命令，而無法與丙保持一致。

在符合有解的條件下，每位將軍只要根據收到的口信，根據多數原則做決策就行了。

如果拜占庭帝國的國王給每個將軍發了一個不同的印章，將軍們可以利用印章確定通信中的將軍身份，將軍可以對其它人的印章進行驗證。有了這些印章，每位將軍分別給其他將軍發送書信，並在書信上附上自己蓋印；其他將軍收信後，附上自己的印章後再發給所有其他將軍；最終，每位將軍根據收到的書信進行決斷。這樣就能杜絕叛徒給每個人發送不同信息。但是對於這種書面信息，實物的印章是靠不住的，偽造發生的可能性很高；國王的存在實際是一個高度可信的第三方，不符合去中心化的特徵。最好這可以用一個客觀的理論代替印章和國王，實現真正的分散式共識。這個理論具備數學公理般牢不可破的特性，比國王更讓人信任。

兩軍問題和拜占庭問題，體現了去中心化組織為了達成共識所碰到的困境。內部原因和外部原因都可能造成無法達成共識。雖然在特定條件下有對應的解決方案，但會破壞去中心化的特徵。作為集大成者，比特幣吸收了前人在密碼學、分散式系統上的經驗，它是如何解決區塊鏈網路節點的共識難題的呢？關於共識演算法，歡迎收聽下一講的內容。恭喜你完成《區塊鏈入門到精通》第8講的學習。

「區塊鏈從入門到精通」：從玄武門之變到分叉和算力攻擊 | 第7講