暗号通貨

ビザンチン将軍問題悪意や障害の中での分散合意

「ビザンチン将軍問題」は中央システムがなく、参加者の中に故障したコンピュータや悪意を持った個人が含まれている状態で、全体で正しい合意に到達できるかが焦点にある問題だ。1982年にコンピュータ科学者であるレスリー・ランポートらによって考案されたものである。

吉田拓史

09 6月 2020 — 3 min read

このジレンマは、各将軍がそれぞれの軍隊を持っており、各グループは攻撃しようとしている都市の周辺の異なる場所に位置していると仮定している。将軍たちは、攻撃するか退却するかについて合意する必要があります。この問題においては、すべての武将が合意に達している限り、攻撃するか退却するかは重要ではない。

したがって、次のような要件を考えることができる。

各将軍は決定しなければならない：攻撃か退却か（イエスかノーか）。
決定後は変更できない。
すべての将軍は同じ決定に同意し、同期して実行しなければならない。

将軍は、宅配便で転送されたメッセージを介してしか他の将軍と通信できない。その結果、ビザンチン将軍問題の中心的な課題は、メッセージが何らかの形で遅れたり、破壊されたり、紛失したりする可能性があるということである。

さらに、メッセージが正常に配信されたとしても、1人以上の将軍が（理由は何であれ）悪意を持って行動し、他の将軍を混乱させるために不正なメッセージを送信し、完全な失敗につながる可能性がある。

レスリー・ランポートの1982年の論文に掲載された図。司令官と中尉2人の構成だが、一人でも反逆者が混ざるだけで、正しい合意に到達できなくなる。Source: Leslie Lamport et al."The Byzantine Generals Problem".

コンピューターネットワークのなかのビザンチン将軍問題

この比喩は、多くのコンピュータネットワークを悩ませている問題を説明している。分散コンピューティング環境、つまり複数のユーザー、アプリケーション、サーバー、または他のタイプのノードが環境を構成している環境（ブロックチェーンのようなもの）では、不正な行為者や信頼性の低い行為者が環境を崩壊させる危険性がある。サーバークラスタ内の一部のサーバーが、他のサーバーへのデータの一貫した受け渡しに失敗すると、サーバークラスタはうまく機能しない。コンピュータネットワーク上のデバイスが、情報を交換する際に使用する共通のネットワーキングプロトコルに合意していない場合、コンピュータネットワークは失敗する。

信頼性を確保するためには、分散コンピューティング環境は、ビザンチン障害耐性（BFT）として知られているものを提供することで、ビザンチン将軍の問題を解決するように設計されなければならない。

ビザンチン障害耐性（Byzantine Fault Tolerance: BFT）

ビザンチン障害耐性（BFT）とは、ビザンチン将軍問題から派生した障害に抵抗できるシステムの特性のことを示している。つまり、BFTシステムは、一部のノードが故障したり、悪意を持って行動したりしても、動作を継続できる。

ビザンチン将軍問題に対する解決策は1つ以上あり、それゆえBFTシステムを構築する方法も複数ある。同様に、ブロックチェーンがビザンチン障害耐性を達成するための異なるアプローチがあり、これがいわゆるコンセンサスアルゴリズムにつながる。

ほとんどの従来の分散コンピューティング環境には、ビザンチン障害が発生した場合に過ちを正すのに役立つ中央の設定データベースや権限がある。しかし、ブロックチェーン上には、定義上、中央システムは存在しません。コミュニティのコンセンサスだけに基づいて取引を正当化するブロックチェーンの能力が、ブロックチェーンをこれほど強力なものにしている。

このコミュニティ・コンセンサスへの依存度の高さが、ビザンチン・フォールトをブロックチェーンにとって特に重要な課題としている。コミュニティの一部のメンバーが、トランザクションに関する一貫性のない情報を他のメンバーに発信してしまうと、ブロックチェーンの信頼性が崩れてしまい、それを修正するために踏み込んでくれる権威がいなくなってしまう。つまり、ブロックチェーンに参加している全員に絶対的な信頼を置くことができない限り（ほとんどの状況ではできません）、一部のメンバーが不正確な情報や誤解を招く情報、悪意のある取引情報を配信した場合に発生する可能性のあるビザンチン将軍問題から守る方法が必要になるということだ。