The Byzantine Generals Problem

一個可信的計算機系統必須容忍一個或多個部件的失效。失效的部件可能送出相互矛盾的信息給系統的其他部件。這正是目前網路安全要對付的情況，如銀行交易安全、存款安全。美國2001/9/11遭恐怖攻擊之後，大家普遍認識到銀行的異地備份非常重要。紐約的一家銀行可以在東京、巴黎、蘇黎世設定異地備份。當某些點受到攻擊甚至破壞以後，可以保證賬目仍然不錯，得以復原和恢復。從技術的角度講，這是一個很困難的問題。因為被攻擊的系統不但可能不作為，而且可能進行破壞。國家的安全就更不必說了。

基本介紹

• 中文名：拜占庭將軍問題
• 外文名：The Byzantine Generals Problem
• 領域：邏輯學
• 套用：計算機

個人簡介

英文

為了利於對“拜占庭將軍”問題原意的理解把英文解釋奉上：

Byzantine General Problem ——The problem of reaching a consensus among distributed units if some of them give misleading answers. The original problem concerns generals plotting a coup. Some generals lie about whether they will support a particular plan and what other generals told them. What percentage of liars can a decision making algorithm tolerate and still correctly determine a consensus?

中文

拜占庭帝國就是5～15世紀的東羅馬帝國，拜占庭即現在土耳其的伊斯坦堡。我們可以想像，拜占庭軍隊有許多分支，駐紮在敵人城外，每一分支由各自的將軍指揮。將軍們只能靠通訊員進行通訊。在觀察了敵人以後，忠誠的將軍們必須制訂一個統一的行動計畫。然而，這些將軍中有叛徒，他們不希望忠誠的將軍們能達成一致，因而影響統一行動計畫的制訂與傳播。問題是：將軍們必須有一個算法，使所有忠誠的將軍們能夠達成一致，而且少數幾個叛徒不能使忠誠的將軍們做出錯誤的計畫。

解決拜占庭將軍問題的保證

解決拜占庭將軍問題的算法必須保證：

所有忠誠的將軍基於相同的計畫做出決策

忠誠的將軍按算法的要求行動，而叛徒則按他們自己的意志行動。算法要保證不管叛徒怎么做，條件A都能得到保證。忠誠的將軍們不但要能達成一致，而且要同意一個合理的計畫。這就要求條件B。

少數叛徒不能使忠誠的將軍做出錯誤的計畫

這一條是很難做到的，因為“錯誤的計畫”很難形式地加以定義。

我們考慮將軍們怎么達成一致。設有n個將軍，v(i)表示第i個將軍送出的信息。每個將軍用相同的方法把v(1),…,v(n)按某一種邏輯方式組合起來，形成一個行動計畫。要滿足條件A，將軍們就必須用同樣的方法來組合這些信息。而條件B要求使用的方法是健壯的。考慮最簡單的情況，如果決定只有進攻和撤退兩種可能，v(t)就是將軍認為選擇那一種行動最好，而最後的決定則基於多數表決。少數叛徒只有在忠誠的將軍們幾乎隨機地（每一種選擇的機率都是1/2）做出決策時才能影響決策，但既然每一種選擇的機率都是1/2，那就不管怎么決策都不能說是壞的。

如果把第i個將軍的信息v(i)送給其他將軍。由於條件A要求每一個忠誠的將軍得到v(1),…,v(n)相同的值，而叛徒將軍可以給不同的將軍送不同的值。為了使條件A得到滿足，下面兩條必須成立：

1．每一個忠誠的將軍得到v(1),…,v(n)相同的值。

這就意味著忠誠的將軍並不一定使用第i個將軍送來的信息作為v(i)。因為第i個將軍可能是叛徒。但這又可能使忠誠的將軍送來的信息也被修改，因為忠誠的將軍並不知道第i個將軍是忠誠的，還是叛徒。如果要滿足條件B，這是不能允許的。例如，我們不能因為少數叛徒說“撤退”，忠誠的將軍說“進攻”，而做出“撤退”的決定。因此，要求

2．對每一個 i，如果第i個將軍是忠誠的，其他忠誠的將軍必須以他送出的值作為v(i).

我們可以重寫條件1如下。

1’。 對每一個 i，不論第i個將軍是忠誠的，或是叛徒，任何兩個忠誠的將軍使用相同的值v(i).

