拜占庭將軍問題深入探討

轉載

了解過比特幣和區塊鏈的人，多少都聽說過拜占庭將軍問題，或聽說過比特幣（或區塊鏈）的一個重要成就正是解決了拜占庭將軍問題。但真正明白這個問題的人並不多，甚至知道這個問題實質的人都很罕見。本文是一篇技術科普，將重點提供了拜占庭將軍問題本身對本質及經典演算法的解析，並探討與之相關的一些問題。筆者參考了不少文獻，夾雜了大量私貨，但並沒有提出解決該問題的新演算法，這也不是本文的目的。

Part1：拜占庭將軍問題是什麼

拜占庭將軍問題是一個共識問題: 首先由Leslie Lamport與另外兩人在1982年提出，被稱為The Byzantine Generals Problem或者Byzantine Failure。核心描述是軍中可能有叛徒，卻要保證進攻一致，由此引申到計算領域，發展成了一種容錯理論。隨著比特幣的出現和興起，這個著名問題又重入大眾視野。

1.1. 拜占庭將軍問題場景

關於拜占庭將軍問題，一個簡易的非正式描述如下：

拜占庭帝國想要進攻一個強大的敵人，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵禦5支常規拜占庭軍隊的同時襲擊。基於一些原因，這10支軍隊不能集合在一起單點突破，必須在分開的包圍狀態下同時攻擊。他們任一支軍隊單獨進攻都毫無勝算，除非有至少6支軍隊同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵相互通信來協商進攻意向及進攻時間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進攻意向或者進攻時間。在這種狀態下，拜占庭將軍們能否找到一種分散式的協議來讓他們能夠遠程協商，從而贏取戰鬥？這就是著名的拜占庭將軍問題。

應該明確的是，拜占庭將軍問題中並不去考慮通信兵是否會被截獲或無法傳達信息等問題，即消息傳遞的信道絕無問。Lamport已經證明了在消息可能丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。所以，在研究拜占庭將軍問題的時候，我們已經假定了信道是沒有問題的，並在這個前提下，去做一致性和容錯性相關研究。如果需要考慮信道是有問題的，這涉及到了另一個相關問題：兩軍問題。

1.2.與拜占庭將軍相關問題：兩軍問題

正如前文所說，拜占庭將軍問題和兩軍問題實質是不一樣的。國內大量解釋拜占庭將軍問題的文章將兩者混為一談，其實是混淆了兩個問題的實質，由此造成了許多誤解。這兩個問題看起來的確有點相似，但是問題的前提和研究方向都截然不同。

（圖1：兩軍問題圖示）

如圖1所示，白軍駐紮在溝渠里，藍軍則分散在溝渠兩邊。白軍比任何一支藍軍都更為強大，但是藍軍若能同時合力進攻則能夠打敗白軍。他們不能夠遠程的溝通，只能派遣通信兵穿過溝渠去通知對方藍軍協商進攻時間。是否存在一個能使藍軍必勝的通信協議，這就是兩軍問題。

看到這裡您可能發現兩軍問題和拜占庭將軍問題有一定的相似性，但我們必須注意的是，通信兵得經過敵人的溝渠，在這過程中他可能被捕，也就是說，兩軍問題中信道是不可靠的，並且其中沒有叛徒之說，這就是兩軍問題和拜占庭將軍問題的根本性不同。由此可見，大量混淆了拜占庭將軍問題和兩軍問題的文章並沒有充分理解兩者。

兩軍問題的根本問題在於信道的不可靠，反過來說，如果傳遞消息的信道是可靠的，兩軍問題可解。然而，並不存在這樣一種信道，所以兩軍問題在經典情境下是不可解的，為什麼呢？

倘若1號藍軍（簡稱1）向2號藍軍（簡稱2）派出了通信兵，若1要知道2是否收到了自己的信息，1必須要求2給自己傳輸一個回執，說「你的信息我已經收到了，我同意你提議的明天早上10點9分準時進攻」。

然而，就算2已經送出了這條信息，2也不能確定1就一定會在這個時間進攻，因為2發出的回執1並不一定能夠收到。所以，1必須再給2發出一個回執說「我收到了」，但是1也不會知道2是否收到了這樣一個回執，所以1還會期待一個2的回執。

雖然看似很可笑，但在這個系統中永遠需要存在一個回執，這對於兩方來說都並不一定能夠達成十足的確信。更要命的是，我們還沒有考慮，通信兵的信息還有可能被篡改。由此可見，經典情形下兩軍問題是不可解的，並不存在一個能使藍軍一定勝利的通信協議。

不幸的是，兩軍問題作為現代通信系統中必須解決的問題，我們尚不能將之完全解決，這意味著你我傳輸信息時仍然可能出現丟失、監聽或篡改的情況。但我們能不能通過一種相對可靠的方式來解決大部分情形呢？這需要談到TCP協議。事實上，搜索「兩軍問題與三次握手」，您一定可以找到大量與TCP協議相關的內容。若您是通信方面的專家，權當筆者是班門弄斧，這裡僅用最淺顯易懂的方式科普TCP協議的原理和局限，可能存在一些毛刺，請多包涵。

