ホワイトペーパー

DFINITYホワイトペーパー日本語訳16(終)

更新日:

本稿について

本稿では、DFINITY White Paper:Consensus Systemのうち第9章「SECURITY ANALYSIS」の9.4「Chain Properties」と「ACKNOWLEDGEMENT」の日本語訳、「REFERENCE」を掲載します。

原文はこちらになります。

スポンサードサーチ

9 セキュリティ分析(続き)

9.4 チェーンの特徴

各ラウンドの最終時点において各レプリカは、append-only(追記のみ可能)のファイナライズされたチェーンに関してそれぞれ独自の見方を持つことを思い出してほしい(アルゴリズム2を参照)。ステートとファイナライズされたチェーンCの内容に関して以下の特性を考える。

定義9.21(チェーンの特性)

a)パラメータkに伴う成長。ラウンドrの最終時点での誠実なレプリカそれぞれのファイナライズされたチェーンは、r - k以上の長さを持つ。
b)一貫性。C及びC'が任意の時点における誠実な2パーティのファイナライズされたチェーンであるならば、CC'のプレフィックスであるか、またはその逆である。
c)パラメータlμに伴うクオリティ。ある誠実なレプリカのファイナライズされたチェーンから任意の連続するl個のブロックを取り出すと、少なくともμl個のブロックはある誠実慣れプリによって提案されたものである。

命題9.22

永続性は、チェーンの一貫性並びにチェーンの成長という特性から導かれる。

証明

あるトランザクションは1つの誠実なレプリカiのファイナライズされたチェーンに取り込まれると仮定して、そのトランザクションが取り込まれるブロックはラウンドrのものとする。他の全ての誠実なレプリカjを考えると、成長の特性により、jのファイナライズされたチェーンも最終的に長さrに到達する。その時点で一貫性の特性は、ラウンドrにおけるjのブロックがiのファイナライズされたチェーンにあるブロックと同一であることを保証する。□

命題9.23

ライブネスは、チェーンのクオリティ並びにチェーンの成長という特性から導かれる。

証明

ある誠実なレプリカから発せられたトランザクションはその他全ての誠実なパーティにピックアップされ、そのパーティのブロック提案に取り込まれる10。成長の特性は、ファイナライズされたチェーンが最終的に任意長になることを保証する。チェーンのクオリティの特性が適用されて、ある誠実なレプリカによって提案されたブロックが最終的にファイナライズされたチェーンの中にあることが保証される。□

(脚注10)

ブロックの提案者が誠実な場合であっても、ブロック提案にトランザクションを取り込めない理由はいくつかあると思われる。例えば、ブロックスペースの制限だとか、我々の「ライブネス」の定義から外れたものであるとか、そもそもここで考慮していないものである等がその理由の一例である。

(筆者注)

9.4.1 チェーンの成長(Chain Growth)

命題9.24(チェーンの成長)

BlockTime ≥ 3Δを仮定する。失敗確率ρを許容すると、チェーンの成長の特性はパラメータk = ⌈- logβ ρ⌉で持続する。

証明

始めに、ラウンドrにおける通常のオペレーションを仮定して成長の特性を見てみる。この場合、アルゴリズム2に従って、ラウンドr + 1の終了時点に2Δを足した時点において、チェーンはrを含むそれまでのラウンドについてファイナライズされることになる。ラウンド数の観点から、命題9.10に基づくと、ラウンドr + 2を含む各ラウンドは少なくともBlockTime - Δ > 2Δかかるので、ラウンドr + 2終了時点でラウンドrについてファイナライズすることができてファイナライズされたチェーンは長さr + 1を持つことになる。これは、パラメータk = 1で成長の特性が持続していることを意味する。

ラウンドrについての最も高い優先度を持つブロック生成者が誠実であるならば、必ずラウンドrは通常のオペレーションである(命題9.14による)。従って、一般に通常のオペレーションは少なくとも確率1 - 1/βで起こる。ゆえに、成長の特性がパラメータkで持続する確率は、少なくとも1 - (1/β)kである。従って、この確率を最小限期待できる成功確率1 - ρと一致するとみなすのならば、kについて解くとk = ⌈- logβ ρ⌉が得られる。□

(筆者注)

  • 命題9.10は、BlockTime ≥ Δを仮定する。すると、任意の誠実なレプリカのラウンド数は最大でBlockTime - Δごとに増加する。さらに、任意の時点において2つの誠実なレプリカのラウンド数の差は最大でも1に収まる、ということ。詳細はDFINITYホワイトペーパー日本語訳14を参照。
  • ゆえに、成長の特性がパラメータkで持続する確率は、少なくとも1 - (1/β)kである。従って、この確率を最小限期待できる成功確率1 - ρと一致するとみなすのならば、kについて解くとk = ⌈- logβ ρ⌉が得られる。
    • まず、1/β = β-1 であるから、1 - (1/β)k = 1 - β-kである。
    • この確率を最小限期待できる成功確率1 - ρと一致するとみなす...を式で表現すると1 - (1/β)k ≥ 1 - ρ。
      • これを式変形すると、1 - (1/β)k ≥ 1 - ρ ⇔ 1 - β-k ≥ 1 - ρ ⇔ ρ ≥ β-k
    • ここで、βを底とする対数をとると、β > 1であるので、logβ ρ ≥ -k ⇔ k ≥ -logβ ρ
    • kは自然数であるので、k ≥ -logβ ρは、k = ⌈- logβ ρ⌉と書ける。なお、k = ⌈- logβ ρ⌉は、kは、-logβ ρ以上の最小の整数であることを示す。

