Byzantine Generals Problem

街を囲んで配置された部隊を想像してください。全員で攻撃するか、全員で撤退する必要があり、行動が分かれると壊滅しかねません。司令官は命令を送りますが、誰かが裏切り、相手によって違う話をするかもしれません。信頼できる参加者は、どうすれば最後に同じ行動を取れるでしょうか。これは実際の戦争の記録ではなく、一致した記録を保つコンピューターのための思考実験です。たとえば共通のサービスを提供する複数のコンピューター、つまりサーバーで、ある支払いが処理済みかどうかを同じように判断する必要があります。何らかの返答が届くだけでは足りず、それらが共通の決定につながらなければなりません。 [1] [9]

Leslie Lamport、Robert Shostak、Marshall Peaseは、故障下での合意を扱った1980年の研究に続き、1982年7月にこの有名な形で問題を示しました。裏切り者は、振る舞いを予測できなくなったシステムの部品を表します。コンピューターは単に停止するとは限りません。一方には正しい返答を、別の相手には誤った返答をし、メッセージを省いたり、違う情報を見たと主張したりできます。原因は攻撃とは限らず、プログラムの不具合の場合もあります。ビザンチン故障が表すのは周囲から見える振る舞いで、機械の意図ではありません。BFT (Byzantine Fault Tolerance)は、定められた条件でそのような振る舞いに耐える能力を意味します。 [1] [2]

元の問題には二つの条件があります。IC1は、信頼できる部下が全員同じ命令を受け入れること。IC2は、司令官も信頼できるなら、実際にその司令官が送った命令を受け入れることです。後者がなければ「いつも撤退する」で解決したように見えますが、正直な司令官を無視してしまいます。計算機では、矛盾した結果を防ぐ安全性と、そもそも結果に到達できる活性を区別します。どの結果が妥当かは、さらに別の規則が定めます。記録が一致しても、入力された主張が現実世界で真実だった証明にはなりません。 [1] [9]

司令官をA、部下をBとCとします。CはAから攻撃命令を受けますが、Bは「司令官は撤退と言った」と伝えます。嘘をついているのはBでしょうか。それともAが違う命令を送ったのでしょうか。転送後にも確認できる署名がなければ、Cは区別できないかもしれません。Bにも同じ不確実性が生じます。常に司令官に従えば不正なAが二人を分断でき、常に無視すれば正直な司令官についての条件を満たせません。この三人、一人が裏切る可能性がある問題では、署名なしで常に成功する手順は存在しません。足りないのは状況を見分ける情報であり、速いコンピューターではないのです。 [1] [9]

署名を使わない古典的モデルでは、最大m人の裏切り者に耐えるために少なくともn ≥ 3m+1人が必要です。nは参加者の総数、mは対応すべき裏切り者の最大数です。一人に備えるなら四人です。単に一票増やして一度多数決を取るという意味ではありません。OM(m)は、聞いた内容を繰り返し転送し、共通の規則で評価する手順です。基本のOM(0)は司令官の値、または合意済みの既定値を採用します。モデルは参加者が既知で、直接通信でき、送信したメッセージが正しく届き、直前の送信者が分かり、メッセージの欠落を検出できると仮定します。「署名なし」は「出所を全く認証しない」ではありません。この前提を外せば、四という数字だけでは何も保証できません。 [1] [9]

検証できる電子署名、Digital Signatureがあれば、Bは司令官が実際に署名した内容をCに示せます。プログラムは秘密の数値である秘密鍵を使って署名を作ります。他の参加者は、秘密鍵を知らなくても、対応する公開鍵で署名を検証できます。裏切り者は信頼できる参加者の命令を気付かれずに書き換えたり、その署名を偽造したりできません。署名付きメッセージのアルゴリズムは、署名された値を伝え、共通の選択規則を使います。このモデルでは先ほどの正直な多数派という条件が不要になりますが、署名の偽造不能性、配送、ラウンドの時間条件は残ります。DolevとStrongの1983年の研究は必要なラウンド数をさらに扱っています。署名が有効でも、内容が正しいことや期限内に届くことは保証されません。秘密鍵が盗まれていない証明にもなりません。特定のメッセージの出所を示すのであり、送信者を全面的に信用できる証明ではありません。 [1] [3]