（圖2：TCP協議的基本原理）

TCP協議中，A先向B發出一個隨機數x，B收到x了以後，發給A另一個隨機數y以及x+1作為答覆，這樣A就知道B已經收到了，因為要破解隨機數x可能性並不大；然後A再發回y+1給B，這樣B就知道A已經收到了。這樣，A和B之間就建立一個可靠的連接，彼此相信對方已經收到並確認了信息。

而事實上，A並不會知道B是否收到了y+1；並且，由於信道的不可靠性，x或者y都是可能被截獲的，這些問題說明了即使是三次握手，也並不能夠徹底解決兩軍問題，只是在現實成本可控的條件下，我們把TCP協議當作了兩軍問題的現實可解方法。

（圖3：量子隱形傳態的原理圖）

那麼，是否能夠找到一個理論方法來真正的破解兩軍問題呢？答案是有的，量子通訊協議，筆者並沒有能力弄清這個頗為高深的問題。據我的理解，處於量子糾纏態的兩個粒子，無論相隔多遠都能夠彼此同步，光是直觀的來看，這個效應可以用來實現保密通訊。

但是由於測不準原理，一測量粒子狀態就會改變其狀態，所以通訊時還必須通過不可靠信道發送另一條信息。儘管這個「另一條信息」是不可靠的，但是由於已經存在了一條絕對可靠的信道（量子糾纏），保證了另一條信道即使不可靠也能保證消息是可靠的，否則至少被竊取了一定能夠被發現。

因此我們可以相信，至少理論上兩軍問題是可解的，即存在一種方法，即使利用了不可靠的信道，也能保證信息傳遞的可靠性。所以，在確保了信道可靠的基礎上，我們可以回到拜占庭將軍問題上繼續討論。

Part2：問題實質及形式化

我們已經了解了拜占庭將軍問題的場景，並且明確了這個問題的解決是建立在通信兵可以正確的傳達信息的基礎上的，即信道絕對可信。同時，通過前文對於兩軍問題的探討，我們明白了理論上可信的信道也是可以實現的。接下來，我們將探討拜占庭將軍問題的實質。

2.1. 拜占庭將軍問題實質

回顧問題，一群將軍想要實現某一個目標（一致進攻或者一致撤退），但是單獨行動行不通，必須合作， 達成共識；由於叛徒的存在，將軍們不知道應該如何達到一致。注意，這裡「一致性」才是拜占庭將軍問題探討的內容，如果本來叛徒數量就已經多到了問題不可解的地步，這個就是「反叛」的問題了；同時，我們的目標是忠誠的將軍能夠達成一致，對於這些忠誠的將軍來說，進攻或者撤退都是可以的，只要他們能夠達成一致就行。

但是，光靠「一致」就可以解決問題嗎？考慮一下，如果萬事俱備，客觀上每個忠誠的將軍只要進攻了就一定能夠勝利，但是卻因為叛徒的存在他們都「一致的」沒有進攻；反之，條件不利，將軍們不應該進攻，但是卻因為叛徒的存在所有人都「一致的」進攻了。

可以發現，只有「一致性」是不足以解決拜占庭將軍問題的，我們還需要提出一個「正確性」要求。這個要求是值得斟酌的，因為如果客觀來看或許會有「絕對正確的」判斷，但是針對每一個將軍，大家的判斷或許都不相同，我們如何定義「正確」呢？我們或許可以簡單地說，正確就是每個忠誠的將軍都正確的表達了自己的意思，不會因為叛徒讓別的將軍認為忠誠的將軍是叛徒而不採用他傳達的消息。

至此，我們將拜占庭將軍問題簡化成了，所有忠誠的將軍都能夠讓別的將軍接收到自己的真實意圖，並最終一致行動；而形式化的要求就是，「一致性」與「正確性」。

如果將問題推廣開來，可以發現針對一致性和正確性的演算法並不要求命令必須是「進攻/撤退」或是「1/0」，而可以是「發送消息1/發送消息2/待機」或「x/y/z/w」，這意味著拜占庭將軍問題演算法可以為多種分散式系統提供啟發，比如電力系統或網路系統。

由此可見，這個問題說到底是一個關於一致性和正確性的演算法問題，這個演算法是針對的是忠誠的將軍，因為叛徒可以做出任何超出約定的判斷。我們就是要在有叛徒的干擾下，找到一個抗干擾的演算法。要解決這個演算法問題，我們需要將形式化要求具體化。

2.2.形式化條件的推演

定義一個變數vi（為不失一般性，並不要求vi是布爾值），作為其他將軍收到的第i個將軍的命令值；i將軍會將把自己的判斷作為vi。可以想像，由於叛徒的存在，各個將軍收到的vi值不一定是相同的。之後，定義一個函數來處理向量(v1,v2,…,vn)，代表了多數人的意見，各將軍用這個函數的結果作為自己最終採用的命令。至此，我們可以利用這些定義來形式化這個問題，用以匹配一致性和正確性。

1）一致性

條件1：每一個忠誠的將軍必須得到相同的(v1,v2,…,vn)指令向量或者指令集合。

