Cardano(ADA)

Cardano(ADA) ウロボロス論文日本語訳 冒頭~1導入まで

注意書き

この文章は、IOHKの論文”Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol”の非公式の日本語訳です。著作権等のすべての権利は、IOHKおよびCardano財団に帰属します。

あくまでも私(レスト)個人による非公式な日本語訳(若干の補足付き)です。また、本文のみの日本語訳で、注については訳しておりません。翻訳間違い等多々あるかもしれませんが、予めご容赦下さい。

なお、公式による日本語訳も今後予定されている? そうなので、公式から出る場合は、この日本語訳はそれまでの繋ぎとなります。

間違い等のご指摘がありましたら、ぜひこちらの記事にコメントを残すか、Twitterアカウントまでお知らせ下さい。よろしくお願いします。

現在の進行状況:「1 導入」まで完了

原論文リンク:Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

ウロボロス:安全性が証明可能なプルーフオブステークブロックチェーンプロトコル

Aggelos Kiayias  Alexander Russell  Bernardo David  Roman Oliynykov

2017年8月21日

要約

我々は「ウロボロス」、厳格なセキュリティ保証を持つ、「プルーフオブステーク」に基づく最初のブロックチェーンプロトコルを示す。我々はビットコインブロックチェーンプロトコルによって達成されたものに匹敵するほどのプロトコルの安全性を確立した。プロトコルは「プルーフオブステーク」のブロックチェーン規律を備えるため、例えばプルーフオブワークのような、物理的リソースによる証明に基づくブロックチェーンに対して、定性的な効率性優位を与える。我々はまた、プルーフオブステークプロトコルにインセンティブを与えるための新しいメカニズムを示す。このメカニズムによれば、誠実な人の振る舞いは近似ナッシュ均衡であり、したがってselfish mining(利己的なマイニング)のような攻撃を中和することを示す。我々はまた、トランザクションの確認と処理における実験的結果を示すことで、現実世界の設定において、我々のプロトコルが実用性を持つことの最初の証拠を示す。

1 導入

ビットコイン[30]のような、プルーフオブワークに基づくブロックチェーンプロトコルの運用に関して、最初に考慮すべきことは、その実行に際して要求されるエネルギーである。これを書いている時点で、ビットコインブロックチェーン上で一つのブロックを生成するためには、2^{60}を超えるハッシュ計算が要求され、驚くべきエネルギーが求められる。実際、早期の計算によって、プロトコルが要求するエネルギーは、一つの小国に匹敵するほどのものであると示されていた[32]。
この状態は、他のよりエネルギー効率に優れ、かつ同様の保証を提供できるメカニズムで置き換えることによって、プルーフオブワークの必要性を除くような代替ブロックチェーンプロトコルの開発を動機付ける。ビットコインのプルーフオブワークメカニズムは、マイナーの一人が次のブロックを生成するという、ランダム化された一種の「リーダー選出」プロセスを容易とする事実を指摘するのは重要であろう。さらには、すべてのマイナーがそのプロトコルに従うならば、この選出はそれぞれのマイナーの計算力に比例する形でランダムに行われる。(このプロトコルから逸脱することは、「selfish mining(利己的なマイニング)」戦略によって例示されるように、この比例関係を歪める恐れがある[21,38])
自然な代替メカニズムは、「プルーフオブステーク」(PoS)の考え方による。リーダー選出プロセスに参加するためにマイナーが計算リソースを投じるよりもむしろ、現在のブロックチェーン台帳に基づいて各々が保有する「ステーク(出資額)」に比例的になるように、彼らの一人をランダムに選出するプロセスを実行する。
実際上、このことは自己参照的なブロックチェーン規律を与える。すなわち、ブロックチェーンの維持はステークホルダー自身により、台帳に記録された各々の保有するステーク額に基づいて彼らに仕事(同様に報酬も)が割り当てられる。このことを除いては、この規律はステークホルダーにさらなる「人工的な」計算要件を一切求めない。ある意味では、このことは理想的に思える。しかしながら、このようなプルーフオブステークプロトコルを実現しようとすると、数々の定義的、技術的、そして解析的な困難が現れ出て来るのである。

