拜占庭將軍問題

背景：以戰(zhàn)國時期為背景

戰(zhàn)國時期，齊、楚、燕、韓、趙、魏、秦七雄并立，后來秦國的勢力不斷強(qiáng)大起來，成了東方六國的共同威脅。于是，這六個國家決定聯(lián)合，全力抗秦，免得被秦國各個擊破。一天，蘇秦作為合縱長，掛六國相印，帶著六國的軍隊叩關(guān)函谷，駐軍在了秦國邊境，為圍攻秦國作準(zhǔn)備。但是，因?yàn)楦鲊婈牱謩e駐扎在秦國邊境的不同地方，所以軍隊之間只能通過信使互相聯(lián)系，這時，蘇秦面臨了一個很嚴(yán)峻的問題：如何統(tǒng)一大家的作戰(zhàn)計劃？

萬一一些諸侯國在暗通秦國，發(fā)送誤導(dǎo)性的作戰(zhàn)信息，怎么辦？如果信使被敵人截殺，甚至被敵人間諜替換，又該怎么辦？這些都會導(dǎo)致自己的作戰(zhàn)計劃被擾亂，然后出現(xiàn)有的諸侯國在進(jìn)攻，有的諸侯國在撤退的情況，而這時，秦國一定會趁機(jī)出兵，把他們逐一擊破的。

問題：二忠一叛的難題

現(xiàn)有三個國家攻打秦國，分別叫齊、楚、燕。同時，又因?yàn)榍貒軓?qiáng)大，所以只有半數(shù)以上的將軍參與進(jìn)攻，才能擊敗敵人。此時，將軍們需要通過信使傳遞消息，然后協(xié)商一致之后，才能在同一時間發(fā)動進(jìn)攻。

正常的情況：

例如：

1. 齊根據(jù)偵查情況決定撤退。
2. 楚和燕根據(jù)偵查信息，決定進(jìn)攻。

這樣最終進(jìn)攻和撤退的二者的占比為2:1，因此最終會執(zhí)行進(jìn)攻的命令。

不正常的情況，存在叛軍（惡意節(jié)點(diǎn)）：

假設(shè)齊和燕為忠誠將軍，楚為叛將?，F(xiàn)在齊決定撤退、燕決定進(jìn)攻。而由于楚已經(jīng)叛變，他向齊傳達(dá)“撤退”的命令，向燕傳達(dá)“進(jìn)攻”的命令。因此齊看到的結(jié)果為：進(jìn)攻:撤退 = 1:2；燕看到的結(jié)果為：進(jìn)攻:撤退 = 2:1。最終就燕自己去進(jìn)攻秦軍了，被滅了。

解決方法一：口信消息型拜占庭問題之解

三位將軍分撥一部分軍隊，由蘇秦帶領(lǐng)。這樣3位將軍的作戰(zhàn)討論，變成了4位將軍的作戰(zhàn)討論，這樣可以增加討論中忠誠將軍的數(shù)量。

然后，四位將軍約定了，如果沒有收到命令，就執(zhí)行預(yù)設(shè)的默認(rèn)命令，例如撤退。需要進(jìn)行多輪作戰(zhàn)信息協(xié)商（協(xié)商的輪次與叛將的數(shù)量有關(guān)）：

第一輪：

• 先發(fā)送作戰(zhàn)信息的將軍作為指揮官，其他的將軍作為副官；
• 指揮官將他的作戰(zhàn)信息發(fā)送給每位副官；
• 每位副官，將從指揮官處收到的作戰(zhàn)信息，作為他的作戰(zhàn)指令；如果沒有收到作戰(zhàn)信息，將把默認(rèn)的“撤退”作為作戰(zhàn)指令。

第二輪：

• 除了第一輪的指揮官外，剩余的 3 位將軍將分別作為指揮官，向另外 2 位將軍發(fā)送作戰(zhàn)信息；
• 然后，這 3 位將軍按照“少數(shù)服從多數(shù)”，執(zhí)行收到的作戰(zhàn)指令。

如果這里需要協(xié)商多輪，那么除了前面幾輪的指揮官外，剩余的將軍作為指揮官將作戰(zhàn)信息發(fā)送每位副官。

具體協(xié)商過程：

分別以忠誠將軍和叛將先發(fā)送作戰(zhàn)信息為例：