這意味著，忠誠的將軍並不一定使用i將軍送來的信息作為vi，i將軍也可能是叛徒。但是僅靠這個條件，忠誠的將軍的信息送來的信息也可能被修改，這將影響到正確性。

2）正確性

條件2：若i將軍是忠誠的，其他忠誠的將軍必須以他送出的值作為vi。

如此，我們得到了一致性和正確性的形式化條件（條件1和條件2），這個條件是充分條件。考慮到正確性條件是針對單個將軍，而一致性條件是針對所有將軍的，為方便我們重寫一致性條件為

條件1′：無論i將軍是忠誠或是叛徒，任何兩個忠誠的將軍都使用相同的vi。

條件1和條件1′是完全等價的。這是很巧妙的一步轉換，如此一致性條件（條件1′）和正確性條件（條件2）都只涉及一個將軍i如何幫別的將軍接受自己送出的值vi，所以可以將問題改為司令-副官模式來簡化問題，即一個司令把自己的命令傳遞給n-1個副官，使得：

IC1：所有忠誠的副官遵守一個命令，即一致性。

IC2：若司令是忠誠的，每一個忠誠的副官遵守他發出的命令，即正確性。

IC1和IC2分別由條件1′和條件2演化得來。司令-副官模式只要將司令遍歷各個將軍，就可以變成完整問題，而他們採用的演算法可以是完全一致的。IC1和IC2構成了解決拜占庭將軍問題的充分條件，在這種模式下，司令副官的形式下達成的一致意味著司令的命令得到了有效傳達，若出現了異議，有異議的將軍會作為司令發起新的司令副官模式尋求自己的觀點表達，以協商達成一致。

接下來，我們可以討論拜占庭將軍問題的演算法了，這個演算法只要能夠滿足IC1和IC2，就代表這個演算法可以切實有效的解決拜占庭將軍問題。

在經典的情形下，我們可以找到兩種辦法，口頭協議和書面協議。筆者將會逐一探討兩種演算法的推演和證明，其中證明部分並不會採用純推理，而以介紹證明思路為主。

事實上，若完整進行了演算法推演，對演算法已經能夠有一個大致的了解。口頭協議和書面協議會有很多不同的啟發，口頭協議的實現起來簡單，但是演算法複雜，同時需要克服的困難更多；書面協議的演算法本身很簡單，卻能夠克服很多問題，但是實現演算法並不容易。這些不同讓兩者有了不同的使用場景和具體實現。

Part3：口頭協議

首先，我們明確什麼是口頭協議。我們將滿足以下三個條件的方式稱為口頭協議：

A1：每個被發送的消息都能夠被正確的投遞

A2：信息接收者知道是誰發送的消息

A3：能夠知道缺少的消息

簡而言之，信道絕對可信，且消息來源可知。但要注意的是，口頭協議並不會告知消息的上一個來源是誰。

先告知結論：採用口頭協議，若叛徒數少於1/3，則拜占庭將軍問題可解。也就是說，若叛徒數為m，當將軍總數n至少為3m+1時，問題可解（即滿足了IC1和IC2）。

這個結論說明了，一個三模冗餘的系統只能容故障凍結類型的錯誤，即一個元件故障以後就卡住不動了（也即已知錯誤後會出現的結果），那麼三模冗餘是足夠的。

但是對於拜占庭將軍問題，由於叛徒可以做出各種各樣的判斷，就必須四模冗餘系統才足夠容錯。口頭協議演算法就是把自己的命令告訴其他人，並利用對其他人的命令取多數的方法來得到自己的結論。但要注意的是，別的將軍傳來的命令是通過演算法遞歸的方法來確定的。利用這個方法，可以保證在叛徒數量少於1/3的情況下，忠誠的將軍可以實現一致性和正確性要求，即問題可解。

那麼，口頭協議演算法又是怎麼實現叛徒數少於1/3即可容錯的呢？下面，筆者將介紹Lamport在其論文中提出的口頭協議OM(m)演算法。筆者將會逐一介紹口頭協議演算法的詳細內容、實例推演及證明，這一部分將會需要您花一些時間來思考。

3.1.口頭協議演算法OM(m)

OM(0)演算法

（1）司令將他的命令發送給每個副官。

（2）每個副官採用從司令發來的命令；如果沒有收到命令，則默認為撤退命令。

OM(m)演算法

（1）司令將他的命令發送給每個副官。

（2）對於每個i，vi是每個副官i從司令收到的命令，如果沒有收到命令，則默認為撤退命令。副官i在OM(m-1) 中作為發令者將之發送給另外n-2 個副官。

（3）對於每個i，和每個j ≠ i，vj 是副官i 從第2步中的副官j （使用OM(m-1)演算法）發送過來的命令，如果沒有收到第2步中副官j 的命令，則默認為撤退命令。最後副官i 使用majority(v1,…,vn-1)得到命令。

其中，majority(v1,…,vn-1)代表了大多數人的命令，若不存在則默認為撤退命令。

要一遍讀懂這個演算法並不容易，筆者也是花了不少時間研究這一小段文字才弄明白的。不過您不用擔心，筆者將會解釋幾個值得注意的點，並利用一個不難的實例來幫助您理解這個演算法。

