如何用數學方法解決拜占庭將軍問題

1. 拜占庭問題

拜占庭帝國即中世紀的土耳其，擁有巨大的財富，周圍10個鄰邦垂誕已久，但拜占庭高牆聳立，固若金湯，沒有一個單獨的鄰邦能夠成功入侵。任何單個鄰邦入侵的都會失敗，同時也有可能自身被其他9個鄰邦入侵。拜占庭帝國防禦能力如此之強，至少要有十個鄰邦中的一半以上同時進攻，才有可能攻破。

然而，如果其中的一個或者幾個鄰邦本身答應好一起進攻，但實際過程出現背叛，那麼入侵者可能都會被殲滅。

於是每一方都小心行事，不敢輕易相信鄰國。這就是拜占庭將軍問題。

在拜占庭問題中，最重要的point就是： 所有將軍如何達成一致攻打拜占庭的共識 ，這當中，可能出現的情況舉例如下：

用一個模型解釋一下：

假設只有3個人，A、B、C，三人中如果其中一個是叛徒。當A發出進攻命令時，B如果是叛徒，他可能告訴C，他收到的是「撤退」的命令。這時C收到一個「進攻」，一個「撤退「，於是C被信息迷惑，而無所適從。

如果A是叛徒。他告訴B「進攻」，告訴C「撤退」。當C告訴B，他收到「撤退」命令時，B由於收到了司令「進攻」的命令，而無法與C保持一致。

正由於上述原因，在只有三個角色的系統中，只要有一個是叛徒，即叛徒數等於1/3，拜占庭問題便不可解。

可以看得出， 只要叛徒的數量大於或等於1/3，拜占庭問題不可解

從技術上理解， 拜占庭將軍問題是分布式系統容錯性問題 。加密貨幣建立在P2P網路之上，是典型的分布式系統，類比一下， 將軍就是P2P網路中的節點，信使就是節點之間的通信，進攻還是撤退的決定就是需要達成的共識 。 如果某台獨立的節點計算機拓機、掉線或攻擊網路搞破壞，整個系統就要停止運行，那這樣的系統將非常脆弱，所以容許部分節點出錯或搞破壞而不影響整個系統運行是必要的 ， 這就需要演算法理論上的支撐，保證分布式系統在一定量的錯誤節點存在的情況下，仍然保持一致性和可用性 。

而且，拜占庭將軍與兩軍問題不同，前者假定信差沒有問題，只是將軍出現了叛變等問題；後者研究信差的通信問題。

終極解決方案到了——

如果 10個將軍中的幾個同時發起消息，勢必會造成系統的混亂，造成各說各的攻擊時間方案，行動難以一致 。

誰都可以發起進攻的信息，但由誰來發出呢？中本聰巧妙地在個系統加入了 發送信息的成本 ，即：

它加入的 成本就是」工作量「 —— 節點必須完成一個計算工作才能向各城邦傳播消息 ，當然，誰第一個完成工作，誰才能傳播消息。（這也是 工作量證明機制的意義：以檢驗結果的方式證明你過去所做過了多少工作 ）

這種加密技術——非對稱加密，完全可以解決古代難以解決的簽名問題：

中本聰在設計比特幣時，它採用了一種工作量證明機制叫哈希現金，在一個交易塊這要找到一個隨機數，計算機只能用窮舉法來找到這個隨機數，可以說，能不能找到全靠運氣，所以對於各個節點來說，這個世界上，只有隨機才是真正的公平，實現隨機的最好辦法是使用數學，所有的將軍在尋找共識的過程，藉助了大家都認可的數學邏輯。

當然了， 憑什麼要義務進行計算工作，那麼肯定要有一個激勵機制 ：比特幣的獎勵機制是每打包一個塊，目前是獎勵25個比特幣，而拜占庭將軍問題的獎勵機制可以是瓜分拜占庭獲得的利益。

在這個分布式網路里：

每個將軍都有一份實時與其他將軍同步的消息賬本 。
賬本里有每個將軍的簽名都是可以驗證身份的。 如果有哪些消息不一致，可以知道消息不一致的是哪些將軍 。
盡管有消息不一致的，只要超過半數同意進攻，少數服從多數，共識達成（只要大多數是好人，那麼就可以實現共識）。

區塊鏈上的共識機制主要解決 由誰來構造區塊 ，以及 如何維護區塊鏈統一 的問題。

拜占庭容錯問題需要解決的也同樣是 誰來發起信息 ，如何 實現信息的統一同步 的問題。

註：區塊鏈學習新人，若有不正確的地方，望指出

2. 理論上區塊鏈怎麼解決拜占庭將軍問題

拜占庭將軍問題（以下簡稱「共識問題」）的正式表述是：如何在一個不基於信任的分布式網路中就信息達成共識？這個表述聽起來有些晦澀，但其本質並不復雜，下面的例子與共識問題雖然並不完全一致，但卻有助於我們的理解[9]。

想像一下在遙遠的拜占庭時代，有一個富饒的城邦，金銀珠寶綾羅綢緞應有盡有，它的領主哆啦A夢獨享著這一切奢華與榮耀。而在城邦的外圍，四位拜占庭將軍大雄、胖虎、小夫和靜香都覬覦著哆啦A夢的財富，於是他們決定聯手攻佔哆啦A夢的城邦。根據雙方的實力對比，必須有超過半數的將軍同時發起進攻方能克敵制勝，因此獲勝條件就是四人中至少三個人可以就進攻時間達成一致。那麼四位將軍的勝算有多少呢？

