摘要

在區(qū)塊鏈中，不同節(jié)點為了達成數(shù)據(jù)一致而按照同一套邏輯處理數(shù)據(jù)。但有時候，區(qū)塊鏈節(jié)點可能為了自身利益而發(fā)送錯誤的信息，也有可能因為網(wǎng)絡中斷而無法傳遞接收信息，這就使區(qū)塊鏈網(wǎng)絡中的節(jié)點得到不一致的結果，從而破壞系統(tǒng)一致性。拜占庭將軍問題被認為是在分布式系統(tǒng)中達成共識的最難解的問題之一，而與之對應的拜占庭容錯共識算法是區(qū)塊鏈網(wǎng)絡的基礎設施之一。

1982年，圖靈獎獲得者萊斯利 · 蘭伯特（Leslie Lamport）發(fā)表了一篇重要的論文《拜占庭將軍問題》（The Byzantine Generals Problem），由此展開了長達幾十年的、關于如何在分布式系統(tǒng)中有節(jié)點被故意破壞的情況下達成共識的討論。

隨著區(qū)塊鏈技術的出現(xiàn)，這種討論有愈演愈烈的趨勢。但對大多數(shù)人來說，直接去啃論文，無異于望梅止渴，并不能很好地理解論文中要表達的思想。在這篇文章里，我就帶你通俗地學習拜占庭將軍問題背后的共識協(xié)議。

兩個將軍問題

首先我們來看一個比較簡單的例子，我們姑且就稱之為“兩個將軍問題”吧，情形是這樣的：

有兩支軍隊一起攻打一座城市，他們各自由一名將軍領導。兩支軍隊各自占領城市附近兩個不同的山谷。兩軍之間隔著一個山谷，雙方間唯一的通信方式就是派遣信使來往于三個山谷。不幸的是，中間山谷已被城市保衛(wèi)軍占領，也就意味著：信使在通過山谷時可能會被捕。

現(xiàn)在兩支軍隊要協(xié)商進攻城市的時間，因為只有兩支軍隊一起進攻才能獲得戰(zhàn)斗的勝利。所以他們就必須溝通一個時間點來發(fā)起進攻，并同意就在那時發(fā)動攻擊。大家可以想一想，兩位將軍能就何時進攻達成一致么？

A1和A2軍隊需要協(xié)調，但是他們派出的信使有可能被B軍隊攔截

現(xiàn)在，我來展開介紹這個過程。

A1將軍寫了封進攻信“我們兩支軍隊凌晨四點一起發(fā)動總攻”，并將信交給信使。信使將信帶出去后，A1將軍根本不知道信使是被捕了還是已將信送達。因此，A1將軍會猶豫是否發(fā)動進攻，除非收到了A2將軍的確認回信。

假設信使通過了山谷，將信交給了A2將軍，A2將軍寫了封回信“我同意在凌晨四點發(fā)動總攻”，他將回信交給信使之后，A2將軍也不知道信使是否成功將回信交給了A1將軍。因此，A2將軍會猶豫是否發(fā)動進攻，除非收到了A1將軍的確認回信。

假設信使又成功地通過了封鎖，將A2將軍的確認進攻回信交給了A1將軍。為了讓A2將軍放心，A1將軍還得給A2將軍寫封信“我已經(jīng)收到了你的確認，我們會取得勝利的”。但是，如果這次的信使被捕了呢？是否A2將軍還得給A1將軍發(fā)信“我確認我已經(jīng)收到了你的確認消息”？
...

于是，你會發(fā)現(xiàn)兩位將軍陷入了僵局，因為他們不能確認信使是否將信息傳遞給了對方。因此，這個問題是無解的。

無限次重試，永遠不可能達成共識

還有另外一個例子，是說三個人在不同房間，進行投票的故事。三個人彼此可以通過電話進行溝通，但經(jīng)常會有人不接電話。比如某個時候，A 投票“贊成”，B 投票“反對”，但是C不接電話。A 和 B 永遠無法在有限時間內獲知最終的結果。如果可以重新投票，類似情形也同樣會再次發(fā)生。

這背后其實有一個很著名的定理：“FLP不可能性”，它是指在分布式異步通信中，沒有任何算法能保證一致性。

我們可能會覺得不可思議，因為在現(xiàn)在的軟件系統(tǒng)架構中，分布式架構隨處可見，比如Paxos算法。這里的區(qū)別在于FLP定理是學術定理，是遵循嚴格數(shù)學證明的，考慮的是最極端的情況，而Paxos算法是工程實踐，學術上的極端性一般情況下很少發(fā)生，即便發(fā)生，多試幾次可能就成功了。

正如第一個例子所示，不可能每次派出的信使都被B軍隊攔截，所以A1、A2將軍可以一次性派出100個信使，只要有1個信使通過了封鎖，就算是送信成功。而同樣在投票的例子里，ABC每輪都給彼此打多次電話，直至打通，這樣也能達成共識。

有句話是這么說的： 科學告訴你什么是不可能的；工程則告訴你，付出一些代價，我可以把它變成可能。這就是工程的魅力。 我很贊同。