拜占庭將軍問題
Last updated
Last updated
提起，大家似乎感覺這項技術很神秘。今天從技術的角度剖析一下區塊鏈的分佈式一致性問題，很多研究人員稱此問題為分佈式領域的幽靈，也就是大家常常聽到的拜占庭將軍問題。
拜占庭將軍問題（The Byzantine Generals Problem）是Leslie Lamport（萊斯利·蘭伯特）提出的針對分佈式對等網絡中的通信容錯問題。
Leslie Lamport在其論文The Byzantine Generals Problem中以一個示例形象的描述了此問題：一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題，各支軍隊的行動策略僅限定為進攻或撤離兩種。因為部分軍隊進攻、部分軍隊撤離可能會造成災難性後果，因此各位將軍必須通過投票來達成一致策略，即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分別處於城市不同方向，他們只能通過信使互相聯繫。在投票過程中每位將軍都將自己投票給進攻還是撤退的信息通過信使分別通知其他所有將軍（此假設中，將軍可能是叛徒，發送錯誤信息等），從而，每位將軍根據自己的投票和其他所有將軍送來的信息就可以知道共同的投票結果而決定行動策略。
用通信術語描述拜占庭將軍問題：可靠的計算機系統必須處理有故障的組件，這些組件的引入可能與系統其它部分信息衝突[1]。根本不發送任何消息，向不同的鄰居發送不同且錯誤的消息，以及謊報自己的輸入值[2]。一個可靠的計算機系統必須能夠處理一個或多個組件的失敗。失敗的組件出現被忽略的行為，向系統的其他部分發送不一致的信息。
在分佈式計算中，不同的計算交換通訊信息從而達成共識並按照同一套協作策略行動。但有時，系統中的成員計算機可能因出錯而發送錯誤的信息，用於傳遞信息的通訊網絡也可能導致信息損壞，使得網絡中不同的成員關於全體協作的策略得出不同結論，從而破壞系統一致性。
拜占庭將軍問題是存在前提假設條件的，在消息丟失的不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的，因此對一致性的研究一般假設是建立在信道是可靠的這個前提下。拜占庭將軍問題的核心是允許存在少數節點作惡（消息存在被偽造的可能性）的情況下如何達成共識的問題。
拜占庭將軍問題實際上是如何讓一個分佈式系統的保持一致性和在特定條件下保持正確性的問題。可抽象為滿足以下2個條件的算法：
條件IC1. 所有忠誠的將軍得出相同的作戰指令，並且按指令執行（正常處理單元必須使用相同的輸入值），保持指令的一致性。
條件IC2. 如果作戰指令是忠誠的將軍發出的，所有忠誠的將軍會遵循該將軍發出的作戰指令（如果輸入單元是正常的，那麼每個正常的單元都應該使用它提供的值作為輸入），特定條件下的正確性。
Leslie Lamport論文裡The Byzantine Generals Problem提到了Oral Messages和Signed messages兩個解決方案，其算法如下：
結論： 如果有m個叛軍，必須至少有 3m+1位將軍（包括背叛和忠誠的將軍）才能保證口頭協議算法（簡稱OM算法）能解“拜占庭將軍問題”。
前提假設：
A1. 每個被發送的消息都能夠被正確的投遞
A2. 信息接收者知道是誰發送的消息
A3. 能夠知道缺少的消息(如果叛軍不配合發送消息，算法默認一個值 “撤退”的來替代)
證明過程：
結論：在不管有多少叛軍的情況下，都能讓忠誠的將軍們保持一致的行動
前提假設：
A1. 每個被發送的消息都能夠被正確的投遞
A2. 信息接收者知道是誰發送的消息
A3. 能夠知道缺少的消息(如果叛軍不配合發送消息，算法默認一個值“撤退”的來替代)
A4.1 簽名不可被偽造，一旦被篡改即可發現
A4.2 任何人都可以驗證將軍簽名的可靠性
證明過程：