這個問題的答案就要取決於四個人的合作方式了，如果是集中式系統，有一個盟主，比如胖虎（相當於中央伺服器），那麼他們的勝利是毫無懸念的，因為就進攻時間達成一致非常簡單，只要胖虎召集大雄、小夫和靜香開個會討論一下就可以了，即使大家意見有分歧胖虎也可以在最後予以定奪。下面讓我們回到拜占庭將軍問題的假設里，在不基於信任的分布式網路中，四位將軍的勝算又如何呢？

?

首先由於四位將軍之間缺乏信任，因此聚到小黑屋裡開個密謀會的可能性被排除了（一旦在小黑屋裡被胖虎綁架了怎麼辦？）；其次由於沒有盟主，四個人的意見都會被同等的看重。在這種情況下，四位將軍只能通過信使在各自營地之間傳遞消息，來商定進攻時間了。比如大雄覺得早上6點是發動進攻的好時機，他就會派信使將自己的意見告訴胖虎、小夫和靜香，與此同時，胖虎可能認為晚上9點發動突襲更好，小夫更喜歡下午3點出擊，而靜香希望是上午10點，他們三人也會在同一時間派出自己的信使。這樣一來，在第一輪通信結束後，四位將軍每個人都有了四個可供選擇的進攻時間，他們各自要在下一輪通信中把自己選定的時間告知另外三人。由於四個人的決策都是獨立做出的，因此最終的選擇結果就有256種可能，而只有當三人以上都恰好選擇了同一時間的時候，共識才被達成，而這樣的結果才64種，也就是說達成共識的概率僅為1/4。這還只是四位將軍的情況，如果將軍的人數是10人，100人，1000人呢？我們稍加計算就可以發現隨著人數的增加，達成共識的希望會變得越來越渺茫。

把上面例子中的將軍換成計算機網路中的節點，把信使換成節點之間的通信，把進攻時間換成需要達成共識的信息，你就可以理解共識問題所描述的困境了。達成共識的能力對於一個支付系統來說重要性不言而喻，如果你給家裡匯了一筆錢買車，第二天去銀行核實的時候櫃台告訴你「關於你匯了多少錢的問題，我們的系統里有三個版本的記錄」，這樣的銀行你顯然是不敢把錢存進去的。在比特幣出現之前共識問題是很難被完美解決的，要保證達成共識就需要採用集中式系統（除非節點滿足特定條件），要想去中心化共識就無法保證。那麼區塊鏈技術又是如何解決這一難題的呢？（關注公眾號weoption，回復「區塊鏈」，可查看全文。）

3. 如何理解拜占庭將軍問題

拜占庭將軍問題（Byzantine failures），是由萊斯利·蘭伯特提出的點對點通信中的基本問題。含義是在存在消息丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。因此對一致性的研究一般假設信道是可靠的，或不存在本問題。
拜占庭位於如今的土耳其的伊斯坦布爾，是東羅馬帝國的首都。由於當時拜占庭羅馬帝國國土遼闊，為了防禦目的，因此每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳消息。 在戰爭的時候，拜占庭軍隊內所有將軍和副官必需達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，左右將軍們的決定又擾亂整體軍隊的秩序。在進行共識時，結果並不代表大多數人的意見。這時候，在已知有成員謀反的情況下，其餘忠誠的將軍在不受叛徒的影響下如何達成一致的協議，拜占庭問題就此形成。
拜占庭將軍問題是一個協議問題，拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。問題是這些將軍在地理上是分隔開來的，並且將軍中存在叛徒。叛徒可以任意行動以達到以下目標：欺騙某些將軍採取進攻行動；促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。如果叛徒達到了這些目的之一，則任何攻擊行動的結果都是註定要失敗的，只有完全達成一致的努力才能獲得勝利。
拜占庭假設是對現實世界的模型化，由於硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊，計算機和網路可能出現不可預料的行為。拜占庭容錯協議必須處理這些失效，並且這些協議還要滿足所要解決的問題要求的規范。這些演算法通常以其彈性t作為特徵，t表示演算法可以應付的錯誤進程數。
很多經典演算法問題只有在n ≥ 3t+1時才有解，如拜占庭將軍問題，其中n是系統中進程的總數。

4. 如何理解拜占庭將軍問題

-----------------[簡單理解]-----------------
因為Lamport是分布式系統祖師爺級的人物，所以我就從分布式系統的角度來說。如果要保證分布式系統一致性和可用性，就必須處理錯誤節點，防止系統出現用戶可以觀察到的錯誤。拜占庭將軍問題在我看來是提出了一個錯誤模型。即錯誤節點可以做任意事情（不受protocol限制），比如不響應、發送錯誤信息、對不同節點發送不同決定、不同錯誤節點聯合起來干壞事等等。總之就是說，沒有節點會出現比這更嚴重的錯誤。很顯然，拜占庭錯誤是overly pessimistic的模型，因為這種錯誤實際環境中比較少見。那麼為什麼要研究這個模型呢？其中最簡單的一個原因是，如果某個一致性演算法能夠保證在系統出現f個拜占庭錯誤時保持系統一致，那麼這個演算法也就能夠保證在出現f個任意其他錯誤的時候也保持系統一致。錯誤模型有上限，肯定也就有一個下限（overly optimistic，沒有比它還要弱的模型）。這個下限就是『fail-stop』模型。這個模型的假設是：當一個節點出錯，這個節點會停止運行，並且其他所有節點都知道這個節點發生了錯誤。用同樣的邏輯，如果某個一致性演算法不能保證在系統出現f個錯誤的時候保持一致，那麼這個演算法也就沒法處理其他f個任意其他問題。應用這些錯誤模型，可以對不同演算法進行比較，也可以對具體演算法的cost進行討論。