（1）演算法始終保證了一個更加安全的默認值，這意味著若信息沒有傳到是可知的，並且傳輸時間不在考慮範圍內。

（2）這個演算法是一個遞歸演算法，在OM(m)中需要採用OM(m-1)得到相關結果。m代表的是叛徒數量，從m到0，意味著對於每個將軍，需要m+1輪的演算法才能完成。

（3）該演算法是關於m的，意味著使用該演算法必須知道有多少個叛徒。或者說，利用該演算法，可以保證叛徒數量在某一個最大值（即總將軍數量的1/3）之下時，拜占庭將軍問題可解。

（4）對於任意k<m，在第m-k+1步中OM(k)的vi，都是利用OM(k-1)得來的，即每個將軍將會在OM(k-1)中詢問其他人，i將軍傳給他們的是什麼，而其他人傳遞迴來的信息則是利用OM(k-2)得到。

這個就是遞歸的意義，若您覺得筆者表達得不甚清楚，不用擔心，您只用記住每一步都會牽涉到下面很多步驟就可以了，之後將在實例推演中明白演算法的核心思路。

3.2.口頭協議實例推演

首先，筆者將先舉一個m=1，n=3的例子來說明三模冗餘的問題所在，並介紹m=1，n=4的時候系統是怎麼容錯的，這樣您就可以明白演算法是運行的。但由於m=1的時候並沒有體現遞歸的過程（因為m-1就變成了0），筆者將再舉一個m=2，n=7的例子來說明演算法遞推的過程。 （1）m=1，n=3的情形 n=3，意味著一個司令發送命令給兩個副官，m=1意味著他們中有一個叛徒。 首先考慮司令忠誠而副官2是叛徒的情況。

（圖4：m=1，n=3中司令忠誠而副官2是叛徒的情形）

司令把進攻命令傳給了兩個副官1和副官2，但是由於副官2為了不讓他們達成一致，將司令的命令改成了撤退。那對於副官1來說，他應該如何判斷？他無法知道是司令是叛徒還是副官2是叛徒，從而無法判斷。

（圖5：m=1，n=3中司令是是叛徒的情形）

而如果司令是叛徒，兩個副官忠誠，司令會發送兩個不同的命令。當兩個副官對照命令時，他們又凌亂了，無法判斷司令是叛徒或者對方是叛徒，從而又無法判斷。這個情形非常簡易的說明了三模冗餘是無法動態容錯的。（2）m=1，n=4的情形 n=4，意味著一個司令發送命令給三個副官，m=1意味著他們中有一個叛徒。 首先考慮司令忠誠而副官3是叛徒的情況。

（圖6：m=1，n=4中司令忠誠而副官3是叛徒的情形）

倘若司令在OM(1)中給各副官發送的消息都是進攻（A），之後OM(0)時，叛徒副官3給副官1和副官2說他收到的消息是撤退（R）。那麼對於副官1（或副官2）來說，他綜合司令、副官3和副官2（或副官1）後得到的消息向量都將會是(A,A,R)，利用majority函數之後，將會採用A，滿足了IC1和IC2（回顧IC1：所有忠誠的副官遵守一個命令，IC2：若司令是忠誠的，每一個忠誠的副官遵守他發出的命令）。

（圖7：m=1，n=4中司令是是叛徒的情形）

倘若司令是叛徒，那麼我們已經不需要滿足IC2。為方便，我們假設叛徒司令在OM(1)會給三個副官發送的信息是(x,y,z)，其中x，y，z都可以是A或R的任意一種。之後，三位忠誠的副官將會按照OM(0)要求的那樣，交換他們收到的信息。

對於副官1，他綜合司令、副官2和副官3後得到的消息向量將會是(x,y,z)，可以發現對於其他兩個忠實的副官，他們得到的消息向量也將是(x,y,z)。不管x，y，z如何變化，majority(x,y,z)對於三人來說都是一樣的，所以三個副官將會採用一致的行動。

（3）m=2，n=7的情形 接下來，我們將討論m=2，n=7的情形，雖然只是多了一個叛徒，但是這裡會出現遞歸過程，所以會複雜很多。

首先，我們先討論司令忠誠的情形，假設叛徒為副官5和副官6。

（圖8：m=2，n=7中司令忠誠而副官5和副官6是叛徒的情形）

在OM(2)中，司令將攻擊命令（A）傳給各個副官。在OM(1)中，忠誠的副官們將會發送他們收到的消息（A），但由於副官5和副官6是叛徒，他們將會發送別的信息（比如R）。這時，忠誠的副官們將會採用使用OM(1)中的方法來確定各個v1~v6。例如，對於副官1，他收到了司令傳來的命令，他會直接採用majority函數綜合司令和其他將軍傳來的信息嗎？他不會，因為這還在OM(1)中，他並不知道司令是不是叛徒，他會利用詢問別人的方式來確認將軍的命令，但是按照演算法他會把司令的命令作為v1（即v1=A）並傳給其他人。

