論文翻訳: DFINITY Technology Overview Series Consensus System

ABSTRACT

Dfinity ブロックチェーンコンピュータは安全でパフォーマンスの高い柔軟なコンセンサスメカニズムを提供する。当初は認可された (permissioned) 参加モデルのために定義されたが、コンセンサスメカニズム自体はオープンな参加モデルを形成するために任意の Sybil 耐性手段 (proof-of-work や proof-of-stake など) と組み合わせることができる。Dfinity の最大の強みはもっとも挑戦的な proof-of-stake のケースで明らかになる。

Dfinity の中核には分散ランダム性ビーコン (decentralized randomness beacon) があり、時間の経過とともに出力ストリームを生成する検証可能なランダム関数 (VRF) として機能する。ビーコンの背後にある新しい技術は一意性決定論的、非対話的、DKG 親和的なしきい値署名スキームの存在に依存している。このような方法の唯一の既知の例はペアリングに基づくものであり BLS [3, 10] から導出される。

Dfinity ブロックチェーンは Dfinity ビーコンの上に階層化されており、リーダー選出とリーダーランキングのためのランダム性の源としてビーコンを使用している。「重み」はチェーン内のブロックを提案するリーダーのランクに基づくチェーンに割り当てられ、その重みは競合するチェーンから選択するために使用される。Dfinity ブロックチェーンはファイナリティまでの時間を劇的に改善し nothing-at-stake や利己的なマイニング攻撃を排除する公証プロセスによってさらに強化されている。

Dfinity のコンセンサスアルゴリズムはランダムビーコンによって駆動される継続的な定足数の選出によってスケーリングされる。実際に Dfinity には僅か 2 回の確認で数秒のブロック時間とトランザクションのファイナリティを達成する。このシステムはネットワーク分割を含むネットワーク同期の一時的な損失を適切に処理するが、同期下では確実に安全である。

Table of Contents

1. ABSTRACT
2. 1 序文
3. 2 導入
4. 3 コンセンサスプロトコルの高レベル概観
5. 4 モデルと事前知識 [under construction]
   1. 4.1 System Model
   2. 4.2 Threat Model
   3. 4.3 Cryptographic Primitives
   4. 4.4 Dfinity's Block Chain
6. 5 PROBABILISTIC SLOT PROTOCOL AND NOTARIZATION
   1. 5.1 Block Rank and Chain Weight
   2. 5.2 Block Protocol
   3. 5.3 Block Notarization
   4. 5.4 Properties of notarization
7. 6 FINALIZATION
   1. 6.1 Description
   2. 6.2 Properties of Finalization
8. 7 DECENTRALIZED RANDOMNESS BEACON
   1. 7.1 Background on Threshold Cryptography
   2. 4.2 The BLS signature scheme
   3. 4.3 Randomness Generation
9. 8 SCALABILITY
   1. 8.1 Threshold Relay
   2. 8.2 Open Participation
10. 9 SECURITY ANALYSIS
    1. 9.1 Broadcast and Processing
    2. 9.2 Timing and Progress
    3. 9.3 Near-Instant Finality
    4. 9.4 Chain Properties
11. 10 ACKNOWLEDGEMENTS
12. References
13. 翻訳抄

1 序文

Dfinity は分散型のネットワークであり、そのプロトコルはソフトウェアをインストールすることができ、スマートコントラクトの改ざん防止モードで動作できるピアツーピアネットワーク上で動作する信頼性の高い「仮想ブロックチェーンコンピュータ」を生成する。目標は、(短いブロック時間を使用し "confirmation" に少数のブロックのみを必要とするで) 仮想コンピュータが計算を短時間で完了させること、(confirmation の間隔をほぼ一定に保つことによって) 予測可能な処理時間を提供すること、および計算とストレージ容量を (我々の別の論文で論議された新しい検証メカニズムとシャーディングシステムの使用によって) サービス需要の増加に応じて無制限にスケールアップすることである。プロトコルはそのノード特有の重要な割合未満を制御しようとする敵に対して安全でなければならず、暗号のランダム性 (分散化された高度なアプリケーションで必要とされる) を生成しなければならず、数百万のノードまでサイズが大きくなるにつれて分散化の性質を維持しなければならない。

