拜占庭概述

首先來說說，什么是拜占庭？

拜占庭即拜占庭帝國，又稱東羅馬帝國，首都位于如今土耳其的伊斯坦布爾，如上圖可以看到，當時的拜占庭帝國國土遼闊，橫跨亞、歐、非大陸，環抱地中海，

拜占庭將軍問題

在那個冷兵器時代，為了征服與反征服，在如此遼闊的疆域不同地方經常駐守著由成百上千個將軍領導的軍隊，如上圖，

• 拜占庭帝國的軍隊要面臨的現實問題是，如何在廣闊的疆域內實作所有軍隊的統一調度、訊息互動，在那個冷兵器時代，訊息指令的傳遞只能依靠通信士兵人為進行傳遞，
• 而因此正由于是人為傳遞訊息，若通信士兵在傳遞途中因暴病、天氣、地理等各種原因沒有及時傳遞訊息，再或者進行了叛變，故意不將訊息傳遞或將統一發號的命令進行虛假篡改，那么將軍們得到的指令會大相徑庭，行動得不到統一保證，因此傳遞訊息的信道是不可靠的，因此導致出現行動執行的一致性問題，

綜上，便是拜占庭將軍問題，

拜占庭將軍問題，實質上是一致性問題，是不同個體（將軍）之間在分布式環境（遼闊疆域）中通過不可靠信道（通信士兵）接收訊息（命令）后采取一致性行動的問題，

分布式領域中“拜占庭將軍問題”

拜占庭將軍問題，其實是一個現實存在的共性問題，只要場景和條件成立便可以認為它是某個領域的拜占庭將軍問題，是一個廣泛問題的現實子集而已，

我們把這個問題延伸到計算機和互聯網領域的話，分布式已經是互聯網中常見的服務部署方案，由于硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊，計算機和網路可能出現不可預料的行為，這和拜占庭將軍問題產生場景和條件是相仿的，

據此，萊斯利·蘭伯特（Leslie Lamport）等提出了著名的拜占庭將軍問題（Byzantine Failures） 來論述分布式環境下點對點通信時在存在訊息丟失的不可靠信道上試圖通過訊息傳遞的方式達到一致性是較為困難的，

萊斯利·蘭伯特（Leslie Lamport）也是著名的Paxos一致性演算法的作者，關于本系列分布式介紹后續的Raft一致性演算法也是在改進Paxos的初衷進行設計的，這里簡單了解下概念相關性線索軌跡，感興趣可以繼續閱讀本篇后續文章，

這里將現實場景的拜占庭帝國和分布式服務做下對比，如下：

問題核心剖析

問題核心

分布式環境/服務中拜占庭將軍問題要解決的核心問題是：如何在缺少可信任的中央節點和可信任的通道的情況下，分布在網路中的各個節點應如何達成共識的一致性問題， 這是分布式服務中首要解決的議題，它也是其他所有問題的基礎和根本保證，

問題分析

這里嘗試剖析問題本質需要從現象到本質一層層剖析根源，這里個人認為是首先有分布式環境的客觀現實導致服務集群的節點分散，當我們充分利用和享受分布式帶來的優勢后也需要面臨和解決海量節點個體統一協調、指揮的一致性問題，而無論是讓統一的控制中心下發指令還是讓節點之間互相協商都必須經歷訊息互動才能實作通信彼此了解對方和外部環境的最新狀態資訊，而承載互動的可能的最小承載因子是資訊，因此我們試著從根源開始剖析！

根據克勞德·艾爾伍德·香農（Claude Elwood Shannon）提出的資訊論，我們一般將資訊分為信源、信宿、信道三部分，資訊體作為載體通過信道穿梭在信源與信宿之間，

下面我們基于以上概念將其引申到分布式環境下，每個服務節點在發送訊息時便是信源角色，若是接收訊息則是信宿角色，信道是建立在節點之前雙向的通道，

因此，我們剖析該問題呈現特點是節點不可靠性、通道不可靠性、資訊不可靠性，因此要針對這些問題特點來進行針對性解決，從而確保一致性的達成，

問題解決

解決方案：口頭協議

實作程序

口頭協議，又稱為口信訊息(Oral message)，滿足以下三個條件的方式稱為口頭協議：

• 每個被發送的訊息都能夠被正確的投遞（信道絕對可信）
• 資訊接收者知道是誰發送的訊息（訊息來源可知，但不知道上一個訊息來源，即不可溯源）
• 能夠知道缺少的訊息

該方案的實作方式是：

• [STEP-1] 各個節點接收Commander指令Command-1
• [STEP-2] 每個節點收到Commander訊息后，再將該訊息分發到其他節點上，最終每個節點都會收到其他節點發來的訊息集合{Commander訊息、其他節點傳遞的Commander訊息}，根據訊息集合來判斷下一步如何執行，

不可靠場景

Commander不可靠

當Commander不可靠時，各節點收到資訊集合為

Node不可靠

少數不可靠

少數節點不可靠場景，當A不可靠時，各節點收到資訊集合為

多數不可靠

