本文へ移動
Financial Context Wiki

ビザンチン将軍問題：矛盾するメッセージ下の合意

ビザンチン将軍問題は、故障参加者が矛盾情報を送れるときに正直な参加者がどう合意するかを問う。合意課題、通信路、認証、故障上限、下限、アルゴリズム、実装を分けて分析する。

更新日

プロトコル分析の教育目的に限ります。一つのビザンチン合意モデルを解けても、実ネットワークの安全性、ライブネス、実装の正しさ、分散性、ファイナリティ、資産保護は証明されません。

直接の答え

ビザンチン将軍問題は、メッセージで通信する正常な参加者が、一部の参加者が任意に振る舞い、受信者ごとに矛盾する主張を送れる状況で、どう一貫した決定に至るかを問う。軍事物語は分散システムの対話的一貫性を示す比喩であり、史実でも特定のブロックチェーン合意アルゴリズムでもない。

司令官と副官の定式化では、IC1 は全忠誠副官が同じ命令に従うこと、IC2 は司令官が忠誠なら全忠誠副官がその命令に従うことを求める。合意だけでは足りない。常に撤退を選べば一致はするが、忠誠司令官の有効な攻撃命令に反する。

論文の「口頭メッセージ」モデルでは、反逆者が最大 m 人なら、n>3m のときだけ解が存在し、整数人数では n>=3m+1 と同値である。このモデルは、忠誠者が送ったメッセージが正しく届き、受信者が送信者を識別し、期待メッセージの欠落を検出できると仮定する。「口頭」は未認証内容を別参加者からの報告として偽造できるという意味で、使者が永遠に消えても検知不能という意味ではない。

論文の「署名付きメッセージ」モデルは、偽造不能で誰でも検証できる署名を追加し、耐故障結果を変える。しかし署名内容を真実にせず、配信、完全非同期での終了、盗難鍵の保護、現代プロトコルの安全性も保証しない。ビザンチン将軍問題、二将軍または協調攻撃問題、FLP、BFT、Proof of Work、Proof of Stake は関連するが別のモデルや構成である。

分析方法

  1. 合意課題を定義する。 参加者、入力、出力、正確な合意、妥当性、終了特性を示す。司令官形式では単に「合意する」とせず、IC1 と IC2 を明記する。
  2. 識別子と通信路を定義する。 点対点メッセージの認証、確実な配信、順序、リプレイ防止、帰責性、欠落検出、ブロードキャストが基本機能か反復送信かを示す。
  3. 時系列モデルを定義する。 遅延上限のある同期、未知の安定化時刻後の部分同期、完全非同期を分ける。あるモデルに消える使者を追加し、別モデルの定理を維持してはならない。
  4. 故障予算を定義する。 総参加者 n、最大ビザンチン参加者 m、静的または適応的腐敗、欠落、矛盾送信、共謀、鍵盗難、通信路故障の範囲を記録する。
  5. 情報を再帰的に追跡する。 各忠誠参加者について、直接・中継主張、送信者経路、欠落時の既定値、決定的な同数規則を列挙し、二人のローカルビューが実行を識別できるか比べる。
  6. 定理とアルゴリズムを併せて確認する。 下限と十分性を正確な口頭または署名モデル、接続性、故障予算に対応させる。閾値式だけでは実装にも証明にもならない。
  7. 配備へ対応付ける。 実プロトコルの OM(m)、SM(m) または別機構、メッセージ領域、ラウンド、ロック、証明書、メンバー変更、タイムアウト、クライアント、ファイナリティ、アプリ確認方針を検証する。

主要な証明技法は識別不能性である。忠誠参加者が見られるのは自身のローカルメッセージだけで、二つの実行が同じに見えるのに妥当性が異なる決定を要求するなら、どの決定的規則も常に正しく選べない。十分な独立参加者、認証証拠、時間仮定、乱択などを加え、必要な実行を識別可能にするか、保証自体を変えることで進展する。

計算例

1. 三人の口頭メッセージで一人の反逆者に耐えられない理由

n=3、m=1 とする。必要条件 n>3m は 3>3 となり偽である。司令官 A が副官 B に ATTACK、C に RETREAT と伝えたとする。B は A が反逆者として矛盾命令を送ったのか、C が反逆者として A の発言を偽って報告したのか区別できず、C も対称な不確実性を持つ。

対応する「忠誠 A」の実行で司令官の命令を守る決定的選択は、「反逆 A」の実行で B と C に異なる選択をさせ得る。中継しても第四の独立情報源は生まれず、IC1 と IC2 を同時保証できない。