9.4.2 チェーンの一貫性(Chain Consistency)

命題9.25(チェーンの一貫性)

T ≥ 2Δを仮定する。また、2つの誠実なレプリカii'は、それぞれFINALIZE(h)、FINALIZE(h')を実行するとすぐにファイナライズされたチェーンCC'をアウトプットするものとする。このとき、C ≤ C'または、C' ≤ Cである。

証明

h'hとしても一般性を失わない。NhN'hi, i'それぞれがFINALIZE(h)をして得られるアルゴリズム2の集合とする。h'hであるので、命題6.1により、C' ≤ C(N'h)である。Xをラウンドhにおける参照されうる公証全ての集合であるとする。Xは全ての誠実なレプリカがラウンドr + 1を終了した後にグローバルに定義されるものである点に注意されたい(ただし、Xは全員に知られるわけではない)。定理9.18(ファイナライゼーションの正当性)により、XNh, N'hである。加えて、FINALIZE(h)はラウンドhにおけるいくつかの公証が実際に参照される場合に限り呼び出されるので、X集合は空ではない。ゆえに、C = C(Nh) ≤ C(X)かつC' ≤ C(N'h) ≤ C(X)である。チェーンCC'は共通チェーンのプレフィックスであるという事実により、この主張は示される。□

(筆者注)

  • 命題6.1は、FINALIZE(h)が実行されるとき、Nhには参照されうるラウンドhの全ブロックが含まれている、ということ。詳しくはDFINITYホワイトペーパー日本語訳9を参照。
  • 定理9.18は、T ≥ 2Δとすると、誠実なレプリカそれぞれについて、レプリカはアルゴリズム2のFINALIZE(h)を実行する前に、レプリカは参照されうるラウンドhについての全ての公証を受け取っている、ということ。詳しくはDFINITYホワイトペーパー日本語訳15を参照。

9.4.3 チェーンのクオリティ(Chain Quality)

ラウンドrにおいて最も高い優先度を持つレプリカが攻撃者であるかどうかは、成功確率をƒ(U)/|U|とするベルヌーイ試行Xrとしてモデル化できる。攻撃者はランダムビーコンにバイアスをかけることはできないので、異なるラウンドrに対するベルヌーイ試行Xrは独立である。従って、プロトコルを実行すると、攻撃者が提案されたブロックに対する優先権を獲得できるかをモデル化したベルヌーイ過程X1, X2, ... も伴って発生する。

Garayら[5]によれば、ベルヌーイ過程がその期待値を大幅に超えないのであれば、プロトコルの実行を「典型的な(typical)」ものとして定義できる。任意の複数ラウンドの集合Sについて、確率変数X(S) := ∑iS Xiを定義する。

定義9.26

|S| ≥ ηであるような任意の連続するラウンドの集合Sについて以下の関係式が成り立つのであれば、ある実行は(ε, η)-typicalである。

アイデアは次のようなものである。a)全ての典型的な実行においてチェーンのクオリティは保証できる。b)無視できるほどの確率を除いてあらゆる実行は典型的である。実際には「無視できるほどの確率」はセキュリティパラメータκで定義され、パラメータεηκの関数である。

命題9.27(チェーンのクオリティ)

BlockTime ≥ 3Δを仮定する。(ε, η)-typicalな実行において、チェーンのクオリティの特性はµ = (1 - 1/β)(1 - ε)かつl = ηに関して持続する。

証明

Xr = 0であるならば、必ずラウンドrについてただ一つだけ公証が存在する。この公証は誠実なブロック提案者のブロックに対するものであるので、誠実なブロック提案は必ずファイナライズされたチェーンにある。従って、l ≥ ηであるならば、チェーンのクオリティは(ε, η)-typicalな実行について少なくとも(1 - 1/β)(1 - ε)である。□

謝辞

Robert LaukoとMarko Vukolic、Arthur Gervais、Bryan Ford、Ewa Syta、Philipp Jovanovic、Eleftherios Kokoris、Cristina Basescu、Nicolas Gaillyからは有益なコメントと議論をいただいた。この場を借りて感謝の意を表明したい。

参考文献

[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íguezHenrí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 Theory 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. The 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ホワイトペーパー日本語訳15 ←← 前)|(始めから →→ DFINITYホワイトペーパー日本語訳1

免責

邦訳には誤りがある場合がございます。予めご承知おき下さい。

確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。

-ホワイトペーパー
-, , , , , , , , ,

Copyright© 暗号通貨界隈のメモ書きなど。 , 2019 All Rights Reserved Powered by STINGER.

%d人のブロガーが「いいね」をつけました。