ビザンチン将軍問題：視覚的な解説

ビザンチン将軍問題

忠実な将軍たちは、常に一致して行動できると確信できるのでしょうか？上記の物語には、2つの異なる問題が隠されており、コンピュータ科学者はそれらを別々に研究しています。最初の、二元将軍問題と呼ばれるものには、全員が正直ですが、騎兵が失われる可能性があります。2番目の問題では、すべての騎兵がたどり着きますが、誰かが嘘をついています。これがビザンチン将軍問題そのものです。どちらも驚くべき答えを持っています。一つずつ見ていきましょう。まず、ルールからです。

パズル1 · 迷子の伝令

「了解。」「君の『了解』を受け取った。」…

たった2人の将軍、AとB、どちらも完全に正直だとします。Aは夜明けに攻撃したいのですが、Bも攻撃する場合に限ります。唯一の危険は、彼らの陣営の間にある谷です。そこを越えて送られた騎兵は捕らえられる可能性があり、その将軍は決してそれを知りません。

予測

将軍Aは「夜明けに攻撃」と送ります。将軍Bは「了解」と返信します。両方の騎兵が偶然たどり着いたとしても、各将軍は自分に届いた騎兵のことしか知りません。今、それぞれが相手も攻撃することに確信を持てるでしょうか？

パズル2 · 裏切り者

序列の中の裏切り者

今度は危険を逆転させます。3人の将軍に戻りますが、今回は道は安全です。

予測

今やすべての伝令が到着しますが、3人の将軍のうち1人が裏切り者で嘘をつく可能性があります。2人の忠実な将軍は、いくらでも互いにメッセンジャーを送ることができます。彼らは常に同じ行動をとることができるでしょうか？

lieutenant 1 の視点から

1人の裏切り者が2人の忠実な将軍を打ち負かす方法を説明します。自分を lieutenant の一人の靴に例えてみてください。

4人目の将軍を追加する

今、3人目の lieutenant を追加し、同じ操作を続けます。司令官は各 lieutenant に命令を送ります。次に、各 lieutenant は他の2人に、受け取った命令を報告するメッセンジャーを送ります。最後に、各 lieutenant は、彼が現在持っている3つのバージョンの多数決に従います。2つのケースを順に見て、次に裏切り者の仮面を自分でつけてみてください。

裏切り者としてどのようにプレイしても、忠実な lieutenant たちの意見は一致します。嘘をつく lieutenant は、命令の2つの正しいコピーによって多数決で負かされます。嘘をつく司令官は、異なる lieutenant に異なる命令を送ることができますが、他の lieutenant が正直に中継するため、すべての忠実な lieutenant は同じ3つの値を持つことになり、全員が同じ多数決に達します。

これは一般的な規則であることが判明しました。裏切り者がメッセージに何でも好きなものを入れることができる場合、合意は将軍の3分の2より多い場合にのみ保証されます。裏切り者1人を含む3人の将軍では足りません。4人いれば十分です。

裏切り者の数をf、将軍の数をnと呼びます。裏切り者が何をしても、忠実な将軍たちが合意できることが保証されるためには、以下が必要です。

n ≥ 3f + 1

最も少ない将軍数:

適用

あるシステムには10台のコンピュータがあり、通常のメッセージを送信するため、嘘つきは何でも主張できます。嘘つきが最大何台まで許容され、それでも合意が保証されるでしょうか？

抜け道

現実のシステムがこの罠から抜け出す方法

このパズルは、航空機を飛ばすのに十分な信頼性を持つコンピュータを作成するためのNASA支援の研究から生まれました。エンジニアは不可能性を克服したことはありません。代わりに、次の3つの方法のいずれかでゲームのルールを変更します。

偽造不可能な封印

変更

すべての命令には、誰も偽造できない封印が付けられます。コンピュータでは、これはデジタル署名です。

得られるもの

どんな数の裏切り者でも合意が得られます。2人の裏切り者を持つ司令官の封印が2つの異なる命令に現れるため、3人の将軍でも十分です。

代償

すべての将軍は偽造できない封印を必要とし、すべてのメッセージは依然として到着する必要があります。

時計と締め切り

変更

メッセージが既知の時間内に到着すると仮定します。これはパズル2のルールからの締め切りであり、失われた騎兵がどのように認識されるかです。締め切りまでに彼が到着しない場合、彼は来ないということです。

得られるもの

PBFT（Practical Byzantine Fault Tolerance、1999年）のようなシステムは、ネットワークが遅い場合でも矛盾した回答を返すことはなく、メッセージが時間通りに到着する限り進歩し続けます。それらには3f + 1台のマシンが必要です。将軍の3分の2のルールが再び登場します。

代償

遅延が無制限である場合、たとえ1台のマシンしかクラッシュしない可能性があっても、どの方法も完了を約束することはできません。これは1985年に証明されました。

ほぼ確実で妥協する

変更

投票は、IDではなく計算能力によってカウントされます。それがビットコインの「プルーフ・オブ・ワーク」です。

得られるもの

攻撃者が10%の計算能力を持って5ブロック深く確認された支払いを元に戻す確率は約0.09%です。ブロックが増えれば、確率は小さくなりますが、ゼロになることはありません。

代償

正直なコンピュータが計算能力の大部分を制御している間のみ有効です。

予測

暗号通貨ファンが言います。「ビットコインはビザンチン将軍問題を解決した。一度支払いが確認されれば、元に戻すことは数学的に不可能だ。」どちらのバージョンが正確でしょうか？

覚えておくべきこと

• メッセージが失われる可能性がある場合、2つの側面は合意していることを決して確信できません。すべての確認には別の確認が必要です。
• メッセージは到着するが、誰かが嘘をつく可能性がある場合、合意が保証されるのは、3分の2より多い将軍が忠実な場合のみです。裏切り者1人を生き残らせるには4人の将軍が必要です。
• 現実のシステムはこれらの限界を打ち破りません。ルールを変更します。偽造不可能な署名、締め切り、または「ほぼ確実」です。

では、将軍たちは決して確信できるのでしょうか？ゲームのルールを変更した場合のみ、そしてそのルールが有効である限りにおいてのみです。

↑ 包囲を再演する