過去の仕事
PoSの概念は、ビットコインフォーラム(注1)で広く議論されてきた。プルーフオブステークに基づくブロックチェーン設計は、Bentovらによって、PoWとともに[5]、ブロックチェーンプロトコル[4]のための特有のメカニズムとして正式に研究されてきた。Bentovらは、彼らのプロトコルがいくつかのクラスの攻撃に対しては安全であることを示したものの、PoSに基づくプロトコルを解析するための正式なモデルを与えなかったし、厳密な定義に基づくセキュリティ証明も示さなかった。ヒューリスティック(発見的、経験則的)なプルーフオブステークに基づくブロックチェーンプロトコルが、数々の暗号通貨(注2)に対して提案された(そして実装された)。ヒューリスティックなセキュリティ議論に基づいているため、これらの暗号通貨はセキュリティの面で欠陥があることがしばしば露呈した。種々の攻撃についての議論は、[4]を見よ。
PoSに基づくブロックチェーンプロトコルと、固定された権威者(例えば[17]を見よ)による古典的なコンセンサス(合意)ブロックチェーンとの比較も興味深い。PoSに基づくブロックチェーンと、静的な権威者を想定するそれらとを区別するものは、ステークは時間に応じて変化し、したがって信用の仮定はシステムとともに進展していくということである。
PoWに対する他の代替手段としては、「プルーフオブスペース」[2,20]という概念がある。これは、ブロックチェーンプロトコルの文脈でとりわけ研究されてきた[33]。プルーフオブスペースの設定では、「証明者」はスペース(ストレージ/メモリー)の利用可能状態を示そうとする。PoWの場合と同様に、この概念は物理的リソースを利用するわけであるが、時間とともに要求されるエネルギーがより少なくて済む。関連する概念としては、「プルーフオブスペースタイム」(PoST)がある[28]。しかしながら、いずれにせよ高価な物理的リソース(ストレージあるいは計算力)が求められる。

PoS設計における困難
PoSに基づくブロックチェーンプロトコルにおける基本的な問題は、リーダー選出プロセスを装うことである。ステークホルダーの間で公平かつランダムな選出が達成されるためには、エントロピーがシステムに導入されていなければならない。そしてエントロピーを導入するためのメカニズムは、攻撃者によって改ざんされやすい。例えば、ステークホルダーの一群を支配する攻撃者は、攻撃的なステークホルダーに利するようなプロトコル継承を狙って、ステークホルダー参加者とは異なる系列を試みるプロトコル実行を装おうとするかもしれない。このことは、いわゆる「グラインド」脆弱性に繋がる。そこでは、攻撃者のパーティーは、リーダー選出を偏らせるために計算リソースを使用するだろう。

