引言

接觸區(qū)塊鏈，經(jīng)常會聽到有人提到「拜占庭將軍問題」（The Byzantine Generals Problem）壹哺，所以這篇文章里畴嘶，我們就詳細探討一下這個「問題」溶其。

本篇文章的討論多數(shù)來自于「拜占庭將軍問題」的原始論文，有一些細節(jié)參考了網(wǎng)上這篇文章策橘。

什么是拜占庭將軍問題

「拜占庭將軍問題」來源于這樣一個場景：
拜占庭帝國的軍隊正在圍攻一座城市炸渡。這支軍隊被分成了多支小分隊丽已，駐扎在城市周圍的不同方位蚌堵，每支小分隊由一個將軍領導。這些將軍們彼此之間只能依靠信使傳遞消息（無法聚在一起開個會）沛婴。每個將軍在觀察自己方位的敵情以后吼畏，會給出一個各自的行動建議（比如進攻、撤退或按兵不動）嘁灯，但最終的需要將軍們達成一致的作戰(zhàn)計劃并共同執(zhí)行泻蚊，否則就會被敵人各個擊破。但是丑婿，這些將軍中可能有叛徒性雄，他們會嘗試阻止其他忠誠的將軍達成一致的作戰(zhàn)計劃。

這就是拜占庭將軍的「問題」：只能依靠通信相互交流羹奉，又不知道誰是叛徒毅贮，怎么能不受叛徒們的影響，讓這些忠誠的將軍快速的達到一致的作戰(zhàn)計劃呢尘奏？

很顯然，將這一場景套用到計算機系統(tǒng)中也是非常適用的：在一個分布式系統(tǒng)中病蛉，針對每個運算炫加，每臺獨立的機器也需要最終達成一致的結(jié)果瑰煎。但每臺計算機之間也只能依靠網(wǎng)絡通信（顯然它們無法聚在一起開會），每臺計算機都有出錯的可能（被攻擊俗孝，或故障）酒甸，從而變成「叛徒」干擾正常的計算機達成一致。

這一問題是由 Leslie·Lamport 等人在這篇論文中提出的赋铝，并在論文中給出了理論可行的解決方案和證明插勤。不過在學習這些解決方案之前，我們還要對「拜占庭將軍問題」作進一步的推導革骨，看一下解決方案只要符合哪些要求农尖，就能解決拜占庭將軍問題。

推導

根據(jù)剛才的描述可以總結(jié)出良哲，忠誠的將軍們使用的算法盛卡，需要保證以下兩點：
A. 所有忠誠的將軍可以達成一致的作戰(zhàn)計劃
B. 少數(shù)的叛徒不會導致忠誠的將軍們無法達成一致

（論文中第二條本來是「少數(shù)的叛徒不會導致忠誠的將軍們采用錯誤的計劃」（A small number of traitors cannot cause the loyal generals to adopt a bad plan），并在接下來對什么是「bad plan」作了一個間接的解釋筑凫，我的理解是滑沧，在這里只要是不一致的行動計劃，都是「bad plan」巍实，無論是「進攻」還是「撤退」）

如果我們假設 為第 個將軍的作戰(zhàn)計劃滓技，且每個將軍使用某種方法將序列 轉(zhuǎn)換成一個單一的作戰(zhàn)計劃。那么只要所有的將軍使用相同的方法轉(zhuǎn)換 棚潦，條件A就可以被滿足令漂。條件B可以通過某種更有彈性的方法來滿足，比如獲取到消息序列 以后瓦盛，通過投票的方式洗显，少數(shù)服從多數(shù)，得出一個最終的原环、一致的作戰(zhàn)計劃挠唆。

問題似乎很簡單就被解決了，但我們忽略了一點嘱吗，想要滿足上面兩個條件玄组，所有忠誠的將軍必須拿到同樣的「 」。而叛徒可能給不同的將軍發(fā)送不同的消息谒麦，使這些將軍拿到的是不同的消息序列俄讹，這種情況下我們剛才的解決方法就無法成立了。所以我們必須想辦法保證：
1. 所有忠誠的將軍必須拿到相同的消息序列

只要某個算法能保證條件1绕德，那么條件A和條件B也是可以保證的患膛，因而這個算法就可以解決將軍們的問題。