多數節點不可靠場景，當A、C不可靠時，各節點收到資訊集合為

綜上，我們可以看到，無論是發號施令的Commander，還是執行命令的Node節點，當不可靠節點數量較多時，分布式中的一致性將遭受破壞，無法保證，

確保一致性情況下，不可靠節點與總結點數量關系

若n代表所有節點（含Commander、Node）總數，m代表不可靠節點數量，則他們必須滿足n≧3m+1這樣的數量關系方可保證分布式的一致性，感興趣可以自己推導下，以下是樣例：

節點總數(n)	Commander數量(1)	Node數量(n-1)	不可靠最大節點數(m)
4	1	3	1
7	1	6	2
10	1	9	3
…	…	…	…

不足

• 訊息無法溯源，無法確定其他節點傳遞訊息的正確性
• 當不可靠節點大多數存在的情況下，無法達成一致性

解決方案：書面協議

為了進一步解決口頭協議的不足，改進點如下：

• 為了確保其他節點傳遞訊息的正確性可溯源，讓節點通信都增加簽名資訊
• 當不可靠節點大多數存在時無法達成一致性，但這是一個未知數，無法實作按照推演公式安排節點總數量來保證容錯，而訊息傳遞加簽名資訊的方式能很好的確保訊息傳遞的可溯源、準確性，以此可以解決任意不可靠節點存在的場景

實作程序

書面協議，又稱為簽名協議，該方案的實作方式是：

• [STEP-1] 各個節點接收Commander帶有簽名的指令Command-1
• [STEP-2] 每個節點收到Commander訊息后，將該訊息進行簽名后再分發到其他節點上，最終每個節點都會收到其他節點發來的帶有簽名資訊的訊息集合{Commander簽名訊息、其他節點簽名的Commander訊息}，根據訊息集合來判斷下一步如何執行，

特點

基于口頭協議的特點，簽名協議規定，每條訊息只可以復制，然后加上自己的簽名再發給其他節點，增加如下特點：

• [1] 節點簽名是不能偽造的，內容修改可檢測
• [2] 任何節點都可以識別Commander的簽名，不可靠節點可以偽造Commander的簽名

不足

• 盡管訊息傳遞均被簽名，但是發送者不一定可信，有可能是A節點使用了C節點簽名來通知B節點，因此需要一個中心化的簽名管理規則或機構對各個發送者進行核驗方可確認真實性

書面協議的本質就是引入了簽名機制，這使得所有訊息都可追本溯源，化解了口頭協議中1/3要求，只要采用了書面協議，可靠節點就可以達到一致，

解決方案：作業量證明

作業量證明演算法（PoW演算法，Proof of Work） 廣泛應用于存在惡意攻擊和篡改且不可靠的分布式環境下，應該廣泛的是區塊鏈技術，

中本聰在位元幣白皮書中，通過位元幣協議給出了終極解決方案如下：

• 引入作業量證明機制，只有第一個完成規定計算作業的節點才能傳播資訊，從而保證一段時間內只有一個提案，

• 引入非對稱加密演算法，為資訊傳遞提供簽名技術支持，以保證訊息傳遞的私密性，且不可抵賴、不可篡改，

關于該部分方案的實作在后續章節中單獨論述，

拜占庭將軍問題是由萊斯利·蘭伯特（Leslie Lamport）等提出的，但真正解決這一難題的是中本聰，

蘭伯特提出的Paxos演算法，還有后續改進的Raft演算法、Zab協議都是基于可靠信道環境下訊息不會被篡改和偽造等惡意攻擊的前提下實作的分布式一致性協議，面對不可靠信道等存在惡意篡改風險的分布式環境是無法保證一致性的，

總結

拜占庭將軍問題，不關心結果的對與錯，只關心節點執行的一致性問題，

現有的分布式一致性協議和演算法主要可分為兩類：

• 非拜占庭容錯演算法
  即非容錯演算法(Crash Fault Tolerance, CFT)，解決的是分布式系統中存在故障，但不存在惡意攻擊的場景下的共識問題，也就是說，在該場景下可能存在訊息丟失，訊息重復，但不存在訊息被篡改或偽造的場景，一般用于局域網場景下的分布式系統，如分布式資料庫，屬于此類的常見演算法有Paxos演算法、Raft演算法,、Zab協議等，
• 拜占庭容錯演算法
  可以解決分布式系統中既存在故障，又存在惡意攻擊場景下的共識問題，一般用于互聯網場景下的分布式系統，如在數字貨幣的區塊鏈技術中，屬于此類的常見演算法有PBFT演算法、PoW演算法，

參考

https://baike.baidu.com/item/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98/265656 拜占庭問題
https://baike.baidu.com/item/%E4%BF%A1%E6%81%AF%E8%AE%BA/302185 資訊論
https://zhuanlan.zhihu.com/p/44024734
https://www.cnblogs.com/aspirant/p/13321203.html
https://www.cnblogs.com/aspirant/p/13321816.html
https://www.8btc.com/article/70370
https://www.jianshu.com/p/81aadcea109b