Dfinity は、コンセンサスバックボーン、スマートコントラクト言語、仮想マシン、同時実行コントラクトモデル、デーモンコントラクト、ピアツーピアネットワーク、セキュアブロードキャスト、ガバナンスメカニズム、スケーリング技術などの Dfinity の独立したイノベーションを強調する一連のテクノロジー概要で紹介される。本文書ではコンセンサスバックボーンと暗号のランダム性に焦点を当てる。

Dfinity プロトコルの中核には不偏で検証可能なランダム関数 (VRF) が組み込まれている。VRF はコンセンサスを駆動するだけではなく、シャーディング、検証タワーなどのスケーリング技術の基礎にもなっている。さらに、コンセンサス層によって生成された VRF は、アプリケーション層、すなはちスマートコントラクトと仮想マシンに利用可能である。このように、コンセンサスバックボーンは他の多くのトピックと絡み合っている。

2 導入

Dfinity のコンセンサスメカニズムは Fig. 1 に示すように 4 つの層で構成されており、第一層は登録された Sybil 耐性のクライアント ID を提供する。第二層は分散ランダムビーコンである。第三層にはブロックチェーンがあり、リーダーランキングの確率的メカニズムを通じてランダムビーコンによって駆動される。第四層にはタイムスタンプと発行の保証を提供する分散型公証人 (decentralized notary) があり、採取的にほぼ即時ファイナリティの効果を発揮する。Dfinity のコンセンサス層とコンセンサスメカニズムの他の重要な側面は、以下の主要なカテゴリに要約できる。

第一層: Identity とレジストリ. Dfinity ネットワークのアクティブな参加者はクライアントと呼ばれ、Dfinity 内のすべてのクライアントは登録されている。つまり永続的な匿名 ID を持っている。クライアントの登録は異なるブロックを同じ採掘者に関連付けることが不可能な典型的な proof-of-work ブロックチェーンよりも利点がある。例えば登録に補償金が必要な場合、不正行為をしているクライアントは保証金の全額を失うことになるが、通常の proof-of-work ブロックチェーンの採掘者は不正な動作中のブロック報酬の配分を免除されるのみである。結果として不正行為に対するペナルティは未登録 ID よりも登録 ID の方が大きくすることができる。ブロックチェーンはネイティブトークン自体の値を超える無制限の外部値を追跡することができるためこれはとくに重要である。さらに、Dfinity は新規クライアントをロックアップ期間付きの stake デポジットを介して登録するためのプロトコルを提供することによりオープンメンバーシップをサポートしている。これは第一層の責任である。

第二層: ランダムビーコン. 第二層のランダムビーコンは登録済みのクライアントが共同で生成する偏りをかけることが不可能な検証可能ランダム関数 (VRF) である。VRF のランダム出力はそれぞれ誰もが利用できるようになる直前まで誰も予測することができない。これは一意性と非対話性を持つしきい値署名方式に依存する Dfinity システムの重要技術である。BLS 署名スキームはこれらの機能を提供できる唯一の実用的¹なスキームであり、Dfinity には BLS 組み込みの実装が特に最適化されている [2, 11]。ランダム性の作成にしきい値メカニズムを使用することによって基本的な「最後のアクター」問題が解決される。しきい値メカニズムなしに公開のランダム性を生成する任意の分散プロトコルは、そのプロトコルの最後のアクターが次のランダム値を知っており、プロトコルを中断することを決定できるという問題がある。

第三層: ブロックチェーンとフォークの解決. 第三層は "確率的スロットプロトコル" (PSP; probabilistic slot protocol) を展開する。このプロトコルはチェーンの各高さに対応するクライアントを、その高さのランダムビーコンの不偏出力から決定論的に導出される順序でランク付けする。リスト最上位のクライアントからのブロックがより高い重みを受け取るように、提案者のランクに基づいてブロック提案にも重みが割り当てられる。フォークは、累積ブロック重量の点で「最も重い」チェーンを優先することで解決される。これは従来の proof-of-work のコンセンサスが累積作業量の最大値に基づいている方法と非常に似ている。PSP プロトコルの第一の利点はランキングが瞬時に利用できることであり、予測可能な一定のブロック時間を可能にしている。第二の利点は単一の最高ランクのクライアントが常に存在し、均一なネットワーク帯域幅の利用を可能になることである。代わりに、クライアント間の競合はバーストでの使用を好むだろう。

