分散コンピューティングとビザンチン将軍問題

連載解説

ビザンチン将軍問題とは?
― 分散コンピューティングの課題 ―

 

分散コンピューティングを考える上で避けては通れない課題が「ビザンチン将軍問題」です。
今回はこの問題を解りやすく解説します。


ビザンチン将軍問題の概要

 ビザンチン将軍問題(ビザンチンしょうぐんもんだい、英語: Byzantine Generals Problem)とは、分散コンピューティングにおいて、悪意ある者(あるいは故障したコンピューターなど)が正しくない情報を提供した場合に、システム全体として正しい合意を形成できるかどうか、という問題です。 この問題は、1980年代に、コンピューターサイエンティストであるレスリー・ランポート氏達によって研究され定式化されました。

ビザンチンとは、東ローマ帝国(ビザンチン帝国)のことで、1453年に首都コンスタンティノープル(現イスタンブール)がオスマン帝国軍に包囲され陥落した故事にちなんでいます。 オスマン帝国の9人の将軍が9つの軍団を率いてコンスタンティノープルを包囲しており、将軍は伝令を通じて他の将軍と作戦や攻撃・撤退の連絡を取っていると仮定した状況で、この将軍の中に悪意ある者がおり、嘘の情報を他の将軍に伝えたらどうなるか、という想定のもとに分散コンピューティングが内包する問題を考えるのがビザンチン将軍問題です。

ビザンチン将軍問題に関連した攻撃や故障を、ビザンチン故障やビザンチン障害(Byzantine Failure)と呼び、ビザンチン将軍問題が発生してもシステム全体が悪影響を受けないような設計をビザンチン・フォールトトレランス(Byzantine Fault Tolerance)、あるいはフォールト・トレラント性と呼びます。

※Tolerat: 耐性がある、寛容である。


ビザンチン将軍問題の例題 

 もっとも単純なビザンチン将軍問題では、9人の将軍たちは攻撃か撤退かの2点だけについて合意形成を図ります。また、将軍は他の8人の将軍達と伝令を通じて意思疎通を図っています。 その状況下で、将軍たちは、攻撃するか撤退するかを多数決で決定することになったと場合を想定して問題が提起されます。

 それぞれの将軍は、他の8人の将軍に自分が攻撃に賛成するか、撤退に賛成するかの意志を記した手紙を送り、結果的に多数派の意見が採用されます。しかし、将軍の中に裏切り者がいたり、あるいは伝令が手紙を書き変えたりして、ある将軍には撤退の意志を送り、残りの将軍には攻撃の意志を記した手紙が送られた場合、他の将軍はばらばらの行動をとることになり軍全体は混乱することになるでしょう。

これがビザンチン将軍問題のもっとも簡単なケースです。そして、将軍や伝令の中に裏切り者がいても、軍全体で正しい行動が出来るようにしたシステムが、ビザンチン・フォールトトレラント性を持つシステムです。


技術上の問題

 ビザンチン故障は現実に発生しています。 オンラインショップのAmazonが提供するオンラインストレージサービス Amazon Simple Strage Service (Amazon S3) が、たったひとつの端末の故障により生じた不具合により、サービス全体が数時間停止しました。

 ビットコインなどが利用するブロックチェーンも分散コンピューティングを利用しており、世界中の不特定多数の人々がブロックチェーンに参加してトランザクションの承認や記録の保管を行っています。誰でも参加可能なブロックチェーンに、悪意あるハッカーが間違った情報を故意に流して攻撃を仕掛けることは容易に想像でき、それを防ぐ仕組みはブロックチェーンには不可欠です。 したがって、ブロックチェーン技術を知る上ではビザンチン将軍問題の理解は不可欠なのです。

ビットコインのブロックチェーンは、ビザンチン・フォールトトレラント性をProof of Work (PoW)で解決しています。これは、簡単に言えば、ブロックチェーンに参加している端末(ノード)の51%が同意したトランザクションを正しいトランザクションと認める方法です。 したがって、過半数の参加者が結託して不正な情報をブロックチェーンに流した場合、システムを書き変える事が出来ます。これを51%攻撃といいます。

しかし、ビットコインのマイニングには世界中から何十万人もの人々が参加しているため、これらの人々の51%で合意を形成することは事実上不可能と言えます。一方で、参加者の少ないマイナーコインの場合、理論上はブロックチェーンを乗っ取ることが可能です。 ビザンチンを包囲する9人の将軍の内、5人が結託してオスマン帝国を裏切っている状態、これが51%攻撃であると言えます。