ブロックチェーンのビザンチン将軍問題とは/くりぷと知っ得情報5月15日号
画像出典：https://www.slideshare.net/springerw/byzantine-generals
クリプトスタディ(クリスタ)の水野です。
今回は、前回のFantom(FTM)でも触れた、ビザンチン将軍問題について書いていきます。
ビザンチン将軍問題(※)は、ブロックチェーンの生みの親であり、ビットコイン論文を発表したサトシナカモトが考案した、ビットコインの大きな成果の一つ、合意形成上の問題点の実用的な解消方法として引用されています。
ビザンチン将軍問題は、1980年代に、レスリー・ランポートにより提唱されたもので、ランポートは、コンスタンティノープルを包囲し攻撃しようとするビザンチン軍を例にあげて、分散型ネットワークにおける、多数決の妥当性や信頼性を評価する方法を提唱しました。
ビザンチン将軍問題？
｢ビザンチン将軍問題｣と言われる語源ですが、東ローマ帝国(ビザンチン帝国)の将軍達の問題に由来します。
🔶🔶想定🔶🔶各将軍はそれぞれの軍を率いて、敵軍を包囲している状況を想定しましょう。
将軍たちは敵軍を攻撃する計画について合意したいと考えていますが、｢攻撃｣するか｢撤退｣するか、合意決定をしなければなりません。
しかし各将軍はそれぞれ離れた場所にいて、直接話し合うことはできず、今みたいにSNSもないわけですから、直接伝えることでしか連絡ができません。
将軍たちは一斉に指令を出して攻撃を仕掛ければ勝てるが、一部の部隊だけで攻撃を仕掛けるとなると負けてしまうかもしれず、攻撃するか撤退するかのどちらかを、全将軍が合意しなければならない状況となっているとしましょう。
裏切り者がいるとしたら‥‥
将軍たちの中に裏切り者の将軍がいるとしたら‥‥。
裏切り者の将軍は、他の将軍から｢攻撃｣の連絡を受けても、｢撤退｣というように情報をすり替えて別の将軍に伝達する可能性がありますね。(データの改ざん)
そうなると、将軍の中には攻撃と撤退の両方の連絡を受け取る可能性があります。
結果、迷ってしまい、合意形成ができず、一部の部隊だけが攻撃を開始してしまって、負けてしまうかもしれません。
ビザンチン将軍問題の具体例
3人の将軍の合意形成
具体例として、3人の将軍がそれぞれの部隊を構えているとします。
ここでいう、ビザンチン将軍問題は、将軍1が、攻撃と提案したとして、2人の将軍が一致して攻撃ができるかどうかが、ということが、ビザンチン将軍問題になります。
仮に、将軍2が裏切り者だったとして、「攻撃｣を｢撤退｣に替えて将軍3に伝えるかもしれません。(データの改ざん）
このとき将軍3は最初の提案が｢攻撃｣だったのか｢撤退｣だったのかわからなくなってしまうので、最終的に正しい合意形成ができなくなってしまいます。
もし将軍3が将軍2が提案した｢撤退｣案をが選んでしまうと、将軍1が選択した攻撃案と意見が分かれてしまい、戦に負けてしまうかもしれません。
つまり、3人では合意形成ができないということになります。
4人(以上)の将軍の合意形成
しかし、合意形成する将軍が4人(以上)になったらどうでしょう？
先の例同様、将軍1が｢攻撃｣を提案。
将軍2が裏切り者だったとして、将軍3・将軍4に撤退という偽の情報を送ったとしても、将軍3と将軍4は｢攻撃｣という提案を双方から得ているので、正しい判断を下すことができます。
🔶🔶まとめ🔶🔶裏切り者の将軍がN人のとき、誠実な将軍が2N＋1人以上であれば、誠実な将軍同士の合意形成が成立する。
今回の例で言うと、誠実な将軍が2人、裏切り者が1人なので、2人＋1人=3人で合意形成。
言い換えると、裏切り者(コンピュータで言えば障害となるノード)が、全ノードの1/3以下であれば
正しい合意形成ができることになります。
ビザンチン将軍問題とは｢複数人で合意形成を図る際、その一部の不正や不具合が生じ得る時に、全体での正しい合意形成ができなくなる可能性がある｣という問題のことを言います。
分散型のネットワークにおいて合意形成を図るためには、このビザンチン障害が起きないようにする必要があります。
ビザンチン・フォールトトレランス性とは？
Byzantine Fault Tolerance(ビザンチン・フォールトトレランス)とは、なんか英語で難しそうですが、ビザンチンフォールトトレランス性があると言うのは、ビザンチン将軍問題が生じたとしても、全体としての合意を形成できることを意味し、ビザンチン将軍問題に由来する障害に抵抗できるシステムの特性のことを言います。
ビザンチン将軍問題とブロックチェーン分散型ネットワーク
分散型ネットワークとは特定の中央管理者のいないネットワークのことです。
このようなネットワークでは、データはネットワークの参加者が対等に、分散的に管理をすることになります。
peer-to-peer(P2P)ネットワークとも言います。
ビットコインを支えているブロックチェーンも、このP2Pネットワークを応用した技術です。
分散型ネットワークにはビザンチン将軍問題が付きものです。
ビットコインを支えるブロックチェーンは、このビザンチン将軍問題に対する現実的な解決方法として話題になりました。
ビットコインでは、取引の改ざんがビザンチン将軍問題における裏切り者の将軍に相当します。
逆に言えばビザンチン将軍問題を解決しないとビットコインは通貨として成立せず、ビットコインはこのような不正を発見・抑止するメカニズムを導入しています。
コンセンサスアルゴリズムPoW
ビットコインをはじめとするブロックの承認作業｢プルーフ・オブ・ワーク(PoW)｣は、難しい計算問題を解かせること(マイニング)で、改ざんデータをブロックに記録させるのを困難にしています。
さらにマイニングに対して報酬というインセンティブを与えることで、マイナーは誠実に行動していた方が経済合理的になるような仕組みになっています。
すなわち、マイニング及び報酬というシステムを採用することで、ビザンチン将軍問題における裏切り者がいなくなる状況を作り出すことに成功したと言うわけですね。
51%攻撃
不正を働こうとした人は計算に参加している人全体の50%を超える計算力を得られると、取引記録の改ざんができてしまいますが、このことを、51%攻撃と言います。
しかし、この51%攻撃には、とてつもないコストが必要となり、また、もしその改ざんができたとしてもその時点で信用を失った通貨の価値は一気に暴落すると考えられるため、不正取引ができたり、報酬を独占できる状態になってもそのメリットがほとんどなくなってしまいます。
PoW、報酬とインセンティブと言う設計を組み込むことで、ビットコインは実用性ビザンチン耐性(Practical Byzantine Fault Tolerance:PBFT)を持つ、世界初のP2P決済システムとなりました。
ビットコインが誕生して15年。
未だ合意が覆されずにブロックチェーンが機能していることを考えると、ビットコインは実質的にはビザンチン将軍問題を解決できていると言えます。
お読みいただいてありがとうございました。