ビザンチン将軍問題とその解決策

ビザンチン将軍問題とは

ビザンチン将軍問題とは、合意形成における一般的なモデルです。

n人の将軍の中に最大f人の裏切り者（合意形成を失敗させる行動をとる）が存在していることがわかっています。将軍らは「攻撃」「撤退」のメッセージを相互に送り合うことが出来ます。

以上の制約条件で正しい合意形成か可能かどうかを問う問題が「ビザンチン将軍問題」であり、P2Pネットワークにおいてシステム全体で正しい合意形成が機能しないことを「ビザンチン障害」と呼びます。

ビザンチン障害を回避するためには、裏切り者の数fが将軍nの1/3未満であること(=n>3f)である必要があることが証明されています。

ブロックチェーンの場合

分散管理が行われている状況において、システム全体で一つの解に決定される必要性があります。

ブロックチェーンの文脈においては、新たなブロックの生成において、確実にファイナリティに達することができるかどうかという問題は、換言すると「確実な合意形成が行われるかどうか」という問題と言えます。

具体的には、生成したブロックにはハッシュIDが付与されますが、合意が行われた場合、そのブロックの生成者への報酬を付与するためのトランザクションもブロック内に含まれていますので、複数のブロックが生成された場合には、それぞれのブロックのハッシュIDも異なります。

つまり、「複数のハッシュIDをただ一つに定める行為」が、ブロックチェーンの文脈における合意形成です。

オープンなP2Pネットワークにおいては、全ノード数nと悪意のあるノードfの数を把握することが不可能であるが故に不正利用の対応が不可能です。これがP2P方式のサービスが流行らなかった要因の一つです。

ビットコインにおける解

これらの問題は

・ナカモトコンセンサス

・PoW

によって暫定的な解決が達成されています。

前提として、ブロック生成者は、どのチェーンに後続して自分の生成したブロックを繋げるかという判断を行います。

ナカモトコンセンサスでは、チェーンの分岐は「最も長い」チェーンの採用が行われます。しかし、これでは悪意のあるノードが一度選択された過去のブロックから長いチェーンを繋げ続ければ簡単にシステムを崩壊させることが可能です。

そこで、PoWを用いて、ブロック生成の為のコストを計算リソースに転化させることで簡単に長いチェーンを繋げることを防止しています。

これによって、後続ブロックが多くなる程、合意が覆る確率が逓減していくことを「確率的ビザンチン合意」と呼びます。

100％の合意は図られませんが、全体として１つの暫定解が決定されていく仕組みになっています。