那么如何保證條件1呢耻蛇？有些將軍（叛徒）可能給不同的將軍發(fā)送不同的值踪蹬，而要使所有忠誠的將軍拿到相同的消息序列胞此，這些忠誠的將軍們就不能直接使用自己接收到的值。也就是說跃捣，將軍們最終使用的 不一定就是將軍當初發(fā)送的原始值漱牵，即使將軍是一個忠誠的將軍。為什么這么說呢疚漆？因為如果讓將軍們必須直接使用其它將軍發(fā)送的原始值酣胀，那么由于叛徒會給不同將軍發(fā)送不同值，所以條件1永遠也無法達成娶聘。所以對于叛徒發(fā)出的值闻镶，將軍們不能直接使用。但將軍們無法區(qū)分誰是叛徒誰是忠誠的趴荸，所以如果不多加注意儒溉，就會導致拋棄或修改某個忠誠的將軍發(fā)出原始值的情況。但這顯然是不對的发钝，對于忠誠的將軍顿涣，我們應該必須使用他發(fā)出的原始值，所以我們必須保證：
2. 如果將軍 是忠誠的酝豪，那么它發(fā)出的原始值 必須被其他忠誠的將軍所采用

條件2只提到了「如果將軍是忠誠的」的情況涛碑，如果將軍是叛徒呢？根據(jù)條件1孵淘，我們依然要保證所有忠誠的將軍拿到相同的值蒲障。所以我們可以得出：
1'. 對于任意一個將軍，無論他是忠誠的還是叛徒瘫证，當他發(fā)出值時揉阎，所有的忠誠的將軍都將采用相同的值，即 （雖然可能不是將軍發(fā)送的原始值）

至此背捌，只要某個算法能保證條件1'（對任意一個將軍發(fā)出的值毙籽，其他忠誠的將軍都將使用相同的值），就能保證條件1（所有忠誠的將軍肯定會拿到相同的消息序列）毡庆。再加上條件2（忠誠的將軍發(fā)出的原始值肯定會被其它忠誠的將軍采用）坑赡，就可以保證條件A和條件B的成立，因而這個算法就可以解決將軍們的問題么抗。

注意條件2和條件1'考慮的都是單個的將軍發(fā)送的值的情況毅否，而只要這兩個條件成立，我們就可以保證解決將軍們的問題蝇刀。因此我們將問題的關鍵轉(zhuǎn)移到了「單個的將軍如何發(fā)送他的值給其它人」上來螟加。我們把這一問題表達為「司令官發(fā)送命令給他的副官們」，得到了如下拜占庭將軍問題：

拜占庭將軍問題：
一位司令官必須發(fā)送命令給他的 n - 1 個副官們，且滿足條件：
IC1. 所有忠誠的副官獲得相同的命令
IC2. 如果司令官是忠誠的仰迁，那么所有忠誠的副官都會獲得司令官發(fā)出的原始命令

這里 IC1 對應著條件1'甸昏； IC2 對應著條件2，不同的是 IC2 特別強調(diào)了「司令官」徐许，而條件2只說「對任意一個將軍」。后面我們會看到卒蘸，司令官是會輪換的雌隅，任意一個將軍都可能成為司令官，所以這兩個說明其實是一樣的缸沃。

至此恰起，我們得出了確定性的拜占庭將軍問題的定義。只要能保證 IC1 和 IC2趾牧，就可以解決將軍們的問題检盼。

（這里可能會有人疑惑：IC1 和 IC2 到底是「問題」，還是「解決條件」翘单。我覺得「問題」和「解決條件」是一致的吨枉。它們構(gòu)成了問題，也是解決問題的關鍵哄芜，解決了它們貌亭，就解決了問題）

解決方案的不可能性

介紹完拜占庭將軍問題以后，你可能會覺得其實也挺簡單认臊。不過論文中也提出了「解決方案的不可能性」（IMPOSSIBILITY RESULTS）圃庭，指出在某些條件下，將軍們無論如何是無法達成一致的失晴。我們需要先對這個作一個介紹剧腻，然后再去介紹解決方案。

