分散アルゴリズム

論文翻訳: The Sleepy Model of Consensus

Takami Torao 2022年の論文 #Sleepy
  • このエントリーをはてなブックマークに追加
Rafael Pass
CornellTech
Elaine Shi
Cornell
May 11, 2017

Abstract

分散コンピューティングに関する文献では (暗号に関する文献も同様に) 通常、誠実な (honest) プレイヤーと故障した (corrupted) プレイヤーの 2 種類を考慮する。そして誠実なプレーヤーの割合に下限を設定して障害耐性を分析する。しかし誠実なプレーヤーは既定のプロトコルに従うだけでなくプロトコルの実行中ずっとオンラインであることが前提となる。ただ (ブロックチェーンプロトコルのような) "大規模な" コンセンサスプロトコルが現れたことによって数百万のプレーヤーが存在するようになるとこの前提は非現実的ではなくなった。この研究ではプレイヤーはオンライン (警戒中; alert) またはオフライン (睡眠中; asleep) になることができ、それらのオフライン状態はプロトコル実行中のどの時点でも変化する可能性があるという "sleepy" 計算モデルにおける分散プロトコルの研究を開始する。我々が取り組む主な疑問は:

任意の時点で、プレイヤーの一部のみが実際にオンラインであるような "発散的な参加" (sporadic participation) の下でも維持できるコンセンサスプロトコルを設計できるだろうか?

我々の知る限り、すべての標準的なコンセンサスプロトコルは、たとえオンラインの 99% のプレイヤーが誠実だとしてもこのような散発的な参加の下では破綻してしまう。