條件1’和2都只牽涉到第i個將軍怎么送一個值v(i)給其他的將軍。因此，我們可以用司令送命令給副官的方式敘述如下：

拜占庭將軍問題：一個司令要送一個命令給他的n-1個副官，使得

IC1。所有忠誠的副官遵守同一個命令。

IC2。假如司令是忠誠的，則每一個忠誠的副官遵守他送出的該命令。

條件IC1和IC2稱為互動一致性條件。注意，如果司令是忠誠的，IC1可以從IC2推出來。但是，司令並不一定是忠誠的。

這個問題比過去的容錯更困難。因為過去的容錯都是針對那樣一些軟硬體故障，其故障效果是固定的。而拜占庭故障卻假定故障機是鮮活的，它可以做壞事。

拜占庭將軍問題的可解性

拜占庭將軍問題的可解性

叛徒數大於或等於1/3

叛徒數大於或等於1/3，拜占庭問題不可解

如果有三位將軍，一位副官是叛徒，如圖1所示。當司令發進攻命令時，副官2可能告訴副官1，他收到的是“撤退”的命令。這時副官1收到一個“進攻”的命令，一個“撤退”的命令，而無所適從。

如果司令是叛徒，如圖2所示。他告訴副官1“進攻”，告訴副官2“撤退”。當副官2告訴副官1，他收到“撤退”命令時，副官1由於收到了司令“進攻”的命令，而無法與副官2保持一致。

正由於上述原因，在三模冗餘系統中，如果允許一機有拜占庭故障，即叛徒數等於1/3，因而，拜占庭問題不可解。也就是說，三模冗餘對付不了拜占庭故障。三模冗餘只能容故障-凍結(fail-frost)那類的故障,就是說，元件故障後，它就凍結在某一個狀態不動了。對付這類故障，用三模冗餘比較有效。

用口頭信息，叛徒數少於1/3

用口頭信息，如果叛徒數少於1/3，拜占庭問題可解

注意，這裡說“少於1/3”表明，要對付一個叛徒，至少要用四模冗餘。在四模中有一個叛徒，叛徒數是少於1/3的。所謂口頭信息，是指它滿足三個條件：① 傳送正確，② 接收者知道是誰發的。③ 沉默（不發信息）可以被檢測。拜占庭問題可解是指：所有忠誠的副官遵循同一命令。若司令是忠誠的，則所有忠誠副官遵循其命令。我們可以給出一個多項式複雜性的算法來解這一問題。算法的中心思想很簡單，就是司令把命令發給每一副官，各副官又將收到的司令的命令轉告給其他副官，遞歸下去，最後用多數表決。如圖3所示。如果司令是忠誠的，他送一個命令v給所有副官。若副官3是叛徒，當他轉告給副官2時命令可能變成x。但副官2收到{v, v, x}，多數表決以後仍為v，忠誠的副官可達成一致。如果司令是叛徒，如圖4所示。他發給副官們的命令可能互不相同，為x, y, z。當副官們互相轉告司令發來的信息時，他們會發現，他們收到的都是{x,y,z}，因而也取得了一致。

用書寫信息，至少2/3的將軍是忠誠的

用書寫信息，如果至少有2/3的將軍是忠誠的，拜占庭問題可解

所謂書寫信息，是指帶簽名的信息，即可認證的信息。它是在口頭信息的基礎上，增加兩個條件：① 忠誠司令的簽名不能偽造，內容修改可被檢測。② 任何人都可以識別司令的簽名，叛徒可以偽造叛徒司令的簽名。一種已經給出的算法是接收者收到信息後，簽上自己的名字後再發給別人。由於書寫信息的保密性，可以證明，用書寫信息，如果至少有2/3的將軍是忠誠的，拜占庭問題可解。

如果司令是叛徒，他送“進攻”命令給副官1，並帶有他的簽名0，送“撤退”命令給副官2，也帶簽名0。副官們轉送時也帶了簽名。於是副官1收到{“進攻”：0，“撤退”：0,2}，說明司令發給自己的命令是“進攻”，而發給副官2的命令是“撤退”，司令對我們發出了不同的命令。對副官2也同樣。

形式描述

考慮網路N，包含n個處理器，或叫遊戲者，記為1,2,…,n，設n≥4。每一個處理器是一個互動的、機率的多項式時間圖靈機。設網路N是完全的以私人通道連線，即每對處理器皆可互相通信而不能被其他處理器讀取。該網路是同步的，即有統一的時鐘。在d和d+1個脈衝間送出的信息將在d+1個脈衝時收到。