我們這里先說結(jié)論：在使用口頭消息的情況下涂屁，不存在將軍總數(shù)小于 的解決方案书在，能夠在存在 個叛徒的情況下解決拜占庭將軍問題。也就是說胯陋，如果有 個叛徒蕊温，則至少需要 個將軍，才能讓忠誠的將軍們達成一致遏乔。

什么是口頭消息呢义矛？所謂口頭消息，是指內(nèi)容完全由發(fā)送者或轉(zhuǎn)發(fā)者控制的消息盟萨。將軍們使用這種消息傳遞信息時凉翻，叛徒可以修改自己收到的任意消息，再轉(zhuǎn)發(fā)給其人捻激，而其它人無法識別出這個消息是否被修改過制轰。（與口頭消息對應的是簽名消息前计，即消息是經(jīng)過原始發(fā)送者簽名的，收到消息的人可以根據(jù)簽名驗證此消息是否被修改過）

下面我們簡單證明一下這個結(jié)論垃杖。首先來證明最簡單的情況徐鹤，即當叛徒數(shù)量 m=1 時，不存在將軍總數(shù) <= 3 的解決方案乱豆，可以解決拜占庭將軍問題躺盛。下面這張圖我直接截取自原始論文：

我們先來看 Fig.1 代表的第一種情況。此時司令官是忠誠的彩库，2號副官是叛徒肤无。司令官給所有副官發(fā)送了「attack」命令，但副官2是叛徒骇钦，所以他欺騙副官1自己收到了「retreat」命令宛渐。因為副官1也不知道誰是叛徒，所以此時副官1會很迷茫眯搭，不知道誰說的是真的：如果他相信副官2窥翩，那么他將不會與忠誠的司令官達成一致；如果他相信司令官坦仍，倒是暫時正確了鳍烁，但事情還未結(jié)束。

我們再來看 Fig.2 代表的第二種情況繁扎。此時司令官是叛徒幔荒，兩個副官是忠誠的。司令官給不同的副官發(fā)送了不同的命令梳玫，副官2也如實將司令官的命令發(fā)給了副官1爹梁。但此時副官1依然會迷茫，因為他仍然收到了兩個不同的命令提澎∫可以看到，對于副官1來說盼忌，當前收到的消息與剛才第一種情況下收到的消息是一樣的积糯，他依然不知道該相信誰。在第一種情況里谦纱，選擇相信司令官是暫時正確的看成，但在當前的情況里卻是錯誤的。

所以結(jié)合這兩種情況來看跨嘉，無論副官1選擇相信誰川慌，都有可能是錯誤的。所以可以得出結(jié)論，在只有一個叛徒但將軍總量 <= 3 的情況下梦重，無法保證忠誠的將軍們達成一致兑燥。

現(xiàn)在我們再來看叛徒數(shù)量 m>1 的情況。m>1 時論文的證明很有意思琴拧，它將 m=1 時的每一位將軍想象成同類將軍的代表降瞳，比如在 Fig.1 中，司令官和副官1分別代表 個忠誠的將軍蚓胸，副官2代表 個叛徒力崇；在 Fig.2 中，司令官代表 個叛徒赢织，副官1和副官2分別代表 個忠誠的將軍。因此也可以得出馍盟， 但將軍總量 <= 時于置，無法保證忠誠的將軍們達成一致。

以上就是這一「解決方案的不可能性」的證明過程贞岭。但我總是感覺這個證明有些「玄乎」八毯，感覺能理解，但好像又不是真的可以理解瞄桨。論文中也提到了類似的問題话速，然后將嚴謹?shù)淖C明過程指向了另一篇論文。不過我們不是作學術(shù)研究芯侥，就不繼續(xù)追究下去了泊交。

口頭消息的解決方案

剛才我們介紹了不可能存在解決方案的情況，那么現(xiàn)在我們就來介紹一下柱查，存在解決方案的時廓俭，如何解決拜占庭將軍問題。

在這一小節(jié)里我們假設將軍們使用「口頭消息」（Oral Message）傳遞消息唉工。前面我們已經(jīng)介紹過研乒，所謂口頭消息，是指內(nèi)容完全由發(fā)送者或轉(zhuǎn)發(fā)者控制的消息淋硝。將軍們使用這種消息傳遞信息時雹熬，叛徒可以修改自己收到的任意消息，再轉(zhuǎn)發(fā)給其人谣膳，而其它人無法識別出這個消息是否被修改過竿报。另外，我們還要對將軍們的消息傳遞系統(tǒng)作如下的限制：