-----------------[關於演算法]-----------------
第一個提出解決拜占庭將軍問題演算法的，是Lamport於1980年發表的 Reaching agreement in the presence of faults [http://research.microsoft.com/en-us/um/people/lamport/pubs/reaching.pdf]。這篇文章描述了當出現拜占庭錯誤的節點數（f）為1時的演算法。上面匿名用戶貼的鏈接是Lamport與1982年發表的文章，其中描述了第一個能夠處理f≥1的演算法。對這個問題的下一個進展是在1999年，是由Barbara Liskov（三位女性圖靈獎獲得者之一）提出。但是，具體列出這個進展之前，需要提一下拜占庭將軍問題和FLP定理之間的關系。除了錯誤模型，系統一致性的另一個重要方面是討論在不同系統假設（通信非同步/同步，任務完成時間有沒有規定上限）下達成一致性的可能性和相應演算法/協議。由於FLP（Impossibility of Distributed Consensus with One Faulty Process）決定了在非同步+無響應上限的情況下不存在能夠mask一個節點崩潰（強於fail-stop，節點崩潰，其他節點不知情）的有效演算法。所以解決拜占庭問題的演算法都會有同步假設（或者同步保證safety，或者同步保證liveness）。

5. 拜占庭問題與共識演算法

「拜占庭將軍問題」（Byzantine Generals Problem）是一個經典難題，這個難題是這樣描述的：拜占庭是東羅馬帝國的首都，它的軍隊分成多個師，每個師都由一個將軍統領。這些將軍通過信使進行交流，來達成一個共同作戰方案，有些將軍可能是叛徒，想故意破壞這個過程，這會造成那些忠誠的將軍也無法達成一個統一的作戰計劃。這個難題在於如何讓那些忠誠的將軍在這樣的情況下達成統一作戰方案，而避免那些叛徒對作戰方案的誤導。

在點對點、分布式的區塊鏈中，常常用拜占庭問題來比喻節點如何達成共識的問題。將軍即對應著一個個節點，達成統一作戰方案即達成共識，正確的打包與驗證區塊數據，防止惡意節點（叛徒將軍）破壞區塊鏈的運行。

顧名思義，就是能夠解決拜占庭問題，使各個節點達成共識，解決共識問題的各種機制也被稱為共識演算法。在各種各樣的共識演算法中，又一直存在一個「不可能三角」的難題，這三角是指「安全性」、「去中心化」和「速度」，也就是說難以同時保證速度、安全性和去中心化程度，三者之間往往會顧此失彼。

現在各種共識演算法算起來有好幾十種，計算機界也一直處於研究階段，並沒有說哪種演算法已經完美。
下面盤點一下講解pBET和POW兩種演算法，以及它們的「安全性」、「去中心化」和「速度」如何。

實用拜占庭容錯是一種較早的共識演算法。pBFT的一個原則，就是少數服從多數。節點通過在相互傳遞有關決策的消息，誰的決策贊同的人數多，就採用誰的。所以在這個系統中，安全性隨著誠實節點的數量而增加。誠實節點同意正確的決策，拒絕惡意節點的錯誤決策，只要惡意節點的數量少於總數的1/3，就能保證達成共識。

達成共識可以簡化為四步：

pBFT 使用投票機制以循環方式選舉領導節點。
領導者發起決策並將其廣播給輔助節點。
所有節點，包括領導節點和輔助節點，都發送響應。
當 ⅔ + 1 個節點發送相同的響應時，該響應被認為是有效的。

如果領導者有惡意行為，它可以被大多數節點刪除。

按少數服從多數的原則。那按理來說，只要惡意節點的數量少於1/2就夠了啊，那麼為什麼PBFT演算法的容錯數量要滿足惡意節點的數量少於總數的1/3呢？

因為 PBFT 演算法的除了需要支持容錯故障節點之外，還需要支持容錯作惡節點。假設集群節點數為 N，有問題的節點為 f。有問題的節點中，可以既是故障節點，也可以是作惡節點，或者只是故障節點或者只是作惡節點。那麼會產生以下兩種極端情況：

（1）這f 個有問題節點既是故障節點，又是作惡節點，那麼根據少數服從多數的原則，集群里正常節點只需要比f個節點再多一個節點，即 f+1 個節點，正確節點的數量就會比故障節點數量多，那麼集群就能達成共識，即總節點數為f+(f+1)=n，也就是說這種情況支持的最大容錯節點數量是 (n-1)/2。
（2）故障節點和作惡節點都是不同的節點。那麼就會有 f 個作惡節點和 f 個故障節點，當發現節點是作惡節點後，會被集群排除在外，剩下 f 個故障節點，那麼根據少數服從多數的原則，集群里正常節點只需要比f個節點再多一個節點，即 f+1 個節點，確節點的數量就會比故障節點數量多，那麼集群就能達成共識。所以，所有類型的節點數量加起來就是 f+1 個正常節點，f個故障節點和f個作惡節點，即 3f+1=n。

結合上述兩種情況，因此PBFT演算法支持的最大容錯節點數量是(n-1)/3，即少於1/3。

pBFT的優缺點
pBFT 系統不需要高計算資源或大量能源來運行。pBFT 在節點少的時候可以快速達成共識，因為所有節點都在不斷地相互通信。一旦節點就決策達成一致，交易就完成了。

然而，pBFT的缺點也很明顯：頻繁的通信使它只能在節點數量有限的網路中正常工作。隨著每個新節點加入網路，通信開銷呈指數增長，響應所需的時間也隨之增加。

pBFT 網路也容易受到女巫(Sybil)攻擊，女巫就是惡意黑客製造的不同節點，黑客可以控制多個節點，使其超過1/3，那系統將無法達成正確的共識。

從不可能三角的角度來看，由此可見pBFT在節點少的時候速度快，但安全性差，去中心化低；節點多了又會導致速度很慢。

中本聰設計了POW共識機制來解決上面pBFT這個經典共識的可擴展性問題。

上面說到，pBFT通過不斷廣播然後計算節點的消息數，時間花費過長。POW是怎麼做的：我不要計算節點數是否超過2/3，我直接選一個節點，按它的決策，其他節點全部同步它的決策。這樣就省去在全節點通信然後計算節點數的費時操作。

那麼，對於哪個節點來打包區塊，那就很重要，萬一是惡意節點呢？必須對打包的節點進行要求，哪個節點有權力進行打包呢？那就是解決復雜的數學問題，俗稱挖kuang。節點必須花費大量算力和電費來爭取某次打包區塊的權力。這樣的成本就限制了黑客的女巫攻擊。

如果打包區塊的權力真的被黑客搶到了，那可能會有什麼問題？

（1）竊取冰糖橙
黑客能夠竊取屬於另一個用戶，不受她控制的地址里的冰糖橙嗎？答案是否定的。即使這一輪是由黑客打包區塊鏈上的下一個區塊，她也不可能竊取別人的比特幣。這么做的話，黑客需要發起一筆有效的交易來轉移比特幣到自己的地址。這就要求黑客偽造比特幣擁有者的簽名，然而如果數字簽名機制是安全的，她是無法辦到的。只要背後的密碼學基礎是牢靠的，她就無法輕易竊取比特幣。
（2）拒絕服務攻擊
讓我們來考慮另一種攻擊。假設黑客不喜歡叫鮑勃的某個用戶，黑客可以決定她不把鮑勃發起的任何交易放進她所提議的區塊里。換言之，她拒絕提供服務給鮑勃。盡管這是黑客可以開展的有效的攻擊，但幸好這不過是個小問題。如果鮑勃的交易沒有被放進黑客所打包的下一個區塊，鮑勃只要等到下一個誠實節點發起區塊的時候，他的交易記錄就會被放進這個區塊里。所以這其實也不算是一個有效的攻擊。

也就是說，黑客花費重大成本取得的打包，但並不能起到有效的攻擊。由於對惡意節點進行懲罰、對誠實節點進行獎勵這樣的機制下，共識就達成了。

盡管有所改進，POW也引入了其他問題。工作量證明需要所有節點解決復雜的數學問題，這會消耗大量的能源，就是大家所熟知的挖kuang耗費電力。並且解決復雜的數學問題的時間也要求不短，10分鍾左右。

從不可能三角的角度來看，POW去中心化高，安全性高，但速度還是慢，但至少已經不會像pBFT那樣由於節點多導致花費時間呈指數增長。

共識演算法各式各樣，冰糖橙的POW並不是真正去解決分布式共識問題，它不能完美的套用到其他場景。但它在貨幣系統的這個特定場景下解決了冰糖橙的共識問題。POW在冰糖橙里運行得非常好。

6. 拜占庭將軍問題的解決演算法

拜占庭問題的最初描述是：n 個將軍被分隔在不同的地方，忠誠的將軍希望通過某種協議達成某個命令的一致（比如一起進攻或者一起後退）。但其中一些背叛的將軍會通過發送錯誤的消息阻撓忠誠的將軍達成命令上的一致。Lamport 證明了在將軍總數大於3m ，背叛者為m 或者更少時，忠誠的將軍可以達成命令上的一致。
為了保證上面的需求，必須滿足下面兩個條件：
1. 每兩個忠誠的將軍必須收到相同的值 v(i)（v(i)是第i 個將軍的命令）
2. 如果第i 個將軍是忠誠的，那麼他發送的命令和每個忠誠將軍收到的v(i)相同
為了簡化以上模型，我們使用一個將軍發送命令給多個副官的形式來證明，發送命令的將軍稱為發令者，接收命令的將軍為副官，那麼上面的兩個條件可以表述為：
IC1. 所有忠誠的副官遵守相同的命令
IC2. 如果發出命令的將軍是忠誠的，那麼所有忠誠的副官遵守司令（發出命令的將軍）的命令
特別提示：發送命令的每次只有一個將軍，將其命令發送給n-1 個副官。m 代表叛國者的個數，因為將軍總數為n，所以副官總數為n-1 個。IC2 中副官遵守實際上是指忠誠的將軍能夠正確收到忠誠將軍的命令消息。 通過口頭消息傳遞達到一致，如果有m 個叛國將軍，則將軍們的總數必須為3m+1 個以上。下面是口頭消息傳遞過程中默認的一些條件：
A1. 每個被發送的消息都能夠被正確的投遞
A2. 信息接收者知道是誰發送的消息
A3. 能夠知道缺少的消息
A1 和A2 假設了兩個將軍之間通信沒有干擾，既不會有背叛者阻礙消息的發送（截斷）也不會有背叛者偽造消息的情況（偽造）。即是每個將軍都可以無誤地將自己的消息發送給其他每個將軍。（下一節中可以不需要這個必要條件）
我們定義口頭消息演算法OM(m) 。對於所有的非負整數m ，每個發令者通過OM(M) 演算法發送命令給n-1 個副官。下面將說明OM(m) 演算法在最多有m 個背叛者且總將軍數為3m+1 或者更多的情況下可以解決拜占庭將軍問題。（考慮到網路應用實際環境，原文使用了收到值代替收到命令，本文不做修改）
演算法定義一個函數：majority(com1,com2,…,comn)等於多數派命令。
OM(0)演算法
（1）發令者將他的命令發送給每個副官。
（2）每個副官採用他從發令者得到的命令，或者默認使用撤退命令，如果沒有收到任何命令。
OM(m)演算法
（1）發令者將他的命令發送給每個副官。
（2）對於每個i ，vi 是每個副官i 從發令者收到的命令，如果沒有收到命令則為撤退命令。副官i 在OM(m-1) 中作為發令者將vi 發送給另外n-2 個副官。
（3）對於每個i，並且j eq i，vj 是副官i 從第（2）步中的副官j 發送過來的命令（使用OM(m-1)演算法），如果沒有收到第（2）步中的副官j 的命令則默認為撤退命令。最後副官i 使用majority(v1,…,vn-1)得到命令。
接下來實際的考慮一個n=4，m=1 的情況：
1. 當副官D是背叛者
第一步發令者A執行演算法OM(1)將自己的命令發送給三個副官B，C，D，三個副官都正確地收到了命令。
第二步每個收到命令的副官都作為發令者執行演算法OM(0)，將自己收到的命令轉發給其餘副官，因為副官D是背叛者，所以他給副官B和C傳遞的消息可能會是假消息。副官B和C分別根據majority 函數來決定命令。
這樣背叛的副官D 同理也干擾不了發令者的決定。下面看看如果發令者是背叛者。
2. 發令者是背叛者，其餘副官為忠誠的
第一步：發令者A向副官B，C，D發送了不同的命令，實際情況中是一個攻擊者向不同方發送了不一致的值（例如，0或1）企圖擾亂副官做出一致決定。
第二步：副官收到命令後，搖身一變為發令者執行OM(0) 向所有的副官發送命令，每個副官通過多數表決演算法仍可以達成一致的命令。
文章接著就證明了OM(m)演算法對任意m 都是可以滿足，首先引入一個引理（歸納法證明）：
引理1：對於任意m 和k ，如果有超過2k+m 個將軍和最多k 個背叛者，那麼演算法OM(m) 滿足IC2 （回顧下IC2 指的是，如果將軍是忠誠的，所有的副官遵守將軍命令）。
證明：當m=0 的時候，OM(0) 在將軍是忠誠的時候滿足IC2。當m>0 時，首先將軍將命令傳遞給 n-1 個副官，然後每個副官對n-1 個將軍執行OM(m-1) 演算法。因為假設了n>2k+m（引理中有將軍數大於2k+m），所以 n-1 > 2k+(m-1) >= 2k（即每一輪中副官總數不小於背叛者的兩倍），這樣每輪OM(m-k) 演算法中忠誠的副官收到的命令都是majority(v1,v2,...,v(n-1))，其中忠誠副官發送的命令大於或者等於一半。
接著解決拜占庭將軍問題。
定理1：對於任意m，如果有超過3m 個將軍和最多m 個背叛者，演算法OM(m) 滿足條件IC1 和條件IC2。
證明：通過m 的歸納法證明，我們通過假設OM(m-1) 成立來證明OM(m) m>0。首先考慮發送命令的將軍是忠誠的。那麼將引理中k 設為m 則OM(m) 滿足IC2 ，IC1 在發令將軍是忠誠的情況下也滿足。
接著考慮m 個背叛者中有一個是發令者，那最多就只有m-1 個副官是背叛者了，又因為有3m 個將軍，所以副官的總數超過3m-1，且有3m-1>3(m-1) 。因此通過歸納法假設 OM(m-1) 滿足IC1 和IC2（最多3(m-1) 個將軍和最多m-1 個背叛者）。那麼任意兩個忠誠的副官j 在OM(m-1) 獲得相同命令vj，那麼在OM(m) 演算法中每個忠誠的副官都會收到(v1,v2,...,v(n-1))，可知滿足條件IC1 和IC2。
看完這段證明其實我也挺糊塗的~~~~，畫了張圖來看看lamport 是怎麼證明的：
簽名消息在除了滿足口頭消息A1-A3 三點要求外還應該滿足下面A4：
A4 （a）簽名不可被偽造，一旦被篡改即可發現
（b）任何人都可以驗證將軍簽名的可靠性
下面定義一個類似於上面majority() 函數的choice() 來決定副官的選擇：1.當集合V 只包含了一個元素v ，那麼choice(V)=v ；2. choice(o)=RETREAT。
有了上面A4 和choice() 基礎我們給出SM(m) 方法：
SM(m) 演算法
初始化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)
演算法的幾點說明：
演算法第三步並沒有說明副官如何判斷沒有新的消息，可以通過兩個解決方法：一是要求每個副官收到消息後要麼簽名轉發該消息，要麼發送一個通知他將不發送這個消息；二是設置一個超時時間，如果在該時間段還沒有收到消息，則認為不再收到消息。
演算法SM(m) 中，讓副官簽名是確認其收到了該消息（有點像來了份文件給每個領導批閱）。在SM(1) 中副官收到消息就不用簽字了，因為不用轉發給其他副官。
定理2：對於任意m，最多隻有m 個背叛者情況下，演算法SM(m) 解決拜占庭將軍問題
Proof：首先證明IC2，如果發令者是忠誠的，那麼所有的副官一定收到相同的命令，因為簽名無法篡改，且IC1 也就滿足了。證明IC1 只用考慮發令者是背叛者的情況（重新回顧下IC1 是指所有忠誠的副官執行相同的命令），IC1 要求兩個忠誠的副官（i，j）必須收到相同的命令集合Vi、Vj，也就是Vi 中每個v 都在Vj 中。會存在兩種情況，其一當副官i 收到v 命令的序列後，加入到Vi，並將其發送給副官j ，j 將命令v 保存；其二副官i 收到命令v:0:j1:...:jk:i，其中有jr=j，所以 由A4 可知副官j 也收到了該命令。如果沒有，則有：
k<m。這種情況下，i 發送信息v:0:j1:...:jk:i 給副官j ，那麼j 一定收到v 。（這點感覺和上面有重復）
k=m。發令者是背叛者，最多隻有m-1 個副官是背叛者。因此，最少有一個序列j1,...,jm是忠誠的。那麼j 一定收到這個忠誠的副官序列發來的值v ，所以副官j 收到v 。
證明完畢。