この論文ではこのような問題に対して肯定的な答えを提示する。我々はオンラインのプレーヤーの過半数が誠実であると仮定した場合に耐性を持つ、sleepy モデルにおけるコンセンサスプロトコルの構成を提示する。我々のプロトコルは公開鍵基盤 (PKI)、共通乱数列 (CRS; 訳注: 共通参照列の誤記?) に依存し、Dwork-Naor-Sahai (STOC'98) のタイミングモデルで安全性が証明されている。ここで、すべてのプレーヤーは弱く同期した時計 (weakly-synchronized clocks) (すべての時計は "実時間" から \(\Delta\) 以内) を持ち、ネットワーク上で送られるすべてのメッセージは \(\Delta\) 時間以内に配信され、亜指数敵に安全な衝突耐性を持つハッシュ関数と拡張トラップドア順列が存在すると想定している。驚くべきことに、我々のプロトコルは分散コンセンサスに対する標準的なアプローチから大きく逸脱しており、代わりに Nakamoto のブロックチェーンプロトコルの背後にある重要なアイディアに依存している (ただし "proofs-of-work" の必要性は排除している)。我々は最後に、不誠実な大多数のオンラインプレーヤーが存在する場合、sleepy コンセンサスは不可能であることを観察する。

Table of Contents

  1. Abstract
  2. 1 導入
    1. 1.1 コンセンサスの Sleepy モデル
    2. 1.2 主な結果
    3. 1.3 技術的概要
    4. 1.4 パーミッションド設定とパーミッションレス設定での適用
    5. 1.5 関連研究
  3. 2 定義
    1. 2.1 プロトコル実行モデル
    2. 2.2 準拠した実行
    3. 2.3 表記規則
  4. 3 問題定義
    1. 3.1 ステートマシンレプリケーション
    2. 3.2 ブロックチェーンの形式的な抽象化
      1. 3.2.1 Chain Growth
      2. 3.2.2 Chain Quality
      3. 3.2.3 Consistency
    3. 3.3 Blockchain Implies State Machine Replication
  5. 4 静的な破損に対する Sleepy コンセンサス
    1. 4.1 Valid Blocks and Blockchains
    2. 4.2 基本的な Sleepy コンセンサスプロトコル
    3. 4.3 Compliant Executions
    4. 4.4 Theorem Statement
  6. 5 Proof for Static Security
    1. 5.1 Simplified Ideal Protocol \(\Pi_{\sf ideal}\)
    2. 5.2 Convergence Opportunities
    3. 5.3 Chain Growth Lower Bound
    4. 5.4 Chain Quality
    5. 5.5 Consistency: Proof Intuition
    6. 5.6 Consistency: the Proof
      1. 5.6.1 Definition of Pivots and Strong Pivots
      2. 5.6.2 Strong Pivots Force Convergence
      3. 5.6.3 Strong Pivots Recur Frequently
      4. 5.6.4 Proof of Consistency
      5. 5.6.5 Tighter Consistency Analysis
    7. 5.7 Chain Growth Upper Bound
    8. 5.8 Real World Emulates the Ideal World
    9. 5.9 証明におけるランダムオラクルの除去
  7. 6 Achieving Adaptive Security
    1. 6.1 Intuition: Achieving Adaptive Sleepiness
    2. 6.2 Intuition: Achieving Adaptive Corruption
    3. 6.3 Preliminary: Non-Interactive Zero-Knowledge Proofs
    4. 6.4 適用的安全性を持つ Sleepy コンセンサス
    5. 6.5 Theorem Statement
  8. 7 Proofs for Adaptive Sleepiness and Adaptive Corruption
    1. 7.1 Ideal-World Protocol: Adaptive Sleepiness and Static Corruption
    2. 7.2 Intermediate-hybrid-protocol
    3. 7.3 The Real World Emulates the Hybrid World
    4. 7.4 Proofs for Adaptive Sleepiness and Adaptive Corruption
  9. 8 Lower Bound
    1. 8.1 Lower Bound on Resilience
    2. 8.2 Foreknowledge of \(\Delta\) is Necessary
  10. Acknowledgements
  11. References
  12. A Tighter Consistency Proof
    1. A.1 Strong Pivots Recur Frequently
    2. A.2 Proof of Consistency
  13. B Chernoff Bound
  14. 翻訳抄

1 導入

コンセンサスプロトコルは分散コンピューティングの中核であり、マルチパーティ暗号プロトコルの基礎となるプロトコルを提供するものである。この論文では、分散システムの文献でしばしばステートマシンレプリケーションや線形化可能性と呼ばれている "線形順序ログ" (linearly ordered log) を実現するためのコンセンサスプロトコルを考察する。このようなプロトコルは一貫性 (consitency) と活性性 (liveness) という 2 つの重要な耐障害性特性を尊重しなければならない。一貫性はすべての誠実なノードが同じログのビューを持つことを保証し、また活性性はトランザクションが迅速にログに組み込まれることを必要とする。

分散コンピューティングに関する文献や暗号に関する文献では、一般に誠実なプレーヤーと破損/敵対的な (corrupted/adversarial) プレーヤーの 2 種類を想定する。そして誠実なプレーヤーの割合に下限を設けて (例えば少なくとも過半数のプレーヤーが誠実であると仮定して) 上述の障害耐性を分析する。しかし誠実なプレーヤーは規定のプロトコルに従うだけではなく、プロトコルの実行中ずっとオンラインであることを前提としている。これは、コンセンサスプロトコルが一般的に導入されてきた従来の環境では完全に合理的な前提であるが (例えば "Facebuck" のような企業内で "Faceback Credit" のようなアプリケーションをサポートするためのノード/プレーヤーはおよそ数十程度)、例えばブロックチェーンプロトコルなどの "大規模" コンセンサスプロトコルの出現により、数百万のプレーヤー間で合意を達成したい場合にはこの後半の前提は非現実的になってしまう (例えばビットコインでは、ビットコインを持っているユーザのうち実際にマイナーとして参加しているのはごく一部である)。

1.1 コンセンサスの Sleepy モデル

この問題を解決するために我々は "sleepy" 計算モデルにおける分散プロトコルの研究を開始する。このモデルでは、プレーヤーはオンライン ("起きている/ 活動している"; awake/active) かオフライン ("寝ている"; asleep) のいずれかとなり、そのオンライン状態はプロトコル実行中の任意の時点で変更される可能性がある。我々が取り組む主な疑問は次の通りである:

"散発的な参加"、つまりある時点でプレーヤーの一部しか実際にオンラインではない場合に、オンラインプレーヤーの適切な割合 (例えば過半数) が誠実であると仮定して、弾性 (resilient) のある合意プロトコルを設計することができるのか?

我々の知る限りこの問題は Micali [32] が最近の原稿で初めて提起したものである1。彼曰く "… 1 ラウンドも参加しなかったユーザは悲観的に悪質と判断されるが、実際にはネットワーク接続の問題が発生したか、単に休息しただけの可能性がある。[…] 1 つの可能性として、現在の Honest Majority of Users 仮定を "現在存在している" ユーザではなく "現在活動している" ユーザにのみ適用されるように修正することが考えられる。" しかし Micali の作業では別の道が追求されている2。対して我々のゴールはこの疑問を解決することである。このモデルでは、起きているプレーヤーの少なくとも過半数が誠実であると仮定しない限り (起きているプレーヤーの集合が実行中に任意に変化しうる場合) 合意が不可能であることは容易に分かる。その理由は、長い間眠っていたプレーヤーが、誠実なプレーヤーによる本当の行動なのか、それとも悪意のあるプレーヤーによってエミュレートされた "偽" の行動なのかを区別できないため、少なくとも \(\frac{1}{2}\) の確率で "偽" の方を選ばなければならないということである。我々はこれを (セクション 8 の) 定理 10 で定式化する。

そこで我々は次のような疑問を考える:

オンラインプレーヤーの過半数が誠実であると仮定した場合、一貫性と活性を達成するコンセンサスプロトコルを設計することができるか?

我々の知る限り、99% のインラインプレーヤーが誠実であると仮定しても、すべての標準的なコンセンサスプロトコルは sleepy モデルで破綻する! 簡単に説明すると、標準的なプロトコルは 2 つのタイプに分けられる。1) 同期通信 (synchronous communication) を前提としたプロトコル (誠実なプレーヤーによって送信されたすべてのメッセージは、次のラウンドでほかのすべての誠実なノードによって受信されることが保証されている)、または 2) 部分的同期 (partially synchronous) または非同期 (asynchronous) の通信を扱うプロトコル (この場合、実際に参加しつつある誠実なプレーヤー数に関する厳しい境界を知る必要がある) である。より詳細には:

  • [13, 17, 22] といった従来の同期プロトコルは、合意に達するために次のラウンドまたは既知の境界付き遅延 \(\Delta\) 以内にメッセージが配信されることに強く依存している。これとは対照的に、sleepy モデルでは誠実なプレーヤーが (\(\Delta\) より大きい) 長い時間眠りにつき、将来のある時点で目を覚ますと、そのプレーヤーはかなり名が一円ですべての "古い" メッセージを受信する (同期性の仮定が破られる)。これらのプロトコルでは、このようなプレーヤーは古いメッセージをすべて拒否し、ほかのプレーヤーと合意に達することはないだろう。例えば [13] のプロトコルを修正し、トランザクションがある閾値のプレーヤー (例えば過半数）によって承認されたとき、プレーヤーが何かの合意に達したとしたくなるかもしれないが、実際にはプロトコルが実際に活動しているプレーヤーの数を認識できないため閾値ををどのように設定するかが問題になる!

  • [8, 12, 14, 30, 33, 39] のような部分同期プロトコルまたは非同期プロトコルは一見して同期プロトコルで上記の問題を対処しているように見える: 我々は単に眠っているプレーヤーが長い遅延でメッセージを受信するとみなすことができる (これは通信の非同期モデルで許可されている)。ここで代わりに問題となるのは、活動しているプレーヤーの数がプレーヤーの総数よりも大幅に少なくなる可能性があるという事実であり、これはトランザクションが承認されることすらないということを意味する! もう少し正確には、これらのプロトコルはある数のノードがトランザクションを "確認" (acknowledged) したときにそれらを承認する。例えば Castro と Liskov の古典 BFT プロトコル [12] (全プレーヤーの \(\frac{2}{3}\) が誠実であると仮定した標準モデルで弾性を持つ) では、\(N\) を当事者の総数として、プレーヤーはあるメッセージの \(\frac{2N}{3}\) の "確認" (confirmation) を聞いたときのみトランザクションを承認する。ここでの問題は、例えば \(N\) 個のプレーヤーのうち半分しか活動していない場合にプロトコルが止まってしまうことである。また同期プロトコルの場合は活動しているプレーヤーの数がわからないとこの閾値をどのように変更すればいいのかがわからない。

  • 1我々の論文はそれより後のものだが、この論文を書いた当初の時点では実はこのことを認識していなかった。この論議は 2016 年 8 月の arXiv 版に存在していたが彼の最新の原稿には存在しない。
  • 2簡単に説明すると、彼はこの緩和された誠実さの仮定の下で弾性を保つプロトコルを設計するのではなく、誠実なプレーヤーだけが、頻度は低いが個別に定められたラウンドで参加することを求める(そして定められたラウンドで参加を逃すと破損と見なされる) という、比較できない "誠実だが怠惰" (honest-but-lazy) の仮定でプロトコルを設計している。今後、我々のプロトコルにおける誠実戦略はこのような怠惰の特性も満たすことになる。

1.2 主な結果

我々の主な結果は上記の疑問に肯定的にこたえるものである。我々は sleepy モデルにおけるコンセンサスプロトコルを構築し活動しているプレーヤーの過半数が誠実であることだけを仮定した弾性のあるプロトコルを提示する。我々のプロトコルは ”覆いのない" (bare) 公開鍵基盤 (PKI)3、共通乱数列 (CRS)4 の存在に依存し、すべてのクロックが "実時間" の \(\Delta\) 以内にありネットワーク上で送信されるすべてのメッセージは \(\Delta\) 時間以内に配送されるという弱く同期した時計をすべてのプレーヤーが持っていると仮定した Dwork-Naor-Sahai [34] のタイミングモデルの単純版で安全であることが証明されている。

最初のプロトコルは衝突耐性のあるハッシュ関数の存在にのみ依存する (そして標準的なコンセンサスプロトコルに比べて実用的で非常に単純に実装することができる)。しかしこのプロトコルは静的な破損と、どのノードがどの時間ステップで活動しているかという静的な (固定の) スケジュールしかサポートしない。これを "静的オンラインスケジュール" と呼ぶ。

定理 1 (非公式). 衝突耐性を持つハッシュ関数 (CRH; collision-resistant hash function) のファミリーが存在すると想定する。このとき Bare PKI、CRS およびタイミングモデルにおいて、静的オンラインスケジュールと静的破損を仮定し、実行中の任意の時点で目を覚ましたプレイヤーの過半数が誠実である限り、一貫性と活性性を実現するステートマシンレプリケーションのプロトコルが存在する。

次のプロトコルは、最初のプロトコルを強化して、どのノードが何時オンラインであるかを敵対的に任意に選択できるようにしたもので、プレーヤーの適応的な (adaptive) 破損も扱えるようにしたものである。しかし、この新しいプロトコルは指数関数的に安全な衝突耐性ハッシュ関数と拡張トラップドア順列 (後者は非対話的ゼロ知識証明の構成に必要) を仮定する代償として実現するものである。

定理 2 (非公式). 亜指数関数的に安全な衝突耐性ハッシュ関数 (CRH) のファミリーと、拡張トラップドア順列 (TDP; enhanced trapdoor permutations) が存在すると想定する。このとき、Bare PKI、CRS およびタイミングモデルにおいてステートマシンレプリケーションプロトコルが存在し、実行中のどの時点でも目を覚ましたプレーヤーの過半数が誠実である限り、適応的な破損の下で一貫性と活性性を達成する。

おそらく驚くべきことに、我々のプロトコルは分散コンセンサスへの標準的なアプローチから大きく逸脱しており、代わりに Nakamoto の美しいブロックチェーンプロトコル [35] の背後にある重要なアイディアに依存している一方で、"proofs-of-work" [15] の必要を払拭している。我々の知る限り、我々の研究は Nakamoto のプロトコルの背後にあるアイディアが、分散コンピューティングにおける "標準的な" 問題を解決するために役立つことを初めて実証しており、これを我々の主要な概念的貢献と見なしている (そしてうまく行けば他の文脈でも有用となるだろう)。

我々の証明は Pass ら [36] による Nakamoto ブロックチェーンの形式分析を活用してその上に構築されているが、我々はもはや proofs-of-work には依存しないため、いくつかの新しい問題に直面する。我々の主な技術的貢献と分析の大部分はこれらの問題に対処するための新しい組み合わせ解析である。

最後に、ブロックチェーンの背後にあるアイディアを使用してコンセンサスを達成するためのアドホックなソリューション (ただし proof-of-work は使用しない) が提案されていることにも言及する [2, 4, 25]。これらのいずれにも分析は含まれておらず、標準のステートマシンレプリケーションプロトコルからどの程度改善されいるか (さらに深刻なことに、コンセンサスの標準概念を達成しているか) さえも明らかではない。

  • 3つまりプレーヤーには公開鍵を登録する方法がある。誠実なプレイヤーの場合、この登録はプロトコルの開始前に行われるが、破損なプレーヤーは任意の時点で鍵を登録することができる。プレーヤーは自分の秘密鍵の知識を証明する窓の必要はない。
  • 4一般に知られている "架空の" (in the sky) 真の乱数列。

1.3 技術的概要

まず静的オンラインスケジュールと静的破損のみを扱う我々のコンセンサスプロトコルの概要を説明する。次に、適用的なセキュリティを実現するためにこのプロトコルを強化する方法を紹介する。

前述の通り、我々のコンセンサスプロトコルの設計は Bitcoin の proof-of-work に基づくブロックチェーン [35]、いわゆる "Nakamoto コンセンサス" プロトコルからインスピレーションを得たものである。このプロトコルは誰でもプロトコルの実行に参加できる、いわゆる "permissionless 設定" で動作するように設計されている。これに対して我々は、参加プレーヤーの固定集合 \([N]\) を持つ古典的な "permissioned" 計算モデルにおけるコンセンサスを研究する。さらに、プレーヤーは公開鍵 (その真正性が検証可能) を登録できると仮定している。我々の中心的なアイディアはこのプロトコルで proofs-of-work の使用を排除することである。このゴールに向けてまず Nakamoto の美しいブロックチェーンプロトコルの概要を説明する。

Nakamoto consensus in a nutshell. 大雑把に言えば、Nakamoto のブロックチェーンでは、プレーヤーはこれまでのトランザクションと履歴の関数となる何らかの計算パズルを解くことによって "ブロックを採掘" (mining blocks) し、トランザクションを "承認" (confirm) する。より正確には、各参加者はブロックチェーンと呼ばれるトランザクションの "ブロック" のローカルな "チェーン" を維持する。各ブロックは \((h_{-1},\eta,{\sf txs})\) のトリプルで構成され、\(h_{-1}\) はチェーンの前のブロックへのポインタ、\({\sf txs}\) は承認されたトランザクション、\(\eta\) は \((h_{-1},{\sf txs})\) ペアから派生した計算パズルの解である "proof-of-work" である。proof-of-work はこの時点までのブロックチェーン全体に対する "鍵なしデジタル署名" (key-less digital signature) とも考えることができる。ノードはどの時点でも、これまでに見た中で最も長い有効なチェーンを選び、この最も長いチェーンを延長しようとする。

Proov-of-work の削除. 証明可能な保証を維持しながら Nakamoto ブロックチェーンから proof-of-work を削除することは捉えどころがなく証明は自明ではないことが判明した。Nakamoto のプロトコルから proof-of-work を取り除くには次にようにする: 計算能力によるレート制限の代わりに各プレーヤーが許容するパズル解の種類に制限をかける。具体的には \(\mathcal{P}\) をプレーヤーの識別子、\(t\) をブロックタイムと呼び、パズル解を \((\mathcal{P},t)\) 形式と再定義する。誠実なプレーヤーは常に現在時間ステップをブロックタイムとして埋め込む。\(H(\mathcal{P},t) \lt D_{p}\) であればペア \((\mathcal{P},t)\) は "有効なパズル解" であり、\(H\) はランダムオラクル、\(D_{p}\) はハッシュの結果が \(D_p\) よりも小さい確率 \(p\)で存在するようなパラメータである (今のところランダムオラクルでプロトコルを提供するが、まもなく見るようにランダムオラクルは CRS と擬似ランダム関数でインスタンス化できる)。もし \(H(\mathcal{P},t) \lt D_p\) であれば、時間 \(t\) におてい \(\mathcal{P}\) がリーダーに選出されたと言う。同じ時刻ステップで複数のノードがリーダーに選出される可能性があることに注意。

さて、時刻ステップ \(t\) でリーダーに選ばれたノード \(\mathcal{P}\) は "解" \((\mathcal{P},t)\)、前のブロックのハッシュ \(h_{-1}\) および承認すべきトランザクション \({\sf txs}\) を含むブロックでチェーンを拡張することができる。ブロックが本当に \(\mathcal{P}\) によってもたらされたものであることを確認するために、ブロックの内容全体、つまり \((h_{-1},{\sf txs},\mathcal{P})\) が \(\mathcal{P}\) の公開鍵で署名されている必要がある。Nakamoto プロトコルと同様に、ノードは観測した中で最も長い有効なチェーンを選択し、この最も長いチェーンを延長する。

誠実者は現在時刻ステップを \(t\) とする \((\mathcal{P},t)\) 形式の解のみで採掘しようとするが、今のところ敵対者が不正なブロックタイム (例えば過去や未来の時間ステップ) を使うことを防ぐものは何もない。これを防ぐために、有効なチェーンのブロックタイムに以下の制限を追加で課す。

  1. 有効なチェーンは厳密に増加するブロックタイムを持たなければならない。
  2. 有効なチェーンは "未来" のブロックタイムを含むことができない (ここで "未来" はノードのクロックオフセットを考慮し調整される)。

ここで、解決すべき重要な技術的課題が 2 つある。第一に、ブロックタイムルールが活性性を妨げないことを保証することが重要である。つまり敵対者がブロックタイム機構を利用して (例えば偽のブロックタイムを注入することによって) 警戒中ノードを立ち往生させる方法があってはならない。

第二に、ブロックタイムルールは敵対者を厳しく拘束するが、敵対者にはまだ余裕があり警戒中ノードよりも優位に立てる。具体的には前述したように、警戒中ノードは現在 (すなはち実際のタイムステップ) のにおいてのみ "採掘" し、さらに、同じ長さの異なるチェーンを拡張しようとすることはない。対照的に敵対者は複数のチェーンで過去のブロックタイムを再利用しようとすることができる。(Proof of work の設定ではハッシュ関数がチェーンの履歴にも適用されるため "古い" 勝利解を複数のチェーンで再利用することができないことからこの種の攻撃は不可能である; 対照的に我々のプロトコルではハッシュ関数はもはやチェーンの履歴に適用されない。これは、攻撃者が単に異なるトランザクションを追加しようとすることによってリーダーに選出される機会を多く与えてしまうからである。)

我々の主な技術的成果では、この余分な揺らぎ (extra wiggle room) はある意味で重要ではなく、敵対者はプロトコルの一貫性保証を破るためにこの揺らぎを利用できないことを示している。この余分な揺らぎ扱うことは技術的に困難であり、proof-of-work 型ブロックチェーン [20, 36] に対する既存の解析はどれも適用できないことが判明した。より正確には、我々はブロックチェーン形式のプロトコルを使用しているため、Nakamoto ブロックチェーン [20, 36] の既存の分析からアイディアを直接借りられるかどうかを確認するのが自然なアイディアである。既存の研究 [20, 36] ではブロックチェーンの 3 つの特性、すなはちチェーンの成長 (大雑把に言えばチェーンが一定即で成長すること)、チェーンの品質 (敵対者がチェーンの内容を制御できないこと)、そして一貫性 (誠実者が常にチェーンの適切なプレフィクスに同意すること) を定義しており、以前の研究 [36, 38] で示されているように、ステートマシンレプリケーションで必要となる一貫性と活性性を示唆している。したがって、これらの結果によって我々のプロトコルがこれらの特性を満たしていることを示せば十分である。

良いニュースはチェーンの成長とチェーンの質の特性は以前の Nakamoto ブロックチェーン分析 [36] とほぼ同じ方法で証明できる。悪いニュースは、先行研究 [20, 36] の一貫性証明が我々の設定では破綻することである (我々の想定する攻撃者は前述のように強力になったためである)。我々の証明の核心は、これに対処するための新しくそして著しく連戦された分析である。

ランダムオラクルの削除. 前述のプロトコルはランダムオラクルに依存している。我々は、実際には共通参照列 (CRS; common reference string) で選択されるシードを持つ PRF でランダムオラクルをインスタンス化できることに留意する。大まかに言えば、この理由は我々の証明においてハッシュ関数/RPF の出力のみに依存し、あらゆる (たとえ無限の) 攻撃が成功するかを決定するようないくつかの単純な多項式時間計算が可能な事象の存在を実際に示すからである。我々の証明ではランダムオラクルの選択に対して圧倒的な確率でこれらの事象が起こらないことを示す。PRF の安全性によりこれらの事象は PRF のシードの選択に対して無視できる確率でしか起こらない。

適用型の睡眠と破損への対処 (dealing with adaptive sleepiness and corruption). 上記のプロトコルは PRF シードが選択される前にノードが活動するタイミングの選択が行われた場合にのみ機能することに注意。そうでなければ、リーダーに選ばれた誠実なプレーヤーは行動しなければならない時間ステップで単純に眠らされる可能性がある。問題は、ノードがいつリーダーになるかを予測できることである。この問題を克服するために我々は Micali の研究 [31] の美しいアイディアからヒントを得ている。まず各プレーヤーに PRF の秘密シードを選択させ、シードに対するコミットメントを公開鍵の一部として公開させる。次にプレーヤーは自分のプライベート PRF を評価し、PRF が正しく評価されたことをゼロ知識で証明することができる (したがって他の誰もが PRF 出力の正しさを検証することができる)5。最後に、各プレーヤーは自分自身の "private" PRF でランダムオラクルをインスタンス化する。直感的には、これには上記の攻撃を防止するものである。敵対者がどの誠実ノードをスリープ状態にするか選択できたとしても、ブロックをブロードキャストする前にそれらのどれがリーダーに選出されるかを知るすべがないためである。

しかしこれを定式化するのはかなり困難である (そしてプロトコルを修正する必要がある)。問題は、ユーザが PRF のシードを自分で選ぶと "悪いシード" を選択できる可能性があることである (PRF の定義にはこれを防ぐものはない)。この問題を克服するために、ランダムオラクルの評価の代替で "コインを井戸に投げ込む" ことを行う。前述と同様に CRS は PRF のシード \(k_0\) を指定し、さらに各ユーザ \(\mathcal{P}\) は PRF のシード \(k[\mathcal{P}]\) を公開鍵の一部としてコミットする。ノード \(\mathcal{P}\) は次の関数を使って時間 \(t\) に選出されたかを判断できる: \[ {\sf PRF}_{k_0}(\mathcal{P},t) \oplus {\sf PRF}_{k[\mathcal{P}]}(t) \lt D_p \] ここで \(D_p\) は特定の時間ステップで任意の単一ノードが確率 \(p\) で選択されるように調整された難易度パラメータである。さらに、\(\mathcal{P}\) はそれが生成するどのブロックにおいてでも、上記のリーダー選出関数を正しく評価したことをゼロ知識で証明する。

しかし実際に何か得るものはあるのだろうか? 悪意のあるユーザは \(k_0\) を確認した後でもそのシード \(k[\mathcal{P}]\) を選択する可能性があり、これによってそもそも \({\sf PRF}_{k_0}(\cdot)\) があることの効果が相殺される可能性がある! (例えば \({\sf PRF}_{k_0}(\mathcal{P},t)\) \(\oplus\) \({\sf PRF}_{k[\mathcal{P}]}(t)\) の列は明らかにランダムではなくなる。) しかし、ユーザシード \(k[\mathcal{P}]\) がシード \(k_0\) より大幅に短く、暗号プリミティブが指数関数的に安全であれば、ランダムオラクルを \({\sf PRF}\) に置き換えるのと同じ方法で、\(k[\mathcal{P}]\) が \(k_0\) の関数として選択されたとしても敵対者の成功確率は破損している可能性のある各ユーザに対して計数 \(2^L\) だけ増加すると主張することができる。ここで \(L:=|k[\mathcal{P}]|\) は各ユーザシードのビット長 (したがって \(N\) をプレーヤー数とすると最大でも \(2^{NL}\)) であり、基礎となるプロトコルのセキュリティパラメータが十分に大きければセキュリティを破るのには十分ではない。最終的に、同様のスタイルの結合境界を使用して適応型破損に対処することができる。(ただしこのような複雑性を利用することによる効率の低下は軽視できないことに注意。セキュリティパラメータは \(N\) より大きくする必要がある。静的な破損のみを要求し、すべての公開鍵が登録された後に CRS を選択できるようにすれば合理的である ─ この複雑さを活用することなく、したがって効率を損なうこともなく適応型の睡眠に対処できる。)

  • 5本質的には Micali [31] と同じように VRF [32] が必要なのだが、とにかく CRS があるのだからもっと弱いプリミティブに頼れば良い。

1.4 パーミッションド設定とパーミッションレス設定での適用

前述のように、静的な破損 (および静的または適用型の睡眠) に対処する我々のプロトコルの変種は複雑性を利用する必要がないため実世界のシステムで実装して採用することができる。我々は、我々の sleepy コンセンサスモデルが以下のアプリケーションシナリオなどで非常に望ましいと考えている。

パーミッションド設定: コンソーシアムブロックチェーン. 現在、世界中の銀行が "コンソーシアムブロックチェーン" を高知宇するのをブロックチェーン企業が支援するという大きな動きがある。コンソーシアムブロックチェーンは、共同事業体の銀行がそれぞれいくつかのノードを提供して共同でコンセンサスプロトコルを実行し、その上で分散型台帳やスマートコントラクトアプリケーションを実行できるようにする。登録が管理されているためコンソーシアムブロックチェーンはコンセンサスの古典的な "permissioned" モデルに分類される。参加ノードが膨大になる可能性があるため (例えば通常は数百の銀行が、場合によって数役から数千ノードが参加)、PBFT [12]、ビザンチン Paxos [27] など、総帯域幅がプレーヤーの数に対して二次関数的にスケールする設定の従来のプロトコルでは理想的ではないかもしれないと多くの人が推測している。我々の sleepy コンセンサスプロトコルはこの設定にたいして説得力のある代替手段を提供する。sleepy コンセンサスにより委員会の再構成などのタスクは従来のプロトコル [28] のような特別なプログラムパスなしに簡単に達成でき、各銀行はほかの銀行とあまり調整することなく自分のノードを管理することも可能である。

パーミッションレス設定: proof-of-stake. Bentov, Pass および Shi [5] によるその後の研究 Snow White は我々のプロトコルをパーミッションレス設定に適応させ、証明可能で安全な最初の proof-of-stake プロトコルの一つを手に入れた。proof-of-stake プロトコルとはオープンな分散環境で実行されるパーミッションレスコンセンサスプロトコルであり、大まかにいえば各プレーヤーは暗号通貨システムでのステーク量に比例した決議兼を持っている (参照: proof-of-work はプレーヤーが利用可能な計算能力に比例して投票力を持つ)。イーサリアムなどの主要な暗号塚は無駄な計算を省くために proof-of-work ではなく proof-of-stake モデルへの移行を切望している。proof-of-stake を実現するために Snow White [5] はシステム内のステーク分布に依存してコンセンサス委員会を定期的にローテーションするメカニズムを導入し我々の sleepy コンセンサスプロトコルを拡張した。さらに Show White は proof-of-stake システムでよく知られている "nothing at stake" や事後破損 (posterior corruption) といった他の問題にも対処している (これらの問題は proof-of-stake にのみ関係するため本論文の対象外であることに注意)。

独立した研究との比較. proof-of-stake は我々の論文の焦点ではないが、proof-of-stake に関するいくつかの独立した研究 [24, 31] と比較した。具体的には Micali による連戦された研究は古典的なスタイルのコンセンサスプロトコルを適応させ proof-of-stake プロトコルを実現することを提唱している [31]。Kiayias らによる独立した研究 [24] は、ブロックチェーン形式のプロトコルとコイントスのような古典的なプロトコルを組み合わせて proof-of-stake を実現することを提案している。これらの研究はどちらも古典的なスタイルのプロトコルと同様に sleepy モデルでは失敗する可能性がある。これに対し、我々はブロックチェーン型プロトコルを sleepy モデルでのコンセンサスに不可欠な純粋な方法で使用する。また Kiayias のコイントスプロトコルを理想的なランダムビーコンに置き換えても Kiayias の証明は sleepy モデルでは失敗することも指摘し、彼らの証明を sleepy モデルで機能するように解釈しなおす簡単な方法はないようである。。他の proof-of-stake プロトコル [2, 4, 25] も表面的には似ているが、正式なセキュリティモデルや証明可能な保証はなく、我々の証明に不可欠であることが判明した要素も見逃している可能性がある。

我々はコンセンサスに関する豊富な文献を簡単にレビューし、特に破損したノードが規定の動作から任意に逸脱する可能性のあるビザンチン障害に対する安全性を達成するプロトコルに焦点を当てる。

パーミッションドコンセンサスのモデル. パーミッションド設定のコンセンサス [3, 6, 7, 8, 12, 13, 14, 17, 18, 19, 22, 26, 27, 28, 29, 30, 39] は過去 30 年間に渡って活発に研究されてきた。これらのプロトコルはネットワークの同期性、暗号の仮定およびその他の様々な側面に基づいて大まかに分類することができる。

大まかに言えば一般に 2 種類のネットワークモデルが考えられる。同期モデルでは誠実なノードが送信したメッセージは次のラウンドで他のすべての誠実なノードに配信されることが保証されている。また部分同期または非同期プロトコルではメッセージが無限に遅延する可能性があり、ネットワーク遅延に関するいかなる事前上限もない状況でプロトコルは一貫性と活性性を達成しなければならない。暗号の仮定という点では 2 つの主要なモデルが注目されている。認証されたチャネルでノードが相互に接続されている "未認証ビザンチン" (unauthenticated Byzantine) モデル [29]6、そして公開鍵基盤が存在し、ノードがメッセージに署名してそのデジタル署名を転送することのできる "認証ビザンチン" (authenticated Byzantine) モデル [13] である。

パーミッションド同期プロトコル. 多くの実現可能性と実現不可能性の結果が示されている。Lamport ら [29] は "未認証ビザンチン" モデルにおいて \(\frac{1}{3}\) の連合が存在する場合、(同期を仮定しても) 安全な合意を得ることが不可能であることを示した。しかし Dolev と Strong が [13] で示すように、同期的で認証済みビザンチンモデルでは任意の数の破損を許容するプロトコルを設計することが可能である。また \(f\) ラウンド未満の決定論的プロトコルは \(f\) 個の障害ノードを許容できないことも理解されている [13]。ただしランダム性が許容される場合、既存の研究では半分までの破損まで今日できる一定のラウンドが期待されるプロトコルを実証している [17, 22]。

パーミッションド非同期プロトコル. Fischer, Lynch, Paterson [18] による有名な下限 (lower bound) は、決定論的でノードがクロックを読み取らないプロトコルに制限すると、たった一つのノードがクラッシュする可能性がある場合であってもコンセンサスは不可能であることを示している。既知の実行可能性の結果は、通常、次の 2 種類の仮定を置くことによってこのよく知られてた下限を回避する。1) ランダム性の仮定。ランダム性は様々なソースから得られる。例えば架空の共通のコイン (a common coin in the sky) [8, 19, 33]、ノードのローカルランダム性 3, 39]、またはネットワーク配信のランダム性 [7]。そして 2) クロックとタイムアウト。ノードはクロックを読み取り、クロックの値に基づいて行動することができる。このアプローチは PBFT [12] や FaB [30] などのよく知られたプロトコルで採用されており、タイムアウトを使用してリーダーを再選択し、前のリーダーが破損している場合でも活性性を確保することができる。