接下來他會努力取得其他的v2~v6的值，這時已經在OM(1)中了，副官1絕不會輕易相信別人傳來的消息，比如副官2給他傳來了命令A，但是他會懷疑副官2傳來的消息，所以他用OM(1)大法，問其他人副官2傳給了他們什麼，副官3和副官4誠實的告訴副官1，副官2給他們傳的是A，而這時副官5和副官6又要撒謊了，他們又亂說，我們姑且假定他們傳來的是x』和y』吧。這樣，終於進入到了OM(0)，這時副官1將會綜合其他副官對於v2的反饋，得到向量(A,A,A,x』,y』)，再利用majority函數，得到了v2=A。如下圖，這是副官1在OM(1)中得到的信息（x，y等表示了不確定的命令）。

（圖9：司令忠誠時副官1在OM(1)中得到的信息）

我們就可以得到副官1的v1~v6向量為(A,A,A,A,x,y)，利用majority函數，副官1最終採用的行動會是A。 類似的，我們可以發現，其他幾個忠誠的副官得到的命令向量都會是(A,A,A,A,x,y)，利用majority函數後採用的行動都會是A。所以，我們可以發現忠誠的副官採用的命令都是A（滿足IC1），並且和忠誠的將軍的命令一致（滿足IC2）。至此，您應該已經明白了這個演算法是怎麼遞歸的，不管m等於多少，都只是一個演算法步驟多寡的問題。 至於司令是叛徒的情形，其實是相似的，這裡簡單的再提一下便於理解。若您已經明白了演算法過程，完全可以跳過。

（圖10：m=2，n=7中司令和副官6是叛徒的情形）

為方便，我們假定了副官6是叛徒。司令在OM(2)中就很雞賊的給副官1~副官6發送了不同的命令(A,R,A,R,A,x)。在OM(1)中，各副官把自己收到的命令傳出去，而（為方便，假定）副官6則給其他副官分別發送了(A,R,A,R,A)。類似於前文推演的那樣，考慮副官1，他將司令傳來的命令A作為v1後，還會詢問其他人傳來的命令，由此去確認v2~v6，類似的，我們將之表達為下圖：

（圖11：司令反叛時副官1在OM(1)中得到的信息）

如圖，我們就可以得到副官1的v1~v6向量為(A,R,A,R,A,A)，利用majority函數，副官1最終採用的行動會是A。類似的，我們可以發現忠誠的副官1~副官5得到的消息向量都是(A,R,A,R,A,A)，最終他們採用的行動都會是A（滿足了IC1），而司令是叛徒不需要滿足IC2。值得提醒的是，若副官6傳遞的是(R,A,R,A,R)，那麼他們所有人得到的消息向量都是(A,R,A,R,A,R)，此時A和R數量一樣多，這並不代表majority不起作用了，他將採用默認值R（回顧前文：majority(v1,…,vn-1)代表了大多數人的命令，若不存在則默認為撤退命令），所有人的行動都會採用R，這同樣是滿足的。

到此為止，我們已經將口頭演算法的實例推演進行的很徹底了，若您還有興趣，可以試一試當n=7，m=3的時候為什麼就不能達成一致了，操作是類似的。 3.3.口頭協議演算法證明 演算法的證明思路其實並不複雜，簡單的來說，對於一個遞歸演算法，我們使用數學歸納法來證明是最直觀而又有效的方法了。我們回顧一下命題：將軍總數為n，叛徒數量為m，OM(m)可以實現，在n>3m的情況下，使得：

IC1：所有忠誠的副官遵守一個命令。

IC2：若司令是忠誠的，每一個忠誠的副官遵守他發出的命令。

為了證明整個命題，我們先引入一個針對IC2的引理：

引理：對於任意m和k，如果有超過2k+m 個將軍和最多k 個背叛者，那麼演算法OM(m)滿足IC2。

證明：

（1）m=0，而將軍是忠誠的，直接滿足IC2；

（2）m>0，此時假定OM(m-1)是有效的，那麼只需要考慮OM(m)這一輪即可。

n>2k+m，意味著n-1>2k，n-1是除了司令以外的所有副官，而所有副官的數量比叛徒的兩倍還多，那他們直接利用majority函數的時候，就可以直接正確得到司令的命令。

證明：

首先考慮司令是忠誠的，令引理中的k=m，直接得到OM(m)可以滿足IC2。

這時，我們只用考慮司令是叛徒的狀況。同樣利用數學歸納法。

（1）m=1，之前我們已經推演過OM(1)可以滿足1個叛徒司令，3個忠誠副官的情況；

（2）m>1，那麼假設n』>3m』的情況下，OM(m-1)能夠滿足IC1和IC2。

由於司令是叛徒，在OM(m)中司令會把命令發給各個副官，而這些副官中會有m-1個叛徒。在下一輪中，副官的數量至少有3m個，叛徒數為m-1，很顯然3m>3(m-1)，也就是說n』>3m』，根據假設，OM(m-1)可以滿足IC1和IC2，儘管司令是叛徒，由於OM(m-1)是有效的，OM(m)這一輪中忠誠的副官可以得到相同的(v1,…,vn-1)向量，所以忠誠的副官將會利用majority函數採用相同的命令，得證。

