拜占庭將軍問題

拜占庭將軍問題（Byzantine failures），是由萊斯利·蘭伯特提出的點對點通信中的基本問題。含義是在存在訊息丟失的不可靠信道上試圖通過訊息傳遞的方式達到一致性是不可能的。因此對一致性的研究一般假設信道是可靠的，或不存在本問題。

基本介紹

• 中文名：拜占庭將軍問題
• 外文名：Byzantine failures
• 又稱：兩軍問題
• 提出：萊斯利·蘭伯特

起源

拜占庭位於如今的土耳其的伊斯坦堡，是東羅馬帝國的首都。由於當時拜占庭羅馬帝國國土遼闊，為了防禦目的，因此每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳訊息。 在戰爭的時候，拜占庭軍隊內所有將軍和副官必須達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，左右將軍們的決定又擾亂整體軍隊的秩序。在進行共識時，結果並不代表大多數人的意見。這時候，在已知有成員謀反的情況下，其餘忠誠的將軍在不受叛徒的影響下如何達成一致的協定，拜占庭問題就此形成。

將軍問題

拜占庭將軍問題是一個協定問題，拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。問題是這些將軍在地理上是分隔開來的，並且將軍中存在叛徒。叛徒可以任意行動以達到以下目標：欺騙某些將軍採取進攻行動；促成一個不是所有將軍都同意的決定，如當將軍們不希望進攻時促成進攻行動；或者迷惑某些將軍，使他們無法做出決定。如果叛徒達到了這些目的之一，則任何攻擊行動的結果都是注定要失敗的，只有完全達成一致的努力才能獲得勝利。

拜占庭假設是對現實世界的模型化，由於硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊，計算機和網路可能出現不可預料的行為。拜占庭容錯協定必須處理這些失效，並且這些協定還要滿足所要解決的問題要求的規範。這些算法通常以其彈性t作為特徵，t表示算法可以應付的錯誤進程數。

很多經典算法問題只有在n ≥ 3t+1時才有解，如拜占庭將軍問題，其中n是系統中進程的總數。

失效

所謂拜占庭失效指一方向另一方傳送訊息，另一方沒有收到，或者收到了錯誤的信息的情形。

在容錯的分散式計算中，拜占庭失效可以是分散式系統中算法執行過程中的任意一個錯誤。這些錯誤被統稱為“崩潰失效”和“傳送與遺漏式失效”。當拜占庭失效發生時，系統可能會做出任何不可預料的反應。

這些任意的失效可以粗略地分成以下幾類：

1.進行算法的另一步時失效，即崩潰失效；

2.無法正確執行算法的一個步驟；

3.執行了任意一個非算法指定的步驟。

各個步驟由各進程執行，算法就是由這些進程執行的。一個錯誤的進程是在某個點出現了上述情況的進程。沒有出現錯誤的進程是正確的進程。

解決算法

拜占庭問題的最初描述是：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不等於 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。

Iamport的證明

通過簽名訊息

簽名訊息在除了滿足口頭訊息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 。

證明完畢。

使用鴿巢原理證明拜占庭問題解決的機器總數是3f+1台機器（PBFT）。

使用構造法進行證明。

1、2f+1個節點，f+1個正確節點，f個惡意節點

客戶端收到f+1個節點的回覆之後，由鴿巢原理可以知道，至少收到一個正確節點的回覆，系統可以進行下去，可是，如果惡意節點配合尚未完成執行的正確節點，那么有可能推翻之前協定的順序，導致不一致，所以正確節點的數量不夠。

2、3f+1個節點，2f+1個正確節點，f個惡意節點。

同上可得系統可以執行下去，值得注意的是，兩次協商操作提供正確相應的節點數目達到了f+1個，這樣兩次操作共同的正確節點的數目至少有一個，這樣；兩次定序就不會發生不一致。