遊戲者i稱為是好的，如果它遵循協定，即正確執行其程式，在適當的時間在適當的地點寫入返回的值。i稱為是壞的，如果它破壞了該協定。如果壞的遊戲者被敵手選用和控制，則更一般的故障行為可能發生。敵手是一個算法，在一個網路中發作，腐化一定比例的遊戲者。

定義：設A是一個機率算法，r為常數。A稱為是一個r-敵手，如果A可以在任何n遊戲者的、運行任何協定P的網路上發作，並且滿足：

(1) A可以讀取非私人通道上的任何通信鏈路。

(2) A可腐化任何t個遊戲者。當A腐化i時，A可以讀取i的所有數據，並奪取i輸出的執行寫控制。

(3) 動態性：A可以在P的任何步驟上腐化遊戲者。

(4) 急促性：A讀第d周期內通過非私人通道傳送的信息。第d周期私人通道信息在第d周期送給壞遊戲者。基於這些信息，A在第d周期腐化其他的遊戲者（少於t個）。而且在第d周期把d周期信息送給新被腐化者。這一過程繼續到腐化t個遊戲者。在第d+1個脈衝之前，A不需要選擇在第d周期由壞遊戲者送給好遊戲者的信息。

(5) A可以即時完成無限步的計算

有文章給出了拜占庭一致性算法，不要求親信夥伴和預處理。給定私人通信鏈路，可望在常數時間內達成一致，如果同步網路故障機；異步網路，故障機。如果不能保證私人通信，可以用密碼得到在容錯和敵手有限計算能力的運行時間兩方面最優的算法。在這種情況下，對異步網路也能容n/3個故障。

可信計算中的拜占庭將軍問題

可信計算中必須考慮人為的故障，特別是人為惡意的攻擊。這是保證計算安全性的基本出發點，在今天的網路環境下有非常重要的現實意義。拜占庭將軍問題不過是保持並行計算中數據一致性問題的一個抽象表達。一種抽象表達往往能把本質問題從繁瑣的工程實現中提取出來，對於基礎研究極其重要。工程師們常常被繁瑣的工程任務所左右，在保證安全的要求下要考慮的問題非常多，而忽略了提綱挈領的功夫。

在可信計算領域，過去考慮的故障-凍結模式，假定部件故障以後就“死”去了，不再工作了。現在我們必須考慮故障-活動模式，即部件故障以後，它可能仍然活動，甚至進行系統所有者所不希望它做的事情。這正是電子對抗中要著力研究的問題。

並行計算中有兩個基本問題：一個是控制的同步性；一個是數據的一致性。不論是並行的處理器，還是並行的執行緒，總需要保持某種程度上的同步，以期達到各個計算部件之間的協同與合作。儘管這種同步可以是緊耦合，也可以是鬆散的耦合。另一方面，各計算部件之間的數據一致性也至關重要。例如銀行系統在為用戶存取款服務時，人名的查找必須和存取款數量相對應，否則就錯了。而這兩件事可能由不同的計算部件或不同的時刻完成。而這種一致性常常能被故障，特別是惡意攻擊所破壞。敵人的攻擊也常常是利用這一點。拜占庭將軍問題只把數據簡化為二值的0和1。當然，多版本的一致性不單是“進攻”和“撤退”這樣簡單的信息，但原理是一樣的。

為了保持多版本的一致性，系統需要一定的時間。在這段時間內，系統還沒來得及達成一致，系統可能有可攻擊的脆弱之處。這段時間表現為故障潛伏期，即敵人的攻擊不一定馬上生效，系統在某一時機來到時就可能做出錯誤的回響。

解拜占庭將軍問題的算法給我們提供數據一致性的思路和算法。而在該算法中就有各位將軍的同步問題。這些問題都為計算可信性的提高以啟發。要解決拜占庭將軍問題需要四模冗餘，硬體開銷是很大的。所以，現在銀行的異地備份並不都是四模冗餘。這就看你的系統要求有多高的安全性，相對於那些投資，孰輕孰重。

從拜占庭將軍問題解法可以看出，簽名和認證對保證數據安全有節省硬體的效果。這些技術將在後文詳細介紹。