前回は、これまで研究されてきた分散システムにおける「合意」とビットコインの「合意」の意味を比較しながら、ビットコインにおける「合意」の意味にいくつかの解釈の余地があることを説明した。

 今回は最初に、「ビットコインが初めて問題を解決した」「いや解決していない」などと議論を呼んだ分散システムの難題、「ビザンチン将軍問題」を紹介する。

 次に、ビザンチン将軍問題が、ビットコインのようなP2Pシステムにとってどのような意味があるのか、過去の研究からビットコインに関係する論文として「The Sybil Attack」と「Exposing Computationally-Challenged Byzantine Imporstors」を紹介する。

 そして最後に、ビザンチン障害に耐性があるシステムを作れたとしても、プログラム(アルゴリズム)の正しさだけに依存してシステムを運営・維持することには限界があり、システムの運営方針・開発方針について人間同士の話し合いがどうしても必要になってしまうことについて考えてみたい。

合意問題とビザンチン将軍問題

 これまでビットコインの議論で話題にされてきたビザンチン将軍問題とはどのような問題なのか、Fischerの論文を参考に迫ってみたい。

 少々遠回りになるが、ビザンチン将軍問題の説明までに、以下5つのステップを踏んで説明していこう。
1.合意問題
2.Interactive Consistency問題
3.将軍問題
4.ビザンチン障害
5.ビザンチン将軍問題

1.合意問題

 合意問題は前回の記事でも紹介したとおり、まず、全ての故障していないプロセスが一つの値を提案する。そして、その提案された値の中からある一つの値に、全ての故障していないプロセスが合意するというものである(図1)。

図1●合意問題
図1●合意問題
[画像のクリックで拡大表示]

2.Interactive Consistency問題

 では、全てのプロセスが一つの値に合意するためには、どうしたらよいだろうか?

 その一つの方法として、「全てのプロセスが、それぞれが提案した値を全て知る」という方法が考えられる。つまり、全プロセスが、全プロセスの提案値のリスト(interactive consistency vector)を得られれば、そのリストの中から全プロセス共通のルール(例:最小値、最大値、中央値、多数決)で、値を一つに絞り込めばよい。

 このように、全プロセスがお互いの提案した値を全て知り合うためのアルゴリズムを考える問題をInteractive Consistency問題(参照論文)と呼ぶ(図2)。

図2●Interactive Consistency問題
図2●Interactive Consistency問題
[画像のクリックで拡大表示]

3.将軍問題

 将軍問題は、Interactive Consistency問題の特殊なケースと言える。何が特殊かと言えば、値を提案するプロセスが一つだけなのである(図3)。

図3●将軍問題
図3●将軍問題
[画像のクリックで拡大表示]

 ここで将軍(general)とはプロセスのことを表している。値を提案するプロセスも、値を知るプロセスも、全て将軍である。

 将軍問題も、Interactive Consistency問題も、問題の本質は同じである。

 というのは、Interactive Consistency問題を解くアルゴリズムは、提案する全プロセスのうち1つのプロセスに着目すれば、将軍問題も解いていることになるからだ。逆に、将軍問題を解くアルゴリズムが存在すれば、そのアルゴリズムを全プロセスに対して実行することで、Interactive Consistency問題を解くことができる。

 そして先に述べたように、Interactive Consistency問題を解くことができれば、合意問題も解くことができる。