難問・ビザンチン将軍問題とは何か?|DApps(ブロックチェーンを活用したアプリケーション)のことなら

TOP  コラム  難問・ビザンチン将軍問題とは何か?

難問・ビザンチン将軍問題とは何か?

2018.11.29

コラム

難問・ビザンチン将軍問題とは何か?

よく耳にするけれど分からない“あの言葉”
ブロックチェーン技術や暗号通貨(仮想通貨)に一定以上の関心をもち、情報に接している方であれば、おそらく「ビザンチン将軍問題」というワードを目にしたことがあるでしょう。

ブロックチェーンの技術や仕組み、特性を理解するための解説でしばしば言及されるものですが、それ自体がどんな問題なのか、なぜブロックチェーンと関係があるとされるのか、よく分からないままになっているという方も多いようです。

しかし、ブロックチェーンを基盤とする暗号通貨の代表格、ビットコインが注目される初めのきっかけとなったポイントは、ここにこそあると指摘する専門家も多く存在します。そこで、今回はこの「ビザンチン将軍問題」について、少し詳しくみていくこととしましょう。

歴史の問題?NO!合意形成に関する重要問題!
ビザンチン将軍問題(Byzantine General Problem)とは、1982年にLeslie Lamport博士によって指摘・提唱された、分散型ネットワークにおける正しい合意形成をめぐる問題で、長く情報工学領域の難問とされてきたものです。

中世ヨーロッパには、コンスタンティノープルを首都とするビザンチン帝国(東ローマ帝国)という国がありました。問題は、この首都・コンスタンティノープルが、敵対するオスマン帝国によって包囲された状況下で発生します。

オスマン帝国の将軍9人は、それぞれが軍団を率い、コンスタンティノープルを攻め落とす策を練っていました。現状を鑑みるに、9つの軍が全て協力し全軍攻撃を仕掛けなければ、攻め落としは成功しそうにありません。仮にたった1軍でも欠ければ、失敗する可能性が高く、痛手を被ると考えられることから、選択は全軍攻撃か全軍撤退の二者択一になります。

いずれの計画に決定するかは、9人の将軍による全員一致の合意によらなければなりませんが、それぞれ離れた場所に陣を張っているため合議を行うことが難しいことから、個々に判断を下した時点でそれを伝令兵に伝えさせ、相互に使いとして送り合うことで多数決による合意形成を目指すこととしました。

しかし、一部の将軍は反逆者であり得、撤退意思のある将軍には撤退支持、攻撃意思のある将軍には攻撃支持と伝令するなど、計画を失敗させる混乱を招こうとしているとみられているのです。さらに困ったことに、将軍らは離れたところから伝令を放つため、伝令兵に信書を運ばせるのに失敗したり、届けられるまでに内容が改ざんされたりするリスクもあります。

どんな伝令を受け取ったか、互いに情報共有を図る手段もなく、受け取った信書の内容を信じて、おのおのが手元の多数決結果に従った行動をするしかない、こうした状態でどうすれば正しい合意形成が導けるのか、不可能なのではないか、これがビザンチン将軍問題として定式化された問題の概要です。

ビットコインはPoWで現実的解決方法を提示
分散型ネットワークは、全体を管理・統合する主体を置かない仕組みで、参加者をみな同等の地位に置くP2Pのシステムとなっており、各ノードはちょうどこの離れた位置にいる将軍同士のような環境にあります。

不特定多数の参加する、オープンで分散的なネットワークですから、悪意あるノードの存在も想定しなければなりませんし、単純な数による多数決も困難ですから、何らかの合意形成を図ろうとすると、ビザンチン将軍問題と同様の問題発生が懸念されるのです。

分散コンピューティングでは、実際にこの合意形成における問題が引き金となり、「ビザンチン障害(故障)」と呼ばれる事態が発生しています。意図的な不正行為で生じるケースと、クラッシュや受信の失敗など不作為で生じるケースがありますが、ネットワーク内の局所障害に対する対応応答がサブシステムごとに異なるものとなり、その結果、障害がネットワーク全体に深刻な影響を及ぼすものとなって拡大してしまう可能性が大いに高まるのです。

2008年には、Amazon Web Servicesによるオンラインストレージサービス「Amazon S3」が、たった1ビットのハードウェア障害から、ビザンチン障害でサービス全体に不具合が広がり、数時間のシステムダウンとなった事例もありました。

中央で管理する主体が存在すれば、将軍らが一堂に会して意見を交わすことができ、それをとりまとめて決定する仕組みがあるということですから、こうしたビザンチン将軍問題はおよそ顕在化せずに処理されますが、分散型ネットワークのシステムでは、そうはいきません。それゆえ難題とされてきたのです。

しかしブロックチェーンは、ビザンチン障害を含む不特定多数のノードが存在し、そうしたネットワークで運用されていても、時間の経過とともに合意が覆る可能性がほぼゼロへと収束していくもの、このビザンチン将軍問題による障害をおよそ克服できる技術として編み出されました。

それがブロックチェーンのコンセンサスアルゴリズムで、このような性格をもつことを、「ビザンチン・フォールトトレラント性(Byzantine Fault Tolerance)がある」といいます。

ビットコインの場合でみると、PoW(Proof of Work)の仕組みが採用されており、これがビザンチン将軍問題への現実的な解決方法を提示したかたちとなっています。PoWでは、マイニング作業にあたる計算処理を行い、いち早くナンスを発見、ブロックの生成、承認、追加に成功した人が、報酬を得られる仕様になっており、その後は誰もが簡単に正しさを検証できるため、正確性や信頼性を担保し合っていくことができます。

合意形成の方法であるコンセンサスアルゴリズムは、PoWの他にも複数存在し、それぞれにブロックチェーンを支えるものとして組み込まれています。

いかがでしたか。ビザンチン将軍問題がどのようなもので、ブロックチェーンとどう関わっているのか、理解できたでしょうか。ブロックチェーンの革新性をより実感できたのではないかと思われます。今後もブロックチェーン技術へのさらなる理解向上に努めましょう。

▼DApps総研
https://dapps-info.com/

(画像は写真素材 足成より)