拜占庭將軍的難題

古老的“拜占庭將軍問題”

讓人生，讓人死，讓人癡迷，讓人瘋狂。

這就是傳說中繁華與沒落，絕望與救贖并存的東羅馬帝國首都，拜占庭。

在2013年獲得計算機科學(xué)領(lǐng)域最高獎項圖靈獎的31年前，1972年，萊斯利·蘭伯特（Leslie Lamport）搬到灣區(qū)。此時，他仍然是一個寂寂無聞的美國小伙。他充當Compass（馬薩諸塞州計算機合伙人公司）西海岸計劃前哨基地的先鋒，不幸的是，這個分支機構(gòu)最終未能落實。在長達5年的時間里，他曾是Compass總部派駐加州的唯一員工。最后，他卻收到撤回東海岸的指令。于是，他決定加入斯坦福國際研究院（SRI）。在那段歲月里，SRI有一個項目，要在美國航空航天局建立容錯型航電計算機系統(tǒng)。考慮到系統(tǒng)的工作性質(zhì)，故障是不允許發(fā)生的。這段經(jīng)歷孕育了兩篇旨在解決一種特殊故障的論文，由蘭伯特和SRI同事馬歇爾·皮斯（Marshall Pies）及羅伯特·肖斯塔克（Robert Shostak）合作完成。用計算學(xué)術(shù)語說，普通故障可能會導(dǎo)致信息丟失或進程停止，但系統(tǒng)不會遭到破壞，因為這種普通故障屬于一出錯就會停下來的故障類型，剩下的備份的、正常的部分照樣可以運轉(zhuǎn)，發(fā)揮作用。就像戰(zhàn)場上的士兵，他們一旦受傷或陣亡就停止戰(zhàn)斗，但并不妨礙他人繼續(xù)作戰(zhàn)。

然而一旦發(fā)生“拜占庭故障”，就會非常麻煩，因為它們不會停下來，還會繼續(xù)運轉(zhuǎn)，并且給出錯誤訊息。就像戰(zhàn)爭中有人成了叛徒，會繼續(xù)假傳軍情，惑亂人心。當時為了解決這個問題，常常使用的技術(shù)被稱為“三重模塊冗余”：也就是說使用三臺計算機進行萬一出錯的備份工作，三臺獨立的計算機按照少數(shù)服從多數(shù)的原則“投票”。這樣，即使其中一臺機器提供了錯誤結(jié)果，其他兩臺仍然會提供正確答案。但是為了證明這種方法的有效性，必須拿出證據(jù)。而在編寫證據(jù)的過程中，研究人員遇到了一個問題：“錯誤”計算機可能給其他兩臺計算機發(fā)送互不相同的錯誤值，而后者卻不會知道。這就需要使用第四臺計算機來應(yīng)對這個故障。

蘭伯特說：“如果你使用數(shù)字簽名，就可以用三臺機器達成目的，因為如果‘壞了’的計算機向一臺計算機發(fā)送了帶簽名的錯誤值，并向另一臺發(fā)送了不同的帶簽名錯誤值，另外兩臺計算機就能夠交換消息，以檢查究竟發(fā)生了什么情況，因為兩個不同的值都是簽名發(fā)送的。”蘭伯特還聽吉姆·格雷談?wù)撨^另一個性質(zhì)大體相同的問題，人們稱之為“中國將軍問題”。這引起了蘭伯特有關(guān)司令將軍和叛徒將軍的聯(lián)想，于是他將這個問題及其解決方案命名為“拜占庭將軍問題”。

“我記得，與我的朋友懷特·迪菲（White Duffy）坐在伯克利的一間咖啡館里，當時他描述了一個構(gòu)建數(shù)字簽名的問題。”蘭伯特回憶說，“他說：‘如果能辦到的話，會非常有用。’我說：‘這聽起來并不很困難。’于是在一張餐巾紙上，我為他勾畫出了第一種數(shù)字簽名算法。雖然當時并不很實用，但目前已經(jīng)變得切實可行。”只可惜那張餐巾紙已經(jīng)消逝在時間的流沙中。在后來1982年正式出版的拜占庭將軍論文的序言中，他這樣寫道：

