ブロックチェーンの生みの親であるナカモトサトシが考案したビットコインの大きな成果の1つとして、分散データベースシステムにおける、ビザンチン将軍問題という合意形成上の問題点の実用的な解消方法となったことが挙げられます。ブロックチェーンを理解する上で、合意形成に関する問題点を理解することは非常に重要になります。今回はその問題点であるビザンチン将軍問題について見ていきましょう。
ビザンチン将軍問題の概要
ビザンチン将軍問題とは、2013年にチューリング賞を受賞した数学者のレスリー・ランポート博士（Leslie Lamport）らが考案した分散システム上の信頼性に関わる問題です。
ビザンチン将軍問題とは何かを簡潔に説明すると、「相互に通信し合うP2Pネットワーク上で、通信そのものや個々のノードが故障、または故意に偽の情報を伝達する可能性がある場合に、全体として正しい合意が形成できるかを問う問題」です。この問題を解決し、P2Pネットワークが正常に稼働するシステムは、ビザンチン・フォールト・トレランス性（Byzantine Fault Tolerance：BFT）を持つと言われます。
さて、「ビザンチン将軍問題」と言われる語源は、東ローマ帝国（ビザンチン帝国）の将軍達の問題に由来します。各将軍はそれぞれの軍を率いて、敵軍を包囲している状況を想定します。将軍たちは敵軍を攻撃する計画について合意したいと考えており、「攻撃」するか「撤退」するかの合意決定をしなければなりません。しかし各将軍はそれぞれ離れた場所にいて、直接話し合うことはできず、メッセージを相互に送ることでしか連絡ができません。よって、将軍たちは一斉に指令を出して攻撃を仕掛ければ勝てるが、一部の部隊だけで攻撃を仕掛けると負けてしまうという状況にあります。つまり、攻撃か撤退かのどちらかを、全将軍が一致して同意しなければならない状況となっています。
しかし、将軍たちの中には敵に寝返っている裏切り者の将軍がいるかもしれません。裏切り者の将軍は、他の将軍から攻撃の提案を受けると、撤退の提案にすり替えて別の将軍に伝達する可能性があります。そうなると、一部の将軍は攻撃提案と撤退提案の両方を受け取ることも想定されます。最悪、合意形成ができずに攻撃か撤退で意見が半々に分かれて一部の部隊だけが攻撃を開始してしまい、負けてしまいます。
このビザンチン将軍問題は、インターネット上での合意形成問題によく当てはまります。P2Pネットワーク上において、各ノードは他の全ノードに関するデータベースを持っていません。さらに各ノード間で調停を行うことはできず、相互にメッセージを送りつける通信を行うことしかできません。これは、各将軍が全員の将軍の意思決定が分からない中で、相互にメッセージを送ることしかできないというビザンチン将軍問題の状態と同様であると言えます。どちらもこのような状況の中でいかに全員の合意形成を取るかということが問題になってきます。
なお、ビザンチン将軍問題は分散システムの教科書であればたいてい取り上げられるポピュラーな話題であります。また故障の結果、予測不能な不具合を起こすことをビザンチン障害（またはビザンチン故障）と呼ぶこともあり、これはコンピュータの故障の中でも一番面倒なケースとなると言われています。
ビザンチン将軍問題の具体例
概要だけでは分かりにくいので、具体例を用いて考えてみましょう。1人の裏切り者と2人の誠実な将軍、合わせて3人の将軍がいると想定します。ここである誠実な将軍が「攻撃」を提案すると想定すると、2人の誠実な将軍が全員一致で攻撃ができるかどうかが、ビザンチン将軍問題の問いになります。
攻撃を提案した将軍1は、他の将軍たちにその提案を送ります。その提案を受け取った将軍は別の将軍に転送します。しかし、将軍2が裏切り者の場合、攻撃を撤退に替えて将軍3に送ることができます（データの改ざん）。このとき将軍3は最初の提案が攻撃だったのか撤退だったのかわからなくなってしまうので、最終的に正しい合意形成ができなくなってしまいます。もし将軍2が提案した撤退案を将軍3が選んでしまうと、将軍1が選択した攻撃案と意見が分かれてしまい、（将軍1と将軍3は）戦に負けてしまします。
しかし、誠実な将軍が3人（合計で4人の将軍）に増えるとどうでしょうか。将軍2が同様に裏切り者である場合、将軍3・将軍4に撤退という偽の情報を送ったとしても、3人の誠実な将軍は攻撃という正しい判断を下すことができます。
一般的に、裏切り者の将軍がN人のとき、誠実な将軍が2N＋1人以上であれば、誠実な将軍どうしの判断が一致できることがわかっています（今回の例はN=1でした）。言い換えると、裏切り者（障害となるノード）が、全ノードの1/3以下であれば正しい合意形成ができることになります。
（参考文献：The Byzantine Generals Problem｜Lamport L , 国立情報学研究所）
ビザンチン将軍問題とビットコイン
ブロックチェーンを使ったプロダクトの代表例がビットコインです。それではビザンチン将軍問題とビットコインとの関係は何でしょう。ビットコインでは、取引の改ざんがビザンチン将軍問題における裏切り者の将軍に相当します。逆に言えばビザンチン将軍問題を解決しないとビットコインは通貨として成立しません。そこでビットコインはこのような不正を発見・抑止するメカニズムを導入しています。これがプルーフ・オブ・ワークです。
分散ネットワークでの合意を可能にしたコンセンサスアルゴリズム「プルーフ・オブ・ワーク」
プルーフ・オブ・ワークは、難しい計算問題を解かせること（マイニング）で、改ざんデータをブロックに記録させるのを困難にしています。さらにマイニングに対して報酬というインセンティブを与えることで、マイナーは誠実に行動していた方が経済合理的になるような仕組みになっています。すなわち、マイニング及び報酬というシステムを利用することで、ビザンチン将軍問題における裏切り者がいなくなる状況を作り出すことに成功したのです。
ビザンチン将軍問題とブロックチェーン
ビットコインだけでなく、ブロックチェーン全体においてもこのビザンチン将軍問題は関係しています。ブロックチェーンを利用したその他のプロジェクトであるEthereumやNEMはプルーフ・オブ・ステークやプルーフ・オブ・インポータンスといった代替方法を用いて、ビザンチン将軍問題を解消していると言えます。
Proof of Workの欠点を克服させた合意形成アルゴリズム「プルーフ・オブ・ステーク」
富の偏りの解決を目指すコンセンサスアルゴリズム「プルーフ・オブ・インポータンス」
また、ブロックチェーン関連技術にまつわるビジネスを振興し、政策提言を行うことを目的として設立された日本ブロックチェーン協会（Japan Blockchain Association：JBA）は、ブロックチェーンを以下のように（狭義に）定義しています。
「ビザンチン障害を含む不特定多数のノードを用い、時間の経過とともにその時点の合意が覆る確率が0へ収束するプロトコル、またはその実装をブロックチェーンと呼ぶ。」
この定義は、ナカモトサトシの論文及びその実装である、ビットコインのブロックチェーンをオリジナルのブロックチェーンとして強く意識していると述べています。ここでビザンチン障害とはビザンチン将軍問題によって引き起こされる故障や障害を指します。このように、JBAはビザンチン将軍問題を解消している点を、ブロックチェーンの重要な特徴と捉えています。
画像：
ブロックチェーンのメカニズムは、ビザンチン将軍問題におけるデータ改ざんや通信障害といったことを行う「不誠実な将軍」がいても、システムが組み込まれています。ブロックチェーンの技術から発展し、様々な分散システムにおけるビザンチン将軍問題が解決されるようになり、将来的には、ビザンチン将軍問題に対する新しい解法につながるかもしれません。