1、忠誠將軍先發(fā)送作戰(zhàn)信息：

假設(shè)忠將蘇秦先發(fā)送作戰(zhàn)信息，作戰(zhàn)指令是“進(jìn)攻”。那么在第一輪作戰(zhàn)協(xié)商中，蘇秦向齊、楚、燕發(fā)送作戰(zhàn)指令“進(jìn)攻”，意味著齊、楚、燕分別收到了“進(jìn)攻”的信息，并作為自己的作戰(zhàn)指令。

在第二輪作戰(zhàn)信息協(xié)商中，齊、楚、燕分別作為指揮官，分別向另外兩位（第一輪指揮官蘇秦除外）發(fā)送作戰(zhàn)信息“進(jìn)攻”。由于楚已經(jīng)叛變，他為了干擾作戰(zhàn)計劃，向另外兩位將軍發(fā)送了“撤退”作戰(zhàn)命令。

最終，齊和燕收到的作戰(zhàn)信息都是“進(jìn)攻、進(jìn)攻、撤退”。按照少數(shù)服從多數(shù)的原則，執(zhí)行“進(jìn)攻”指令，實(shí)現(xiàn)了作戰(zhàn)計劃的一致性。

2、叛將先發(fā)送作戰(zhàn)信息：

當(dāng)叛將先發(fā)送作戰(zhàn)消息，干擾作戰(zhàn)計劃時。在第一輪協(xié)商中，楚向蘇秦發(fā)送“進(jìn)攻作戰(zhàn)指令”，向齊、燕發(fā)送“撤退”作戰(zhàn)指令。蘇秦、齊、燕收到后并將其作為自己的作戰(zhàn)指令。

在第二輪作戰(zhàn)信息協(xié)商中，蘇秦、齊、燕分別作為指揮官，向另外兩位發(fā)送作戰(zhàn)信息。

最終蘇秦、齊、燕收到的信息都是“撤退、撤退、進(jìn)攻”，按照少數(shù)服從多數(shù)的原則，執(zhí)行“撤退”指令，實(shí)現(xiàn)了作戰(zhàn)計劃的一致性。

這個算法的前提：

1. 如果叛將人數(shù)為m，將軍人數(shù)不能少于3m+1（也就是：n位將軍，最多能容忍（n-1）/3 位叛將）。
2. 叛將數(shù)m決定遞歸循環(huán)的次數(shù)（進(jìn)行多少輪作戰(zhàn)信息協(xié)商），即m+1輪。

二忠一叛問題中，在存在1位叛將的情況下，必須增加1位將軍。那么有沒有辦法在不增加將軍人數(shù)的時候，直接解決二忠一叛的難題？可以通過簽名消息型拜占庭問題之解進(jìn)行解決。

解決辦法二：簽名消息型拜占庭問題之解

還可以通過簽名的方式，在不增加將軍人數(shù)的情況下，解決二忠一叛的難題。簽名具有如下的特性：

• 忠誠將軍的簽名無法偽造，而且對他簽名消息的內(nèi)容進(jìn)行任何更改都會被發(fā)現(xiàn)；
• 任何人都能驗(yàn)證將軍簽名的真?zhèn)巍?/li>

與口信消息型拜占庭問題之解類似，簽名消息型拜占庭問題之解同樣需要多輪協(xié)商。協(xié)商的過程也與口信消息型拜占庭問題之解類似，但最終執(zhí)行作戰(zhàn)計劃時并不是使用少數(shù)服從多數(shù)的原則。下面同樣以忠誠將軍和叛將分別先發(fā)送消息為例。

忠誠將軍先發(fā)送消息

第一輪協(xié)商中，忠誠將軍齊分別向楚和燕發(fā)送“進(jìn)攻”的作戰(zhàn)信息，燕和楚收到進(jìn)攻的作戰(zhàn)信息后將其作為自己的作戰(zhàn)消息。

第二輪協(xié)商中，楚和燕分別作為指揮官分別向另一位將軍（第一輪將軍除外）發(fā)送作戰(zhàn)信息。叛將楚修改或偽造作戰(zhàn)信息，將“撤退”信息發(fā)送給了燕。那么燕在收到楚的作戰(zhàn)信息的時候，會發(fā)現(xiàn)齊的作戰(zhàn)信息被修改，楚已經(jīng)叛變，這是燕會忽視來自楚的作戰(zhàn)信息，最終執(zhí)行齊發(fā)送的作戰(zhàn)信息。