總結一下，口頭協議中，我們始終要求的是相同的(v1,…,vn-1)向量，只要這個向量是相同的我們怎麼處理都可以。又由於演算法是遞歸的，所以我們一定需要把這個處理方法變得通用而邏輯有效才行，所以我們才選用了majority函數這個演算法。這一點至關重要卻又沒有這麼直觀，因為我們的第一反應是要得到相同的majority函數值。但是反過來一想，既然演算法是遞歸的，majority函數值相同不就意味著(v1,…,vn-1)向量相同嗎？正確理解遞歸的思想是使用該演算法和利用數學歸納法證明該演算法的關鍵點。

至此，我們已經大致明確了口頭協議是怎麼回事，可以做到什麼不能做到什麼，以及這個演算法的推演和證明。很多系統都會出現口頭協議的情況，即各個系統節點可以把自己的消息準確的發送出去，同時可以知道消息的來源於何處。但是，這個方法的消息並不能追本溯源，這使得在口頭協議中至少得四模冗餘，我們可以試圖找到一個方法，讓消息能夠追本溯源，可以想像這能夠拓寬使用條件，這個方法可以是書面協議。

Part4：書面協議

口頭協議中我們討論了很多，揭示了口頭協議的缺點是消息不能追本溯源，這使得口頭協議必須在四模冗餘的情況下才能保證正確。但是，若能引入一種方法讓消息能夠追本溯源，情況會不會有所改變呢？這就是書面協議引入的靈感。

除了A1，A2和A3以外，我們在口頭協議之上添加一個條件A4，使之成為書面協議

A4：（a）簽名不可偽造，一旦被篡改即可發現，而叛徒的簽名可被其他叛徒偽造；（b）任何人都可以驗證簽名的可靠性。

那麼，我們先說結論：對於任意m，最多只有m個背叛者情況下，演算法SM(m)能解決拜占庭將軍問題。也就是說，在使用簽名的情況下，書面協議可以打破三模冗餘的僵局，使用了簽名的情況下，只要知道了叛徒數量，我們就可以利用SM(m)演算法解決拜占庭將軍問題。

4.1.書面協議演算法SM(m)

口頭協議演算法我們已經討論過很多了，所以筆者對書面協議盡量簡短的介紹。回顧

IC1：所有忠誠的副官遵守一個命令，即一致性。

IC2：若司令是忠誠的，每一個忠誠的副官遵守他發出的命令，即正確性。

我們要找到一個演算法SM(m)，不管將軍總數n和叛徒數量m，只要採用該演算法，忠誠的將軍總能達到一致（滿足IC1和IC2）。我們用集合Vi來表示i副官收到的命令集，這是一個集合，也就是滿足互異性（沒有重複的元素）等集合的條件。類似的，我們定義choice(V)函數來決定各個副官的選擇，這個函數可以有非常多種形式，他只要滿足了以下兩個條件：

（1）如果集合V只包含了一個元素v，那麼choice(V)=v

（2）choice(o)=RETREAT，其中o是空集

任何滿足了這兩個條件的函數都可以作為choice()，例如取平均值就可以。我們只需要根據具體情形定義choice()即可，這個非重點，筆者並不加以討論，您可以自行思考。之後我們會發現SM(m)演算法並不是一個遞歸演算法，我們只要讓各個副官收到的V集相同，choice(V)也一定能夠得到相同的值。

簡單解釋該演算法如下：

初始化Vi=空集合。

（1）將軍簽署命令並發給每個副官；

（2）對於每個副官i：

（A）如果副官i從發令者收到v:0的消息，且還沒有收到其他命令序列，那麼他

（i）使Vi為{v}；

（ii）發送v:0:i給其他所有副官。

（B）如果副官i收到了形如v:0:j1:…:jk的消息且v不在集合Vi中，那麼他

（i）添加v到Vi；

（ii）如果k<m，那麼發送v:0:j1:…:jk:i 給每個不在j1,..,jk 中的副官。

（3）對於每個副官i，當他不再收到任何消息，則遵守命令choive(Vi)。

值得注意的是，如果司令忠誠，由於其簽名不可偽造，所有忠誠的副官都將得到一個單點集{v}，他們採用的命令集Vi相同，得到的choive(Vi)也為v，滿足了IC1和IC2。

如果司令並非忠誠，只需要滿足IC1，但是演算法SM(m)使得所有忠誠的副官得到相同的Vi，使用choice()函數後採用的命令也就一定相同。

4.2.書面協議實例推演

司令是叛徒的狀況稍難想像，舉個例子，n=3，m=1，其中司令是叛徒，這是口頭協議不能解決的狀況。

（圖12：m=1，n=3中司令是叛徒的情形）

很顯然，副官1得到的V1={A,R}，副官2得到相同的V2={A,R}。他們採用choice函數後得到的命令一定相同。

相似的，n=4，m=2，其中司令是叛徒，這同樣是口頭協議不能解決的狀況。

（圖13：m=2，n=4中司令和副官3是叛徒的情形）

副官1和副官2得到的V1=V2={A,R}，他們採用choice函數後得到的命令也相同。即使命令不是布爾值，經過上面的分析框架，也可以得到相似的結論。至於這個演算法的證明，有興趣的讀者可以參考Lamport的原文，筆者就不做過多解釋了，如有問題仍可與筆者聯繫。