我々の結果
我々は「ウロボロス」、安全性が証明可能なプルーフオブステークシステムを示す。我々の知る限り、厳密なセキュリティ解析を伴うものとしては、この手のブロックチェーンプロトコルでは最初のものである。より詳しくは、我々の結果は次の通りである。
第一に、我々はPoSに基づくブロックチェーンプロトコルを実現するに際しての問題を定式化するモデルを与える。我々が提供するモデルは[24]の精神に従い、強固なトランザクション(取引)台帳における2つの正式な性質である、「持続性」と「生存性」に焦点を当てる。「持続性」とは、ひとたびシステムのあるノードがあるトランザクションを「安定である(確かなものである)」と宣言したならば、残りのノードも、それが照会され誠実に応答する限り、そのトランザクションが安定である(確かなものである)と報告することを述べるものである。ここに、安定性とは、その性質が持つ確かさに影響を及ぼすいくつかのセキュリティーパラメータkによってパラメータ化される述語(例えば、「kブロックの深さよりも深い」)として理解されるべきものである。「生存性」とは、ひとたび誠実に生成されたトランザクションが、ネットワークノードによって十分な時間有効とされているならば、例えばuステップ時間有効とされているならば、それは安定であるということを保証するものである。生存性と持続性が同時に成り立つならば、誠実に生成されたトランザクションは採用され不変となるという意味で、強固なトランザクション台帳であることが示される。我々のモデルは、PoSに基づくダイナミクス(動学)を容易にするよう適切に改善されている。
第二に、我々はPoSに基づく新しいブロックチェーンプロトコルを記述する。我々のプロトコルでは、パーティーは自由にアカウントを作成し、支払を受け取ったり行ったりし、ステークは時間の経過に応じて変化すると仮定する。リーダー選出プロセスにランダム性を生むため、我々は(とても単純で)安全なコイントスプロトコルの多者間実装を利用する。これは我々のアプローチを、ブロックチェーンの現在の状態に基づいてそのような値を決定論的に定めたり、コイントスの集まりをエントロピー生成方法として用いる[4]従前の手法とは区別する(そしていわゆる「グラインド攻撃」を防ぐ)。また、我々のアプローチに特有のことは、システムはラウンドからラウンドへのステークの変化は無視するという事実である。その代わり、「エポック」と呼ばれる通常のインターバルにおいて、ステークホルダーの現在集合のスナップショットが撮られる。各々のそのようなインターバルの中で安全な多者間計算が行われ、ブロックチェーンそれ自身をブロードキャストチャンネルとして利用するのである。具体的には、各々のエポックでは、ランダムに選択されたステークホルダーの一群がcommittee(委員会)を構成する。committee(委員会)はコイントスプロトコル実行の責を担う。プロトコルの実行結果が、エポックのためのすべてのリーダー選出結果と同様に、次のエポックにおいてプロトコルを実行する次のステークホルダーの一群を決める。
第三に、我々はいかなる攻撃者も持続性と生存性を破ることができないことを証明するための正式な議論を示す。我々のプロトコルは、いくつかのもっともらしい仮定の下で安全である。(1)いかなる誠実なステークホルダーも他のステークホルダーと連絡することのできる上限が決まっているという意味でネットワークは同時的である。(2)誠実なマジョリティから選ばれたステークホルダーたちは、必要に応じて各々のエポックに参加することができる。(3)ステークホルダーは長期間に渡ってオフラインに留まらない。(4)改ざんの適応性は、セキュリティーパラメータについて概ね線形に測定される小さな遅延にしたがう(あるいは言い換えれば、プレイヤーは送信者が匿名のブロードキャストチャンネルへのアクセスを持っている)。我々のセキュリティ議論の核心は、「フォーク可能なストリング」についての組合せ的概念に関する確率的な議論である。それを我々は定式化し、証明し、さらに実験的に検証する。我々の解析では、我々は「covert attack(秘密の攻撃)」という一般のフォーク攻撃の中の特別なクラスを区別する。「covertness(秘密性)」は、例えば[3]にあるように、ここでは安全な多者間計算プロトコルに対する秘密の攻撃者の精神として解釈される。ここで攻撃者はプロトコルを破ることを望んでいるが、そうしているのを知られることを望んでいない。我々は秘密にフォーク可能なストリングは、フォーク可能なストリングの中の遥かに小さな密度を持つサブクラスであることを示す。このことは我々に二つの異なるセキュリティ議論をもたらす。それは効率性とセキュリティ保証についての異なるトレードオフを与える。我々のフォーク可能なストリング解析はPoS設定のセキュリティ議論の一部として適用できる自然で適正な一般的ツールである。
第四に、我々はプロトコルのインセンティブ構造に目を向ける。我々は、我々が(近似)ナッシュ均衡であると証明するシステムの参加者にインセンティブを与える新しい報酬メカニズムを示す。この方法によって、「block withholding(ブロック保留)」や「selfish-mining(利己的なマイニング)」[21,38]といった攻撃は我々の設計によって和らげられる。報酬メカニズムの背後にある核心のアイデアは、プロトコルから逸脱しているパーティーの連合によって抑止することができないプロトコル活動に積極的な報酬を与えることである。このようにして、もっともらしい仮定の下、すなわちあるプロトコル実行にかかるコストが小さいとき、すべてのプレイヤーが合理的ならば、プロトコルに忠実に従うことが均衡であると示すことができる。
第五に、我々は、我々のブロックチェーンプロトコルにシームレスに加えることのできるステーク委任のメカニズムを示す。委任はステークホルダーの集合が高度に分かれている設定においてさえも我々のプロトコルのスケールを可能にするという意味で、我々の事情にとってとりわけ有用である。そのようなケースでは、委任メカニズムはステークホルダーに彼らの「投票権」を委任することを可能とする。すなわち、各々のエポックにおいてリーダー選出プロトコルを実行するcommittee(委員会)へ参加する権利である。liquid democracy(delegative democracy(委任可能民主主義)としても知られる[23])のように、ステークホルダーは望むとき、互いに独立に委任の約束を取り消すことができる。
我々のモデルおよびプロトコルの記述の下で、我々は我々のフレームワークの中で実際に考えられる種々の攻撃がどのように扱われるかを調査する。具体的には、我々はdouble spending attacks(二重使用攻撃)、transaction denial attacks(トランザクション拒否攻撃)、51%攻撃、nothing-at-stake(二重投票)、desynchronization attacks(非同期化攻撃)その他である。最後に、我々は我々の設計の効率性に関する証拠を示す。まず我々はdouble spending attacks(二重支払攻撃)を考える。例証として、我々は保証が99.9%になるトランザクション確認時間について、ビットコインに関するナカモトの解析と比較する。covert(秘密の)な攻撃者に対して、トランザクション確認時間はビットコインよりも10倍から16倍速い。これは攻撃者のハッシュパワーによっており、一般の攻撃者に対しては5倍から10倍速い。さらに、double-spending attacks(二重使用攻撃)についての我々の具体的な解析は、フォーク可能なストリングと秘密にフォーク可能なストリングについての我々の組合せ的な解析によっており、ナカモトのより単純化された解析(注3)よりもはるかに広いクラスの攻撃的行動に適用できる。我々はそれから我々のプロトタイプ実装を調査し、Amazonクラウドで実行したベンチマーク実験を報告する。それは我々のプルーフオブステークプロトコルのパフォーマンスにおける力のショーケースとなる。

