ブロックチェーンなどの技術を勉強していると遭遇する『ビザンチン将軍問題』。このnoteでは、このビザンチン問題がどんなものであるかについてをまとめます。また、この問題から分散型ネットワークの弱点を説明します。

ビザンチン将軍問題とはどんなものか

ビザンチン将軍問題とは、以下のようなものです。

かつてヨーロッパにはビザンチン帝国という帝国があった。
現在、ビザンチン帝国の9人の将軍のうちの1人であるあなたは、ある都市を攻め落とすために包囲している状態である。都市を攻め落とすには、それぞれの将軍がもつ部隊9つが一斉に攻撃をしなければならない。1部隊でも欠けてしまった場合は負けてしまう。

ここで、全将軍の合意を形成するため、「攻撃」か「撤退」の2択で多数決を取ることにする。しかし都市を包囲している状態のため、将軍らが集まって多数決を取ることはできない。そこで自分の選択は他の8部隊全てへ伝令兵を送ることで意思表示をする。例えば、自分の選択が「攻撃」で、他部隊からの伝令兵の情報の集計結果が「攻撃 : 3、撤退 : 5」だった場合は撤退する。

実際に他部隊からの選択を集計した結果、「攻撃 : 4、撤退 : 4」であった。つまりこれからのあなたの選択次第で、全部隊の行動が決定する。あなたはビザンチン帝国に恨みがあり、全部隊を裏切りたいとする。自分以外の8部隊へどのように伝令を送れば、他部隊全ての選択を裏切ることができるだろうか？

ちょっと小難しい問題文なんですが、解答を書いていきましょう。

ビザンチン将軍問題を解説

この問題ではあなたはビザンチン帝国の1将軍であり、ビザンチン帝国に対して恨みを持っている設定です。「仲間の部隊を裏切るためにどのように伝令を送れば良いか」と問われています。問題文だけではイマイチ理解が難しいので、状況をイラストで整理しましょう。

まずはじめに、ある都市を全部隊で包囲している状態で問題はスタートします。ビザンチン帝国全体で「この都市を攻め落としてやろう！」と意義込んでいるわけです。「攻める」か「撤退する」かは全体の合意を形成しなければなりません。ここで全体の決定はそれぞれの将軍たちが集まって話し合いたいのですが、包囲している状態で将軍たちはその場を離れることができません。

そこで、それぞれの将軍は自分以外の他部隊へ伝令兵(「攻撃」か「撤退」かを伝える兵)を送って、自分の意思を他部隊へ伝えます。自分が「攻撃」を選択した場合はこんな感じです。

自分の意思は、それぞれの将軍に伝令兵を介して伝わります。つまり、自軍の8人の伝令兵に伝言をしてもらうことになります。これがこの問題のミソになります。これを全軍のネットワークで示すと、以下の図のようになります。

ネットワークの構図はイメージできたでしょうか？これがいわゆる分散型ネットワークです。さて、ここから実際にビザンチン将軍問題について考えてみましょう。

あなたがまだ伝令兵を送って意思を表示していない状態で、他部隊全てから伝令兵の伝言が来ました。その結果、下の図のようになっていました。

攻撃4、撤退4ということで、あなたの選択で攻撃するか撤退するかが決まります。

しかしあなたはビザンチン帝国に恨みをもっており、他の将軍を裏切りたいと考えています。このとき、周囲の選択全てを裏切るためにはどのように伝令を伝えていけば良いでしょうか？

ビザンチン将軍問題の解答

答えは下のように伝令を送ることです。

その結果...

こうなります。それぞれの将軍は自分の選択した通りにはいかず、全体としても統一された選択を得られていません。あなたは見事に他将軍全てを欺き、彼らの意図しない結果へ導くことができます。

ビザンチン問題と分散型ネットワークの弱点

ビザンチン将軍問題とは、「分散されたネットワーク上で合意を形成する際に、悪意のある者がいると信頼性の保証できる合意の形成ができない」ということを暗示しているものです。これは仮想通貨のようなP2Pシステム(Peer to Peer : 分散型ネットワークシステム)上で解決しなければならない問題です。

かつてまではこのような問題点が解決できていなかったため、分散されたネットワーク上でのシステムは難しいものとされていました。しかしこの弱点を克服し、分散ネットワークを実現しようとしたものがブロックチェーン技術です。