ビザンチン将軍問題

ビザンチン将軍問題とは？　ビットコインが解決したコンピュータ科学の難問

ビザンチン将軍問題とは

ビザンチン将軍問題とは、1980年代にコンピュータ科学者であるレスリー・ランポート氏らによって定式化された問題です。中央の管理システムが存在せず、参加者の中に故障したコンピュータや悪意を持った個人が紛れ込んでいる状態で、全体で正しい合意を形成できるのかが焦点にある問題です。

ビザンチンとは、中世ヨーロッパ世界で権勢を誇ったビザンチン帝国（東ローマ帝国）を指しています。ビザンチン帝国の首都であるコンスタンティノープル（現在のイスタンブール）を包囲するオスマン帝国の将軍が9人おり、攻撃計画について合意を得ようとしているとしたら……という仮想状況を想定することで、コンピュータ科学の問題を表現しています。

攻撃計画は、攻撃か撤退の2通りです。計画の決定は、9人の将軍たちの多数決で行われますが、必ず全軍一致でないと計画は成功しません。将軍たちは兵を率いているため、合議を開催することはできません。しかし、包囲する将軍の中には反逆者がおり、間違った計画の方に賛成票を投じて混乱させます。たとえば、攻撃を主張する将軍には攻撃票を通知し、撤退を主張する将軍には撤退票を通知することで、軍を2つに分割できてしまうのです。こうした状況でいかに全軍一致の合意を形成するのかが、ビザンチン将軍問題の概要です。

コンピュータネットワークの場合、ビザンチン将軍問題が原因となって「ビザンチン障害」を引き起こす可能性があります。ネットワーク内の局所的な障害に対する応答がサブシステムごとに異なるために、障害がネットワーク全体へ拡大する可能性があるのです。実際、2008年にグローバル企業のオンラインストレージサービスにおいてビザンチン障害が発生し、サーバーのダウンにつながったケースが存在します。

かつてのコンピュータネットワークには、必ず中央の管理機関がありました。そのため、ビザンチン将軍問題は顕在化しませんでした。ビザンチン帝国の包囲戦の例で言えば、9人の将軍たちが一堂に会して意見交換できる状態にあったと言えるでしょう。そのため、意思決定の不一致が問題になりにくかったと考えられます。

しかし、その後複数のコンピュータがつながりあう分散コンピューティングが主流となったことで、中央を持たないネットワークにおける合意の形成が大きな問題となりました。コンピュータの故障や悪意を持ったハッカーの存在を前提としても、なお技術的に問題をクリアできるかどうかが1980年代以降のコンピュータ科学における課題だったのです。

ビットコインはビザンチン将軍問題の代表例

ビットコインの取引システムも、中央の管理システムを持たない分散型のネットワーク構造を持っています。各コンピュータは、将軍たちと同じ状況に置かれています。他のコンピュータとやり取りできるものの、全体を統括するメインコンピュータはありません。そんな中で、取引データをすべて間違いなく処理していかなければなりません。たとえば、あるコンピュータが一方には「Aさんに1BTC（ビットコインの単位）送った」と通知し、他方には「Bさんに1BTC送った」と通知したケースを考えてみましょう。この場合、1BTC送ったという情報が二重に記録されてしまうとともに、ビットコインの残高情報にも不整合が発生します。これは、まさにビザンチン将軍問題の発露と言えます。

決済システムとしての実用化を目指すには、データを正しく処理し続けることが必要不可欠です。少しでも間違いが生じるなら、ビットコインに対する信頼性は暴落してしまうでしょう。ビットコインを暗号資産（仮想通貨）として機能させるためには、ビザンチン将軍問題の解決が実用化に際しては大きなハードルとして立ちはだかっていました。

ビットコインにおけるビザンチン将軍問題を解決するのが、プルーフ・オブ・ワーク（Proof of Work、「PoW」と略されます）でした。これは、取引データに誤りがなく、間違いなく送信者本人から発生したものであることを承認するための承認システムです。取引データをいくつかまとめたブロックを作り、ブロックチェーン（block chain）というデータベースへ格納するために必要な出力値になるようなパラメータを探します。

パラメータを探すのは大変ですが、一度発見されるとそれが正しいかどうかはすぐに計算できるようになっています。そのため、パラメータを含めて取引データを改ざんするのが難しく、仮にネットワーク内に悪意あるハッカーがいても問題なく「取引データは正しい」という合意形成を取ることができるようになっているのです。パラメータの計算という作業（＝ワーク）によってデータを承認すること（＝プルーフ）から、プルーフ・オブ・ワークと呼ばれています。

プルーフ・オブ・ワークを導入したことで、分散型ネットワークであるビットコインは致命的なセキュリティトラブルを起こすことなく稼働を続けています。