7. 實用拜占庭容錯演算法（PBFT）

       拜占庭帝國即東羅馬帝國，擁有巨大的財富，並對鄰邦垂誕已久，為此派出了10支軍隊去包圍這個敵人。這個敵人雖不比拜占庭帝國，但也足以抵禦5支常規拜占庭軍隊的同時襲擊。基於一些原因，這10支軍隊不能集合在一起單點突破，必須在分開的包圍狀態下同時攻擊。他們任一支軍隊單獨進攻都毫無勝算，除非有至少6支軍隊同時襲擊才能攻下敵國。他們分散在敵國的四周，依靠通信兵相互通信來協商進攻意向及進攻時間。困擾這些將軍的問題是，他們不確定他們中是否有叛徒，叛徒可能擅自變更進攻意向或者進攻時間。在這種狀態下，拜占庭將軍們能否找到一種分布式的協議來讓他們能夠遠程協商，從而贏取戰斗？這就是著名的拜占庭將軍問題【在分布式系統中指的是消息不僅可以被丟失、延遲、重放，還可以被偽造】。

        PBFT(Practical Byzantine Fault Tolerance)演算法由Miguel Castro 和Barbara Liskov在1999年提出來的，解決了原始拜占庭容錯演算法效率不高的問題，將演算法復雜度由指數級降低到多項式級，使得拜占庭容錯演算法在實際系統應用中變得可行。

        PBFT是一種狀態機副本復制演算法，一般包括三種協議:一致性協議(agreement)、檢查點協議(checkpoint)和視圖更換協議(view change)。該演算法要滿足以下兩個性質：   

        安全性(safety)：safety means nothing bad happens.                                                        活性(liveness)：liveness means that something good eventually happens.

        在一個拜占庭系統裡面，要容忍f個拜占庭節點錯誤，則replica數量至少為3f+1，這是滿足安全性的前提。因為網路延遲或宕機，系統存在f個節點不回復響應（f個節點包括拜占庭節點和非拜占庭節點，最壞情況f個節點全是非拜占庭節點），剩下2f+1個響應中可能有f個拜占庭節點，從而得到n-2f>f，即響應中非拜占庭節點數目大於拜占庭節點數目（f+1>f）。

        演算法不依賴同步提供安全性，則必須依賴同步提供活性，否則違背FLP定理(在非同步通信場景，即使只有一個進程失敗了，沒有任何演算法能保證非失敗進程能夠達到一致性)。在拜占庭節點不超過f，並且delay(t)有界的情況下就能保證系統活性，delay(t)表示從消息發送到接受的時間間隔。

        在一個view裡面，會從replicas中選擇一個primary，其餘的replicas則叫backups。如果主節點行為發生異常，則進行view change換主。                                  

       游戲從client向primary發送請求 開始。 狀態機操作， 時戳。                                                                                                                                       游戲從client至少收到f+1個replicas的響應 結束。 視圖編號， 時戳， 客戶端身份， replica編號， 請求結果。【why f+1？因為在2f+1個committed中有f個拜占庭節點表面上同意請求，實際上根本不會回復請求】

