ビットコインとビザンチン将軍問題

ビットコインやブロックチェーンについて調べてみると、時折、ビザンチン将軍問題というフレーズが出てきます。

一般の人にとっては、あまり関係のない単語のようにも思えますが、ビザンチン将軍問題は、仮想通貨などの分散システムの信頼性を評価するために重要な指標となるものであり、今後の仮想通貨やブロックチェーンの将来性を考える上でも、是非、知っておきたいものです。

今回は、ビザンチン将軍問題について解説していこうと思います。

 

(画像出典:https://www.slideshare.net/springerw/byzantine-generals)
ビザンチン将軍問題とは、中央集権的な管理者のいないネットワークにおいて、通信障害や個々のノードに故障がある場合、あるいは悪意のある参加者が偽の情報を伝達し得る場合に「ネットワーク全体で合意形成ができるかどうか」を問う問題です。

ビザンチン将軍問題は、分散型ネットワークにおける、多数決の妥当性や信頼性を評価するために、1980年代に、レスリー・ランポートにより提唱されたもので、ランポートは、コンスタンティノープルを包囲し攻撃しようとするビザンチン軍を例にあげて定式化しました。(論文:The Byzantine Generals Problem

それでは、具体的にその内容を見ていきましょう。

【前提条件】

画像に alt 属性が指定されていません。ファイル名: ビザンチン将軍.png

・ビザンチン軍の9人の将軍は、コンスタンティノープルの城壁を包囲している。

・ビザンチン軍はそれぞれ、分かれて配置しており、全員が集まって作戦会議をする事は出来ない。このため、各将軍は手紙を使った伝令により意思疎通を行う。

・伝令が回ってきた9人の将軍は「攻撃」か「撤退」に投票し、軍全体の意思決定は、多数決により決議される。

・ビザンチン軍の9人の将軍の中には、コンスタンティノープルのスパイ(裏切者)が一人潜伏しており、ビザンチン軍を敗北させようとしている。

 

【攻略条件】

・城を攻め落とすには9人の将軍の率いる部隊が同時に攻撃を仕掛けなければならず、一部隊でも欠けた場合、兵力不足で敗退する。

【裏切り者の解】

さて、ここで問題です。裏切り者の将軍に伝令が届いた時、4人の将軍は「攻撃」に投票しており、残りの4人は「撤退」に投票していました。裏切り者の将軍は、ビザンチン軍は敗退させるためにどのような行動をとるのでしょう?

それは、「攻撃」に投票した4人の将軍に対して、自軍は「攻撃」をするという伝令を送り、「撤退」に投票した4人に対しては、自軍は「撤退」をするという伝令を送る、というものです。「攻撃」に投票した4部隊は、全軍攻撃と判断して、攻め込みますが、「撤退」に投票した4部隊は、全軍撤退と判断します。結果、戦力不足によりビザンチン軍は敗退します。
画像に alt 属性が指定されていません。ファイル名: ビザンチン2.png
中央集権的な管理者が不在の分散化ネットワークにおいて、ビザンチン将軍問題に依拠するネットワーク障害を、ビザンチン障害(Byzantine Failure)と呼び、ビザンチン障害に対して耐性があり、正常に動作しうるシステムをビザンチン耐性(Byzantine Fault Tolerance:以下、BFT)があると言います。

ビットコインとビザンチン将軍問題

サトシ・ナカモトがビットコインで目指していたのは、特定の第三者の信頼に依存しないP2Pネットワークによる送金システムの実現でした。
悪意あるハッカーの存在や個々のノードの故障を前提として、ネットワーク全体で合意形成を作れる仕組みを作らなければ、通貨の信頼性が担保されません。そのため、ビザンチン将軍問題は、取引履歴の改ざんが不可能で、安全な送金システムを実現するために、避けて通れないものだったのです。
例えば、あるノードが、複数のノードに対して「AさんからBさんに1BTCを送金した」と通知する一方で、別のノードに対して「AさんからCさんに1BTCを送金した」と通知したとしましょう。
この時、Aさんの持つ1BTCに関して二重支払いが生じ、ビットコインの取引データ上で不整合が生れてしまいます。二重支払いが一度でも起きてしまったらその瞬間、通貨としての信頼性は失われ、ビットコインの価値はゼロになります。
サトシ・ナカモトは、ビザンチン障害耐性を持つ、決済システムを実現するために、ビットコインにプルーフ・オブ・ワーク(仕事量による証明)を導入しました。プルーフ・オブ・ワークとは、ネットワークにおける、挙動の信頼性を、仕事量(≒投下したCPUパワー)によって評価するというアルゴリズムです。
ビットコインの取引データを公開帳簿に記録する権利を得るためには「膨大な計算量が必要な演算」を処理する必要があります。
そのため、悪意あるハッカーが取引履歴を恣意的に改ざんするためには、他の善良な参加者の持つCPUパワーの総和を超える量のCPUパワーが必要になります。これは現実的には不可能であることに加えて、それだけのCPUパワーを持っているのならルールに則って、報酬のビットコインを貰った方が利益がでることから、取引履歴を改ざんするインセンティブがなくなるというロジックです。
このような設計を組み込むことで、ビットコインは実用的ビザンチン耐性(Practical Byzantine Fault Tolerance 、以下、PBFT)を持つ、世界初のP2P決済システムとなりました。

実用的ビザンチン障害耐性と非同期ビザンチン障害耐性

しかし、留意すべきなのは、PBFT(Practical Byzantine Fault tolerance)は、あくまで”実用に耐えうるレベルの耐性”は認められるものの、数学的にビザンチン耐性が証明されている訳ではありません。

例えば、ビットコインのマイニング機器最大手のビットメインは、マイニング機器のメーカーとして、唯一、TSMCの最新の半導体チップ(5nm規格)の供給先に選ばれています。

前述したように、プルーフ・オブ・ワークを採用するネットワークでは、演算処理速度の高いマシンを大量に確保することが勝負となるため、(実際に彼らがやるかはどうかは別として)ビットメインが5nm規格のマイニングマシンを量産化した暁には、ビットコインのネットワークを掌握することが現実的に可能となります。そのため「ビットコインはビザンチン将軍問題を解決した」という表現は間違っています。

因みに、イーサリアムなどが採用しているプルーフ・オブ・ステーク(Proof of Stake)には、ビザンチン耐性はないため、分散型ネットワークにおいて、信頼のおけるスマートコントラクトを実現することは不可能です。
ビットコインが登場して以降も、数学的にビザンチン将軍問題を解決した分散型台帳の研究は続けられました。
現在、BFTの中で最もセキュリティが高いといわれるのが、非同期ビザンチン耐性(Acynchronous Byzantine Fault Tolerance )です。ABFTは理論上、ビザンチン将軍問題が生じないことが、数学的に証明されたもので、ゴシップアルゴリズムやハッシュグラフアルゴリズムがこれに当たります。
仮想通貨や分散型台帳システムの中では、Hedera HashgraphなどがABFTを実現していることが知られています。( THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCE
近年、仮想通貨の市場規模は順調に成長していますが、一方で、多くの仮想通貨やブロックチェーン関連のプロジェクトでは、未だにビザンチン将軍問題が解決されてはいません。興味を持った仮想通貨やブロックチェーンプロジェクトを調べる時は、ビザンチン将軍問題に対する耐性レベルも、是非、チェックしたいものです。
(文・飯倉光彦)
最新情報をチェックしよう!
>デカルトサーチ-日本最大級のエンジニアのグローバルネットワーク-

デカルトサーチ-日本最大級のエンジニアのグローバルネットワーク-

デカルトサーチ合同会社は、日本最大級 のエンジニアのグローバルネットワークを持つ人材紹介会社として、14年間に渡り、世界中のハイクラスなエンジニアを日本企業様に紹介してきました。

デカルトサーチでは、計算工学の修士号を持つ経験豊富なリクルーターがエンジニア採用を包括的にサポートします。