What is Byzantine Generals Problem？

拜占庭問題Byzantine Generals Problem由獲得圖靈獎的Leslie Lamport、Robert Shostak、和Marshall Pease於1982年提出了一個思維實驗，其論文《The Byzantine Generals Problem》中主要是為了網路中通信的一致性而煩惱，以拜占庭帝國為例，拜占庭帝國派出了 10 支軍隊去攻打實力不如其確能抵擋5 支軍隊的圍攻的帝國，若拜占庭軍隊想獲勝，就必須不小於6 支的軍隊同時進攻，但拜占庭的 10 支軍隊要靠通信兵彼此傳信來協商策略，國王怕奸臣，將軍怕叛徒與間諜，要讓好的將軍們達成一致共識後，才有勝利可言，因此要如何在有叛徒的干擾下，還能達到一致共識便是我們要討論的問題。

叛徒和間諜做的事情就是要讓軍隊一盤撒沙，將軍們要做的是凝聚團隊力，在論文中指出，對於拜占庭問題來說，假如節點總數為 N，壞節點數為 F，則當 N >= 3F + 1 時，問題才能BFT 演算法進行保證；其中也證明，當叛變者不超過 1/3 時，存在有效的BFT演算法（最壞需要 F+1 輪交互），反之，如果叛變者過多，超過 1/3，則無法保證一定能達到一致結果。叛徒或間諜發送前後不一致的進攻或撤退提議，被稱為「拜占庭錯誤」，而能夠處理拜占庭錯誤的這種容錯性稱為「拜占庭容錯BFT, Byzantine fault tolerance」。

可能性為：
• 叛徒或間諜可能欺騙某些將軍自己將採取進攻或撤退的行動。
• 叛徒或間諜可能迷惑其他將軍，使他們接受不一致的資訊，從而感到迷惑。

非對稱加密可解決辦法：

• 限制一段時間內提案的個數，只有擁有最高權限的將軍(節點)可以發出消息。在比特幣裡，誰是第一個答對問題的節點，就有權限發出宣告。
• 在消息要傳出去前，一將軍必須要簽名並蓋上一個時間章(戳)，以此代表自己發言的正確性，並且用要傳給二將軍的公用密鑰來加密；當消息傳出去後，收到消息的二將軍要用自己的私密密鑰來解密，以此來證實接收內容的真實性，在消息上簽名並蓋上時間章後，再傳給其他將軍，其他將軍便可用二將軍的公鑰來驗證這個簽名是否有正確的可信任度。

另有所謂的兩將軍問題，但這與拜占庭將軍問題本質不同，就不多加討論。

文章另會分享在stars blog中，歡迎一起交流。