ビザンチン将軍問題は、故障したプロセスが任意に振る舞い、相手によって矛盾するメッセージを送るとき、正常なプロセスが一つの決定に合意できるかを調べる。Lamport、Shostak、Pease の1982年の定式化は、署名のない口頭メッセージで m 人の裏切りに耐えるには最低 3m+1 人が必要と証明し、口頭および署名付きメッセージの再帰アルゴリズムを示した。結果は厳密な前提に依存し、あらゆるブロックチェーン合意の同義語ではない。
Lamport、Shostak、Peaseは複製システムの対話的一貫性を説明するため、1982年7月にACM TOPLASでこの寓話を発表した。離れた将軍は一つの作戦を選ぶが、裏切者は相手ごとに異なる主張を送れる。ビザンチン故障は停止故障より強く、嘘、矛盾送信、欠落、観測者ごとに異なる正常らしさを含む。 [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
論文はIC1「忠実な副官は全員同じ命令に従う」とIC2「司令官が忠実なら、その命令に従う」を区別する。現代の関連語は合意または安全性、妥当性、終了または活性である。ネットワーク、認証、最大故障数を明示しなければ保証の意味は定まらない。 [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]
口頭メッセージ模型では直送者が分かり、欠落を検出でき、全組が通信できるが、裏切者は異なる値を送れる。OM(m)は値を再帰転送し決定的多数を取る。m故障を許すには最低3m+1、すなわち忠実者が三分の二を超える必要がある。三者では一人の裏切者の役割を忠実者が識別できない。 [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]
偽造不能署名は矛盾送信を露呈し、忠実者の署名命令の改変を防ぐ。算法は未見の署名値を中継し、収集集合に同じ決定規則を適用する。理想的署名仮定では任意数の裏切者を扱える。ただし署名は出所を証すだけで、内容の真実、期限内配送、侵害鍵の誠実性は保証しない。Dolev–Strongは後にラウンド境界を厳密化した。 [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]
進行を保証できるかは通信の時間条件による。1985年のFischer–Lynch–Patersonの結果は、完全非同期の決定的なメッセージ通信システムでは、停止故障が許されるプロセスが一つあるだけでも、合意が終了しない許容実行が存在することを示す。FLPは実際のシステムが決して合意できないとは述べていない。活性の保証には、やがて成立する時間上限や特定の性質を持つ故障検出器などの追加仮定、あるいはランダム化プロトコルへの変更が必要になる。リーダーを任命するだけでは足りない。長いネットワーク分断では、安全なプロトコルが操作の完了を止めることがある。 [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
Miguel CastroとBarbara Liskovが1999年に発表したPBFTは、ビザンチン合意を複製状態機械に適用する。基本構成n = 3f+1でf個のビザンチン複製に耐える。準備完了には主複製からのpre-prepareと一致する2f通のprepareが含まれ、局所的な確定には準備完了と一致する2f+1通のcommitが必要になる。定足数の交差とビュー変更規則が矛盾した確定を防ぐ。認証、通し番号、チェックポイント、ビュー変更は、偽造、再送攻撃、ログ増大、不正なリーダーに対処する。既知の複製集合と決定的な確定性は、開かれたProof of Workネットワークとは異なる。 [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]
BitcoinはOMやPBFTを実行せず、名前の付いたノードを数えない。Sybil攻撃に耐えるProof of Workが競合する履歴を累積作業量で重み付けし、各Full Nodeは合意規則に違反するブロックを独立に拒否し、累積作業量が最大の有効なチェーンを追う。一時的な分岐は想定内である。正直な作業量の優位と通信条件の仮定の下で、書き換えの確率は承認の深さとともに下がるが、数学的な不可逆性ではない。Bitcoin Backboneモデルは、攻撃側の作業量の割合とネットワーク条件を明示して、共通接頭辞、チェーン成長、チェーン品質を形式化する。 [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]
Bitcoinがビザンチン将軍問題を解いたという言い方は、モデルの変更を隠してしまう。古典的合意は身元が既知の固定集団と故障上限fから始まるが、Bitcoinは変動する仮名参加者と外部の希少資源を認める。その保証にもメッセージ配送について具体的な仮定が必要である。Proof of WorkはSybilの身元数による影響を抑えるが、エクリプス攻撃、検閲、利己的採掘、ソフトウェアの誤り、多数ハッシュレートによる再編を防ぐわけではない。脅威モデルでは攻撃者、時間条件、参加資格、確定性を定める必要があり、BFTという表示だけでは足りない。 [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]
理解を深めるには、この項目とあわせて次もお読みください Nakamoto consensus, Proof of Work, コンセンサス規則, 二重支払い, Bitcoin, Finality.