第四層: 公証とほぼ瞬時のファイナリティ. 特定のトランザクションのファイナリティとは、そのトランザクションが不可逆的に実行されたというシステム全体の合意を意味する。大部分の分散システムは迅速なトランザクションのファイナリティを必要とするが、既存のブロックチェーン技術ではそれを提供できない。Dfinity は第四層にブロック公証 (block notarization) の新しい手法を展開してファイナリティを高速化する。公証は登録されたクライアントによって共同で作成されたブロックに基づくしきい値署名である。チェーンに含めることができるのは公証されたブロックのみである。公証のためにクライアントに提示されるすべてのブロック候補の中から、クライアントはランダムビーコンによって駆動される公開検証可能ランキング (publicly verifiable ranking algorithm) に対して再上位ランクのもののみを公証する。タイミングの悪さによって与えられた高さにおいて複数のブロックが公証される可能性があることから公証はコンセンサスでないことを強調することが重要である。これは明示的に容認されており、すべてのブロックで完全なビザンチン合意を適用する他の proof-of-stake 提案との重要な違いである。Dfinity では公証が完全なコンセンサスでないため高速で短いブロック生成時間を実現している。ただし 1 つのブロックのみが公証されることが多いことから公証は楽観的な合意とみなすことができる。これが当てはまるかどうかは後続の 1 ブロックとリレー時間の後に検出できる (Theorem 9.3 参照)。したがって、ブロードキャストネットワークが正常に機能する場合は常に、公証された 2 つの confirmation にネットワークトラバーサルを加えた時間が経過した後、Dfinity コンセンサスでトランザクションが最終的となる。

Dfinity の公証は主に有効性の保証ではなくタイムスタンプと公開の証明であることを強調したい。公証の段階では、リンクされ公証されたブロックのチェーンを敵対者がひそかに構築し維持することができない。このため Dfinity は利己的採掘攻撃 (selfish mining attack) [4] や nothing-at-stake 問題に悩まされることはない。

しきい値リレーとネットワーク拡張性. Dfinity のコンセンサスは数百万のクライアントネットワーク上で動作するように設計されている。この規模のスケーラビリティを可能にするためにランダムビーコンおよび公証プロトコルは安全かつ効率的に committee に線委任され得るように設計されている。committee とは、登録されているすべてのクライアントからランダムサンプリングされた部分集合であり、(安全のため) しきい値メカニズムを展開し、さらに (効率のため) 非対話型を採用している。Dfinity ではアクティブな committee は定期的に変更される。すべてのクライアントに代わって一時的にプロトコルを実行した後、committee はその実行を別の事前設定された committee にリレーする。Dfinity ではこの手法を "しきい値リレー" (threshold relay) と呼ぶ。

整合性 vs 可用性. ネットワーク分断は Dfinity によって暗黙的に検出され、保守的に処理されることに注意。これは committee の無作為抽出の結果である。ネットワークがほぼ同じサイズの 2 つに分割された場合、ランダムビーコンは数ブロック内に自動的に一時停止しどちら側も続行できなくなるあろう。ネットワークが再接続されるとランダムビーコンは自動的に再開される。片方がネットワークの半分よりも大幅に大きくなるように分割された場合、その 1 つの大きなコンポーネントでプロトコルを続行できるが、それ以外のコンポーネントは一時停止する。このようなネットワーク分割は通信が中断されたときのみ発生するのではない。もう一つの重要でより現実的なケースは、Dfinity クライアントの実装が複数あり、それらがバグの露呈によって合意が一致しない場合である。Dfinity はこのケースを適切に処理する。均等に広く利用されている 2 つのクライアントがあり、それらが不一致になり始めると、両方のクライアントが一時停止する。均等に配布されたクライアントが多数あり、1 つが他のすべてのクライアントに同意しなくなると、ネットワークは継続して分離されたクライアントのみが一時停止する。これはまさに特定のシナリオで望ましい状態である。他のブロックチェーンはこのケースをうまく扱えず、そのようなイベントの発生は彼らにとって現実の脅威となる。その理由は、これらのチェーンが一貫性よりも可用性を重視しすぎているからである。