関連する仕事
ウロボロスの開発に並行して、いくつかの他のプロトコルが、PoSに基づく分散化台帳の設計スペースにおける種々のポジションを狙って開発されてきた。Sleepy consensus[6]は固定されたステークホルダーの配分を考え(すなわち、ステークは時間にしたがって進展しない)、「複合化された」改ざん設定を狙っている。そこでは、攻撃者はビザンチン障害に加えて、失敗を食い止めるように振る舞うことや、改ざんを回復することが許されている。実際、我々の解析を複合化された改ざん設定に拡張することは容易い。Remark2を参照せよ。それでも、結果的なセキュリティは「遅延を伴った改ざん」の設定においてのみ論じられ、したがって十分に対応できているとは言い難い。Snow White[7]は進展的なステークホルダー分布を取り扱っており、セキュリティを論じるにあたって我々のものと似た改ざん遅延メカニズムを用いている。それにも関わらず、我々のプロトコルとは逆に、Snow Whiteの設計は「グラインド」タイプの攻撃の影響を受けやすく、攻撃者に有利な高い可能性の事象に偏向をかけてしまう。このことは漸近的にはセキュリティを害さないものの、攻撃者の計算力を考慮に入れない具体的なパラメータ化を妨げる。Algorand[27]は改ざんの適応に抵抗力のある「ブロック当たりの」ビザンチン合意アプローチにしたがう分散化台帳を示している。各々のブロックで合意に達する必要があるため、そのようなプロトコルは、PoSブロックチェーンよりもブロックを生成する頻度が概ね遅くなる(ここで、スローダウンの程度は、期待されるビザンチン合意プロトコルの実行の長さに合致する)であろうが、フォークとは無縁となる。この点において、フォークの存在にも関わらず、ブロックチェーンプロトコルには、クライアントが望むようにリスクのレベルを設定できる柔軟性があり、楽観的な意味で、リスクの低いプロファイルクライアントが処理時間を短縮できる。最後に、Fruitchain[36]はPoWに基づくブロックチェーンに対して、報酬メカニズムと近似ナッシュ均衡の証明を示している。我々はブロックチェーンレベルでは似た報酬メカニズムを用いているが、それにも関わらず、PoS設定において実行するため、我々の基礎手順は異なる。アイデアの核心は、[24]にあるような誠実なマジョリティにとってのPoWに基づくビザンチン合意プロトコルと同じ論理を用いた公正な割合の入力を「裏書きする」PoSの類似物を提供することである。

論文の概観
我々はセクション2において基本モデルを展開する。我々のプロトコルの解析を簡素化するため、我々はセクション3にて概説される4つのステージにおいてそれを示す。要するに、セクション4で我々は静的な設定においてプロトコルを記述し解析する。我々はそれからセクション5にて動的な設定に移る。我々のインセンティブメカニズムと均衡の議論はセクション7で示される。我々はそれからプロトコルの強化を、セクション6にて匿名チャンネルについて、セクション8にて委任メカニズムについて示す。これにしたがい、セクション9で我々は興味深い種々の特定の攻撃の下でのプロトコルの回復力について論じる。セクション10で我々はトランザクション確認時間と、Amazonクラウドにおけるプロトタイプ実装の実行から得られた一般的なパフォーマンス結果について論じる。

関連記事

  1. 仮想通貨

    仮想通貨を始めよう その3 長期分散投資のすすめ

    長期分散投資のすすめ~敗者のゲーム―ほぼ負ける素人がそれでもプロに負け…

  2. 仮想通貨

    仮想通貨を始めよう その1 仮想通貨を始める前に知っておいて欲しいこと

    仮想通貨を始める前に知っておいてほしいこと~購入方法、手数料とリスクに…

  3. Cardano(ADA)

    Cardano(ADA) ウロボロス論文日本語訳 9 攻撃についての議論

    この記事はCardano(ADA) ウロボロス論文日本…

  4. NEM

    NEMを自分なりに調べてみた~「富の分配」の理想と現状の課題点~

    NEMを自分なりに調べてみた~「富の分配」の理想と現状の課題点~N…

  5. ポストブロックチェーン通貨

    ポストブロックチェーンの到来~DAG系通貨の未来に迫る~

    ポストブロックチェーンの到来~DAG系通貨の未来に迫る~IOTAと…

コメント

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

リンク

数学ブログもやってます

restmath.com

  1. Cardano(ADA)

    Cardano(ADA)について徹底的に調べてみた その1 ホワイトペーパーを読…
PAGE TOP
error: Content is protected !!