A1. 每一個消息都可以在兩個將軍間正確的傳遞参歹，傳遞過程中不會被修改
A2. 消息的接收者知道這個消息的真正發(fā)送者是誰
A3. 消息的缺失是能夠被將軍們發(fā)現(xiàn)的

A1 和 A2 可以防止叛徒干擾兩個將軍之間的通信：A1 讓叛徒無法在通信過程中修改信息仰楚；A2 讓叛徒無法冒充其它將軍發(fā)送消息。A3 可以防止叛徒通過不發(fā)消息的方式影響一致共識的達成。并且如果將軍們發(fā)現(xiàn)缺少某個消息僧界，他們可以使用統(tǒng)一的默認值（比如 RETREAT）來替代缺失的消息侨嘀。

另外，我們還假設每個將軍都可以直接發(fā)消息給其它任意一個將軍捂襟，不需要中間有人代理轉(zhuǎn)發(fā)咬腕。

下面我們先給出算法的定義，然后再詳細解釋一下算法過程葬荷。

我們首先要定義一個函數(shù) 涨共，這個函數(shù)有這樣的功能：如果大多數(shù)的 等于 ，那么 宠漩。比如可以這樣實現(xiàn)這個函數(shù)：

1. 函數(shù)可以取出現(xiàn)次數(shù)最多的那個值举反，否則為一個默認值（如 RETREAT）
2. 函數(shù)可以取所有值的中位數(shù)（如果這些值可以排序的話）

我們定義使用口頭消息解決拜占庭將軍問題的算法為 ，其中 代表叛徒的數(shù)量且 扒吁， 代表將軍的總數(shù)量且 火鼻。 算法如下：

:
(1). 司令官把他的值發(fā)送給每一位副官。
(2). 每一位副官使用從司令官那里接收到的值作為共識值雕崩。如果沒接收到任何值則使用默認值作為共識值魁索。

:
(1). 司令官把它的值發(fā)送給每一位副官。對于每一個副官 盼铁，假設 為自己從司令官那里接收到的值（如果沒接收到則為默認值）粗蔚。
(2). 每一個副官 作為新的司令官、其它所有副官（當然不包含自己和當前司令官啦）作為新的副官饶火，執(zhí)行算法 鹏控。（在算法 中新司令官 會將他接收到的值 發(fā)送他的副官們）。
(3). 假設 為第二步中的副官們對第二步中的新司令官 發(fā)送的值達成的共識值趁窃，則當前副官們的共識值為 牧挣。

這里我們要馬上解釋一下 共識值 這個概念（這個詞是我自己創(chuàng)造的，原論文中沒有）醒陆。所謂「共識值」瀑构，是指副官們一致認同的司令官發(fā)送的值。這里的關鍵是并不是司令官發(fā)什么值刨摩，副官們就接受并相信什么值寺晌；而是副官之間要對司令官發(fā)送的值進行「探討」，最終形成一個一致意見澡刹，接受并相信一個相同的值呻征，這個值就是「共識值」。如果司令官是叛徒罢浇，那么這個值不一定就是司令官發(fā)出的原始值陆赋。比如有 4 個將軍沐祷，司令官是叛徒，他給其他 3 個副官發(fā)送的值分別是 a攒岛、b赖临、c。那么 3 個副官最終的共識值應該是 灾锯。

算法使用了遞歸兢榨，這使它非常難以理解。但我們這里先不詳細考慮算法本身的流程顺饮，而是從更高一層的角度想想吵聪，為什么會產(chǎn)生拜占庭將軍問題，以及應該怎樣應對兼雄。

產(chǎn)生拜占庭將軍問題的原因我認為是：每個忠誠的將軍不知道誰是叛徒吟逝，從而產(chǎn)生了對其他將軍的不信任。

那怎么應對呢赦肋？既然是不知道該相信誰且多數(shù)將軍是忠誠的澎办，那么只能使用 函數(shù)產(chǎn)生一個「多數(shù)人的意見」，并服從這個意見金砍。所以當副官們接收到司令官的命令時，副官們不知道司令官是不是叛徒麦锯，從而不能輕易相信司令官恕稠，只能依然副官們「相互溝通」后，達成一個可以相信的「共識值」扶欣。