3.1 重彩大戲------三階段協議

Pre-prepare:

        Primary為客戶端請求分配一個序列號n，向所有backups發現預准備消息 。 視圖編號， 消息 的摘要。

Prepare:

        若滿足以下條件，backups接受預准備消息：                                                                    1.客戶端請求和預准備消息具有正確簽名。                                                                        2.當前視圖編號是v。                                                                                                          3.backups從未在當前視圖v接收過序列號為n但摘要不同的預准備請求。                          4.h<n<H。【防止一個拜占庭節點選擇一個大的序號來消耗序號空間】

        如果上述條件滿足，backups接收預准備消息，進入prepare階段，向其他節點廣播准備消息 ，並將預准備和准備消息寫入日誌。

commit:

       如果backups收到2f【包括自己】個與預准備消息一致的准備消息，請求消息和預准備消息具有相同的視圖v和序列號n，並且已將相關消息寫入日誌，則進入commit階段，向其他節點廣播一條確認消息 。如果各節點收到2f+1條相同的commits消息，則向客戶端發送一條reply消息。

3.2 垃圾回收

      PBFT是一種狀態機副本復制演算法，replicas會將執行過消息記錄在本地日誌中，為了節省內存，需要一種機制來清理日誌。何時來清理？在每次操作完後執行是不明智的，因為比較耗資源。可以定期清理，比如每100次清理一次。我們將請求後執行的狀態稱為檢查點checkpoint；帶證明的檢查點稱為stable certificate，當節點收到2f+1個checkpoint消息時，可證明穩定檢查點是正確的。穩定檢查點之前的日誌消息均可刪除。                       

      當清理檢查點時replica i向其他replicas廣播一條檢查點協議 ， 是最近一次正確執行請求序號， 是其當前狀態摘要。如果每一個replica收到2f+1個具有相同序號 和摘要 的檢查點消息，這時每一個replica可以清理序列號 小於等於n的日誌信息。

       檢查點協議也用來更新水平線。低水平線 等於最近穩定檢查點的序號，高水平線 ， 為日誌大小。