叛將先發(fā)送消息

第一輪協(xié)商中，叛將楚向齊發(fā)送“撤退”的作戰(zhàn)消息，向燕發(fā)送“進(jìn)攻”的作戰(zhàn)消息。

第二輪協(xié)商中，燕和齊分別作為指揮官分別向另一位將軍（第一輪將軍除外）發(fā)送作戰(zhàn)信息。此時齊收到了[撤退、進(jìn)攻]兩個作戰(zhàn)消息，燕收到了[進(jìn)攻、撤退]兩個作戰(zhàn)消息。但是齊和燕會按照一定的規(guī)則在排序后的所有已接受的指令中選取一個（例如按照排序規(guī)則后的作戰(zhàn)順序?yàn)閇進(jìn)攻，撤退]，都選擇第一個作戰(zhàn)計劃）作戰(zhàn)計劃進(jìn)行執(zhí)行。最終執(zhí)行一致的作戰(zhàn)計劃。

齊、燕收到的信息列表是內(nèi)容是一樣的，只是順序不一樣，使用相同的排序算法，選取策略，可以保證選取的指令時一樣的

這個算法的前提是：

1、n位將軍，最多允許 （n-2）位叛將。

2、同樣需要多輪協(xié)商，如果叛將數(shù)位m，那么需要m + 1輪協(xié)商。

那如何實(shí)現(xiàn)簽名消息呢？

可以使用非對稱加密算法（如RSA），發(fā)送方使用哈希算法（如MD5）進(jìn)行摘要，然后使用私鑰對摘要進(jìn)行加密，生成數(shù)字簽名。然后將加密摘要和消息一起發(fā)送給接受方。接受方收到消息和加密摘要后，會用公鑰對加密摘要進(jìn)行解密，并對消息內(nèi)容進(jìn)行摘要，將兩個摘要進(jìn)行對比，以判斷消息是否被篡改。

私鑰加密，公鑰解密。可以保證消息不會被冒充，因?yàn)樗借€是不可泄漏的。如果公鑰能正常解密出私鑰加密的內(nèi)容，就能證明這個消息是來源于持有私鑰身份的人發(fā)送的。

感覺使用簽名消息型拜占庭問題之解會更消耗算力一點(diǎn)。

小結(jié)

將將軍作戰(zhàn)中的場景與計算機(jī)世界的分布式場景進(jìn)行對應(yīng)：

• 故事里的將軍，可以理解為計算機(jī)節(jié)點(diǎn)。
• 忠誠將軍，可以理解為正常運(yùn)行的計算機(jī)節(jié)點(diǎn)。
• 叛變將軍，可以理解為出現(xiàn)故障并會發(fā)送誤導(dǎo)信息的計算機(jī)節(jié)點(diǎn)。
• 信使被殺，可以理解為通訊故障、信息丟失。
• 信使被間諜替換，可以理解為通訊被中間人攻擊，攻擊者在惡意偽造信息和劫持通訊。

拜占庭將軍問描述的是最困難的，也是最復(fù)雜的一種分布式故障場景，除了存在故障行為，還存在惡意行為的場景。因此在存在惡意行為的場景中（如數(shù)字貨幣的區(qū)塊鏈技術(shù)中），必須使用拜占庭容錯算法（Byzantine Fault Tolerance，BFT）。除了上面提到的兩種算法（口信消息型拜占庭問題之解、簽名消息型拜占庭問題之解），常用的拜占庭容錯算法還有：PBFT算法，PoW算法。

在計算機(jī)分布式系統(tǒng)中，最常用的是非拜占庭容錯算法，即故障容錯算法（Crash Fault Tolerance，CFT）。CFT 解決的是分布式的系統(tǒng)中存在故障，但不存在惡意節(jié)點(diǎn)的場景下的共識問題。 也就是說，這個場景可能會丟失消息，或者有消息重復(fù)，但不存在錯誤消息，或者偽造消息的情況。常見的算法有 Paxos 算法、Raft 算法、ZAB 協(xié)議。

參考

• 分布式協(xié)議與算法實(shí)戰(zhàn) 學(xué)習(xí)筆記