ビットコイン技術中級

ビザンチン将軍問題

ビットコインがプルーフ・オブ・ワークによって巧みに解決した、分散コンピューティングにおける古典的な合意形成問題。

26.03.11 · 1分

ビットコインが誕生する前に、コンピュータ科学者たちはある一見シンプルな問いと格闘していました。互いを信頼しない参加者のグループが、どうすれば一つの行動方針に合意できるのか？ この問いは「ビザンチン将軍問題」として定式化され、分散型デジタル通貨を実現する上で最大の障壁の一つでした。サトシ・ナカモトの画期的な業績は、単に通貨を作ったことではなく、数十年にわたり研究者を悩ませてきたこの問題を解決したことにあります。

元の問題

1982年、コンピュータ科学者のレスリー・ランポート、ロバート・ショスタク、マーシャル・ピーズが画期的な論文を発表し、次のような状況を提示しました。ビザンチン帝国の複数の軍団が敵の都市を包囲しています。各軍団にはそれぞれ将軍がおり、攻撃を連携する必要があります。将軍同士は伝令を通じてのみ通信が可能です。問題は、将軍の中に計画を妨害するため矛盾したメッセージを送る裏切り者がいる可能性があることです。

忠実な将軍たちには、以下の二つを保証するプロトコルが必要です。

すべての忠実な将軍が同じ計画に合意すること（全員が攻撃するか、全員が撤退する）
少数の裏切り者が、忠実な将軍に誤った計画を採用させることができないこと

この論文は、純粋なメッセージベースの通信では、将軍の3分の1以上が裏切り者である場合に合意が不可能であることを証明しました。この結果は深い意味を持ちました。メッセージ交換のみに依存する分散システムは、根本的に組織的な欺瞞に対して脆弱であるということです。

デジタル通貨にとっての重要性

デジタル通貨は本質的に合意形成の問題です。ネットワークのすべての参加者が「誰が何を所有しているか」について合意する必要があります。物理的な世界では簡単です。金貨を手に持っているか、持っていないかのどちらかです。しかしデジタルの世界では、データはコピー可能で、メッセージは偽造でき、参加者は嘘をつくことができます。

従来の金融システムは、信頼できる権威者を指名することでこの問題を解決してきました。銀行が公式の台帳を管理し、Visaが取引の有効性を確認し、PayPalが支払いの可否を判断します。これは機能しますが、単一障害点（そして単一の支配点）を生み出します。

数十年にわたり、サイファーパンクたちは中央権威者なしにデジタル通貨を実現することを夢見ていました。しかしビザンチン将軍問題が、それを不可能にしているように見えました。信頼できる調整者がいなければ、世界中の何千もの匿名コンピュータが一つの取引履歴に合意するにはどうすればよいのか？

ビットコインはどう解決したか

サトシ・ナカモトのイノベーションは、ゲームのルールそのものを変えたことにあります。メッセージ交換だけでビザンチン合意を解こうとするのではなく、ビットコインはプルーフ・オブ・ワークを通じて参加に物理的なコストを導入しました。

核心的な洞察はこうです。元の問題ではメッセージの送信はタダであり、裏切り者は矛盾するメッセージを無制限にコストなく送ることができます。ビットコインでは、ブロックの提案（将軍のメッセージに相当）に暗号パズルを解くための実際のエネルギーの消費が必要です。これにより嘘をつくことが計算上非常に高コストになります。

その仕組みは以下の通りです。

ブロックを提案するために、マイナーは現在の難易度ターゲットを満たすハッシュを見つける必要があります。これには数兆回の計算と実際の電力が必要です
履歴を書き換えるために、攻撃者は変更したいすべてのブロックのプルーフ・オブ・ワークをやり直した上で、正直なネットワーク全体のペースを上回り続けなければなりません
正直な行動にはブロック報酬と取引手数料という報酬がある一方、ネットワークへの攻撃には数十億ドルのハードウェアと電力コストがかかります。しかも攻撃者は、自分が盗もうとしている資産そのものの価値を破壊してしまうのです

ビットコインは裏切り者の可能性を排除したのではありません。裏切りを非常に高コストにすることで、合理的な行為者が常に協力を選ぶようにしたのです。このプロトコルは、ゲーム理論の問題を経済学の問題に変換しました。

確率的合意と決定論的合意

従来のビザンチン障害耐性アルゴリズムは決定論的な合意を実現します。一度合意されれば、その決定は最終的です。ビットコインは確率的合意という異なるアプローチを取ります。取引が絶対的に確定することはありませんが、その上に新しいブロックが追加されるたびに、取消しの確率は指数関数的に低下します。

1回の承認後でも、取消しには莫大な計算能力が必要です。6回の承認後には、事実上不可能になります。数十回の承認後には、一部の国の発電量を超えるエネルギーが必要になります。この確率的ファイナリティは弱点ではなく、参加者が誰であるか、何人いるかを知らなくてもシステムが機能するための特徴なのです。

ナカモト・コンセンサスの優雅さ

ビットコインの解決策が際立っているのは、そのシンプルさにあります。最も長い有効なチェーンが勝つ。 それだけです。すべてのノードが独立にすべてのブロックを検証し、最も多くのプルーフ・オブ・ワークが蓄積されたチェーンに従います。投票もなく、リーダー選出もなく、メンバーシップ名簿もありません。誰でもいつでも参加・離脱できます。

これは、Practical Byzantine Fault Tolerance（PBFT）のような以前のアプローチとは対照的です。PBFTではネットワーク参加者の正確な数を把握し、複数ラウンドのメッセージ交換が必要でした。そのようなシステムは小規模で既知のグループには機能しますが、グローバルでオープンなネットワークにはスケールしません。

ビットコインは、合意を物理的現実（エネルギー消費）に固定することで、何百万もの匿名参加者間で信頼できる合意を達成できることを示しました。ビザンチンの将軍たちは互いを信頼する必要がないのです。最も多くの作業が蓄積されたチェーンに従えばよいだけです。

ビットコインにとっての意義

ビザンチン将軍問題は単なる歴史的トリビアではありません。過去のすべてのデジタル通貨の試みが失敗し、ビットコインが成功した根本的な理由そのものです。この問題を理解することで、プルーフ・オブ・ワークが無駄ではなく不可欠であることが明らかになります。それは電力を信頼に変換するメカニズムであり、信頼できる権威者を必要としない通貨の形態を可能にするものです。

サトシ・ナカモトは元のホワイトペーパーにこう書いています。「ネットワークはトランザクションをハッシュベースのプルーフ・オブ・ワークの連鎖にハッシュすることでタイムスタンプを付与し、プルーフ・オブ・ワークをやり直さない限り変更できない記録を形成する。」この一文で、数十年にわたる不可能性の結論が克服されたのです。