部分同期または非同期の設定におけるもう一つのよく知られている下限は Dwork ら [14] によるものである。これは、どのようなプロトコルも (ランダム性やクロックを考慮しても) \(\frac{1}{3}\) (またはそれ以上の) 破損した連合が存在すると安全性を達成できないことを示したことでよく知られている。

Guerraoui ら [21] は動的にノードが参加・離脱するような敵対的な環境でもコンセンサスを達成できるように、ノードを nice 特性に基づいて動的にクラスタ分割する技術を提案ている。彼らの手法は隣接する時間ステップでオンラインの誠実なノード集合が完全にバラバラになる可能性があれば sleepy モデルでも失敗する。

パーミッションレスコンセンサス. パーミッションレスモデルは、おそらく Canetti らが示したような強い下限が存在するため [1] 学術的に十分な注目を集めなかった。大まかに言えば、ノード間に認証チャネルが存在しないパーミッションレスモデルでは追加の信頼仮定がなければ多くの興味深いタスクは達成できないと理解している。

驚くべきことに、Bitcoin や Ethereum などの暗号通貨はパーミッションレス設定を普及させ、おそらく一般的な考えに反して、非常に興味深い重要なタスクをパーミッションレスモデルで実現できることを我々に示した。これらの暗号通貨システムの根底には一般に proof-of-work 型ブロックチェーンと呼ばれる根本的に新しいタイプのコンセンサスプロトコルがある [35]。詳細に調べるとこれらのプロトコルは Canetti ら [1] や Lamport ら [29] のような既知の下限を回避している。なぜなら従来のモデルでは考慮されていなかった proof-of-work という新しい信頼の仮定に依存しているためである。