3.3 視圖更改

        當主節點掛掉，或者在commit階段有些節點收到2f+1個commit，有些沒有收到2f+1個commit，導致狀態不一致，這些狀況都需要更改視圖來提供系統活性和安全性。

        當請求超時，備份節點進入視圖v+1，廣播視圖更改消息 。 穩定檢查點序列號， 是穩定檢查點證明， 是一個集合，包含對請求 （請求的序列號大於 ）相關消息集合 。 包含2f+1個相同的准備消息。

         當視圖v+1的主節點收到2f個相同個視圖更改消息，向其他副本廣播新視圖消息 ， 是2f+1個視圖更改消息， 的計算規則如下：        1.確定序列號 和 。其中 等於 中穩定檢查點序列號, 等於 中最大prepare消息序列號。                                                                                                  2.主節點為 和 之間的每一個序列號n分配pre-prepare消息。如果 中包含n對應的 組合，則對應的預准備消息為 （也就是說序列號n對應的請求有2f+1個prepare消息，在新視圖中依然提交這個請求）。如果 中不包含n對應的 組合，則提交null消息為 ，即不做任何處理。

        副本收到新視圖消息後，廣播一次prepare消息，進入v+1，視圖更換完成。

8. 易理解的拜占庭將軍問題——深入剖析