副官們溝通的方法就是將司令官排除出去鹅巍，每個副官將自己接收到的值發(fā)給其他所有人，這樣每個副官就能知道司令官發(fā)給所有人值了料祠。然后副官們就使用 函數(shù)從這些值中計算出一個「共識值」骆捧。

但問題是，在這些溝通的副官中髓绽，仍可能會有叛徒敛苇，他發(fā)出來的值可能根本不是從司令官接收到的值，且可能發(fā)給其他每個人的值都不一樣顺呕，這樣每個忠誠的副官拿到的就不是一樣的序列 枫攀，還是沒法達成一致的。

其實在副官們的「溝通」過程中株茶，每當一位副官向其他人發(fā)送自己的值時来涨，其他人也不知道這位副官是否是叛徒，因此也不應該直接相信他启盛，而是應該所有接收他消息的人再次「相互溝通」蹦掐，以便對這位副官發(fā)送的值達成共識技羔。這里就產(chǎn)生了遞歸：每一位副官向其他人發(fā)送自己接收到的值時，也可以看作自己是「司令官」卧抗，其他人是自己的副官藤滥。其他的副官在彩納自己發(fā)送的值之前，首先要充分的「相互溝通」達成一個共識值颗味。

以上基本上就是 算法的要素和遞歸過程超陆。這么來看，這個算法的邏輯就比較容易理解了浦马。

那什么時候遞歸結(jié)束呢时呀？或者說，什么時候可以相信司令官發(fā)送的值晶默，而不用再「相互溝通」了呢谨娜。在 算法中，每遞歸一輪磺陡， 的值就減 1趴梢，當 時，副官們就不用再「相互溝通」了币他，而是直接將司令官發(fā)送的值作為當前的共識值坞靶。至于為什么這樣是正確的，我們一會再來說明蝴悉。

下面我們通過實例彰阴，來加深對這一算法的理解。首先看一看論文中比較簡單的 時的例子拍冠。

首先看司令官是忠誠的情況尿这，此時有一個副官是叛徒：

從圖中可以看到，在 OM(1) 的第 (1) 步中庆杜，司令官開始給每個副官發(fā)送一個值射众，本例中司令官是忠誠的，所以他給每個副官的值都是一樣的晃财，為 a叨橱。

在 OM(1) 的第 (2) 步中，每個副官各自作為司令官断盛，進入到 算法中雏逾，將自己收到的值發(fā)給其他副官。此時 郑临，所以其它副官把此時自己收到的值作為這一層次的共識值栖博。這一步執(zhí)行完以后，每個副官都會收到其它兩個副官發(fā)送的值厢洞，再加上自己在第 (1) 步中收到的值仇让，此時每個副官共收到了 3 個值典奉。然后進入到下一步中。

在 OM(1) 的第 (3) 步中丧叽，每個副官利用 函數(shù)卫玖，計算自己收到的 3 個值。由于 L1 自己從 L0 那里收到了一個 a 值踊淳；且在 OM(0) 中從 L2 那里收到的也是 a 值假瞬，從 L3 那里收到的是 x，所以 L1 的共識值應該是 a迂尝。L2 的情況與 L1 類似脱茉，他的共識值也是 a。所以 L0垄开、L1琴许、L2 三個忠誠的將軍達成了一致，他們的共識值都是 a溉躲。

我們再來看看司令官是叛徒的情況：

此時在 OM(1) 的第 (1) 步中榜田，由于司令官 L0 是叛徒，所以他可能發(fā)給每個人的值都不一樣（以盡最大可能達到干優(yōu)忠誠將軍們的目的）锻梳，所以我們假設 L1箭券、L2、L3 收到的值各不相同疑枯，分別為 a邦鲫、b、c神汹。

下面的步驟與剛才類似，我們不再贅述古今∑ㄎ海總之 L1、L2捉腥、L3 分別收到了除自己這外的其他兩個副官發(fā)送的值氓拼，所以他們最后每個人收到的三個值其實都是 a、b抵碟、c桃漾。當他們使用 函數(shù)計算共識值時，由于輸入值是相同的拟逮，所以輸出的肯定是同一個值撬统。因此最終三個忠誠的將軍仍然達成了一致的共識值 t，雖然這個值可能與司令官 L0 發(fā)送的值完全不一樣敦迄。