2. 四人の口頭メッセージと一人の反逆者

OM(1) で n=4、m=1 とする。司令官が三副官へ命令し、各副官が受信値を他二人へ中継し、忠誠副官は共通の多数決と既定値を使う。司令官が忠誠で v を送れば、忠誠副官は v、v、反逆者の可能な x を見て v を選ぶ。

司令官が唯一の反逆者なら三副官は全員忠誠で、受け取った内容をそのまま中継する。そのため全員が同じ司令官別主張集合を再構成し、同じ決定規則を適用する。司令官の「真意」は分からなくても合意は満たす。

3. 口頭メッセージの一般下限

n=7、m=2 では 7>6 が成立するため人数条件を満たし、他の仮定下で再帰的口頭メッセージ構成は最大二人の反逆者に耐える。n=6 では 6>6 は偽である。n=10、m=3 では 10>9 が成立する。式を満たすのは必要条件であり、ラウンド、中継、多数決、既定値、通信路の正しい実装が要る。

4. 署名が変えるもの

三人の SM(1) で、反逆司令官が B 向け ATTACK と C 向け RETREAT に署名する。忠誠副官が両方を中継するため、双方は同じ集合 {ATTACK, RETREAT} を得て、指定された同じ既定値、例えば RETREAT を選ぶ。司令官の矛盾送信は帰責できる。

モデル上、署名は忠誠者の命令の偽造や検知不能な改変を防ぐ。反逆者の二命令のどちらが「真意」かは示さず、適時配信を保証せず、正規秘密鍵を持つ攻撃者の二重署名も防がない。

リスクと検証上の失敗

問題とモデル

  • 正確な合意、妥当性、終了条件なしに物語だけを語る。
  • 問題を史実の包囲、単一アルゴリズム、ブロックチェーンの同義語とする。
  • 不可靠な通信路での共通知識を扱う二将軍問題と混同する。
  • 検出不能な永久損失を加えつつ、それを除く口頭メッセージ定理を引用する。
  • n>3m を全ての認証、非同期、加重、無許可、資源型プロトコルへ適用する。
  • クラッシュ、欠落、矛盾、任意計算、通信路故障、鍵侵害を同一の故障とする。
  • 参加者数を独立主体、ステーク、ハッシュ力、委員会重みと同一視する。
  • 妥当性で忠誠司令官と反逆司令官の違いを落とす。

アルゴリズムと実装

  • 最終多数だけを見て、再帰的送信者経路と各ローカルビューを追わない。
  • 実装ごとに欠落時既定値、同数規則、メンバースナップショット、順序が違う。
  • プロトコル、チェーン、課題、高さ、ラウンド、値、送信者、メンバー時期に結び付かないメッセージを受ける。
  • 実行、ラウンド、フォーク、ネットワーク、メンバー変更をまたいでメッセージを再生・接合する。
  • 署名が真実、新鮮さ、権限文脈、配信、可用性、正直な鍵保管を証明すると仮定する。
  • OM(m) や SM(m) を掲げるだけで必要なラウンド、中継、検証、接続性を実装しない。
  • 一つの反逆者配置だけを試し、司令官、副官、共謀、欠落、矛盾を試さない。

配備と解釈

  • 正確な安全性、ライブネス、ネットワーク仮定なしに「ビザンチンを解決した」と主張する。
  • バイト列の合意をアプリ実行やオフチェーン事実の正しさの証明とする。
  • 共通クライアント、運営者、クラウド、鍵系、ガバナンスによる相関故障を無視する。
  • 必要なファイナリティ前に入金反映、ブリッジ発行、不可逆決済を行う。
  • 耐障害ラベルから分散性、資産安全、法的真実、トークン価値を推論する。

よくある誤解

  • これは単なる 51% 攻撃である。 定義された合意モデルで任意・矛盾行動を扱い、資源多数攻撃は特定プロトコルの問題である。
  • 多数なら常に解ける。 古典的口頭モデルで m 人に耐えるには総数がその三倍を超える必要があり、忠誠者が一人多いだけでは足りない。
  • 電子署名はメッセージの真実を証明する。 鍵を認証し完全性を守るが、悪意または侵害済み鍵は虚偽や矛盾内容に署名できる。
  • 元の口頭結果は不可靠な配信を含む。 明示的な配信、送信者識別、欠落検出を仮定しており、別の時間・通信路モデルには別の結果が要る。
  • 合意すれば現実を知ったことになる。 別の検証規則がなければ、忠誠ノードも無効な出力や誤った外部データに合意し得る。

関連トピック

出典

ナビゲーション

Wiki を検索...