パーミッションレスモデルの形式的な理解は始まったばかりである [20, 36, 37, 38]。特に Garay ら [20] は同期ネットワークにおける Nakamoto ブロックチェーンプロトコルを正式に分析している。Pass ら [36] は彼らの分析を非同期ネットワークに拡張している。さらに最近 Pass と Shi [38] はパーミッションレスコンセンサスを利用して委員会選出を行い、パーミッションドコンセンサスのインスタンスをブートストラップする方法を示しており、この方法で彼らはパーミッションレスコンセンサスの応答時間を漸近的に改善する方法を示している。

最後に、既存のブロックチェーンは利己的マイニング攻撃 (selfish mining attack) [16] に苦しむことが知られており、\(\frac{1}{3}\) の計算能力を持つ連合が最大で半分の報酬を獲得できる。Pass と Shi [37] は最近、正のチェーン品質を持つ任意のブロックチェーンプロトコルから川迫院ブロックチェーン (Fruitchains と呼ばれる) を設計する方法を示している。sleepy コンセンサスプロトコルはブロックチェーン型のプロトコルであるため、同じ利己的マイニング攻撃も継承している。ただし Pass や Shi [37] と同じ手法を利用して Sleepy から公正なブロックチェーンを構築することができる。

  • 6この用語の衝突は分散システムおよび暗号コミュニティで採用されている用語の違いに起因している。

2 定義

2.1 プロトコル実行モデル

暗号の文献でしばしば採用される標準的な対話型チューリングマシン (ITM; Interactive Turing Machine) モデル [9, 10, 11] を想定する。

(弱い) 同期クロック. すべてのノードが時間を刻むクロックにアクセスできると仮定する。より一般的な形式では、ノードのクロックが上限量付きでオフセットされている (正確なクロックから差異を持つ) ことを許可する。これは一般に弱い同期クロックと呼ばれる。我々は、クロックオフセットをネットワーク遅延に変換できるような一般的な変換を適用することが可能であり、その結果、形式モデルでは一般性を失うことなくノードがクロックを同期していると単純に仮定できることを指摘する。