時 算法很簡單恋追，也很容易理解凭迹。以此為預熱，我們來看一下復雜一些的情況苦囱，比如 時嗅绸， 是如何執(zhí)行的。我們下面的示意圖使用的圖例與剛才完全一致撕彤，只是更復雜而已鱼鸠。由于 的情況實在太復雜，如果全部用圖示意出來羹铅，圖片會非常的大蚀狰，也會非常復雜，這樣反而失去了圖片示意的意義睦裳。因此在下面這張圖中造锅，每一個步驟我只示意了第一種情況和最后一種情況，其它情況都用省略號代替了廉邑。另外在乍用這張圖理解 算法時哥蔚，建議先縱向看，即先沿著某一分支一直向下看蛛蒙，看明白了再看其它分支糙箍。最后再橫向綜合起來看。

另外牵祟，也由于 太復雜深夯，所以這里也只示意了叛徒作為司令官的情況。忠誠將軍作為司令官的情況是類似的（甚至會更簡單些）诺苹。

下面就是 的示意圖（如果圖片太小咕晋，可以嘗試點擊圖片看大圖，或在新標簽中打開圖片收奔，或圖片另存為本地圖片后查看）：

雖然整個過程變復雜了掌呜，但細節(jié)上與剛才介紹的 是相同的，因此就不每一步都說明介紹了坪哄。需要特別提出來的是质蕉，在 step (1) 中、L9 作為司令官時翩肌，最終忠誠的將軍們是無法對 L9 發(fā)送的信息達成一致的共識值的（ step (3) 中）模暗，但這并不妨礙忠誠將軍們達到最終的一致共識。

與前面介紹過的 中判徒作為司令官的情況類似念祭，這里忠誠將軍們雖然最終達成了一致（上圖中用值 C 表示）兑宇，但這個值可能與最開始司令官發(fā)出來的值不一樣。

在原論文中還給出了這個算法的正確性證明粱坤。這里我們就不進行證明了顾孽，只是聊一下證明相關的思路祝钢，以及為什么當 m=0 時各將軍就不再相互確認，而是直接將接收到的值作為當前的共識值若厚。由于在 算法中拦英，每進行一輪都會忽略當前司令官、剩下的副官們相互發(fā)送消息確認测秸。那么我們設想兩個極端的情況：
第一種情況是每次忽略的都是叛徒疤估；
第二種情況是每次忽略的都是忠誠將軍。

在第一種情況下霎冯，每次忽略的都是叛徒铃拇，因此當最后 m=0 時，一共忽略了 m 個叛徒沈撞，但總共也就 m 個叛徒慷荔。也就是說，在這種情況下當最后 m=0 時缠俺，剩下的所有將軍都是忠誠的显晶，因此他們肯定可以達成一致的共識值。

在第二種情況下壹士，每次忽略的都是忠誠將軍磷雇，因此最后當 m=0 時，一共忽略了 m 個忠誠將軍躏救，此時剩下的將軍中唯笙，有 m 個是叛徒，有 m+1 個是忠誠將軍盒使。忠誠將軍的數(shù)量大于叛徒的數(shù)量崩掘，因此還是可以達成一致的共識值的。

因此無論哪種情況下少办，在 的第 (3) 步中苞慢，忠誠將軍們肯定是可以達成一致共識的。論文中證明的關鍵也是無論什么時候凡泣，忠誠將軍的數(shù)量總是多于叛徒的。

簽名消息的解決方案

回看一下口頭消息的解決方案皮假，還是很復雜的鞋拟。其實口頭消息的解決方案之所以復雜，就是因為叛徒可以隨意改更忠誠將軍的消息惹资，而別人無法發(fā)現(xiàn)消息被改贺纲。如果我們讓忠誠將軍的消息無法篡改，那么問題就變得簡單多了褪测。這就是簽名消息的解決方案猴誊。

前面介紹口頭消息時潦刃，我們對將軍們之間的消息傳遞系統(tǒng)作了一些限制（前面的 A1 - A3）。在使用簽名消息時懈叹，我們要在之前限制的基礎上乖杠，再加一條：

