## 拜占庭將軍問題深入探討  了解過比特幣和區塊鏈的人，多少都聽說過拜占庭將軍問題，或聽說過比特幣（或區塊鏈）的一個重要成就正是解決了拜占庭將軍問題。但真正明白這個問題的人并不多，甚至知道這個問題實質的人都很罕見。本文是一篇技術科普，將重點提供了拜占庭將軍問題本身對本質及經典算法的解析，并探討與之相關的一些問題。筆者參考了不少文獻，夾雜了大量私貨，但并沒有提出解決該問題的新算法，這也不是本文的目的。 ## 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函數的時候，就可以直接正確得到司令的命令。 可以發現，這個引理說明了如果只需要考慮IC2，將軍總數是不需要3倍背叛者之多的，接下來我們回歸命題。 證明： 首先考慮司令是忠誠的，令引理中的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，我們做了一些在現實中比較難以完成的假設，比如沒考慮傳輸信息的延遲時間，書面協議的簽名體系難以實現，而且簽名消息記錄的保存難以擺脫一個中心化機構而獨立存在。事實上，存在能夠完美解決書面協議實際局限的方法，這個方法就是區塊鏈。如果您感興趣，也可以參考筆者同系列的文章《大材小用——用區塊鏈解決拜占庭將軍問題》。 作者：毒毒程 審校：初夏虎 村長 責編：printemps 稿源：[巴比特資訊](http://www.8btc.com/baizhantingjiangjun "baizhantingjiangjun") 來源：[拜占庭將軍問題深入探討 | 巴比特](http://www.8btc.com/baizhantingjiangjun) last update：2018-1-9 06:07:10