“我一直覺得正是因為通過用一組圍坐在圓桌旁的哲學(xué)家來表述，Dijkstra（迪克斯塔）的‘哲學(xué)家就餐問題’才變得如此讓人關(guān)注（比如在理論界，它可能比‘讀者/作者’問題都引人注目，盡管讀者/作者問題可能更具實際意義）。我認為Reaching Agreement in the Presence of Faults（達成共識的缺陷）中所描述的問題十分重要，值得計算機科學(xué)家們?nèi)リP(guān)注。‘哲學(xué)家就餐問題’使我認識到，把問題以講故事的形式表達出來更能引起人們的關(guān)注。在分布式計算領(lǐng)域有一個被稱作‘中國將軍問題’的問題。在這個問題中，兩個將軍必須在進攻還是撤退上達成一致，但是相互只能通過信使傳送消息，而且這個信使可能永遠都無法到達。我借用了這里的將軍的叫法，并把它擴展成一組將軍，同時這些將軍中有些是叛徒，他們需要達成一致的決定。同時我想給這些將軍賦予一個國家，同時不能得罪任何讀者。那時候，阿爾巴尼亞還是一個完全封閉的國家，我覺得應(yīng)該不會有阿爾巴尼亞人看到這篇文章，所以最初的時候這篇論文題目實際是The Albanian Generals Problem（阿爾巴尼亞將軍問題）。但是Jack Goldberg（杰克·古登博格）后來提醒我，在這個世界上除了阿爾巴尼亞之外還有很多阿爾巴尼亞移民，所以建議我換個名字。于是就想到了這一更合適的叫法——Byzantine generals（拜占庭將軍）。”

寫這篇論文的最主要目的是將拜占庭將軍這個叫法用在這個問題上。基本的算法文章在1980年的論文中就已經(jīng)出現(xiàn)了。

起源：拜占庭位于現(xiàn)在土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當時拜占庭羅馬帝國國土遼闊，為了防御敵人每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳消息。在戰(zhàn)爭時期，拜占庭軍隊內(nèi)所有將軍和副官必須達成一致共識，決定是否有贏的機會才去攻打敵人的陣營。但是，軍隊可能有叛徒和敵軍間諜，左右將軍們的決定，擾亂軍隊整體的秩序。在達成共識的過程中，有些信息，往往并不代表大多數(shù)人的意見。這時候，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達成一致的協(xié)議，就是“拜占庭將軍問題”。

兩軍問題：軍隊與軍隊之間分隔很遠，傳遞信息的信差可能在途中陣亡，或因軍隊距離不能在得到消息后即時回復(fù)，發(fā)送方也無法確認消息確實丟失的情形，導(dǎo)致不可能達到一致性。在分布式計算上，試圖在異步系統(tǒng)和不可靠的通道上達到一致性是不可能的。因此對一致性的研究一般假設(shè)信道是可靠的，或非異步系統(tǒng)上運行。

“拜占庭將軍問題”在通信領(lǐng)域的意義

“拜占庭將軍問題”并非如傳說中那樣，源于公元5世紀的東羅馬戰(zhàn)場，而是產(chǎn)生于1982年一位美國計算機科學(xué)家的頭腦當中。因此，我們不會使用任何1982年之前的案例來描述這個問題在古老年代的意義，因為再往前追溯，它并未真正、嚴肅地被提出并加以審視。