（圖14：Lamport在論文中對書面協議演算法的證明）

書面協議的本質就是引入了簽名系統，這使得所有消息都可追本溯源。這一優勢，大大節省了成本，他化解了口頭協議中1/3要求，只要採用了書面協議，忠誠的將軍就可以達到一致（實現IC1和IC2）。這個效果是驚人的，相較之下口頭協議則明顯有一些缺陷。

書面協議的結論非常令人興奮，這不是解決了拜占庭將軍問題了嗎？但請注意我們在A1~A4中實際上是添加了一些條件的，這使得拜占庭將軍問題在這些假設下能夠解決，但是在實際狀況中卻會有一些問題。觀察A1~A4，我們做了一些在現實中比較難以完成的假設，比如沒考慮傳輸信息的延遲時間，書面協議的簽名體系難以實現，而且簽名消息記錄的保存難以擺脫一個中心化機構而獨立存在。事實上，存在能夠完美解決書面協議實際局限的方法，這個方法就是區塊鏈。如果您感興趣，也可以參考筆者同系列的文章《大材小用——用區塊鏈解決拜占庭將軍問題》。

作者：毒毒程

稿源：巴比特資訊

每次我向那些不熟悉比特幣的人解釋比特幣的獨特之處的時候，我都會用會計學上的總賬和拜占庭將軍問題來幫助講解。此文就是幫助講解的內容，有了此文我就可以把鏈接發給小夥伴們，而不需要每次都重新打一大堆字了。

首先，不要把比特幣當成一種貨幣，而是一個總賬。它是個電子總賬，網路上的每一個參與者的電腦都會有一份總賬的備份，並且所有的備份都是在實時的持續的更新、對賬、以及同步著。每一個參與者都能在這本總帳里記上一筆，這一筆記錄著一定數量的幣從一個參與者那裡被發送到另一個參與者那裡，並且每一條這樣的記錄都接著就實時的廣播到網路了，所以在每一台電腦上的每一分份拷貝都是幾乎同時更新的，並且所有的總賬拷貝都保持著同步。這本公開的分散式的總賬的官方叫法是「區塊鏈（blockchain）」，並且它使用了BT技術以保證所有的拷貝都是同步的。

你還可以把比特幣當作一個對於在分散式系統領域的一個複雜的演算法難題的通用解決方法，這個難題俗稱「拜占庭容錯」、「拜占庭將軍問題」、或者「兩軍問題」。

這一問題的趣味非正式表述如下：想像一下，在拜占庭時代有一個牆高壁厚的城邦，拜占庭，高牆之內是它的鄰居想像不到之多的財富。它被其他10個城邦所環繞，這10個城邦也很富饒，但和拜占庭相比就微不足道了。它的十個鄰居都覬覦拜占庭的財富，並希望侵略並佔領它。

但是，拜占庭的防禦是如此的強大，沒有一個相鄰的城邦能夠成功入侵。任何單個城邦的入侵行動都會失敗，而入侵者的軍隊也會被殲滅，使得其自身容易遭到其他九個城邦的入侵和劫掠。這十個城邦之間也互相覬覦對方的財富並持續互相對抗著。而且，拜占庭的防禦如此之強，十個鄰居的一半以上同時進攻才能攻破它。

也就是說，如果六個或者更多的相鄰敵軍一起進攻，他們就會成功並獲得拜占庭的財富。然而，如果其中有一個或者更多背叛了其他人，答應一起入侵但在其他人進攻的時候又不幹了，也就導致只有五支或者更少的軍隊在同時進攻，那麼所有的進攻軍隊都會被殲滅，並隨後被其他的（包括背叛他們的那（幾）個）鄰居所劫掠。這是一個由不互相信任的各方構成的網路，但他們又必須一起努力以完成共同的使命。

而且，是個鄰居之間通訊和協調統計時間的唯一途徑是通過騎馬在他們之間傳遞信息。他們不能聚在一個地方開個會（所有的王都不互相信任他們的安全在自己的城堡或者軍隊範圍之外能夠得到保障）。然而，他們可以在任意時間以任意頻率派出任意數量的信使到任意的對方。每條信息都包含類似如下的內容：「我將在第四天的6點鐘進攻，你願意加入嗎？」。

如果收信人同意了，他們就會在原信上附上一份簽名了的/認證了的/蓋了圖章的/驗證了的回應，然後把新合併了的信息的拷貝再次發送給九個鄰居，要求他們也如此這樣做。最後的目標是，通過在原始信息鏈上蓋上他們所有十個人的圖章，讓他們在時間上達成共識。最後的結果是，會有一個蓋有十個同意同一時間的圖章信息鏈，可能還會有一些被拋棄了的包含部分但不是全部圖章的信息鏈。

但是，問題在於如果每個城邦向其他九個城邦派出一名信使，那麼就是十個城邦每個派出了九名信使，也就是在任何一個時間又總計90次的傳輸，並且每個城市分別收到九個信息，可能每一封都寫著不同的進攻時間。除此以外，部分城邦會答應超過一個的攻擊時間，故意背叛發起人，所以他們將重新廣播超過一條的信息鏈。這個系統迅速變質成不可信的信息和攻擊時間相互矛盾的糾結體。

