仮想通貨とビザンチン将軍問題について

ビットコインやブロックチェーンについて調べてみると、ビザンチン将軍問題というフレーズが出てきます。何の事だか、と思った人も多いかも知れません。今回は、ビザンチン将軍問題と、分散型ネットワークにおける同問題の意義について紹介したいと思います。

ビザンチン将軍問題

(画像出典:medium.com)

ビザンチン将軍問題とは、中央集権的な管理者のいないP2Pネットワークにおいて、通信障害や個々のノードに故障がある場合、もしくは悪意のある参加者が偽の情報を伝達し得る場合に、ネットワーク全体で合意形成が出来るか否かを問う問題です。

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

それでは具体的に見て行きましょう。

【前提条件】

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

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

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

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

【攻略条件】

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

【裏切り者の解】

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

それは、「攻撃」に投票した4人の将軍に対して、自軍は「攻撃」をするという伝令を送り、「撤退」に投票した4人に対しては、自軍は「撤退」をするという伝令を送る、というものです。「攻撃」に投票した4部隊は、全軍攻撃と判断して、攻め込みますが、「撤退」に投票した4部隊は、全軍撤退と判断します。結果、戦力不足によりビザンチン軍は敗退します。

分散化ネットワークにおけるビザンチン将軍問題

中央集権的な管理者が不在の分散化ネットワークにおいて、ビザンチン将軍問題に依拠するネットワーク障害ないし故障を、ビザンチン故障(Byzantine Failure)と呼び、ビザンチン故障に対して耐性があり、正常に動作しうるシステムをビザンチン耐性(Byzantine Fault Tolerance)があると言います。

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

さて、中央集権的な管理者がいない分散化されたP2Pネットワーク上で挙動する電子決済システムを実現する上で、ビザンチン将軍問題は最も重要な課題でした。悪意あるハッカーの存在や、個々のノードの故障を前提条件として、P2Pネットワーク全体で合意形成を作れる仕組みを作らなければ、通貨の信頼性が担保されないためです。

例えば、あるノードが、複数のノードに対して「AさんからBさんに1BTCを送金した」と通知する一方で、別のノードに対して「AさんからCさんに1BTCを送金した」と通知したとしましょう。この時、Aさんの持つ1BTCに関して二重支払いが生じ、ビットコインの取引データ上で不整合が生れてしまいます。二重支払いが一度でも起きてしまったらその瞬間、通貨としての信頼性はゼロになります。

サトシ・ナカモトはビザンチン故障耐性を持つ、決済システムを実現するためにビットコインにプルーフ・オブ・ワーク(仕事量による証明)を導入しました。プルーフ・オブ・ワークとは、ネットワークの参加者が、取引データをまとめて公開帳簿に記録する際に、膨大な計算量が必要な演算を課す事で、信頼性を担保するというアルゴリズムです。

ビットコインにおいては、計算量に応じて、取引履歴を追加する権利が与えられる仕組みになっているため、悪意あるハッカーが取引履歴を恣意的に改ざんするためには、他の善良な参加者の持つCPUパワーの総和を超える量のCPUパワーが必要になります。

これは現実的には不可能である事から、ビットコインは実用的ビザンチン耐性(Practical Byzantine Fault Tolerance)を持つ、世界初のP2P決済システムであると言えます。

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

ただ、留意すべき点はPBFT(Practical Byzantine Fault tolerance)は、あくまで”実用に耐えうるレベルの耐性”は認められるものの、数学的にビザンチン耐性が証明されている訳ではありません。ビザンチン耐性は相対的に評価されるものであり、「ビットコインはPBFTを持つため、ビザンチン将軍問題を解決した」という表現は誤りです。

そのため、かねてより、P2Pネットワークで世界規模の決済システムを構築する上で、PBFTではセキュリティレベルが不十分だという指摘はありました。

BFTの中で最もセキュリティが高いといわれるのが、非同期ビザンチン耐性(Acynchronous Byzantine Fault Tolerance )です。ABFTは理論上、ビザンチン将軍問題が生じえない事が数学的に証明されたネットワークの事を言います。

ビットコイン以後、人々は、より高いセキュリティレベルを求めて、ABFTを持つアルゴリズムに基づいた、P2P決済システムの研究・開発が活発化しました。分散型台帳システムの中では、Hedera HashgraphなどがABFTを実現しています。( THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCE

因みに、後日詳しく解説しますが、古典的なプルーフ・オブ・ステーク(Proof of Stake)にはビザンチン耐性はありません。PoSへの移行を準備するイーサリアムに対して人々が眉を顰めるのは、このためです。

要するに、「より高いレベルのビザンチン耐性を持つ分断型台帳の実現のために、これまで研究者たちが、努力してきたのに、はなからビザンチン将軍問題を放棄して、経済的合理性に委ねるのは無責任であり、時代に逆行している。」というのです。

分散型ネットワーク上で正しく挙動する仮想通貨を構築するためには、ビザンチン将軍問題は避けて通れない問題です。今後、ABFT(非同期ビザンチン障害耐性)が証明されている事が、その分散型ネットワークにとっての重要な評価指標となるでしょう。