在原始的戰(zhàn)爭年代，將軍與將軍、將軍與下屬間只能采用原始的方式——“出行靠走，通訊靠吼”的口頭傳輸。這對應(yīng)蘭伯特論文提出算法中的第一部分的口頭消息算法，簡稱OM（m）算法。這種情形，真?zhèn)魏茈y辨別，只有當叛徒的總數(shù)不超過將軍總數(shù)的1/3，成為一個特殊的“拜占庭容錯系統(tǒng)”時，才能在很大的消息驗證代價后，實現(xiàn)最終的一致行動。這個結(jié)果非常令人驚訝，如果將軍們只能發(fā)送口頭消息，除非超過2/3的將軍是忠誠的，否則該問題無解。尤其是，如果只有三個將軍，其中一個是叛變者，那么此時無解。但這樣的錯誤，這樣的有意、無意的“叛徒”卻可能經(jīng)常出現(xiàn)。無論是我們把“叛變的將軍”替換成以下哪種，該問題都成立。

? 一個出故障的，向其他計算機不停發(fā)出不同錯誤信息的服務(wù)器；

? 一份為獲取暴利而做出來的金融票據(jù)；

? 一份失效的醫(yī)療糾紛合同；

? 一份含混不清的保單；

? 一個可以發(fā)出消息，做出行動的錯誤信息節(jié)點。

而這里，每一個錯誤節(jié)點可以做任意事情：不響應(yīng)；發(fā)送錯誤信息；對不同節(jié)點發(fā)送不同決定；不同錯誤節(jié)點聯(lián)合起來攻擊其他節(jié)點等。沒準會出現(xiàn)比這更嚴重、更荒謬的錯誤。

如果說“叛變的拜占庭將軍”是我們社會中各種類型的信息節(jié)點的隱喻，那么“拜占庭將軍問題”所描述的情景，這樣一個進攻／撤退命令極難驗證真?zhèn)蔚闹惺兰o戰(zhàn)場，則無疑是我們當今越發(fā)缺乏中心化的、難以判別信息與產(chǎn)生信任的社會的極度悲觀的隱喻。

用算法解決難題——區(qū)塊鏈技術(shù)的雛形

構(gòu)造出一個完美的、可以解決問題的“拜占庭容錯系統(tǒng)”是一個不小的挑戰(zhàn)。而且構(gòu)造出來以后，其是否真的有效，能否經(jīng)得起時間的考驗與各方的質(zhì)疑，這些都關(guān)乎著這個系統(tǒng)未來的命運與其創(chuàng)造群體的聲譽。

2008年冬季，美國MIT（麻省理工學(xué)院）的密碼學(xué)及密碼學(xué)政策戰(zhàn)略的郵件討論組中，一位澳大利亞的企業(yè)家James A Donald（詹姆斯·A. 唐納德）就對一位聲稱構(gòu)造出了一個點對點的、不需要第三方權(quán)威認證的e-cash（電子現(xiàn)金）支付系統(tǒng)提出了質(zhì)疑。而他的理由就是：對方設(shè)計的P2P系統(tǒng)不能夠解決“拜占庭將軍問題”。

在郵件中他挑剔地說道：“我們的確真的非常非常需要這個系統(tǒng)，但我所擔(dān)憂的并不是信任的問題，而是如何獲取一個全局共享的圖景，借由此點而獲取一致性的問題。每個人都知道X，這并不足夠。我們需要讓每個人都知道‘每個人都知道X’。而每個人都知道‘每個人都知道X’就是‘拜占庭將軍問題’中，分布式的數(shù)據(jù)處理最難解決的問題。尤其是當X是非常龐大的數(shù)據(jù)時……”言下之意，他并不清楚或不確信這個去中心化的系統(tǒng)，如何解決拜占庭將軍的難題。

僅僅在一天之后，他就收到了原作者的回復(fù)，一封簡潔、優(yōu)雅的郵件解釋了在這個系統(tǒng)中，破解“拜占庭將軍問題”的算法。

“工作量證明鏈”（proof-of-work chain）正是我解決“拜占庭將軍問題”的方案。我將在那個語境中對它進行重新表述。