論文構成. §3 はプロトコルの概要を示している。§4 はシステム、通信および脅威のモデルを指定し、関連する表記法を紹介している。§5-7 では確率的スロットプロトコルとランダムビーコンプロトコルについて詳しく説明している。§8.1 では全てのレプリカではなく事前に構成された committee がプロトコルを安全に実行できるしきい値リレー手法を導入している。§8.2 では麺ばーがぷとこるに参加したり、プロトコルから離脱したりできるオープン参加モデルについて説明している。最後に§9 は Dfinity プロトコルのセキュリティと正当性の証明を提供する。

• ¹RSA ベースの代替手段も存在するが、信頼できるディーラーなしにしきい値鍵を設定することは非実用的である。

3 コンセンサスプロトコルの高レベル概観

役割. Dfinity ピアツーピアネットワークは全ての参加者にメッセージを送信できるブロードキャストネットワークで接続されたクライアントで構成されている。クライアントは 3 つのアクティブな機能を果たす。(a) 分散ランダムビーコンに参加する、(b) 分散公証に参加する、(c) ブロックを提案する。クライアントはまたブロックを観察し、ファイナライズされたチェーンの独自のビューを構築する。

Committee としきい値リレー. スケーラビリティを改善するためにランダムビーコンと公証者は committee によって運営されている。committee はすべてのクライアントの集合とすることができる。大規模ネットワークでは committee はすべてのクライアントのセットよりも小さく、ラウンドごとに (つまりブロックごとに) 変更される。あるラウンドでのランダムビーコン出力は、§8.1 で説明されているしきい値リレー手法にしたがって次のラウンドの committee を選択する。committee の規模は故障確率の計算に基づいて構成される (§4.2.4 参照)。

ブロックランキング. ランダムビーコンと公証者を分散化した側面を抽象化したコンセンサスプロトコルを Fig. 2 に示す。プロトコルはラウンドで進行し、ラウンド番号と (高さと呼ばれる) チェーン内の位置が 1 対 1 で対応する。ラウンド \(r\) の開始時にランダムビーコンは新規で検証可能なランダム値を生成してネットワークにブロードキャストする (Fig. 2, step 2)。\(\xi r\) で示されるラウンド \(r\) のランダムビーコン出力は登録されているすべてのクライアントの優先順位を決定する。どのクライアントもブロックを提案できるが、クライアントの優先度レベルが高いほどブロックが公証され、後続のラウンドのブロック生成者がその上に構築する可能性が高くなる。

公証. クライアントは有効な \(\xi r\) を見つけると、ユーザから収集したトランザクションをブロック候補にプールし公証者に送信する (Fig. 2, step 2)。公証者は特定の期間 (BlockTime) 待機して提案されたブロックを受信する。次に、公証者はランダムビーコンに基づいてランキングメカニズムを実行し、最高ランクのブロックを選択し、署名してブロードキャストする (Fig. 2, step 3)。クライアントは公証されたブロックを受け取るとすぐにそれを使用してブロックチェーンのコピーを拡張し、それぞれのビューでラウンド \(r\) を終了する。最後に、ランダムビーコンは新しいラウンドの開始を示す \(\xi r + 1\) をブロードキャストする。

分散ランダムビーコン. ランダムビーコンプロトコルは完全に分散化されており committee のすべてのクライアントが協同して走査する。それにもかかわらずビーコンは外部からは信頼できる第三者のように動作する (つまり生成された出力と出力のタイミングのみを見ている)。committee はビーコンが生成するすべての出力に対してビザンチン合意プロトコルを実行する必要がないことを強調する。代わりにビーコン出力のそれぞれについての合意は、しきい値署名スキームの一意性プロパティに対して自動的に行われる。これはランダムビーコンがこのように高速で実行される方法を説明しており、それによって Dfinity ブロックチェーンがこのような低いブロック時間を達成できることを説明している。

