拜占庭將軍問題 Byzantine Generals Problem

這是學術界Leslie Lamport，Robert Shostak，Marshall Pease 早在80年代提出的問題，與2009年誕生的比特幣有莫大關係.

先看一下他們在1982年7月份的ACM Transactions of Programming Languages and Systems罕登的原文:

2This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger，the generals must agree upon a common battle plan. However，one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement.

(原文可參考: https://www.microsoft.com/en-us/research/uploads/prod/2016/12/The-Byzantine-Generals-Problem.pdf)

小編幫忙翻譯一下:
假設有一組拜占庭將軍準備攻佔一座敵軍城池，將軍們依靠通訊兵傳送訊息. 將軍們必須要達成共識: 一起進攻或一起撤退，如果只有部份將軍進攻，那些將軍將會全軍覆沒。問題是，將軍當中可能有叛徒嘗試發出錯誤訊息，例如我告訢將軍A我會進攻，又告訴將軍B我會撤退. 就算保證所有將軍都是忠誠的，也難以保證通訊兵傳送訊息期間被敵軍截獲並篡改訊息。

到底要如何才能保障忠誠將軍的安全呢? Byzantine Impossibility Result證明了: 只有在叛徒將軍不超過三分之一的情況下才能確保忠誠將軍的安全。假設有三個將軍甲乙丙，甲告訴乙進攻，告訴丙撤退，只要乙和丙之間互相確認甲的訊息，就可以知道甲是叛徒; 但如果甲乙都是叛徒，那麼丙就只有乖乖等死的份…

後期論文提出了更多方法，比如所有將軍都不同向其他將軍發出自己已知的訊息，直至收到對方回覆確認，並再確認對方的回覆確認，並確認對方確認你的回覆確認……但代價是要花費更多的通訊時間。

這些將軍和比特幣有甚麼關係呢?

在分散式計算系統當中，將軍們就是分散不同地方的伺服器，通訊兵就是網絡，將軍叛徒可能是被駭的伺服器 比特幣是一個分散式系統，礦工就是將軍，通訊兵是互聯網，將軍叛徒是惡意篡改交易資料的礦工

如果無法解決定拜占庭將軍問題，則很難確保惡意礦工透過發放假交易，來破壞比特幣區塊鏈的正確性。

比特幣厲害之處，就是透過工作量證明(Proof-of-work)方法解決了拜占庭將軍問題，更重要的是比特幣會給挖礦獎賞予正直將軍，吸引叛徒棄暗投明; 而且比特幣系統達成共識的時間較長，以6次confirmation計算大約需時1小時，沒人可以肯定有哪些交易可以在1小時內拿到6次confirmation，以上種種與傳統分散式系統的差異，與及破格的解決方式，使比特幣在學術界大放異彩，也造就比特幣今天的成功。

---

延伸閱讀