NIIについて / About NII

「ビザンチン将軍問題」とは何か(69-4)

ビットコインが通貨になるには、その解決が不可欠

仮想通貨の不正使用とビザンチン将軍問題

 ビットコインを仮想通貨として利用するには、取引内容の改ざんや二重使用などの不正を防がなければならない。こうした不正は、情報学やコンピュータサイエンスでは「ビザンチン将軍問題」(Byzantine Generals Problem)と呼ばれる問題とよく似ている。

 さて、ビザンチン将軍問題とは、2014年にチューリング賞を受賞した数学者のレスリー・ランポート博士(Leslie Lamport)らが考案した分散システム上の信頼性に関わる問題である[1]。なお、ランポート博士はLaTeX(電子組版 システムTeX 用の論文作成用マクロパッケージ)の作成者として有名だが、研究者としての専門は分散システムの基本アルゴリズムである。

 ビザンチン将軍問題の舞台は、ビザンチン帝国の将軍たちがそれぞれ部隊を率いて敵を包囲している戦場である(図1)。各部隊はそれぞれ離れた場所にいて、伝令を相互に送ることでしか連絡できない。戦局は、将軍たちがいっせいに指令を出して攻撃を仕掛ければ勝てるが、一部の部隊だけで攻撃を仕掛けると負けてしまうという状態。つまり、攻撃か撤退かのどちらかを、全将軍が一致して同意しなければならないのだ。しかし、将軍たちの中には裏切り者、つまり敵に寝返っている将軍がいるかもしれない。裏切り者の将軍は、他の将軍から攻撃の提案を受けると、撤退の提案にすり替えて別の将軍に伝達するかもしれない。そうなると、一部の将軍は攻撃指令と撤退指令の両方を受け取ることも想定される。最悪、一部の部隊だけが攻撃を開始してしまい、負ける可能性もある。

img69-4.PNG

 図2-A において、攻撃(または撤退)を提案した将軍は、他の将軍たちにその提案を送る。その提案を受け取った将軍は別の将軍に転送するとする。しかし、将軍2が裏切り者の場合は、攻撃を撤退(または撤退を攻撃)に替えて将軍3に送る。このとき将軍3は最初の提案が攻撃だったのか撤退だったのかわからない。なお図2-B のように、ビザンチン将軍問題では、攻撃(または撤退)を提案した将軍が裏切り者である場合も想定する。この場合は他の将軍たちに、攻撃または撤退を替えて送ることもある。

 さてビザンチン将軍問題とは、(裏切り者ではない)誠実な将軍たちが全員一致で攻撃または撤退に同意できる場合、つまり正しい判断に対して、将軍たちの判断を全員一致へと導く方法を考えることである。ランポート博士らの研究により、裏切り者の将軍がN 人のとき、誠実な将軍が2N +1人以上であれば、誠実な将軍どうしの判断が一致できることがわかっている。将軍4人のうち1人が裏切り者である場合(N =1)を図3に示す。

img69-4 -2.PNG

耐故障性のある分散システムに対する難問

 ランポート博士は、このビザンチン将軍問題を、耐故障性のある分散システムにおける同意問題として考えた。ここで言う分散システムは複数のコンピュータが協調することで、1台のコンピュータではできないような処理を実現するものとする。いま話題のクラウドコンピューティングも、分散システムの一形態にすぎない。また、同意とは複数のコンピュータで同じ値を持つことである。

 同意したい値を通信で他のコンピュータへ送ればいいと思うかもしれないが、コンピュータは壊れることがあるし、複数のコンピュータがあればそれだけ壊れるコンピュータも増える。故障しても、そのまま止まれば対処のしようがあるが、動き続け、しかも間違った通信や処理を始めると非常にやっかいな問題となる。つまり、ビザンチン将軍問題では、故障しても止まらずに、間違った動作を行うコンピュータを裏切りの者の将軍に見立て、他の正常なコンピュータを誠実な将軍に見立てることで、複数の正常コンピュータが同じ値を持つ方法やその条件を扱ったというわけだ。

 なお、ビザンチン将軍問題は分散システムの教科書であればたいてい取り上げられるポピュラーな話題であり、さらに故障の結果、予測不能な不具合を起こすことをビザンチン故障と呼ぶこともある。これはコンピュータの故障の中でも一番面倒なケースとなる。

問題を解決しなければビットコインは成立しない

 ビザンチン将軍問題とビットコインとの関係であるが、ビットコインでは、取引の改ざんや二重使用がビザンチン将軍問題における裏切り者の将軍に相当し、逆に言えばビザンチン将軍問題を解決しないとビットコインは通貨として成立しない。そこでビットコインは、不正を発見・抑止するメカニズムを導入している(P6-7参照)。これはブロックチェーンと呼ばれる10分単位の取引記録を作るには膨大な計算を必要とするようにし、最も早くブロックチェーンを計算した者にビットコインを渡すことで記録作成のインセンティブを与えるというもの。一方で、過去のブロックチェーンを改ざんしようとすると膨大な計算が必要になるように設計されており、取引の改変が困難なことが、仮想通貨としての継続性を保証している。

 これは見方を変えると、ビットコインにおけるブロックチェーンのメカニズムは、ビザンチン将軍問題における不誠実な将軍への対応策としてみることができ、将来、仮想通貨の取引に限られた状況における、ビザンチン将軍問題に対する新しい解法につながるかもしれない。

 ちなみに、ランポート博士はユーモアのセンスがある研究者で、例題としてビザンチンの将軍を持ち出したのはランポート博士のユーモアからであった。ランポート博士は、ビザンチン将軍問題以外にも、パクソス(Paxos)アルゴリズムと呼ばれる、古代ギリシャの島の議会を舞台にした分散同意システムも提案している。ビザンチン将軍問題では裏切り者の将軍だったが、パクソスアルゴリズムでは、議員が議会途中に帰ってしまうケースを、コンピュータの故障と回復の比喩として考えた。ランポート博士は、このアルゴリズムに関する最初の論文[2]を1990年に学術ジャーナルに投稿したが、ユーモアたっぷりに古代ギリシャの議会を例にアルゴリズムを説明したため、そのジャーナルの編集者は冗談だと思い込んだのか、論文をそのまま放置してしまい、結局、論文がジャーナルに掲載されたのは投稿から9年後の1998年になったという、前代未聞の事件まで起きた。

 なお、パクソスアルゴリズムは、その後、クラウドコンピューティングでは複製データの更新処理などの根幹技術として使われている。ビザンチン将軍問題と同様に有名になる日も近いかもしれない。

(文/図=佐藤一郎[国立情報学研究所 アーキテクチャ科学研究系 教授])

参考文献

[1]Leslie Lamport, Robert Shostak, Marshall Pease: "The Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems, Vol.4, No.3, pp. 382-401, 1982.

[2]Leslie Lamport: "The part-time parliament ", ACM Transactions on Computer Systems, Vol.16, No.2, pp. 133-169, 1998.

PDFダウンロード

第69号/2015年9月発行

仮想通貨の技術と課題
群衆の力を科学に活かす

・黎明期にある仮想通貨をどう捉えるか
・実世界データ間の隠れた構造を探る
・仮想通貨に技術的跳躍をもたらしたブロックチェーン技術
・「ビザンチン将軍問題」とは何か

PDFダウンロード

page3563

注目コンテンツ / SPECIAL