分散公証者. ランダムビーコンの場合と同様に公証者も完全に分散化されており、committee のすべてのクライアントによって運営され、全体としての動作は信頼できる第三者と同一とみなすことができる。ただしランダムビーコンとは異なり、公証者は疑似乱数ではなくライブ入力 (ブロック) に合意しようとする。このために利用できる "magic" 暗号は存在しないため、完全なビザンチン合意プロトコルが唯一の選択肢となる。しかし、Dfinity の公証者はそれを行う代わりに "通常の操作の下で" コンセンサスを達成する楽観的なプロトコルを実行するだけだが、ラウンドごとに複数のブロックを公証することもある。これが発生した場合、Dfinity のチェーンランキングアルゴリズムが分岐を解決し、その後の通常ラウンドでファイナリティを達成できる。楽観的なプロトコルは非対話型で高速であるため、公証者はランダムビーコンと同じ速度で実行できる。

4 モデルと事前知識

4.1 System Model

4.2 Threat Model

4.3 Cryptographic Primitives

4.4 Dfinity's Block Chain

5 PROBABILISTIC SLOT PROTOCOL AND NOTARIZATION

5.1 Block Rank and Chain Weight

5.2 Block Protocol

5.3 Block Notarization

5.4 Properties of notarization

6 FINALIZATION

6.1 Description

6.2 Properties of Finalization

7 DECENTRALIZED RANDOMNESS BEACON

7.1 Background on Threshold Cryptography

4.2 The BLS signature scheme

4.3 Randomness Generation

8 SCALABILITY

8.1 Threshold Relay

8.2 Open Participation

9 SECURITY ANALYSIS

9.1 Broadcast and Processing

9.2 Timing and Progress

9.3 Near-Instant Finality

9.4 Chain Properties

10 ACKNOWLEDGEMENTS

We would like to thank Robert Lauko, Marko Vukolic, Arthur Gervais, Bryan Ford, Ewa Syta, Philipp Jovanovic, Eleftherios Kokoris, Cristina Basescu and Nicolas Gailly for helpful comments and discussions.

References

1. RANDAO: A DAO working as RNG of Ethereum. https://github.com/randao/randao, 2017.
2. J.-L. Beuchat, J. E. González-Díaz, S. Mitsunari, E. Okamoto, F. Rodríguez-Henríquez, and T. Teruya. High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves. Pairing, 6487:21–39, 2010.
3. D. Boneh, B. Lynn, and H. Shacham. Short Signatures from the Weil Pairing. In Proceedings of the 7th International Conference on the theory and Application of Cryptology and Information Security: Advances in Cryptology, ASIACRYPT ’01, pages 514–532, London, UK, UK, 2001. Springer-Verlag.
4. I. Eyal and E. G. Sirer. Majority is not enough: Bitcoin mining is vulnerable. In International conference on financial cryptography and data security, pages 436–454. Springer, 2014.
5. J. Garay, A. Kiayias, and N. Leonardos. The Bitcoin Backbone Protocol with Chains of Variable Difficulty. In Annual International Cryptology Conference, pages 291–323. Springer, 2017.
6. R. Gennaro, S. Goldfeder, and A. Narayanan. Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin wallet security. In International Conference on Applied Cryptography and Network Security, pages 156–174. Springer, 2016.
7. R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Advances in Cryptology — EUROCRYPT ’99: International Conference on the Šeory and Application of Cryptographic Techniques Prague, Czech Republic, May 2–6, 1999 Proceedings, chapter Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, pages 295–310. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999.
8. Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scaling Byzantine Agreements for Cryptocurrencies.
9. D. E. Knuth. Œe art of computer programming. volume 1: Fundamental algorithms. volume 2: Seminumerical algorithms. Bull. Amer. Math. Soc, 1997.
10. B. Libert, M. Joye, and M. Yung. Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares. Theoretical Computer Science, 645:1–24, 2016.
11. S. Mitsunari. Barreto-Naehrig curve implementation and BLS. https://github.com/dfinity/bn, 2017.

翻訳抄

Dfinity のテクニカルオーバービューを記述した 2018 年の論文。公証 (notalization) がブロックの承認を表している? 少し用語の言い替えがある。

1. Timo Hanke, Mahnush Movahedi and Dominic Williams. 2016. DFINITY Technology Overview Series Consensus System. In Proceedings of Technology Overview Series, DFINITY Stiftung, Jan. 23, 2018 (Technology Overviews), 16 pages