拜占庭將軍問題和兩軍問題實質是不一樣的，不能混為一談。其中兩軍問題如下圖所示：

兩軍問題描述：

和拜占庭將軍問題有一定的相似性也有不同之處，所以我們必須注意的是：

兩軍問題的根本問題在於信道的不可靠，也就是信號做不到真正的同步，那麼想要做到真正的同步唯一的辦法就是量子通信——畢竟遇事不決量子搞定:

到底是一個關於一致性和正確性的演算法問題。針對的是忠誠的將軍，因為叛徒可以做出任何超出約定的判斷。我們就是要在有叛徒的干擾下，找到一個抗干擾的演算法。

類似TCP/IP的三次握手，我們也同樣的是採用容錯機制，通過限制一部分條件最後使得在有叛徒的情況下依然能夠得到信息的真實性。

失效說明：

滿足以下三個條件的方式稱為口頭協議：

對於正整數 和 ，當圖 是 -正則的是，定義演算法 OM(m, p) ：

在演算法中，司令官發送一個簽名的命令給他的每個副官。然後，每個副官添加他的簽名到命令上，並發送給其他副官，收到命令的副官再添加他的簽名發送給其他副官......

演算法還假定了一個 choice 函數，作用在一個命令的集合上來獲得一個單獨的命令。 choice 函數需要滿足：

例如， choince 函數可以是取有序集合 的中位數。

令 指由將軍 簽名的命令值 ， 指命令指 由將軍 簽名後再由將軍 簽名。令將軍 為司令官，每個副官 維護一個命令集 ，包含他收到的被正確簽名的命令值。(如果司令官是忠誠的，這個值集的元素不會超過一個)。

書面協議的結論非常令人興奮，這不是解決了拜占庭將軍問題了嗎？但請注意我們在A1~A4中實際上是添加了一些條件的，這使得拜占庭將軍問題在這些假設下能夠解決，但是在實際狀況中卻會有一些問題。觀察A1-A4，我們做了一些在現實中比較難以完成的假設，比如：

9. 共識演算法：Raft

上篇講到了「拜占庭將軍問題」：多個拜占庭將軍要如何在可能有叛徒、信使可能被策反或者暗殺的情況下達成是否要進攻的一致性決定？還不了解的先看看上一篇 《拜占庭將軍問題》 。這篇主要是介紹簡化版拜占庭將軍問題的解決方案：Raft 共識演算法。

所以將拜占庭將軍問題根據常見的工作上的問題進行簡化： 假設將軍中沒有叛軍，信使的信息可靠但有可能被暗殺的情況下，將軍們如何達成一致性決定？

對於這個簡化後的問題，有許多解決方案，第一個被證明的共識演算法是 Paxos，由拜占庭將軍問題的作者 Leslie Lamport 在1990年提出，最初以論文難懂而出名，後來這哥們在2001重新發了一篇簡單版的論文 Paxos Made Simple ，然而還是挺難懂的。

因為 Paxos 難懂，難實現，所以斯坦福大學的教授在2014年發表了新的分布式協議 Raft。與 Paxos 相比，Raft 有著基本相同運行效率，但是更容易理解，也更容易被用在系統開發上。

我們還是用拜占庭將軍的例子來幫助理解 Raft。

Raft 的解決方案大概可以理解成 先在所有將軍中選出一個大將軍，所有的決定由大將軍來做。 選舉環節 ：比如說現在一共有3個將軍 A, B, C，每個將軍都有一個 隨機時間 的倒計時器，倒計時一結束，這個將軍就會把自己當成大將軍候選人，然後派信使去問其他幾個將軍，能不能選我為總將軍？假設現在將軍A倒計時結束了，他派信使傳遞選舉投票的信息給將軍B和C，如果將軍B和C還沒把自己當成候選人（倒計時還沒有結束），並且沒有把選舉票投給其他，他們把票投給將軍A，信使在回到將軍A時，將軍A知道自己收到了足夠的票數，成為了大將軍。在這之後，是否要進攻就由大將軍決定，然後派信使去通知另外兩個將軍，如果在一段時間後還沒有收到回復（可能信使被暗殺），那就再重派一個信使，直到收到回復。

故事先講到這里，希望不做技術方面的朋友可以大概能理解 Raft 的原理，下面從比較技術的角度講講 Raft 的原理。

從拜占庭將軍的故事映射到分布式系統上，每個將軍相當於一個分布式網路節點，每個節點有 三種狀態：Follower，Candidate，Leader ，狀態之間是互相轉換的，可以參考下圖，具體的後面說。

每個節點上都有一個倒計時器 (Election Timeout)，時間隨機在 150ms 到 300ms 之間。有幾種情況會重設 Timeout：

在 Raft 運行過程中，最主要進行兩個活動：

