了解過(guò)比特幣和區(qū)塊鏈的人，多少都聽(tīng)說(shuō)過(guò)拜占庭將軍問(wèn)題，或聽(tīng)說(shuō)過(guò)比特幣（或區(qū)塊鏈）的一個(gè)重要成就正是解決了拜占庭將軍問(wèn)題。但真正明白這個(gè)問(wèn)題的人并不多，甚至知道這個(gè)問(wèn)題實(shí)質(zhì)的人都很罕見(jiàn)。本文是一篇技術(shù)科普，將重點(diǎn)提供了拜占庭將軍問(wèn)題本身對(duì)本質(zhì)及經(jīng)典算法的解析，并探討與之相關(guān)的一些問(wèn)題。筆者參考了不少文獻(xiàn)，夾雜了大量私貨，但并沒(méi)有提出解決該問(wèn)題的新算法，這也不是本文的目的。PART1：拜占庭將軍問(wèn)題是什么拜占庭將軍問(wèn)題是一個(gè)共識(shí)問(wèn)題：首先由LeslieLamport與另外兩人在1982年提出，被稱為T(mén)heByzantineGeneralsProblem或者ByzantineFailure。核心描述是軍中可能有叛徒，卻要保證進(jìn)攻一致，由此引申到計(jì)算領(lǐng)域，發(fā)展成了一種容錯(cuò)理論。隨著比特幣的出現(xiàn)和興起，這個(gè)著名問(wèn)題又重入大眾視野。拜占庭將軍問(wèn)題場(chǎng)景關(guān)于拜占庭將軍問(wèn)題，一個(gè)簡(jiǎn)易的非正式描述如下：拜占庭帝國(guó)想要進(jìn)攻一個(gè)強(qiáng)大的敵人，為此派出了10支軍隊(duì)去包圍這個(gè)敵人。這個(gè)敵人雖不比拜占庭帝國(guó)，但也足以抵御5支常規(guī)拜占庭軍隊(duì)的同時(shí)襲擊?；谝恍┰颍@10支軍隊(duì)不能集合在一起單點(diǎn)突破，必須在分開(kāi)的包圍狀態(tài)下同時(shí)攻擊。他們?nèi)我恢к婈?duì)單獨(dú)進(jìn)攻都毫無(wú)勝算，除非有至少6支軍隊(duì)同時(shí)襲擊才能攻下敵國(guó)。他們分散在敵國(guó)的四周，依靠通信兵相互通信來(lái)協(xié)商進(jìn)攻意向及進(jìn)攻時(shí)間。困擾這些將軍的問(wèn)題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進(jìn)攻意向或者進(jìn)攻時(shí)間。在這種狀態(tài)下，拜占庭將軍們能否找到一種分布式的協(xié)議來(lái)讓他們能夠遠(yuǎn)程協(xié)商，從而贏取戰(zhàn)斗？這就是著名的拜占庭將軍問(wèn)題。應(yīng)該明確的是，拜占庭將軍問(wèn)題中并不去考慮通信兵是否會(huì)被截獲或無(wú)法傳達(dá)信息等問(wèn)題，即消息傳遞的信道絕無(wú)問(wèn)。Lamport已經(jīng)證明了在消息可能丟失的不可靠信道上試圖通過(guò)消息傳遞的方式達(dá)到一致性是不可能的。所以，在研究拜占庭將軍問(wèn)題的時(shí)候，我們已經(jīng)假定了信道是沒(méi)有問(wèn)題的，并在這個(gè)前提下，去做一致性和容錯(cuò)性相關(guān)研究。如果需要考慮信道是有問(wèn)題的，這涉及到了另一個(gè)相關(guān)問(wèn)題：兩軍問(wèn)題。與拜占庭將軍相關(guān)問(wèn)題：兩軍問(wèn)題正如前文所說(shuō)，拜占庭將軍問(wèn)題和兩軍問(wèn)題實(shí)質(zhì)是不一樣的。國(guó)內(nèi)大量解釋拜占庭將軍問(wèn)題的文章將兩者混為一談，其實(shí)是混淆了兩個(gè)問(wèn)題的實(shí)質(zhì)，由此造成了許多誤解。這兩個(gè)問(wèn)題看起來(lái)的確有點(diǎn)相似，但是問(wèn)題的前提和研究方向都截然不同。（圖1：兩軍問(wèn)題圖示）如圖1所示，白軍駐扎在溝渠里，藍(lán)軍則分散在溝渠兩邊。白軍比任何一支藍(lán)軍都更為強(qiáng)大，但是藍(lán)軍若能同時(shí)合力進(jìn)攻則能夠打敗白軍。他們不能夠遠(yuǎn)程的溝通，只能派遣通信兵穿過(guò)溝渠去通知對(duì)方藍(lán)軍協(xié)商進(jìn)攻時(shí)間。是否存在一個(gè)能使藍(lán)軍必勝的通信協(xié)議，這就是兩軍問(wèn)題。看到這里您可能發(fā)現(xiàn)兩軍問(wèn)題和拜占庭將軍問(wèn)題有一定的相似性，但我們必須注意的是，通信兵得經(jīng)過(guò)敵人的溝渠，在這過(guò)程中他可能被捕，也就是說(shuō)，兩軍問(wèn)題中信道是不可靠的，并且其中沒(méi)有叛徒之說(shuō)，這就是兩軍問(wèn)題和拜占庭將軍問(wèn)題的根本性不同。由此可見(jiàn)，大量混淆了拜占庭將軍問(wèn)題和兩軍問(wèn)題的文章并沒(méi)有充分理解兩者。兩軍問(wèn)題的根本問(wèn)題在于信道的不可靠，反過(guò)來(lái)說(shuō)，如果傳遞消息的信道是可靠的，兩軍問(wèn)題可解。然而，并不存在這樣一種信道，所以兩軍問(wèn)題在經(jīng)典情境下是不可解的，為什么呢？倘若1號(hào)藍(lán)軍（簡(jiǎn)稱1）向2號(hào)藍(lán)軍（簡(jiǎn)稱2）派出了通信兵，若1要知道2是否收到了自己的信息，1必須要求2給自己傳輸一個(gè)回執(zhí)，說(shuō)“你的信息我已經(jīng)收到了，我同意你提議的明天早上10點(diǎn)9分準(zhǔn)時(shí)進(jìn)攻”。然而，就算2已經(jīng)送出了這條信息，2也不能確定1就一定會(huì)在這個(gè)時(shí)間進(jìn)攻，因?yàn)?發(fā)出的回執(zhí)1并不一定能夠收到。所以，1必須再給2發(fā)出一個(gè)回執(zhí)說(shuō)“我收到了”，但是1也不會(huì)知道2是否收到了這樣一個(gè)回執(zhí)，所以1還會(huì)期待一個(gè)2的回執(zhí)。TCP的三次握手也面臨類似問(wèn)題。雖然看似很可笑，但在這個(gè)系統(tǒng)中永遠(yuǎn)需要存在一個(gè)回執(zhí)，這對(duì)于兩方來(lái)說(shuō)都并不一定能夠達(dá)成十足的確信。更要命的是，我們還沒(méi)有考慮，通信兵的信息還有可能被篡改。由此可見(jiàn)，經(jīng)典情形下兩軍問(wèn)題是不可解的，并不存在一個(gè)能使藍(lán)軍一定勝利的通信協(xié)議。不幸的是，兩軍問(wèn)題作為現(xiàn)代通信系統(tǒng)中必須解決的問(wèn)題，我們尚不能將之完全解決，這意味著你我傳輸信息時(shí)仍然可能出現(xiàn)丟失、監(jiān)聽(tīng)或篡改的情況。但我們能不能通過(guò)一種相對(duì)可靠的方式來(lái)解決大部分情形呢？這需要談到TCP協(xié)議。事實(shí)上，搜索“兩軍問(wèn)題與三次握手”，您一定可以找到大量與TCP協(xié)議相關(guān)的內(nèi)容。若您是通信方面的專家，權(quán)當(dāng)筆者是班門(mén)弄斧，這里僅用最淺顯易懂的方式科普TCP協(xié)議的原理和局限，可能存在一些毛刺，請(qǐng)多包涵。HOSTReceiveACK(acksy+1)HOSTASendSYNReceiveSYNACK=x+USendSYNSendACK(ack=HOSTReceiveACK(acksy+1)HOSTASendSYNReceiveSYNACK=x+USendSYNSendACK(ack=y+1]ReceiveSYN(s?l=<)（圖2：TCP協(xié)議的基本原理）TCP協(xié)議中，A先向B發(fā)出一個(gè)隨機(jī)數(shù)x，B收到x了以后，發(fā)給A另一個(gè)隨機(jī)數(shù)y以及x+1作為答復(fù)，這樣A就知道B已經(jīng)收到了，因?yàn)橐平怆S機(jī)數(shù)x可能性并不大；然后A再發(fā)回y+1給B，這樣B就知道A已經(jīng)收到了。這樣，A和B之間就建立一個(gè)可靠的連接，彼此相信對(duì)方已經(jīng)收到并確認(rèn)了信息。而事實(shí)上，A并不會(huì)知道B是否收到了y+1；并且，由于信道的不可靠性，x或者y都是可能被截獲的，這些問(wèn)題說(shuō)明了即使是三次握手，也并不能夠徹底解決兩軍問(wèn)題，只是在現(xiàn)實(shí)成本可控的條件下，我們把TCP協(xié)議當(dāng)作了兩軍問(wèn)題的現(xiàn)實(shí)可解方法。（圖3：量子隱形傳態(tài)的原理圖）那么，是否能夠找到一個(gè)理論方法來(lái)真正的破解兩軍問(wèn)題呢？答案是有的，量子通訊協(xié)議，筆者并沒(méi)有能力弄清這個(gè)頗為高深的問(wèn)題。據(jù)我的理解，處于量子糾纏態(tài)的兩個(gè)粒子，無(wú)論相隔多遠(yuǎn)都能夠彼此同步，光是直觀的來(lái)看，這個(gè)效應(yīng)可以用來(lái)實(shí)現(xiàn)保密通訊。但是由于測(cè)不準(zhǔn)原理，一測(cè)量粒子狀態(tài)就會(huì)改變其狀態(tài)，所以通訊時(shí)還必須通過(guò)不可靠信道發(fā)送另一條信息。盡管這個(gè)“另一條信息”是不可靠的，但是由于已經(jīng)存在了一條絕對(duì)可靠的信道（量子糾纏），保證了另一條信道即使不可靠也能保證消息是可靠的，否則至少被竊取了一定能夠被發(fā)現(xiàn)。因此我們可以相信，至少理論上兩軍問(wèn)題是可解的，即存在一種方法，即使利用了不可靠的信道，也能保證信息傳遞的可靠性。所以，在確保了信道可靠的基礎(chǔ)上，我們可以回到拜占庭將軍問(wèn)題上繼續(xù)討論。PART2：?jiǎn)栴}實(shí)質(zhì)及形式化我們已經(jīng)了解了拜占庭將軍問(wèn)題的場(chǎng)景，并且明確了這個(gè)問(wèn)題的解決是建立在通信兵可以正確的傳達(dá)信息的基礎(chǔ)上的，即信道絕對(duì)可信。同時(shí)，通過(guò)前文對(duì)于兩軍問(wèn)題的探討，我們明白了理論上可信的信道也是可以實(shí)現(xiàn)的。接下來(lái)，我們將探討拜占庭將軍問(wèn)題的實(shí)質(zhì)。拜占庭將軍問(wèn)題實(shí)質(zhì)回顧問(wèn)題，一群將軍想要實(shí)現(xiàn)某一個(gè)目標(biāo)（一致進(jìn)攻或者一致撤退），但是單獨(dú)行動(dòng)行不通，必須合作，達(dá)成共識(shí)；由于叛徒的存在，將軍們不知道應(yīng)該如何達(dá)到一致。注意，這里“一致性”才是拜占庭將軍問(wèn)題探討的內(nèi)容，如果本來(lái)叛徒數(shù)量就已經(jīng)多到了問(wèn)題不可解的地步，這個(gè)就是“反叛”的問(wèn)題了；同時(shí)，我們的目標(biāo)是忠誠(chéng)的將軍能夠達(dá)成一致，對(duì)于這些忠誠(chéng)的將軍來(lái)說(shuō)，進(jìn)攻或者撤退都是可以的，只要他們能夠達(dá)成一致就行。但是，光靠“一致”就可以解決問(wèn)題嗎？考慮一下，如果萬(wàn)事俱備，客觀上每個(gè)忠誠(chéng)的將軍只要進(jìn)攻了就一定能夠勝利，但是卻因?yàn)榕淹降拇嬖谒麄兌肌耙恢碌摹睕](méi)有進(jìn)攻；反之，條件不利，將軍們不應(yīng)該進(jìn)攻，但是卻因?yàn)榕淹降拇嬖谒腥硕肌耙恢碌摹边M(jìn)攻了?？梢园l(fā)現(xiàn)，只有“一致性”是不足以解決拜占庭將軍問(wèn)題的，我們還需要提出一個(gè)“正確性”要求。這個(gè)要求是值得斟酌的，因?yàn)槿绻陀^來(lái)看或許會(huì)有“絕對(duì)正確的”判斷，但是針對(duì)每一個(gè)將軍，大家的判斷或許都不相同，我們?nèi)绾味x“正確”呢？我們或許可以簡(jiǎn)單地說(shuō)，正確就是每個(gè)忠誠(chéng)的將軍都正確的表達(dá)了自己的意思，不會(huì)因?yàn)榕淹阶寗e的將軍認(rèn)為忠誠(chéng)的將軍是叛徒而不采用他傳達(dá)的消息。至此，我們將拜占庭將軍問(wèn)題簡(jiǎn)化成了，所有忠誠(chéng)的將軍都能夠讓別的將軍接收到自己的真實(shí)意圖，并最終一致行動(dòng)；而形式化的要求就是，“一致性”與“正確性”。如果將問(wèn)題推廣開(kāi)來(lái)，可以發(fā)現(xiàn)針對(duì)一致性和正確性的算法并不要求命令必須是“進(jìn)攻/撤退”或是“1/0”，而可以是“發(fā)送消息1/發(fā)送消息2/待機(jī)”或“x/y/z/w"，這意味著拜占庭將軍問(wèn)題算法可以為多種分布式系統(tǒng)提供啟發(fā)，比如電力系統(tǒng)或網(wǎng)絡(luò)系統(tǒng)。由此可見(jiàn)，這個(gè)問(wèn)題說(shuō)到底是一個(gè)關(guān)于一致性和正確性的算法問(wèn)題，這個(gè)算法是針對(duì)的是忠誠(chéng)的將軍，因?yàn)榕淹娇梢宰龀鋈魏纬黾s定的判斷。我們就是要在有叛徒的干擾下，找到一個(gè)抗干擾的算法。要解決這個(gè)算法問(wèn)題，我們需要將形式化要求具體化。形式化條件的推演定義一個(gè)變量vi(為不失一般性，并不要求vi是布爾值)，作為其他將軍收到的第i個(gè)將軍的命令值；i將軍會(huì)將把自己的判斷作為vi。可以想象，由于叛徒的存在，各個(gè)將軍收到的vi值不一定是相同的。之后，定義一個(gè)函數(shù)來(lái)處理向量(v1,v2,…,vn),代表了多數(shù)人的意見(jiàn)，各將軍用這個(gè)函數(shù)的結(jié)果作為自己最終采用的命令。至此，我們可以利用這些定義來(lái)形式化這個(gè)問(wèn)題，用以匹配一致性和正確性。1)一致性條件1：每一個(gè)忠誠(chéng)的將軍必須得到相同的(v1,v2,…,vn)指令向量或者指令集合。這意味著，忠誠(chéng)的將軍并不一定使用i將軍送來(lái)的信息作為vi,i將軍也可能是叛徒。但是僅靠這個(gè)條件，忠誠(chéng)的將軍的信息送來(lái)的信息也可能被修改，這將影響到正確性。2）正確性條件2：若i將軍是忠誠(chéng)的，其他忠誠(chéng)的將軍必須以他送出的值作為vi。如此，我們得到了一致性和正確性的形式化條件（條件1和條件2），這個(gè)條件是充分條件?？紤]到正確性條件是針對(duì)單個(gè)將軍，而一致性條件是針對(duì)所有將軍的，為方便我們重寫(xiě)一致性條件為條件1,：無(wú)論i將軍是忠誠(chéng)或是叛徒，任何兩個(gè)忠誠(chéng)的將軍都使用相同的vi。條件1和條件1，是完全等價(jià)的。這是很巧妙的一步轉(zhuǎn)換，如此一致性條件（條件1,）和正確性條件（條件2）都只涉及一個(gè)將軍i如何幫別的將軍接受自己送出的值vi,所以可以將問(wèn)題改為司令-副官模式來(lái)簡(jiǎn)化問(wèn)題，即一個(gè)司令把自己的命令傳遞給n-1個(gè)副官，使得：IC1：所有忠誠(chéng)的副官遵守一個(gè)命令，即一致性。IC2：若司令是忠誠(chéng)的，每一個(gè)忠誠(chéng)的副官遵守他發(fā)出的命令，即正確性。IC1和IC2分別由條件1,和條件2演化得來(lái)。司令-副官模式只要將司令遍歷各個(gè)將軍，就可以變成完整問(wèn)題，而他們采用的算法可以是完全一致的。IC1和IC2構(gòu)成了解決拜占庭將軍問(wèn)題的充分條件，在這種模式下，司令副官的形式下達(dá)成的一致意味著司令的命令得到了有效傳達(dá)，若出現(xiàn)了異議，有異議的將軍會(huì)作為司令發(fā)起新的司令副官模式尋求自己的觀點(diǎn)表達(dá)，以協(xié)商達(dá)成一致。接下來(lái)，我們可以討論拜占庭將軍問(wèn)題的算法了，這個(gè)算法只要能夠滿足IC1和IC2,就代表這個(gè)算法可以切實(shí)有效的解決拜占庭將軍問(wèn)題。在經(jīng)典的情形下，我們可以找到兩種辦法，口頭協(xié)議和書(shū)面協(xié)議。筆者將會(huì)逐一探討兩種算法的推演和證明，其中證明部分并不會(huì)采用純推理，而以介紹證明思路為主。事實(shí)上，若完整進(jìn)行了算法推演，對(duì)算法已經(jīng)能夠有一個(gè)大致的了解?？陬^協(xié)議和書(shū)面協(xié)議會(huì)有很多不同的啟發(fā)，口頭協(xié)議的實(shí)現(xiàn)起來(lái)簡(jiǎn)單，但是算法復(fù)雜，同時(shí)需要克服的困難更多；書(shū)面協(xié)議的算法本身很簡(jiǎn)單，卻能夠克服很多問(wèn)題，但是實(shí)現(xiàn)算法并不容易。這些不同讓兩者有了不同的使用場(chǎng)景和具體實(shí)現(xiàn)。PART3：口頭協(xié)議首先，我們明確什么是口頭協(xié)議。我們將滿足以下三個(gè)條件的方式稱為口頭協(xié)議:A1：每個(gè)被發(fā)送的消息都能夠被正確的投遞A2：信息接收者知道是誰(shuí)發(fā)送的消息A3：能夠知道缺少的消息簡(jiǎn)而言之，信道絕對(duì)可信，且消息來(lái)源可知。但要注意的是，口頭協(xié)議并不會(huì)告知消息的上一個(gè)來(lái)源是誰(shuí)。先告知結(jié)論：采用口頭協(xié)議，若叛徒數(shù)少于1/3,則拜占庭將軍問(wèn)題可解。也就是說(shuō)，若叛徒數(shù)為m，當(dāng)將軍總數(shù)n至少為3m+1時(shí)，問(wèn)題可解(即滿足了IC1和IC2)。這個(gè)結(jié)論說(shuō)明了，一個(gè)三模冗余的系統(tǒng)只能容故障凍結(jié)類型的錯(cuò)誤，即一個(gè)元件故障以后就卡住不動(dòng)了(也即已知錯(cuò)誤后會(huì)出現(xiàn)的結(jié)果)，那么三模冗余是足夠的。但是對(duì)于拜占庭將軍問(wèn)題，由于叛徒可以做出各種各樣的判斷，就必須四模冗余系統(tǒng)才足夠容錯(cuò)?？陬^協(xié)議算法就是把自己的命令告訴其他人，并利用對(duì)其他人的命令取多數(shù)的方法來(lái)得到自己的結(jié)論。但要注意的是，別的將軍傳來(lái)的命令是通過(guò)算法遞歸的方法來(lái)確定的。利用這個(gè)方法，可以保證在叛徒數(shù)量少于1/3的情況下，忠誠(chéng)的將軍可以實(shí)現(xiàn)一致性和正確性要求，即問(wèn)題可解。那么，口頭協(xié)議算法又是怎么實(shí)現(xiàn)叛徒數(shù)少于1/3即可容錯(cuò)的呢？下面，筆者將介紹Lamport在其論文中提出的口頭協(xié)議OM(m)算法。筆者將會(huì)逐一介紹口頭協(xié)議算法的詳細(xì)內(nèi)容、實(shí)例推演及證明，這一部分將會(huì)需要您花一些時(shí)間來(lái)思考?？陬^協(xié)議算法OM(m)OM(0)算法(1)司令將他的命令發(fā)送給每個(gè)副官。(2)每個(gè)副官采用從司令發(fā)來(lái)的命令；如果沒(méi)有收到命令，則默認(rèn)為撤退命令。OM(m)算法(1)司令將他的命令發(fā)送給每個(gè)副官。(2)對(duì)于每個(gè)i，vi是每個(gè)副官i從司令收到的命令，如果沒(méi)有收到命令，則默認(rèn)為撤退命令。副官i在OM(m-1)中作為發(fā)令者將之發(fā)送給另外n-2個(gè)副官。(3)對(duì)于每個(gè)i,和每個(gè)j/i,vj是副官i從第2步中的副官j(使用OM(m-1)算法)發(fā)送過(guò)來(lái)的命令，如果沒(méi)有收到第2步中副官j的命令，則默認(rèn)為撤退命令。最后副官i使用majority(v1,…，vn-1)得到命令。其中，majority(v1,…,vn-1)代表了大多數(shù)人的命令，若不存在則默認(rèn)為撤退命令。要一遍讀懂這個(gè)算法并不容易，筆者也是花了不少時(shí)間研究這一小段文字才弄明白的。不過(guò)您不用擔(dān)心，筆者將會(huì)解釋幾個(gè)值得注意的點(diǎn)，并利用一個(gè)不難的實(shí)例來(lái)幫助您理解這個(gè)算法。(1)算法始終保證了一個(gè)更加安全的默認(rèn)值，這意味著若信息沒(méi)有傳到是可知的，并且傳輸時(shí)間不在考慮范圍內(nèi)。(2)這個(gè)算法是一個(gè)遞歸算法，在OM(m)中需要采用OM(m-1)得到相關(guān)結(jié)果。m代表的是叛徒數(shù)量，從m到0，意味著對(duì)于每個(gè)將軍，需要m+1輪的算法才能完成。(3)該算法是關(guān)于m的，意味著使用該算法必須知道有多少個(gè)叛徒。或者說(shuō)，利用該算法，可以保證叛徒數(shù)量在某一個(gè)最大值(即總將軍數(shù)量的1/3)之下時(shí)，拜占庭將軍問(wèn)題可解。(4)對(duì)于任意k<m，在第m-k+1步中OM(k)的vi，都是利用OM(k-1)得來(lái)的，即每個(gè)將軍將會(huì)在OM(k-1)中詢問(wèn)其他人，i將軍傳給他們的是什么，而其他人傳遞回來(lái)的信息則是利用OM(k-2)得到。這個(gè)就是遞歸的意義，若您覺(jué)得筆者表達(dá)得不甚清楚，不用擔(dān)心，您只用記住每一步都會(huì)牽涉到下面很多步驟就可以了，之后將在實(shí)例推演中明白算法的核心思路。口頭協(xié)議實(shí)例推演首先，筆者將先舉一個(gè)m=1，n=3的例子來(lái)說(shuō)明三模冗余的問(wèn)題所在，并介紹m=1，n=4的時(shí)候系統(tǒng)是怎么容錯(cuò)的，這樣您就可以明白算法是運(yùn)行的。但由于m=1的時(shí)候并沒(méi)有體現(xiàn)遞歸的過(guò)程(因?yàn)閙-1就變成了0)，筆者將再舉一個(gè)m=2,n=7的例子來(lái)說(shuō)明算法遞推的過(guò)程。(1)m=1，n=3的情形n=3,意味著一個(gè)司令發(fā)送命令給兩個(gè)副官，m=1意味著他們中有一個(gè)叛徒。首先考慮司令忠誠(chéng)而副官2是叛徒的情況。commanderretreefattackcommanderretreefattack(圖4：m=1，n=3中司令忠誠(chéng)而副官2是叛徒的情形)司令把進(jìn)攻命令傳給了兩個(gè)副官1和副官2,但是由于副官2為了不讓他們達(dá)成一致，將司令的命令改成了撤退。那對(duì)于副官1來(lái)說(shuō)，他應(yīng)該如何判斷？他無(wú)法知道是司令是叛徒還是副官2是叛徒，從而無(wú)法判斷。（圖5：m=1,n=3中司令是是叛徒的情形）而如果司令是叛徒，兩個(gè)副官忠誠(chéng)，司令會(huì)發(fā)送兩個(gè)不同的命令。當(dāng)兩個(gè)副官對(duì)照命令時(shí)，他們又凌亂了，無(wú)法判斷司令是叛徒或者對(duì)方是叛徒，從而又無(wú)法判斷。這個(gè)情形非常簡(jiǎn)易的說(shuō)明了三模冗余是無(wú)法動(dòng)態(tài)容錯(cuò)的。（2）m=1，n=4的情形n=4,意味著一個(gè)司令發(fā)送命令給三個(gè)副官，m=1意味著他們中有一個(gè)叛徒。首先考慮司令忠誠(chéng)而副官3是叛徒的情況。（圖6：m=1，n=4中司令忠誠(chéng)而副官3是叛徒的情形）倘若司令在OM（1）中給各副官發(fā)送的消息都是進(jìn)攻（A），之后OM（0）時(shí)，叛徒副官3給副官1和副官2說(shuō)他收到的消息是撤退（R）。那么對(duì)于副官1（或副官2）來(lái)說(shuō)，他綜合司令、副官3和副官2（或副官1）后得到的消息向量都將會(huì)是（A,A,R），利用majority函數(shù)之后，將會(huì)采用A，滿足了IC1和IC2（回顧IC1：所有忠誠(chéng)的副官遵守一個(gè)命令，IC2：若司令是忠誠(chéng)的，每一個(gè)忠誠(chéng)的副官遵守他發(fā)出的命令）。(圖7：m=1,n=4中司令是是叛徒的情形)倘若司令是叛徒，那么我們已經(jīng)不需要滿足IC2。為方便，我們假設(shè)叛徒司令在OM(1)會(huì)給三個(gè)副官發(fā)送的信息是(x,y,z),其中x，y，z都可以是A或R的任意一種。之后，三位忠誠(chéng)的副官將會(huì)按照OM(0)要求的那樣，交換他們收到的信息。對(duì)于副官1，他綜合司令、副官2和副官3后得到的消息向量將會(huì)是(x,y,z)，可以發(fā)現(xiàn)對(duì)于其他兩個(gè)忠實(shí)的副官，他們得到的消息向量也將是(x,y,z)。不管x，y，z如何變化，majority(x,y,z)對(duì)于三人來(lái)說(shuō)都是一樣的，所以三個(gè)副官將會(huì)采用一致的行動(dòng)。(3)m=2,n=7的情形接下來(lái)，我們將討論m=2,n=7的情形，雖然只是多了一個(gè)叛徒，但是這里會(huì)出現(xiàn)遞歸過(guò)程，所以會(huì)復(fù)雜很多。首先，我們先討論司令忠誠(chéng)的情形，假設(shè)叛徒為副官5和副官6。(圖8：m=2,n=7中司令忠誠(chéng)而副官5和副官6是叛徒的情形)在OM⑵中，司令將攻擊命令(A)傳給各個(gè)副官。在OM⑴中，忠誠(chéng)的副官們將會(huì)發(fā)送他們收到的消息(A)，但由于副官5和副官6是叛徒，他們將會(huì)發(fā)送別的信息(比如R)。這時(shí)，忠誠(chéng)的副官們將會(huì)采用使用OM(1)中的方法來(lái)確定各個(gè)v1~v6。例如，對(duì)于副官1，他收到了司令傳來(lái)的命令，他會(huì)直接采用majority函數(shù)綜合司令和其他將軍傳來(lái)的信息嗎？他不會(huì)，因?yàn)檫@還在OM⑴中，他并不知道司令是不是叛徒，他會(huì)利用詢問(wèn)別人的方式來(lái)確認(rèn)將軍的命令，但是按照算法他會(huì)把司令的命令作為v1(即v1=A)并傳給其他人。接下來(lái)他會(huì)努力取得其他的v2?v6的值，這時(shí)已經(jīng)在OM⑴中了，副官1絕不會(huì)輕易相信別人傳來(lái)的消息，比如副官2給他傳來(lái)了命令A(yù)，但是他會(huì)懷疑副官2傳來(lái)的消息，所以他用OM(1)大法，問(wèn)其他人副官2傳給了他們什么，副官3和副官4誠(chéng)實(shí)的告訴副官1，副官2給他們傳的是A，而這時(shí)副官5和副官6又要撒謊了，他們又亂說(shuō)，我們姑且假定他們傳來(lái)的是x’和y’吧。這樣，終于進(jìn)入到了OM(0)，這時(shí)副官1將會(huì)綜合其他副官對(duì)于v2的反饋，得到向量(A,A,A,x‘，y’)，再利用majority函數(shù)，得到了v2=A。如下圖，這是副官1在OM(1)中得到的信息(x，y等表示了不確定的命令)。（圖9：司令忠誠(chéng)時(shí)副官1在OM（1）中得到的信息）我們就可以得到副官1的v1~v6向量為（A,A,A,A,x,y）,利用majority函數(shù)，副官1最終采用的行動(dòng)會(huì)是A。類似的，我們可以發(fā)現(xiàn)，其他幾個(gè)忠誠(chéng)的副官得到的命令向量都會(huì)是（A,A,A,A,x,y），利用majority函數(shù)后采用的行動(dòng)都會(huì)是A。所以，我們可以發(fā)現(xiàn)忠誠(chéng)的副官采用的命令都是A（滿足IC1），并且和忠誠(chéng)的將軍的命令一致（滿足IC2）。至此，您應(yīng)該已經(jīng)明白了這個(gè)算法是怎么遞歸的，不管m等于多少，都只是一個(gè)算法步驟多寡的問(wèn)題。至于司令是叛徒的情形，其實(shí)是相似的，這里簡(jiǎn)單的再提一下便于理解。若您已經(jīng)明白了算法過(guò)程，完全可以跳過(guò)。（圖10：m=2,n=7中司令和副官6是叛徒的情形）為方便，我們假定了副官6是叛徒。司令在OM⑵中就很雞賊的給副官1?副官6發(fā)送了不同的命令（A,R,A,R,A,x）。在OM（1）中，各副官把自己收到的命令傳出去，而（為方便，假定）副官6則給其他副官分別發(fā)送了a小"小”）。類似于前文推演的那樣，考慮副官1，他將司令傳來(lái)的命令A(yù)作為v1后，還會(huì)詢問(wèn)其他人傳來(lái)的命令，由此去確認(rèn)v2?v6,類似的，我們將之表達(dá)為下圖：副即~vl=Av2v3v4v5v6副官2副官4副官5r副官6~v2~RRRRrxiv3AAAAx2v4RRRRk3v5AAAAx4v6RARAPA(圖11：司令反叛時(shí)副官1在OM(1)中得到的信息)如圖，我們就可以得到副官1的v1~v6向量為(A,R,A,R,A,A),利用majority函數(shù)，副官1最終采用的行動(dòng)會(huì)是A。類似的，我們可以發(fā)現(xiàn)忠誠(chéng)的副官1?副官5得到的消息向量都是(A,R,A,R,A,A)，最終他們采用的行動(dòng)都會(huì)是A(滿足了IC1)，而司令是叛徒不需要滿足IC2。值得提醒的是，若副官6傳遞的是(R,A,R,A,R)，那么他們所有人得到的消息向量都是(A,R,A,R,A,R)，此時(shí)A和R數(shù)量一樣多，這并不代表majority不起作用了，他將采用默認(rèn)值R(回顧前文:majority(v1,…,vn-1)代表了大多數(shù)人的命令，若不存在則默認(rèn)為撤退命令)，所有人的行動(dòng)都會(huì)采用R，這同樣是滿足的。到此為止，我們已經(jīng)將口頭算法的實(shí)例推演進(jìn)行的很徹底了，若您還有興趣，可以試一試當(dāng)n=7,m=3的時(shí)候?yàn)槭裁淳筒荒苓_(dá)成一致了，操作是類似的。3.3.口頭協(xié)議算法證明算法的證明思路其實(shí)并不復(fù)雜，簡(jiǎn)單的來(lái)說(shuō)，對(duì)于一個(gè)遞歸算法，我們使用數(shù)學(xué)歸納法來(lái)證明是最直觀而又有效的方法了。我們回顧一下命題：將軍總數(shù)為n，叛徒數(shù)量為m，OM(m)可以實(shí)現(xiàn)，在n>3m的情況下，使得：IC1：所有忠誠(chéng)的副官遵守一個(gè)命令。IC2：若司令是忠誠(chéng)的，每一個(gè)忠誠(chéng)的副官遵守他發(fā)出的命令。為了證明整個(gè)命題，我們先引入一個(gè)針對(duì)IC2的引理：引理：對(duì)于任意m和k，如果有超過(guò)2k+m個(gè)將軍和最多k個(gè)背叛者，那么算法OM(m)滿足IC2。證明：(1)m=0，而將軍是忠誠(chéng)的，直接滿足IC2；(2)m>0，此時(shí)假定OM(m-1)是有效的，那么只需要考慮OM(m)這一輪即可。n>2k+m，意味著n-1>2k，n-1是除了司令以外的所有副官，而所有副官的數(shù)量比叛徒的兩倍還多，那他們直接利用majority函數(shù)的時(shí)候，就可以直接正確得到司令的命令。可以發(fā)現(xiàn)，這個(gè)引理說(shuō)明了如果只需要考慮IC2,將軍總數(shù)是不需要3倍背叛者之多的，接下來(lái)我們回歸命題。證明：首先考慮司令是忠誠(chéng)的，令引理中的k=m，直接得到OM(m)可以滿足IC2。這時(shí)，我們只用考慮司令是叛徒的狀況。同樣利用數(shù)學(xué)歸納法。(1)m=1，之前我們已經(jīng)推演過(guò)OM⑴可以滿足1個(gè)叛徒司令，3個(gè)忠誠(chéng)副官的情況；(2)m>1，那么假設(shè)n’>3m’的情況下，OM(m-1)能夠滿足IC1和IC2。由于司令是叛徒，在OM(m)中司令會(huì)把命令發(fā)給各個(gè)副官，而這些副官中會(huì)有m-1個(gè)叛徒。在下一輪中，副官的數(shù)量至少有3m個(gè)，叛徒數(shù)為m-1，很顯然3m>3(m-1)，也就是說(shuō)n’>3m’，根據(jù)假設(shè)，OM(m-1)可以滿足IC1和IC2,盡管司令是叛徒，由于OM(m-1)是有效的，OM(m)這一輪中忠誠(chéng)的副官可以得到相同的(v1,…，vn-1)向量，所以忠誠(chéng)的副官將會(huì)利用majority函數(shù)采用相同的命令，得證?？偨Y(jié)一下，口頭協(xié)議中，我們始終要求的是相同的(v1,…,vn-1)向量，只要這個(gè)向量是相同的我們?cè)趺刺幚矶伎梢?。又由于算法是遞歸的，所以我們一定需要把這個(gè)處理方法變得通用而邏輯有效才行，所以我們才選用了majority函數(shù)這個(gè)算法。這一點(diǎn)至關(guān)重要卻又沒(méi)有這么直觀，因?yàn)槲覀兊牡谝环磻?yīng)是要得到相同的majority函數(shù)值。但是反過(guò)來(lái)一想，既然算法是遞歸的，majority函數(shù)值相同不就意味著(v1,…,vn-1)向量相同嗎？正確理解遞歸的思想是使用該算法和利用數(shù)學(xué)歸納法證明該算法的關(guān)鍵點(diǎn)。至此，我們已經(jīng)大致明確了口頭協(xié)議是怎么回事，可以做到什么不能做到什么，以及這個(gè)算法的推演和證明。很多系統(tǒng)都會(huì)出現(xiàn)口頭協(xié)議的情況，即各個(gè)系統(tǒng)節(jié)點(diǎn)可以把自己的消息準(zhǔn)確的發(fā)送出去，同時(shí)可以知道消息的來(lái)源于何處。但是，這個(gè)方法的消息并不能追本溯源，這使得在口頭協(xié)議中至少得四模冗余，我們可以試圖找到一個(gè)方法，讓消息能夠追本溯源，可以想象這能夠拓寬使用條件，這個(gè)方法可以是書(shū)面協(xié)議。PART4：書(shū)面協(xié)議口頭協(xié)議中我們討論了很多，揭示了口頭協(xié)議的缺點(diǎn)是消息不能追本溯源，這使得口頭協(xié)議必須在四模冗余的情況下才能保證正確。但是，若能引入一種方法讓消息能夠追本溯源，情況會(huì)不會(huì)有所改變呢？這就是書(shū)面協(xié)議引入的靈感。除了A1，A2和A3以外，我們?cè)诳陬^協(xié)議之上添加一個(gè)條件A4,使之成為書(shū)面協(xié)議A4：(a)簽名不可偽造，一旦被篡改即可發(fā)現(xiàn)，而叛徒的簽名可被其他叛徒偽造；(心任何人都可以驗(yàn)證簽名的可靠性。那么，我們先說(shuō)結(jié)論：對(duì)于任意m,最多只有m個(gè)背叛者情況下，算法SM（m）能解決拜占庭將軍問(wèn)題。也就是說(shuō)，在使用簽名的情況下，書(shū)面協(xié)議可以打破三模冗余的僵局，使用了簽名的情況下，只要知道了叛徒數(shù)量，我們就可以利用SM（m）算法解決拜占庭將軍問(wèn)題。書(shū)面協(xié)議算法SM（m）口頭協(xié)議算法我們已經(jīng)討論過(guò)很多了，所以筆者對(duì)書(shū)面協(xié)議盡量簡(jiǎn)短的介紹?；仡橧C1：所有忠誠(chéng)的副官遵守一個(gè)命令，即一致性。IC2：若司令是忠誠(chéng)的，每一個(gè)忠誠(chéng)的副官遵守他發(fā)出的命令，即正確性。我們要找到一個(gè)算法SM（m），不管將軍總數(shù)n和叛徒數(shù)量m，只要采用該算法，忠誠(chéng)的將軍總能達(dá)到一致（滿足IC1和IC2）。我們用集合Vi來(lái)表示i副官收到的命令集，這是一個(gè)集合，也就是滿足互異性（沒(méi)有重復(fù)的元素）等集合的條件。類似的，我們定義choice（V）函數(shù)來(lái)決定各個(gè)副官的選擇，這個(gè)函數(shù)可以有非常多種形式，他只要滿足了以下兩個(gè)條件：（1）如果集合V只包含了一個(gè)元素v，那么choice（V）=v（2）choice（o）=RETREAT，其中o是空集任何滿足了這兩個(gè)條件的函數(shù)都可以作為choice（），例如取平均值就可以。我們只需要根據(jù)具體情形定義choice（）即可，這個(gè)非重點(diǎn)，筆者并不加以討論，您可以自行思考。之后我們會(huì)發(fā)現(xiàn)SM（m）算法并不是一個(gè)遞歸算法，我們只要讓各個(gè)副官收到的V集相同，choice（V）也一定能夠得到相同的值。簡(jiǎn)單解釋該算法如下：初始化丫1=空集合。（1）將軍簽署命令并發(fā)給每個(gè)副官；（2）對(duì)于每個(gè)副官i：（A）如果副官i從發(fā)令者收到v:0的消息，且還沒(méi)有收到其他命令序列，那么他（i）使Vi為｛v｝；（ii）發(fā)送v:0:i給其他所有副官。（B）如果副官i收到了形如v:0:j1:…：jk的消息且v不在集合Vi中，那么他（i）添加v到Vi；（ii）如果k<m，那么發(fā)送v:0:j1:…：jk:i給每個(gè)不在j1,..,jk中的副官。(3)對(duì)于每個(gè)副官i,當(dāng)他不再收到任何消息，則遵守命令choive(Vi)。值得注意的是，如果司令忠誠(chéng)，由于其簽名不可偽造，所有忠誠(chéng)的副官都將得到一個(gè)單點(diǎn)集｛v｝，他們采用的命令集Vi相同，得到的choive(Vi)也為v，滿足了IC1和IC2。如果司令并非忠誠(chéng)，只需要滿足IC1，但是算法SM(m)使得所有忠誠(chéng)的副官得到相同的Vi，使用choice()函數(shù)后采用的命令也就一定相同。書(shū)面協(xié)議實(shí)例推演司令是叛徒的狀況稍難想象，舉個(gè)例子，n=3,m=1，其中司令是叛徒，這是口頭協(xié)議不能解決的狀況。（圖12：m=1，n=3中司令是叛徒的情形)很顯然，副官1得到的V1=｛A,R｝，副官2得到相同的V2=｛A,R｝。他們采用choice函數(shù)后得到的命令一定相同。相似的，n=4,m=2,其中司令是叛徒，這同樣是口頭協(xié)議不能解決的狀況。（圖13：m=2,n=4中司令和副官3是叛徒的情形）副官1和副官2得到的V1=V2={A,R}，他們采用choice函數(shù)后得到的命令也相同。即使命令不是布爾值，經(jīng)過(guò)上面的分析框架，也可以得到相似的結(jié)論。至于這個(gè)算法的證明，有興趣的讀者可以參考Lamport的原文，筆者就不做過(guò)多解釋了，如有問(wèn)題仍可與筆者聯(lián)系。Theorem2.Foranye.AlgorithmSM(m)solvestheByzantineGeneralf；Problemifthereareatmcstmtrailers.Proof.WeHistprove1C2,Ifthecommanderisloyal?thenhesendshissignedorderu:0totveiryli噂utenantingtep(l)+Everyloyallieutenantwilltherefort*receivetheorderuinstep(2)(A>.Moreover^sincenotraitorounlieuunantcanfbrgeanyothermessageoftheform』'：0,aloyallieutenantcanreceivenoadditionalorderinstepHence,foreachLoyalLieutenant%thesetV,obtainedinstep(2)coresistsofthe*ng】eorder咯whichhewillobeyinstep(3)byproperty1ofthechoicefunction.ThisprovesIC2.SinceIC】followsfromICSifthecommanderisloyal,toproveIC1weneed0nlyconsiderUihcaseinwhichtheconunanderi?atraitor.TwoloyallieutenantsiandjobeythesameorderinMep(3)i￡thesetsofordersK