A4.
(a) 忠誠將軍的簽名是無法被修改的；任何改動包含了忠誠將軍簽名的消息的行為澄成，都可以被發(fā)現(xiàn)
(b) 任意一個人都可以驗證屬于某將軍的簽名是不是真的是他自己簽的

注意這里我們并沒有對叛徒的簽名作任何的限制胧洒。我們可以允許叛徒之間相互修改和偽造彼此的簽名，而不被別人發(fā)現(xiàn)墨状。

既然我們現(xiàn)在使用了消息簽名卫漫，那么之前將軍數(shù)量必須大于等于 才能達成共識的限制就可以去除了。事實上肾砂，我們可以讓任何數(shù)量的將軍團體在存在 個叛徒的情況下達成共識（這里雖然說任意數(shù)量列赎，但如果總數(shù)小于 將沒有意義。因為「達成共識」意味著兩個或兩個以上的人镐确，只有一個忠誠將軍或跟本沒有忠誠將軍談不上「達成共識」）包吝。

在給出解決方案之前，我們首先要定義一個函數(shù) 辫塌。這個函數(shù)輸入一個值的集合漏策，輸出一個單一值。我們對這個函數(shù)有兩個要求：

1. 如果集合 由單個元素 組成臼氨，那么
2. 始終為相同的默認值掺喻，比如 RETREAT。共中 代表集合為空

另外在算法中储矩，我們使用 代表由將軍 簽名的值 感耙。類似的 代表值 先由將軍 簽名得到 ，然后 又被將軍 簽名持隧，得到 即硼。

我們定義使用簽名消息解決拜占庭將軍問題的算法為 ，其中 代表叛徒的數(shù)量且 屡拨。 算法如下：
(0). 每個將軍 i 初始化自己的值集合 只酥。
(1). 司令官將要發(fā)送的值簽名，然后發(fā)送簽名后的值呀狼。
(2). 對于每個副官 ：
　　　(A) 如果副官 之前沒接收過任何將軍發(fā)過來的任何值裂允，且值的形式是 ，那么：
　　　　　(i) 將 加入到 中（此時 ）
　　　　　(ii) 將 發(fā)送給其他副官
　　　(B) 如果副官 接收到了一個形式如 這樣的值哥艇，并且 不在 中绝编，那么：
　　　　　(i) 將 加入到 中
　　　　　(ii) 如果 ，那么此副官將值 發(fā)送給除 之外的所有其它副官
　　　(C) 如果副官 接收到一個已經(jīng)存在于 中的值，則忽略它十饥。
(3). 對于每個副官 窟勃，當自己不會再接收到更多值的時候，它將 作為最終自己的共識值逗堵。

（論文中解釋了第 (3) 步中如判斷自己不會再接收到更多的值秉氧，但我覺得不太靠譜。這里只是算法砸捏，不是實現(xiàn)谬运，所以就姑且認為可以判斷吧）

可以看到， 算法要比 算法詳細垦藏、簡單梆暖，尤其是 算法沒有用到遞歸來解決問題。注意在第 (2) 步中掂骏，(A)轰驳、(B)、(C) 三種情況是互斥的弟灼，即只要執(zhí)行了某一情況级解，就不會再去執(zhí)行另一情況√锇螅可以把第 (2) 步理解成編程語言中的 switch/case 語句勤哗。

這個算法的關鍵是維護一個集合 ，如果新收到的值不在這個集合中掩驱，就將它加入進去芒划，并對這個值簽名后再將其發(fā)送給其他人；如果已存在于集合中欧穴，就忽略不管了民逼。 仔細理解這一過程你就會發(fā)現(xiàn)， 的關鍵思想是通過消息不可篡改這一特性涮帘，讓所有忠誠將軍成為「一體」拼苍，就像同一個人一樣。 當某個值第一次被忠誠將軍接收到時调缨，無論是第 (2) 步的 情況 (A) 還是 情況 (B)疮鲫，這個忠誠將軍都會將這個值發(fā)送給其他所有沒給這個值簽過名的人；由于簽名值的不可篡改弦叶，最終其他所有忠誠將軍的集合 中肯定也會存在這個值俊犯。因此除非消息到達不了忠誠將軍那里，只要到達湾蔓，就會「全體忠誠將軍都有」瘫析。這樣看來砌梆，無論叛徒怎么干擾默责，都無濟于事了贬循，因為最終忠誠將軍們的集合 肯定都是一樣的，因此 最終的結(jié)果也肯定是一樣的桃序。所不同的是杖虾，如果司令官是忠誠的，那么最終所有忠誠將軍的集合 中肯定只有一個值媒熊，就是司令官原始發(fā)送的值；而如果司令官是叛徒，他給不同的副官發(fā)送了不同的值舞肆，那么最終所有忠誠將軍的集合 中會有多個值（但整個集合還是相等的）僻族。