假設現在有如圖5個節點，5個節點一開始的狀態都是 Follower。

在一個節點倒計時結束 (Timeout) 後，這個節點的狀態變成 Candidate 開始選舉，它給其他幾個節點發送選舉請求 (RequestVote)

其他四個節點都返回成功，這個節點的狀態由 Candidate 變成了 Leader，並在每個一小段時間後，就給所有的 Follower 發送一個 Heartbeat 以保持所有節點的狀態，Follower 收到 Leader 的 Heartbeat 後重設 Timeout。

這是最簡單的選主情況， 只要有超過一半的節點投支持票了，Candidate 才會被選舉為 Leader ，5個節點的情況下，3個節點 (包括 Candidate 本身) 投了支持就行。

一開始已經有一個 Leader，所有節點正常運行。

Leader 出故障掛掉了，其他四個 Follower 將進行重新選主。

4個節點的選主過程和5個節點的類似，在選出一個新的 Leader 後，原來的 Leader 恢復了又重新加入了，這個時候怎麼處理？在 Raft 里，第幾輪選舉是有記錄的，重新加入的 Leader 是第一輪選舉 (Term 1) 選出來的，而現在的 Leader 則是 Term 2，所有原來的 Leader 會自覺降級為 Follower

假設一開始有4個節點，都還是 Follower。

有兩個 Follower 同時 Timeout，都變成了 Candidate 開始選舉，分別給一個 Follower 發送了投票請求。

兩個 Follower 分別返回了ok，這時兩個 Candidate 都只有2票，要3票才能被選成 Leader。

兩個 Candidate 會分別給另外一個還沒有給自己投票的 Follower 發送投票請求。

但是因為 Follower 在這一輪選舉中，都已經投完票了，所以都拒絕了他們的請求。所以在 Term 2 沒有 Leader 被選出來。

這時，兩個節點的狀態是 Candidate，兩個是 Follower，但是他們的倒計時器仍然在運行，最先 Timeout 的那個節點會進行發起新一輪 Term 3 的投票。

兩個 Follower 在 Term 3 還沒投過票，所以返回 OK，這時 Candidate 一共有三票，被選為了 Leader。

如果 Leader Heartbeat 的時間晚於另外一個 Candidate timeout 的時間，另外一個 Candidate 仍然會發送選舉請求。

兩個 Follower 已經投完票了，拒絕了這個 Candidate 的投票請求。

Leader 進行 Heartbeat， Candidate 收到後狀態自動轉為 Follower，完成選主。

以上是 Raft 最重要活動之一選主的介紹，以及在不同情況下如何進行選主。

Raft 在實際應用場景中的一致性更多的是體現在不同節點之間的數據一致性，客戶端發送請求到任何一個節點都能收到一致的返回，當一個節點出故障後，其他節點仍然能以已有的數據正常進行。在選主之後的復制日誌就是為了達到這個目的。

一開始，Leader 和 兩個 Follower 都沒有任何數據。

客戶端發送請求給 Leader，儲存數據 「sally」，Leader 先將數據寫在本地日誌，這時候數據還是 Uncommitted (還沒最終確認，紅色表示)

Leader 給兩個 Follower 發送 AppendEntries 請求，數據在 Follower 上沒有沖突，則將數據暫時寫在本地日誌，Follower 的數據也還是 Uncommitted。

Follower 將數據寫到本地後，返回 OK。Leader 收到後成功返回， 只要收到的成功的返回數量超過半數 (包含Leader) ，Leader 將數據 「sally」 的狀態改成 Committed。( 這個時候 Leader 就可以返回給客戶端了)

Leader 再次給 Follower 發送 AppendEntries 請求，收到請求後，Follower 將本地日誌里 Uncommitted 數據改成 Committed。這樣就完成了一整個復制日誌的過程，三個節點的數據是一致的，

在 Network Partition 的情況下，部分節點之間沒辦法互相通信，Raft 也能保證在這種情況下數據的一致性。

一開始有 5 個節點處於同一網路狀態下。

Network Partition 將節點分成兩邊，一邊有兩個節點，一邊三個節點。

兩個節點這邊已經有 Leader 了，來自客戶端的數據 「bob」 通過 Leader 同步到 Follower。

因為只有兩個節點，少於3個節點，所以 「bob」 的狀態仍是 Uncommitted。所以在這里， 伺服器會返回錯誤給客戶端

另外一個 Partition 有三個節點，進行重新選主。客戶端數據 「tom」 發到新的 Leader，通過和上節網路狀態下相似的過程，同步到另外兩個 Follower。

因為這個 Partition 有3個節點，超過半數，所以數據 「tom」 都 Commit 了。

網路狀態恢復，5個節點再次處於同一個網路狀態下。但是這里出現了數據沖突 「bob" 和 「tom"

三個節點的 Leader 廣播 AppendEntries

兩個節點 Partition 的 Leader 自動降級為 Follower，因為這個 Partition 的數據 「bob」 沒有 Commit，返回給客戶端的是錯誤，客戶端知道請求沒有成功，所以 Follower 在收到 AppendEntries 請求時，可以把 「bob「 刪除，然後同步 」tom」，通過這么一個過程，就完成了在 Network Partition 情況下的復制日誌，保證了數據的一致性。

Raft 是能夠實現分布式系統強一致性的演算法，每個系統節點有三種狀態 Follower，Candidate，Leader。實現 Raft 演算法兩個最重要的事是：選主和復制日誌

參考鏈接：
Raft 官網： https://raft.github.io/

Raft 原理動畫 (推薦看看)： http://thesecretlivesofdata.com/raft/

（本來不想一個個圖片粘，但是在國內時候訪問不了這個鏈接，乾脆就復述了一遍整個過程。）