具体的には、一般性を失うことなく、ノードのクロックが最大 \(\Delta\) のオフセットを持つと仮定する。ここで \(\Delta\) はネットワーク遅延の最大値でもある。2 つのパラメータが異なる場合、2 つのパラメータの最大値を取ることができ、常に一定の損失のみが発生する。以下に、最大オフセット \(\Delta\) を持つ弱い同期クロックを、同期クロック下でネットワーク遅延 \(3\Delta\) で設定したように扱える変換を示す。次のような変換を想像してほしい: 誠実なノードは、受信したすべてのメッセージを "ローカルに配信" する前に常に正確に \(\Delta\) 時間だけキューに入れる。言い換えれば、ノード \(i\) がローカル時間 \(t\) にネットワークからメッセージを受信したと仮定すると、ノードは \(\Delta\) 時間これを無視し、ローカル時間 \(t+\Delta\) に受信したメッセージのみを対応する。ここで、メッセージの送信者 (例えばノード \(j\)) が正直である場合、\(j\) は自身のローカル時間 \([t-2\Delta, t+\Delta]\) の間にこのメッセージを送信しているはずである。このことは、誠実なノード \(j\) がそのローカル時間 \(t\) にメッセージを送信した場合、任意の正直なノード \(i\) はそのローカル時間枠 \([t,t+3\Delta]\) の間にローカルにそのメッセージを配信しなければならないことを示唆している。

したがって、これ以降の論文では (弱い同期性を表現する能力を失うことなく) グローバルに同期されたクロックを備えたモデルを考慮する。各クロックの刻みは原子時計ステップ (atomic time step) と呼ばれる。ノードは、各原子時計ステップで無限の多項式量の計算を実行できるだけではなく、多項式で多くのメッセージを送受信できる。

公開鍵基盤. 公開鍵基盤 (PKI) の存在を前提とする。具体的には Unversal Composition フレームワーク [9] と同じ PKI の技術定義を採用する。具体的には PKI が次のことを行う理想的な機能の (mathcal{F}_\{\rm CA}) (現在のプロトコルインスタンスにのみ利用可能) であると仮定する:

  • \(\mathcal{P}\) から \({\tt register}({\sf upk})\) を受信すると: \(({\sf upk}, \mathcal{P})\) を記憶し、\(\mathcal{P}\) からの以後のメッセージを無視する。
  • \({\tt lookup}(\mathcal{P})\) を受信すると: 保存されている \(\mathcal{P}\) に対応する \({\sf upk}\) を返すか、もし見つからなければ \(\perp\) を返す。

この論文では Bare PKI モデルとして、ノードは実行中いつでも公開鍵を (mathcal{F}_{\rm CA}) に登録できるものとする。ただし、通常、誠実なプロトコルでは誠実なノードはプロトコルの実行時に公開鍵を前もって登録することを規定する (それでも破損したノードは遅れて登録することができる)。

破損モデル. 任意の時間ステップ \(t\) の開始時に \(\mathcal{Z}\) は次の形式の命令を発効できる。\[ ({\tt corrupt},i) \ {\rm or} \ ({\tt sleep}, i, t_0, t_1) \ {\rm where} \ t_1 \ge t_0 \ge t \] \(({\tt corrupt},i)\) はノード \(i\) を破損させ、\(({\tt soeep},i,t_0,t_1)\) はノード \(i\) を \([t_0,t_1]\) の間スリープさせる。ここで \(t_1 \ge t_0 \ge t\) である。\({\tt corrupt}\) または \({\tt sleep}\) 命令は時間ステップの最初に発効されなければならないため、\(\mathcal{Z}\) は現在の多時間ステップで送信された誠実なノードのメッセージを検査できず、この時間ステップでノードをスリープさせてそのメッセージを遡及的に消去することができないことに注意。

標準的な暗号モデリングアプローチ [9, 10, 11] に従えば環境 \(\mathcal{Z}\) はいつでも任意の方法で破損ノードと通信することができる。これはその環境が破損したノードの内部状態を確認できることを意味する。破損したノードは規定のプロトコルから任意に逸脱、つまりビザンチン障害を示すことができる。すべての故障したノードは \(\mathcal{A}\) という確率的多項式時間の敵対者によって制御されており、敵対者は破損したノードの内部状態を見ることができる。誠実なノードであれば環境はそれらの内部状態を観測できないが、プロトコル定義によって環境に出力されたすべての情報を観測できる。

要約すると、ノード内科のいずれかの状態になることができる:

  1. 誠実 (Honest). 誠実なノードは起きているか眠っているか (または sleeping/sleepy) のいずれかである。これ以降、ノードが誠実であり、かつ起きている状態を警戒中 (alert) と言う。またノードが誠実であり、かつスリープ状態 (または sleeping/sleepy) を睡眠中 (asleep) と言う。
  2. 破損 (Corrupt). 一般性を損なうことなく、すべての破損したノードは起きていると仮定する。

以後、プロトコルの実行が開始される前に \(\mathcal{Z}\) がすべての \({\tt corrupt}\) (または \({\tt sleep}\) resp.) 命令を発効する必要がある場合、破損 (または sleepiness resp.) は静的 (static) であると言う。また \(\mathcal{Z}\) がプロトコル実行中にいつでも \({\tt corrupt}\) (または \({\tt sleep}\) resp.) 命令を発効できる場合、破損 (または sleepiness resp.) は適応的 (adaptive) であると言う。

ネットワーク配信. 敵対者はノード間のメッセージ配信を担当する。敵対者 \(\mathcal{A}\) は、誠実なノードから送信されたすべてのメッセージが最大 \(\Delta\) 時間ステップですべての誠実なノードに配信されなければならないという制約を尊重する限り、メッセージを任意に遅延または並べ替えることができると仮定する。

眠っているノードが目を覚ますと \((\mathcal{A}, \mathcal{Z})\) は以下を含むメッセージの非順序づけセットを配信するよう要求される:

  • 受信していないが、ノード \(i\) がスリープしていなければ受信していたすべての保留メッセージ、そして
  • \((\mathcal{A},\mathcal{Z})\) が選択した、敵対的に挿入された任意の多項式数のメッセージ

2.2 準拠した実行

ランダム化されたプロトコル実行. セキュリティパラメータ \(\lambda\) を持つプロトコル \(\Pi\) の、\((\mathcal{A},\mathcal{Z})\) のペアに関するランダムな実行を表すために \({\sf view}\) \(\leftarrow\) \({}_${\sf EXEC}^\Pi (\mathcal{A},\mathcal{Z},\lambda)^\Pi (\mathcal{A},\mathcal{Z},\lambda)\) という表記を使用する。具体的には \({\sf view}\) はプロトコル実行中にすべてのチューリングマシンが送受信するすべての入力、出力、およびメッセージの順序づけられたシーケンスを含む確率変数である。実行トレース \({\sf view}\) の時間ステップ数を表すために \(|{\sf view}|\) という表記を使用する。

実行のパラメータ. 大域的に、\(N\) をノードの総数 (上限)、\(N_{\rm crupt}\) を破損ノード数 (上限)、\(\Delta\) を警戒中ノード間のメッセージの最大遅延として表す。より形式的には \((N,N_{\rm crupt},\Delta)\) に関する \((\mathcal{A},\mathcal{Z})\) を次のように定義することができる。