一群拜占庭將軍，人手一臺電腦想用字符串模式匹配的方法，暴力破解國王的Wi-Fi密碼，當然他們已經(jīng)事先獲取了組成密碼的字符串的長度。一旦他們開始模擬網(wǎng)絡(luò)發(fā)送數(shù)據(jù)包，他們必須在一個限定的時間內(nèi)完成破解工作，并清除服務(wù)器和電腦上的記錄，否則他們就會被發(fā)現(xiàn)，那就麻煩了。只有當絕大多數(shù)將軍在同一時間發(fā)起攻擊和破解，這樣才能有足夠的CPU（中央處理器）和計算能力在短時間內(nèi)完成破解工作。

他們并不特別在乎什么時候開始攻擊，只要他們?nèi)客饩秃谩Ｒ婚_始的時候，大家決定這樣搞：任何人覺得時機到了都可以宣布一個攻擊時刻。而且，不論是什么時候，只要是第一個被聽到的攻擊時刻，就將被確定為官方的攻擊時刻。這樣的話問題又來了，因為網(wǎng)絡(luò)傳達有延遲和干擾，如果有兩個將軍差不多同一時間公布了兩個不同的攻擊時刻，那么有的人會最先聽到其中一個將軍發(fā)布的攻擊時刻，而又有些人則會最先聽到另外一個將軍發(fā)布的攻擊時刻。

他們使用一個“工作量證明鏈”來解決這個問題。當每個將軍接收到任何表達形式的第一個攻擊時刻時，他都會設(shè)置他的計算機來求解一個極其困難的“工作量證明”問題，對這個問題的解答是一個哈希（Hash）散列，里面也將包含著這次的攻擊時刻。由于這個“工作量證明”問題，非常難解，一般而言，就算所有人收到這個問題后同時求解，也至少需要10分鐘才能產(chǎn)生解答。一旦一個將軍解出了“工作量證明”，他將會把這個算出來的“工作量證明”向整個網(wǎng)絡(luò)進行傳播，每一個接收到的人，將在他們當前正在做的“工作量證明”計算的散列中附加上剛剛被求解出來的那個工作量證明。如果任何人正在計算他收到的其他的一個不同的攻擊時刻，他們將會轉(zhuǎn)向新的更新后的“工作量證明”計算當中，因為他現(xiàn)在的“工作量證明鏈”更長了。

兩個小時后，將有一個攻擊時刻被散列在一個有12個“工作量證明”的鏈中。每個將軍只要通過驗證（這條工作鏈的）計算難度，就能估算出平均每小時有多少CPU算力耗費在這上面，也就會知道：這一定是在分配的時間段內(nèi)，絕大多數(shù)將軍的計算機共同協(xié)作才能生成的結(jié)果。如果“工作量證明鏈”中展示出來的算力足夠強大，可以破解國王的Wi-Fi密碼，那么他們就可以在一致同意的時間內(nèi)安全地展開攻擊。

同步、分布式數(shù)據(jù)庫和一個一致的、全局性的視野的問題如何解決？“工作量證明鏈”就是答案。

我們可以看到這封郵件解決了下面幾個問題：

（1）引入一個困難的、需要10分鐘求解的工作量計算，限制了網(wǎng)絡(luò)中每個時刻中被提出的進攻時刻數(shù)目。

（2）將所有求解出的“工作量證明”都逐一加入，形成一個越來越長的鏈條，一個記錄著所有“參與著攻擊時刻哈希計算的將軍、計算的‘工作量證明’、關(guān)于‘工作量證明’的計算的總體名錄”。

（3）基于這條長鏈得出安全的進攻時刻的答案。

最后，請各位讀者注意這封解釋郵件頭上的內(nèi)容：

日期：2008年11月14日06:56:55（GMT+8）

郵件作者的簽名：Satoshi Makamoto