ビザンチン将軍問題を解決したプルーフ・オブ・ワーク
ビットコインを発明し、未だその正体が分かっていないサトシ・ナカモト。そんなサトシが残した約2年間の文章を、小宮自由氏の解説と共に紹介する連載「サトシ・ナカモトが残した言葉〜ビットコインの歴史をたどる旅」の第11回。
まずサトシのメールの前に、本連載の元になっている書籍『ビットコイン バイブル：サトシナカモトとは何者か？』の著者フィル・シャンパーニュ氏の解説も掲載する。
フィル・シャンパーニュ氏の解説
サトシの投稿のうちで最も興味深いものがある。それは、「ビザンチン将軍問題」として知られるコンピューター科学上の問題点を、ブロックチェーンを用いていかにして解決するか、を論じた投稿である。これは「二人の将軍問題」の一般的なバージョンで、二人（ないし、二人以上）の人物が信頼の置けない通信環境下で情報を共有しなければならず、メッセージが喪失したり改ざんされたりする可能性がある場合に生ずる問題である。この問題の言及は1970年代にネットワークコンピューターの文献で最初に登場し、当時は解決不可能とされていた。この投稿で、サトシは、ビットコインがこれを解決すると主張している。
この問題を説明する上で、二人の将軍がある都市を同時に攻撃する状況をイメージしよう。片方が攻撃し、もう片方が攻撃しなかったならば、攻撃した将軍の軍隊は都市の守備隊により全滅する。二人の将軍の間の通信環境は信頼性に欠けた状況にある。伝令が攻撃時刻を告げるメッセージを運ぶが、都市を通らなければならず、捕捉されて届かない危険がある。第一の将軍は、今日中に攻撃を実行するという内容のメッセージを伝令に託し、九時までに急派する。
しかし、一度伝令を放てば、無事に到着できたかどうかを知るすべはない。この不確実さゆえに、もし第二の将軍がメッセージを受け取らなかったら自分一人で攻撃することになるため、攻撃を躊躇することもありうる。
第二の将軍は、第一の将軍の内心を全て見通しつつ、メッセージの受領を知らせるため、確認の返事を出す。しかし、この返事もまた、届かない危険があり、第二の将軍もまた、躊躇する。第一の将軍は確認の確認を送るが、これもやはりまた、捕捉の危険があり、それゆえに、第一の将軍も、第二の将軍の最初の確認に対するこの確認への確認が戻ってこなければ躊躇する。どちらの将軍も、メッセージが無事到着したか、敵に捕捉されたか、知るすべがないまま、このプロセスは無限に続くことになる。
詳しくは次のウィキペディア記事「二人の将軍問題」を読んでいただきたい。また「ビザンチン将軍問題」の記事も参照いただきたい *1。
【訳注】
*1 原著では英語版の記事が示されている。
サトシ・ナカモト 2008年11月2日17時56分27秒のメール
それでは2008年11月2日17時56分27秒のサトシのメールを見てみよう。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
Re：ビットコイン ピア・ツー・ピア 電子キャッシュ 論文
（注：斜体部分は、サトシ以外の者の質問を指す）
サトシ・ナカモト 2008年11月13日 木曜日 19時34分25秒 -0800
James A. Donaldは書きました：
みんながXを知っているだけでは十分ではありません。みんながXを知っている事実をみんなに知ってもらう必要もあり、みんながXを知っている事実をみんなが知っていることをみんなに知ってもらう必要もあります。これは、ビサンチン将軍問題と同じく、分散型のデータ処理における古典的な難題です。
プルーフ・オブ・ワークがビザンチン将軍問題の解決策になります。この文脈で言い換えてみます。
大勢のビザンチン将軍が各自、コンピューターを持ち、パスワードの暴力的突破により国王の WiFi を攻撃しようとしています。このパスワードはある個数の文字列である、と将軍たちは聞いています。ネットワークに命じてパケットを生成すると、制限時間内にパスワードを突破し、ログに侵入して消去しなければなりません。できなければ、見つかって面倒なことになります。彼らのCPUパワーは、大多数が同時に攻撃すればパスワード突破に成功できる、という程度の規模でしかありません。
攻撃が何時になるかは特に問題ではなく、重要になるのは全員が同意した事実だけです。その気になった者が時刻を告知する、最初に聞いた時刻が公式の攻撃時刻になる、と決められています。問題はネットワークが即時的でない点で、二人の将軍がほぼ同時に別々の攻撃時刻を告知すると、人によってどちらを最初に聞いたかで二つに分かれてしまいます。
この問題の解決にプルーフ・オブ・ワーク・チェーンを用います。指定の攻撃時刻が最初に届いた時点から、将軍たちはコンピューターをセットし、攻撃時刻をハッシュに含むプルーフ・オブ・ワークの難題の解決にとりかかります。プルーフ・オブ・ワークの難題の解決には、全員が同時に作業を始めてから、誰か一人が解答を見つけるまでに10分かかる見込みです。誰か一人が解答を見つけると、ネットワークにブロードキャストされます。ここで、全員が、現在のプルーフ・オブ・ワークの計算作業を変更し、解答の見つかったプルーフ・オブ・ワークを現在作業中のハッシュに含めるよう作業を進めます。別の攻撃時刻を作業中だったとしても、こちらのプルーフ・オブ・ワークの方が長くなるので、こちらに切り替えます。
二時間後には、12のプルーフ・オブ・ワーク・チェーンが一つの攻撃時刻をハッシュします。将軍たちは、プルーフ・オブ・ワーク・チェーンの難易度を検証し、同時に消費された一時間当たりのCPUパワーを見積って、その時間内にそれだけのプルーフ・オブ・ワークの産出に成功するには、過半数のコンピューターが必要とされたのだと知ることができます。全員がこれを知らなければなりません。なぜなら、彼らが作業した事実の証明がプルーフ・オブ・ワークだからです。プルーフ・オブ・ワーク・チェーンで示されたCPUパワーがパスワードの破壊に十分なら、合意した時刻の攻撃に安心してとりかかれます。
プルーフ・オブ・ワークのチェーンは、ご質問にあった同期、分散型データベース、グローバルな視点の問題というように、これら全ての解決策になります。
暗号学メーリングリスト
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
解説
プルーフ・オブ・ワーク（Proof of Work/PoW）は複数の重要な未解決問題を解決した画期的発明です。その重要な問題の一つがここで言うビザンチン将軍問題です。
ざっくり言うと「遠くにいるよく知らない人たちと協力しなければならないときに、どうやって足並みを揃えるか」という問題です。遠くにいるので対面で話し合うこともできず、よく知らないので完全に信頼することもできない。そういう状況で大勢の協力が必要なときに、足並みを揃えるのは並大抵のことではありません。
ビットコインネットワークは、他の参加者と離れていても（インターネット越しなので当然です）成立しますし、嘘をつく参加者がいても成立します。つまり、ビザンチン将軍問題を完全に解決しており、それはまさにプルーフ・オブ・ワークの賜物なのです。
プルーフ・オブ・ワークにおいては前提があります。それは、あらかじめルールが定められており、そのルールに従っているかどうかは誰にとっても自明だということです。このルールの中核には「最長チェーンを正当チェーンとする」というものです。
つまり、複数の人がバラバラにマイニングをしてブロック生成していても、結果的に最長になったものが正当とみなされるのです。もしある人が最長チェーン以外にブロックを継ぎ足ししても、正当とはみなされないので、他の人に単純に無視されます。
これをビザンチン将軍問題に当てはめます（簡略化した説明であり、厳密な証明ではありません）。まず、「攻撃時刻X」を全員に連絡し、受け取り次第「攻撃時刻Xを受け取った」と全員にまた連絡します。Xとほぼ同時に「攻撃時刻Y」が全員に連絡されているかもしれません。その場合、将軍たちは以下のように判断します。
- 過半数の将軍から「攻撃時刻X（もしくはY）を受け取った」という連絡を最初に受け取った場合、「X（もしくはY）を受け取った」と全員に連絡する。
- 1. の連絡が来なかった場合、先に受け取った攻撃時刻を自分が受け取った告知として全員に連絡する。
このようにすれば、いずれはほぼ全員が攻撃時刻に関して合意を取ることができ、大多数による攻撃が実現されます。
ビザンチン将軍問題はなかなか難しい問題であり、すぐには理解できないかもしれません。ビザンチン将軍問題について解説したサイトはたくさんあるので、興味が湧いた人はぜひ深く調べてみてください。
小宮自由
（image：iStock/gorodenkoff）