定義 1. (\((N,N_{\rm crupt},\Delta)\) に関する \((\mathcal{A},\mathcal{Z})\)). 以後、非ゼロサポートですべての \({\sf view}\) \(\in\) \({\sf EXEC}^\Pi (\mathcal{A},\mathcal{Z},\lambda)\) に対して次の式が成立する場合に \((\mathcal{A},\mathcal{Z})\) はプロトコル \(\Pi\) に関して \((N,N_{\rm crupt},\Delta)\) であると言う。

  • \((\mathcal{A},\mathcal{Z})\) は \({\sf view}\) において合計 \(N\) のノードを生成し、そのうち \(N_{\rm crupt}\) は破損であり残りは誠実である。
  • もし警戒中ノード \(i\) が \({\sf view}\) 内の時間 \(t\) でメッセージをゴシップするなら、時間 \(t' \gt t + \Delta\) で警戒中の任意のノード \(j\) (\(t\) の後に目覚めたものも含む) はそのメッセージを受信したことになる。

以後、文脈が明確な場合は関心のあるプロトコル \(\Pi\) を明示的に述べることを省略して \((\mathcal{A},\mathcal{Z})\) は \((N,N_{\rm crupt}, \Delta)\) に関するとしばしば言う。

プロトコル固有の準拠ルール (protocol-specific compliance rules). プロトコル \(\Pi\) は特定の準拠ルールを尊重する実行においてのみ、特定のセキュリティ保障を形式的に保証することができる。準拠ルールは \((\mathcal{A},\mathcal{Z})\) に課される制約と見なすことができる。以後、誠実な当事者の支持を指定することに加えて、さらにプロトコル \(\Pi\) が一連の準拠ルールを指定すると仮定する。プロトコル \(\Pi\) の準拠ルールに関する \((\mathcal{A},\mathcal{Z})\) ペアを表すために \[ \Pi{\rm -compilant} \ (\mathcal{A},\mathcal{Z}) \ {\rm pair} \] という表記を用い、また\((\mathcal{A},\mathcal{Z})\) はプロトコル \(\Pi\) に準拠していると言う。

追加のプロトコル規約 (additional protocol conventions). 我々は形式的なモデル化のために普遍的な構成の枠組み [9, 10, 11] を採用する。各プロトコルインスタンスと機能はセッション識別子 sdi と関連付けられている。このセッション識別子は曖昧になる恐れがあるため、明示的に記述することは省略する。理想的な機能は、対象のプロトコルインスタンスに関連しないパーティからのメッセージをすべて無視すると仮定する。

2.3 表記規則

無視できる関数 (negligible functions). 関数 \({\sf negl}(\cdot)\) は、すべての多項式 \(p(\cdot)\) で任意の \(\lambda \ge \lambda_0\) に対して \({\sf negl}(\lambda) \le \frac{1}{p(\lambda)}\) となるような \(\lambda_0\) が存在するとき無視できる (negligible) と言う。

変数の規則. この論文では特に断りのない限りすべての変数はデフォルトでセキュリティパラメータ \(\lambda\) の関数である。\({\sf var}_0 \gt {\sf var}_1\) と言うときはすべての \(\lambda \in \mathbb{N}\) に対して \({\sf var}_0(\lambda) \gt {\sf var}_1(\lambda)\) を意味する。同様に、変数 \({\sf var}\) が正または非負であるという場合、それはすべての入力 \(\lambda\) に対して正または非負であることを意味する。また変数は相互に関数である場合もある。様々な変数がどのように関連しているかは、派生変数を定義し、各プロトコルパラメータの許容ルールを述べるときに明らかになる。重要なことはパラメータが \(\lambda\) に依存しない場合は常にそれを定数と呼んで明示していることである。

特に断りのない限りすべての変数は非負 (\(\lambda\) の関数) であると仮定する。さらに、特に断りのない限りすべての変数は \(\lambda\) の多項式境界 (polynomially bounded) (1 より小さい場合は逆多項式境界 (inverse polynomially bounded)) 関数である。

3 問題定義

このセクションではステートマシンのレプリケーションプロトコルを正式に定義する。ステートマシンレプリケーションは 30 年前から分散システムの文献で研究されている。ステートマシンレプリケーションでは、ノードは一貫性活性性を満たす方法で時間の経過とともに線形に並べられたログに合意する。このセクションでは、ステートマシンレプリケーションの正式な抽象化を明示する。次に Garay ら [20] と Pass ら [36] によって最初に提案された代替ブロックチェーン抽象化を定義する。我々は、Pass と Shi [38] によって示されているようにブロックチェーン抽象化は古典的なステートマシンレプリケーションの抽象化を含意することを指摘する。従って、我々の最終的な目的は古典的なステートマシンレプリケーションを実現することであるが、その足がかりとしてブロックチェーンプロトコルを構築することになる。これとは別に最新のブロックチェーンと従来のステートマシンレプリケーションとの間の、それ自体が興味深いものである。これはコミュニティの常識であったが、我々はこの直感を形式化する。

3.1 ステートマシンレプリケーション

我々は、分散システムの文献でしばしば "全順序ログ" や "線形性" とも呼ばれるステートマシンレプリケーションの抽象化を実現することを目的とする。複製されたステートマシンでは、ノードは基本的にトランザクションのリストである時間経過の \({\sf LOG}\) に同意し、さらに一貫性と活性性が保証される。より正式にはステートマシンレプリケーションの抽象化は以下を満たす。ここでは Pass と Shi [38] と同じ定義を採用する。

入力と出力. 環境 \(\mathcal{Z}\) は時間ステップごとに各警戒中ノードにトランザクションのセット \({\sf txs}\) を入力することができる。各時間ステップで警戒中ノードは環境 \(\mathcal{Z}\) にトランザクションの全順序 \({\sf LOG}\) を出力する (空の場合もある)。

セキュリティ定義. \(T_{\rm confirm}\) を \(\lambda,\) \(N,\) \(N_{\rm crupt},\) \(\Delta\) の多項式関数とする。\((N,N_{\rm crupt},\Delta)\) に関するすべての \(\Pi\)-complaint \((\mathcal{A},\mathcal{Z})\) に対して、十分に大きなすべての \(\lambda \in \mathbb{N}\) に対して \({\sf EXEC}^\Pi(\mathcal{A},\mathcal{Z},\lambda)\) からサンプリングされたビューのうち \({\sf negl}(\lambda)\) を除くすべての部分が次の特性を満たすような無視できる関数 \({\sf negl}\) が存在する。

  • 一貫性 (consistency): 次の条件が満たされる場合、実行トレース \({\sf view}\) は一貫性を満たす:

    • 共通接頭辞 (common prefix). \({\sf view}\) において、ある警戒中ノード \(i\) 時刻 \(t\) に \(\mathcal{Z}\) に \({\sf LOG}\) を出力し、またある (同一または異なる) 警戒中ノード \(j\) が時刻 \(t'\) に \(\mathcal{Z}\) に \({\sf LOG}'\) を出力したとすると、\({\sf LOG} \prec {\sf LOG}'\) または\({\sf LOG}' \prec {\sf LOG}\) のいずれかが成立する。ここで関係 \(A \prec B\) は "\(A\) は \(B\) の接頭辞" という意味である。慣例により任意の \(x\) に対して \(\emptyset \prec x\) と \(x \prec x\) を想定する。

    • 自己一貫性 (self-consistency). \({\sf view}\) において、ノード \(i\) が時刻 \(t\) と \(t' \ge t\) に警戒中となり、時刻 \(t\) と \(t'\) のそれぞれで \({\sf LOG}\) と \({\sf LOG}'\) を出力すると、\({\sf LOG} \prec {\sf LOG}'\) が成り立つとする。

  • 活性性 (liveness): ある実行トレース \({\sf view}\) が \(T_{\rm confirm}\)-liveness を満たすのは次が成立する場合である: \({\sf view}\) において、環境 \(\mathcal{Z}\) が時刻 \(t \le |{\sf view}| - T_{\rm confirm}\) に警戒中ノードに \({\sf txs}\) を入力したとする。このとき、任意の時刻 \(t' \gt t + T_{\rm confirm}\) において警戒中の任意のノード \(i\) について、時刻 \(t'\) におけるノード \(i\) の出力を \({\sf LOG}\) とすると、任意の \({\sf tx} \in {\sf txs}\) は \({\sf LOG}\) に含まれることが成立する。

    直感的には、活性性は警戒中ノードに入力されたトランザクションが \(T_{\rm confirm}\) 時間内にその \({\sf LOG}\) に含まれるようになることを意味する。

3.2 ブロックチェーンの形式的な抽象化

このセクションでは、ブロックチェーンの形式的な抽象化とセキュリティ特性を定義する。Pass と Shi [38] が最近示したように、ブロックチェーンの抽象化は古典的なステートマシンレプリケーションの抽象化を意味する。我々の定義は Pass ら [36] のアプローチを踏襲し、さらに Garay ら [20]、Kiayias と Panagiotakos [23] の以前の定義に基づいている。

我々のモデルは誠実なノードを警戒中ノードと睡眠ノードの 2 種類に区別しているため、警戒中ノードに対してチェーン成長、チェーン品質、一貫性を定義している。ただし、次の点を指摘する: 1) もし警戒中ノードに対してチェーン品質が成り立つならそれは睡眠ノードで成り立つだろう。2) もし一貫性が警戒中ノードで成り立つなら睡眠ノードのチェーンも共通接頭辞と未来の事故移管性を満たすはずだが、睡眠ノードのチェーンは警戒中ノードよりずっと短くなる可能性があるのは明らかである。

入力と出力. 我々はすべての時間ステップで環境 \(\mathcal{Z}\) がすべての警戒中ノードに空の可能性のある入力を提供すると仮定する。さらに、すべての時間ステップで警戒中ノードは環境 \(\mathcal{Z}\) に出力を送信する。非ゼロサポートで \(|{\sf view}| \ge t\) となる特定の実行トレース \({\sf view}\) が与えられ、\(i\) を時刻 \(t\) に \({\sf view}\) で警戒中となるノードとすると、我々は時刻ステップ \(t\) におけるノード \(i\) の環境 \(\mathcal{Z}\) への出力を表すために以下の表記を用いる: \[ {\rm output \ to} \ \mathcal{Z} \ {\rm by \ node} \ i \ {\rm at \ time} \ t \ {\rm in} \ {\sf view}: {\sf chain}_i^t({\sf view}) \] ここで \({\sf chain}\) は抽出された理想的なブロックチェーンを表し、各ブロックにはトランザクションの順序付きリストが含まれている。スリープ状態のノードは再び目が覚めるまで環境への出力を停止する。

3.2.1 Chain Growth

3.2.2 Chain Quality

3.2.3 Consistency

3.3 Blockchain Implies State Machine Replication

4 静的な破損に対する Sleepy コンセンサス

このセクションでは静的な破損と静的なスリープ状態の下で安全な基本的 Sleepy コンセンサスプロトコルを説明する。つまり敵対者 (および環境) は度のノードが破損しているか、またどのノードがどの間隔でスリープに入るかを前もって宣言しなければならない。さらに、攻撃者 (および環境) はどの瞬間においても大まかにいえばオンラインオードの過半数が誠実であるという制約を尊重しなければならない。

簡単のために、まずランダムオラクル \({\sf H}\) が存在するものとして我々の方式を説明し、次に共通参照列を仮定してランダムオラクルを除去する方法を説明する。ランダムオラクル \({\sf H}\) のインスタンスはほかのプロトコルと共有されず、環境 \(\mathcal{Z}\) は \(\mathcal{A}\) を通して間接的にオラクルに問い合わせることはできるが、直接ランダムオラクル \({\sf H}\) に問い合わせることはできないと仮定する。

4.1 Valid Blocks and Blockchains

4.2 基本的な Sleepy コンセンサスプロトコル

Figure 1 に基本的な \({\sf Sleepy}\) コンセンサスプロトコルを示す。このプロトコルはパラメータ \(p\) を入力とし、\(p\) は各ノードが一回の時間ステップでリーダーに選ばれる確率に相当する。生成されたばかりのすべてのノードは \({\sf init}\) エントリポイントを呼び出す。ノードは初期化中に署名鍵ペアを作成し、公開鍵を公開鍵基盤 \(\mathcal{F}_{\rm CA}\) に登録する。

さて、我々の基本的な \({\sf Sleepy}\) プロトコルは proof-of-work ブロックチェーンと非常によく似ているが、計算パズルを解く代わりに時間 \(t\) でリーダーに選ばれたノードが時間 \(t\) でチェーンを拡張することができる仕組みとなっている。ブロックによってチェーンを拡張するには、時刻 \(t\) のリーダーは前のブロックのハッシュ、ノード自身のパーティ識別子、現在の時刻 \(t\)、および確認すべきトランザクションセットを含むタプルに署名するだけである。リーダー選出はランダムオラクルとしてモデル化された公開ハッシュ関数 \({\sf H}\) によって実現できる。