サーバーが返答しないとき、ほかの参加者には停止したのか、接続が非常に遅いだけなのか分かりません。Michael Fischer、Nancy Lynch、Michael Patersonが1985年に発表したFLPの結果は、この不確実性を厳密に示します。ここでいうプロセスは、実行中のプログラムです。決定的な手順は、状態と入力が同じなら同じ次の処理を行い、その処理をランダムには選びません。遅延の上限が分からない完全非同期システムでは、一つのプロセスが停止故障する可能性があるだけで、決定的な手順は許されるすべての実行で合意の完了を保証できません。確実に配送されても遅延に上限がなければ同じです。合意が一度も成立しないという意味ではありません。実用システムは時間の仮定、適切な故障検出器、または乱数を加えます。ネットワークが分断されたときは、矛盾した結果を確定するより待つ方が安全な場合があります。 [4] [13] [8]

Miguel CastroとBarbara Liskovは1999年、既知の複製サーバーで動くサービス向けにPractical Byzantine Fault Tolerance、PBFTを示しました。これは、異なるサーバーで同じサービスを動かし、同じ要求を継続的に処理する構成です。保管しておくバックアップファイルではありません。基本構成n = 3f+1はf台の故障を許容します。四台なら一台がビザンチン故障してもよく、三台ずつの二組には少なくとも二台が共通し、そのうち一台以上は信頼できます。この必要な賛同の集合をクォーラムと呼びます。ただし重複だけでは不十分で、各段階やリーダー交代の規則も必要です。詳しくは、prepared状態には要求、pre-prepareメッセージ、プライマリ以外の異なる複製サーバーからの一致する2f件のprepareが必要です。ローカルな確定にはさらに2f+1件のcommitが必要で、自分のものを含められます。認証、通し番号、チェックポイントが偽造、再送による重複処理、ログの無制限な増大に対処します。安全性は時間上限に依存しませんが、処理の進展には遅延について追加条件が必要です。 [5] [10] [11] [12]

Bitcoinには、あらかじめ閉じたサーバー名簿がありません。新しいアカウントごとに一票なら、攻撃者は多数派を作れてしまいます。これがSybil Attackです。そこでProof of Workはブロック作成を計算作業に結び付けます。ブロックは、共有する履歴に追加する取引のまとまりです。検証用ソフトウェアを動かして自分で規則を確かめるコンピューターであるFull Nodeは、まず無効なブロックを拒み、有効な枝のうち累積作業量が最大のものを追います。BitcoinはOMやPBFTを実行せず、一時的な分岐を許容します。正直な計算能力の割合と通信条件が適切なら、確認が増えるほど履歴の書き換えリスクは下がりますが、絶対に覆らないわけではありません。Bitcoin Backboneの研究は、履歴の一致、チェーンの成長、正直な参加者が作るブロックの割合について、まさにその条件を調べています。 [6] [7]

「ネットワークが合意する」と聞いたら、誰が参加でき、攻撃者は何を支配でき、メッセージはどれほど遅れてよく、決定はいつ変わり得るのかを確認しましょう。Proof of Workもすべての問題を消しません。Eclipse Attackはノードを正直な相手から隔離し、検閲は取引を除外し、Selfish Miningは採掘済みブロックの公開を遅らせます。ソフトウェアの不具合や、十分な攻撃能力による履歴の一部の書き換えも残ります。それでも計算能力の過半数で、正常なFull Nodeに規則違反のブロックを受け入れさせることはできません。将軍の物語が役立つのは、技術の名前ではなく、合意の条件を確かめる姿勢を教えてくれるからです。 [6] [7] [8]