比特幣通過對這個系統做出一個簡單的（事後看是簡單的）修改解決了這個問題，它為發送信息加入了成本，這降低了信息傳遞的速率，並加入了一個隨機元素以保證在一個時間只有一個城邦可以進行廣播。它加入的成本是「工作量證明」，並且它是基於計算一個隨機哈希演算法的。哈希是一種演算法，它唯一做的事情就是獲得一些輸入然後進行計算，並得到遺傳64位的隨機數字和字母的字元串，就像這個：

d70298566aa2f1a66d892dc31fedce6147b5bf509e28d29627078d9a01a8f86b

在比特幣的世界中，輸入數據包括了到當前時間點的整個總賬（區塊鏈）。並且儘管單個哈希值用現在的計算機可以幾乎即時的計算出來，但只有一個前13個字元是0的哈希值結果可以被比特幣系統接受成為「工作量證明」。這樣一個13個0的哈希值是極其不可能與罕見的，並且在當前需要花費整個比特幣網路大約10分鐘的時間來找到一個。在一台網路中的機器隨機的找到一個有效哈希值之前，上十億個的無效值會被計算出來，這就是減慢信息傳遞速率並使得整個系統可用的「工作量證明」。下面是一個例子：

f51d0199c4a6d9f6da230b579d850698dff6f695b47d868cc1165c0ce74df5e1

d70298566aa2f1a66d892dc31fedce6147b5bf509e28d29627078d9a01a8f86b119c506ceaa18a973a5dbcfbf23253bc970114edd1063bd1288fbba468dcb7f8

在找到一個有效值之前，成百萬上億個更多的類似上面這樣的字元串被計算出來。。。

000000000000084b6550604bf21ad8a955b945a0f78c3408c5002af3cdcc14f5

那台發現下一個有效哈希值的機器（或者說在我們類比中的城邦），把所有的之前的信息放到一起，附上它自己的，以及它的簽名/印章/諸如此類，並向網路中的其他機器廣播出去。只要其他網路中的機器接收到並驗證通過了這個13個0的哈希值和附著在上面的信息，他們就會停止他們當下的計算，使用新的信息更新他們的總賬拷貝，然後把新更新的總賬/區塊鏈作為哈希演算法的輸入，再次開始計算哈希值。哈希計算競賽從一個新的開始點重新開始。如此這般，網路持續同步著，所有網路上的電腦都使用著同一版本的總賬。

與此同時，每一次成功找到有效哈希值以及區塊鏈更新的間隔大概是10分鐘（這是故意的，演算法難度每兩周調整一次以保證網路一直需要花費10分鐘來找到一個有效的哈希值）。在那10分鐘以內，網路上的參與者發送信息並完成交易，並且因為網路上的每一條機器都是使用同一個總賬，所有的這些交易和信息都會進入遍布全網的每一份總賬拷貝。當區塊鏈更新並在全網同步之後，所有的在之前的10分鐘內進入區塊鏈的交易也被更新並同步了。因此分散的交易記錄是在所有的參與者之間進行對賬和同步的。

最後，在個人向網路輸入一筆交易的時候，他們使用內嵌在比特幣客戶端的標準公鑰加密工具來同時他們的私鑰以及接收者的公鑰來為這筆交易簽名。這對應於拜占庭將軍問題中他們用來簽名和驗證消息時使用的「印章」。因此，哈希計算速率的限制，加上公鑰加密，使得一個不可信網路變成了一個可信的網路，使得所有參與者可以在某些事情上達成一致（比如說攻擊時間、或者一系列的交易、域名記錄、政治投票系統、或者任何其他的需要分散式協議的地方）。

這裡是比特幣為何如此特別的關鍵：它代表了一個對於一個困難的演算法上的難題的解決方案，這一解決方案在一系列的歷史事件發生之前是不可能的，這些事件有：

1. 互聯網的創造
2. 公鑰加密演算法的發明
3. 點對點Bitorrent(BT)協議的發明。BT協議最開始是開發來用於在網路上的相對小的用戶子集之間共享許多文件的，但比特幣用它來在所有用戶之間共享單個文件。
4. 人們意識到，在系統中添加一個簡單的時間延遲，同時使用公鑰加密演算法以驗證每筆交易，可以解決這個問題。

如果說一些最棒的想法在事後看來是很簡單的，那麼上述的第四點就完全符合條件，儘管整個項目是站在了巨人的肩膀上的。

最後，這一對於拜占庭將軍問題的解決方案，可以推廣到任何核心問題是在分散式網路上缺乏信任的領域。如我們已經提到樂的，人們正在為互聯網建設一個分散式的域名系統，以及為政治選舉建設分散式的投票系統（還沒有網站）。如果人們認為單純的文件分享攪亂了這個世界，那麼比特幣解決方案和協議才剛剛打開洪水的閘門。

原文 http://expectedpayoff.com/blog/2013/03/22/bitcoin-and-the-byzantine-generals-problem/

作者 Byron Gibson

翻譯 He1l_Q

歡迎轉載，轉載時請註明作者翻譯者和出處，謝謝支持！