プロトコル \(\Pi_{\rm sleepy}(p)\)
\(\mathcal{Z}\) からの \({\tt init}()\) 入力時:
\(({\sf pk}, {\sf sk}) := \Sigma.{\tt gen}()\)、\(\mathcal{F}_{\rm CA}\) に \({\sf pk}\) を登録、\({\it chain} := {\it genesis}\) とする。
\({\it chain}'\) 受信時:
\(|{\it chain}'| \gt |{\it chain}|\) であり、\({\it chain}'\) が \({\sf eligible}\) と現在時刻 \(t\) に関して有効なチェーンであれば;
\({\it chain} := {\it chain}'\) かつ \({\it chain}\) をゴシップ。
時刻ステップごとに:
  • \(\mathcal{Z}\) から \({\tt transactions}({\sf txs})\) 入力を受信する。
  • \(t\) を現在時刻とし、\(\mathcal{P}\) を現在のノードのパーティ識別子として、\({\sf eligible}^t(\mathcal{P})\) であれば: \[ \begin{eqnarray*} \sigma & := & \Sigma.{\tt sign}({\sf sk}, {\it chain}[-1].h, {\sf txs}, t) \\ h' & := & {\sf d}({\it chain}[-1].h, {\sf txs}, t, \mathcal{P}, \sigma) \\ B & := & ({\it chain}[-1].h, {\sf txs}, t, \mathcal{P}, \sigma, h') \\ {\it chain} & := & {\it chain} \ || \ B \\ \end{eqnarray*} \] そして \({\it chain}\) をゴシップ。
  • \(\mathcal{Z}\) に \({\sf extract}({\it chain})\) を出力。ここで \({\sf extract}\) は \({\it chain}\) のそれぞれのブロックから抽出された \({\sf txs}\) を含んでいる順序付けられたリストを出力する関数である。
サブルーチン \({\sf eligible}^t(\mathcal{P})\)
\({\sf H}(\mathcal{P},t) \lt D_p\) であり、\(\mathcal{P}\) がこのプロトコルの有効なパーティであれば 1 を返し、そうでなければ 0 を返す。
Figure 1. Sleepy コンセンサスプロトコル。難易度パラメータ \(D_p\) はハッシュの結果が確率 \(p\) で \(D_p\) 未満になるように定義されている。ここでは簡略化のためにランダムオラクル H を使用してスキームを説明するが、このセクションで説明するように H を取り除いて疑似乱数関数と共通参照列に置き換えることができる。

4.3 Compliant Executions

4.4 Theorem Statement

5 Proof for Static Security

5.1 Simplified Ideal Protocol \(\Pi_{\sf ideal}\)

5.2 Convergence Opportunities

5.3 Chain Growth Lower Bound

5.4 Chain Quality

5.5 Consistency: Proof Intuition

5.6 Consistency: the Proof

5.6.1 Definition of Pivots and Strong Pivots

5.6.2 Strong Pivots Force Convergence

5.6.3 Strong Pivots Recur Frequently

5.6.4 Proof of Consistency

5.6.5 Tighter Consistency Analysis

5.7 Chain Growth Upper Bound

5.8 Real World Emulates the Ideal World

5.9 証明におけるランダムオラクルの除去

ランダムオラクルを削除して代わりにリーダー選出関数として \({\sf PRF}_{k_0}(\mathcal{P},t) \lt D_p\) を使用するなら証明の修正は難しくない。ここで \(k_0\) は共通参照列に含まれるランダム列である。以下、証明に必要な修正を述べる:

  • まず、理想的な機能 \(\mathcal{F}_{\rm tree}\) がプロトコルを開始する前に \(k_0\) をランダムに選択し、\(k_0\) を敵対者 \(\mathcal{A}\) に開示する中間ハイブリッドプロトコル (intermediate hybrid protocol) を導入する。また、理想的な機能 \(\mathcal{F}_{\rm tree}\) は誠実なノードと破損したノードの両方でリーダーを決定するためのランダムビットを生成する代わりに \({\sf PRF}_{k_0}(\mathcal{P},t) \lt D_p\) を使用する。

    このようなハイブリッドプロトコルは計算上無制限 (computationally unbounded) な準拠 \((\mathcal{A},\mathcal{Z})\) に対してもセキュアであると主張できる。特に、前述の理想的なプロトコル分析でランダムオラクル (RO) のランダムビット \(\vec{v}\) を一度フィックスすると、ある種の悪いイベントを定義できることに注意 (これはランダムオラクルのランダムビットにのみ依存し \((\mathcal{A},\mathcal{Z})\) には依存しない)。これらの悪いイベントが起きない限り、計算上無制限の \((\mathcal{A},\mathcal{Z})\) であってもチェーンの成長、チェーンの品質、一貫性の性質を破ることはできない。さらに、ランダムオラクルのランダムビットが与えられた場合、悪いイベントを効率的にチェックできる多項式時間アルゴリズムが存在することに注目。

    したがって、ランダムオラクルを \({\sf PRF}_{k_0}(\cdot)\) に置き換えると、\(k_0\) の選択に対して定義された確率空間上で、これらの悪いイベントは同様に無視できる確率を除いて起きないはずである。さもなければ悪いイベントをチェックするアルゴリズムは PRF をランダムオラクルと区別する効率の良い敵対者として使用できることになる。同様に、PRF の場合、悪いイベントが起きない限り計算上無限の敵対者でさえセキュリティ特性を破ることはできないはずである。

  • ここで、実際のプロトコルが上記の修正ハイブリッドプロトコルをエミュレートすることを証明するために、シミュレーションの証明を修正することができる。シミュレーション証明の大部分はシミュレーターが \(\mathcal{F}_{\rm tree}\) から \(k_0\) を学習するとき、単に \(k_0\) を \(\mathcal{A}\) に与えてシミュレーターがもはや \(\mathcal{A}\) に対するランダムオラクルクエリーをシミュレートする必要がないことを除いて、上記のランダムオラクルのケースと同一である。

6 Achieving Adaptive Security

6.1 Intuition: Achieving Adaptive Sleepiness

6.2 Intuition: Achieving Adaptive Corruption

6.3 Preliminary: Non-Interactive Zero-Knowledge Proofs

6.4 適用的安全性を持つ Sleepy コンセンサス

以降、\(\mathcal{F}_{\rm CA}.{\tt lookup}(\mathcal{P})\) を意味する略記 \(\mathcal{P}.{\sf upk}\) を使用する。具体的には \(\mathcal{P}.{\sf upk}\) は \(\mathcal{P}.{\sf upk} := ({\sf pk},c)\) と解析することができる。ここで \({\sf pk}\) は署名公開鍵、\(c\) はユーザの PRF 鍵のコミットメントに相当する。

有効なブロックと有効なブロックチェーンは先述の静的安全性スキームと同様の方法で定義されるが、各ブロックがその有効性を保証するための独自のゼロ知識照明を持っているという事実を組み込むために、ブロックの形式と有効性ルールに小さな変更を加える必要がある。

有効なブロック. タプル \[ B := (h_{-1}, {\sf B}, {\sf time}, \mathcal{P}, \eta, \pi, \sigma, h) \] が難易度パラメータ \(D_p\) と公開パラメータ \({\sf params}\) に関して、以下の場合に限り \({\sf B}\) は有効なブロックであると言う:

  1. \(\mathcal{P}\) は現在のプロトコルインスタンスの有効なノードであり、\(\mathcal{F}_{\rm CA}\) に登録されている;

  2. \(\mathcal{P}.{\sf upk} := ({\sf pk},\_)\) を解析すると \(\Sigma.{\tt ver}_{\sf pk}((h_{-1}, {\sf B}, {\sf time}, \pi); \sigma) = 1\) が成り立つ;

  3. \(\mathcal{P}.{\sf upk} := (\_,c)\) を解析し \({\sf params} := (k_0, {\sf crs})\) を解析すると \({\sf NIZK}.{\tt ver}({\sf crs},{\sf stmt}) = 1\) が成り立つ。ここで \({\sf stmt} := (\eta, c, k_0, \mathcal{P}, {\sf time})\) である;

  4. \(\eta \lt D_p\)　である;

  5. \(h = {\sf d}(h_{-1}, {\sf B}, {\sf time}, \mathcal{P}, \eta, \pi, \sigma)\) である。ここで \({\sf d}:\{0,1\}^* \to \{0,1\}^\lambda\) は衝突耐性のあるハッシュ関数 ─ 厳密には衝突耐性のあるハッシュ関数はファミリに対して定義する必要があるが、ここでは簡略化してプロトコル開始前にすでにファミリからサンプリングされているものと仮定する。したがって \({\sf d}\) はただの関数である。

有効なブロックチェーン. \({\it chain}\) を現実世界のブロックの順序づけられたチェーンとすると、難易度パラメータ \(D_p\) と公開パラメータ \({\sf params}\) に関して、以下の場合に限り \({\sf chain}\) は有効なブロックチェーンであると言う:

  • \({\it chain}[0] = {\it genesis} = (\perp, \perp, {\sf time} = 0, \perp, \perp, h = \vec{0})\)。これは一般にジェネシスブロックと呼ばれる;

  • \({\it chain}[-1].{\sf time} \le t\);

  • すべての \(i \in [1..\ell]\) に対していかが成立する:

    1. \({\it chain}[i]\) が難易度パラメータ \(D_p\) と公開パラメータ \({\sf params}\) に対して有効なブロックである;
    2. \({\it chain}[i].h_{-1} = {\it chain}[i-1].h\);
    3. \({\it chain}[i].{\sf time} \gt {\it chain}[i-1].{\sf time}\)、つまりブロック時間は厳密に増加する。

プロトコルの説明. Figure 2 に我々の適用的安全性スキームの \(\Pi_{\sf sleepy}^*\) を示す。従来の静的安全性プロトコルとの主な違いは次の通りである。前述のように各ノード \(\mathcal{P}\) は PRF 秘密鍵 \(k[\mathcal{P}]\) を選択し、\(k[\mathcal{P}]\) のコミットメント \(c\) を公開鍵基盤 \(\mathcal{F}_{\rm CA}\) に登録する。さらに、共通参照列に含まれるより長いランダムシード \(k_0\) が存在する。あるノード \(\mathcal{P}\) が与えられた時間ステップ \(t\) においてリーダーに選出されたかどうかを判断するために、\(\mathcal{P}\) は \({\sf PRF}_{k_0}(\mathcal{P},t) \oplus {\sf PRF}_{k[\mathcal{P}]}(t) \lt D_p\) かどうかをチェックする。\(\mathcal{P}\) がリーダーに選出された場合、ブロックでチェーンを拡張することができ、リーダー選出関数を正しく計算したことを証明する非対話的ゼロ知識証明 \(\pi\) をブロックに含める。

プロトコル \(\Pi_{\rm sleepy}^*(p,{\sf params} := (k_0,{\sf crs}))\)
\(\mathcal{Z}\) からの \({\tt init}()\) 入力時:
\(({\sf pk},{\sf sk}) := \Sigma.{\tt gen}(1^L)\)、\(k \leftarrow_$\{0,1\}^L\)、\(r \leftarrow_$\{0,1\}^L\) に対して \(c := {\sf comm}(k; r)\)、\({\it chain} := {\it genesis}\)、\({\sf usk} := ({\sf sk}, c, k, r)\) とし、\({\sf upk} := ({\sf pk}, c)\) を \(\mathcal{F}_{\rm CA}\) に登録する。
\({\it chain}'\) 受信時:
\(|{\it chain}'| \gt |{\it chain}|\) であり、\({\it chain}'\) が \(D_p\)、\({\sf params}\)、および現在時刻 \(t\) に関して有効なチェーンであれば;
\({\it chain} := {\it chain}'\) として\({\it chain}\) をゴシップ。
時刻ステップごとに:
  • \(\mathcal{Z}\) から \({\tt transactions}({\sf B})\) 入力を受信する。
  • \(t\) を現在時刻とし、\(\mathcal{P}\) を現在のノードのパーティ識別子として、\({\sf usk} := ({\sf sk}, c, k, r)\) を解析する。
  • \(\eta := {\sf PRF}_k(t) \oplus {\sf PRF}_{k_0}(\mathcal{P}, t)\) とし、\(\eta \lt D_p\) であれば:
    \(\pi := {\sf NIZK}.{\tt prove}({\sf crs}, {\sf stmt}, w)\), ここで \({\sf stmt} := (\eta, c, k_0, \mathcal{P}, t)\), \(w := (k, r)\), \(\sigma := \Sigma.{\sf sign}_{\sf sk}({\it chain}[-1].h, {\sf B}, t, \eta, \pi)\), \(h' := {\sf d}({\it chain}[-1].h, {\sf B}, t, \mathcal{P}, \eta, \pi, \sigma)\), \(B := ({\it chain}[-1].h, {\sf B}, t, \mathcal{P}, \eta, \pi, \sigma, h')\), \({\it chain} := {\it chain} \ || \ B\) として \({\it chain}\) をゴシップ。
  • \(\mathcal{Z}\) に \({\sf extract}({\it chain})\) を出力。ここで \({\sf extract}\) は \({\it chain}\) のそれぞれのブロックから抽出された \({\sf B}\) を含んでいる順序付けられたリストを出力する関数である。
Figure 2. 適応的安全性を持つ Sleepy コンセンサスプロトコル。共通参照列 \({\sf params}\) は次のように生成される; \(k_0 \leftarrow_$\{0,1\}^{L_0}\), \({\sf crs} \leftarrow {\sf NIZK}.{\tt gen}(1^L,\mathcal{L})\)

準拠した実行. \((\mathcal{A},\mathcal{Z})\) が \(\Pi_{\rm sleepy}(p)\)-準拠であるとき \((\mathcal{A},\mathcal{Z})\) のペアは \(\Pi_{\rm sleepy}^*(p)\)-準拠であると言う。ただし、ここでは \(\mathcal{Z}\) が適応的にノードを破損させプロトコル実行中にノードを睡眠させることができるとする。前述の通り、\(\mathcal{A}\) は共通参照列を確認した後、破損したノードの公開鍵を \(\mathcal{F}_{\rm CA}\) に登録することが許されている。

暗号ビルディングブロックのパラメータ選択. 我々は PRF 関数、衝突耐性ハッシュ関数、署名スキーム、NIZK は準指数的な強度を持つと仮定する。この論文全体を通して、準指数強度とは、入力長 \(k\) の暗号プリミティブが固定定数 \(\delta \lt 1\) に対して時間 \(2^{k^\delta}\) で実行する任意の敵対者に対して \(2^{-k^\delta}\) の確率を除いて安全であることを意味する。ここでは以下のパラメータを使用する:

  • 各ユーザの PRF 鍵 \(k\) はビット長 \(L = (2N+\log^2 \lambda)^\frac{1}{\delta}\) を持つ;
  • 共通参照列 \(k_0\) はビット長 \(L_0 = (2LN)^{\frac{1}{\delta}}\) を持つ;
  • ハッシュ関数、電子署名スキーム、NIZK など他のすべての暗号スキームは入力長 \(L=(2N+\log^2 \lambda)^\frac{1}{\delta}\) を持つ。

6.5 Theorem Statement

7 Proofs for Adaptive Sleepiness and Adaptive Corruption

7.1 Ideal-World Protocol: Adaptive Sleepiness and Static Corruption

7.2 Intermediate-hybrid-protocol

7.3 The Real World Emulates the Hybrid World

7.4 Proofs for Adaptive Sleepiness and Adaptive Corruption

8 Lower Bound

8.1 Lower Bound on Resilience

8.2 Foreknowledge of \(\Delta\) is Necessary

Acknowledgements

References

  1. Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, and Tal Rabin. Secure computation without authentication. In CRYPTO, pages 361–377, 2005.
  2. User ”BCNext”. NXT. http://wiki.nxtcrypto.org/wiki/Whitepaper:Nxt, 2014.
  3. Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC ’83, pages 27–30, New York, NY, USA, 1983. ACM.
  4. Iddo Bentov, Ariel Gabizon, and Alex Mizrahi. Cryptocurrencies without proof of work. In Financial Cryptography Bitcoin Workshop, 2016.
  5. Iddo Bentov, Rafael Pass, and Elaine Shi. Snow white: Provably secure proofs of stake. https://eprint.iacr.org/2016/919.pdf.
  6. Alysson Neves Bessani, João Sousa, and Eduardo Adílio Pelinson Alchieri. State machine replication for the masses with BFT-SMART. In DSN, 2014.
  7. Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. J. ACM, 32(4):824–840, October 1985.
  8. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In CRYPTO, pages 524–541, 2001.
  9. R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In FOCS, 2001.
  10. Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish. Universally composable security with global setup. In Theory of Cryptography. 2007.
  11. Ran Canetti and Tal Rabin. Universal composition with joint state. In CRYPTO, 2003.
  12. Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In OSDI, 1999.
  13. Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. Siam Journal on Computing - SIAMCOMP, 12(4):656–666, 1983.
  14. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 1988.
  15. Cynthia Dwork and Moni Naor. Pricing via processing or combatting junk mail. In CRYPTO, 1992.
  16. Ittay Eyal and Emin Gun Sirer. Majority is not enough: Bitcoin mining is vulnerable. In FC, 2014.
  17. Pesech Feldman and Silvio Micali. An optimal probabilistic protocol for synchronous byzantine agreement. In SIAM Journal of Computing, 1997.
  18. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, April 1985.
  19. Roy Friedman, Achour Mostefaoui, and Michel Raynal. Simple and efficient oracle-based consensus protocols for asynchronous byzantine systems. IEEE Trans. Dependable Secur. Comput., 2(1):46–56, January 2005.
  20. Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Eurocrypt, 2015.
  21. Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec. Highly dynamic distributed computing with byzantine failures. In PODC, pages 176–183, 2013.
  22. Jonathan Katz and Chiu-Yuen Koo. On expected constant-round protocols for byzantine agreement. J. Comput. Syst. Sci., 75(2):91–112, February 2009.
  23. Aggelos Kiayias and Giorgos Panagiotakos. Speed-security tradeoffs in blockchain protocols. IACR Cryptology ePrint Archive, 2015:1019, 2015.
  24. Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain protocol. Cryptology ePrint Archive, Report 2016/889, 2016. http://eprint.iacr.org/2016/889.
  25. Sunny King and Scott Nadal. PPCoin: Peer-to-Peer Crypto-Currency with Proof-of-Stake, August 2012.
  26. Leslie Lamport. The weak byzantine generals problem. J. ACM, 30(3):668–676, 1983.
  27. Leslie Lamport. Fast paxos. Distributed Computing, 19(2):79–103, 2006.
  28. Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. Vertical paxos and primary-backup replication. In PODC, pages 312–313, 2009.
  29. Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, July 1982.
  30. Jean-Philippe Martin and Lorenzo Alvisi. Fast byzantine consensus. IEEE Trans. Dependable Secur. Comput., 3(3), 2006.
  31. Silvio Micali. Algorand: The efficient and democratic ledger. https://arxiv.org/abs/1607.01341, 2016.
  32. Silvio Micali, Salil Vadhan, and Michael Rabin. Verifiable random functions. In FOCS, 1999.
  33. Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of BFT protocols. In ACM CCS, 2016.
  34. P. Mockapetris and K. Dunlap. Development of the Domain Name System. In SIGCOMM, pages 123–133, Stanford, CA, 1988. 51
  35. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. 2008.
  36. Rafael Pass, Lior Seeman, and Abhi Shelat. Analysis of the blockchain protocol in asynchronous networks. https://eprint.iacr.org/2016/454.
  37. Rafael Pass and Elaine Shi. Fruitchains: A fair blockchain. Manuscript, 2016.
  38. Rafael Pass and Elaine Shi. Hybrid consensus: Efficient consensus in the permissionless model. Manuscript, 2016.
  39. Yee Jiun Song and Robbert van Renesse. Bosco: One-step byzantine asynchronous consensus. In DISC, pages 438–450, 2008.

A Tighter Consistency Proof

A.1 Strong Pivots Recur Frequently

A.2 Proof of Consistency

B Chernoff Bound

翻訳抄

暗号論的ハッシュ関数とゼロ知識証明を使ってプロセスごとに固有の乱数を内密に生成し、その値が既定のしきい値 \(\lambda\) より小さければ当選というスキーマの委員会選出を行う Sleepy Consensus に関する 2017 年の論文。Algorand が VRF をハッシュ関数と ZKP に置き換えたようなアイディア。

  1. Pass Rafael, Shi Elaine. The sleepy model of consensus. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017. p.380-409.