這里還要解釋一下為什么在算法的 (2)(B)(ii) 步驟中，只有 的情況下柠衅，才會將值簽名后皮仁，發(fā)給其他副官。因為接收到的值 有 個簽名（注意最前面還有編號為 0 的司令官的簽名）菲宴。如果 贷祈，那么 ，即當 時喝峦，至少有 個將軍對這個值簽過名了势誊，而這 個將軍中至少有 1 個忠誠的將軍。也就是說當 時至少有 1 個忠誠的將軍的集合 中已經(jīng)有這個值了谣蠢。剛才我們說過粟耻，忠誠的將軍們是「一體的」，只要有一個忠誠的將軍有這個值了漩怎，其它忠誠將軍也肯定會有這個值勋颖。所以當 時就沒必要再給別人發(fā)送這個值了。

算法比較容易理解勋锤，所以我們這里只看一下論文中給出的簡單例子即可饭玲。論文中的例子中總共有 3 個將軍，其中有 1 個叛徒叁执，并且司令官就是這個叛徒（注意這個例子并不需要如 算法那樣需要 4 個將軍才能達成共識）茄厘。如下圖（圖片來自原論文）：

在上圖中，叛徒司令官給兩個副官分別發(fā)送了不同的值谈宛。副官1收到值后發(fā)現(xiàn)這是自己第一次收到值且是司令官發(fā)來的次哈，于是執(zhí)行步驟 (2)(A)，將 "attack" 加入到了自己的集合 中吆录，然后將 "attack":0:1 發(fā)送給副官2窑滞；類似的副官 2 在收到司令官發(fā)來的值后，也將 “retreat” 加入到自己的集合 中，然后將 "retreat":0:2 發(fā)送給副官1哀卫。

副官1接收到副官2發(fā)來的消息后巨坊，發(fā)現(xiàn)自己的集合中沒有 "retreat" 這個值，因此他將這個值加入到了自己的集合 中此改。此時副官1的集合為 趾撵。

副官2接收到副官1發(fā)來的消息后，也發(fā)現(xiàn)自己的集合中沒有 "attack" 這個值共啃，因此他也將這個值加入到了自己的集合 中占调。此時副官2的集合為 。

最后我們可以看到移剪，兩個忠誠的副官的集合都是一樣的究珊。因此 和 的值也肯定是一樣的（不管這個值是什么）。所以最終忠誠的將軍達成了共識纵苛。

總結(jié)

通過這篇文章苦银，我們詳細了解了什么是拜占庭將軍問題，以及原論文給出的基于口頭消息和簽名消息的解決方法赶站♂Ｂ玻「拜占庭將軍問題」是區(qū)塊鏈共識的一個基礎（我覺得也是各種分布式系統(tǒng)的共識的基礎），了解了這個問題贝椿，有利于我們以后理解其它很多的共識算法想括。

拜占庭將軍問題的原論文雖然給出了基于口頭消息和簽名消息的解決方案，但這些方案并不能很好的應用于實際生產(chǎn)環(huán)境中（比如基于口頭消息的方法烙博，通信量太大瑟蜈；基于簽名消息的方法，如果司令官一直是叛徒渣窜，那這個系統(tǒng)雖然可以達成一致铺根，但也干不了什么正事）。因此很多前輩和大牛給出了不少其他可實際應用的解決方案乔宿，我們以后的文章會繼續(xù)學習這些方案位迂。

限于作者水平，文章中難免有錯誤的地方详瑞，如果發(fā)現(xiàn)感謝您能不吝指正掂林。

本文最先發(fā)表于我的博客，歡迎評論和轉(zhuǎn)載坝橡。