ホワイトペーパー

DFINITYホワイトペーパー日本語訳14

更新日:

本稿について

本稿では、DFINITY White Paper:Consensus Systemのうち第9章「SECURITY ANALYSIS」の9.2「Timing and Processing」の日本語訳を掲載します。

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

スポンサードサーチ

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

9.2 タイミングと処理

本節では異なるレプリカで生じるイベントの相対的なタイミングについて述べる。今回は全てのラウンドにおいて通常のオペレーションを仮定しないので、同一ラウンドrにおいて複数の公証zr, z'r,...が生成・ブロードキャストされる可能性を考慮せねばならない。

9.2.1 準備(Preliminaries)

時点tにおいて誠実なレプリカがブロードキャストするメッセージは、全てのレプリカにt + Δよりも前に到達する(つまり、到達時はt + Δ未満である)と仮定する。処理時間は分析の対象外であるので、全ての処理時間は0と仮定する。この仮定は、メッセージの生成だけでなくブロック提案、署名、公証、ランダムビーコンのシェア、ランダムビーコンのアウトプット等を含むあらゆるメッセージの検証にも適用される。ゆえに、例えば時点tにおいてあるレプリカiがランダムビーコンのアウトプットξrを受信するならば、iはラウンドrについてのブロック提案を同じ時点tでブロードキャストする。また、時点tにおいてあるランダムビーコンのメンバiがラウンドrについての公証zrを受信するならば、iはラウンドr + 1についてのランダムビーコンのシェアを同じ時点tで速やかにブロードキャストする。

定義9.5

τi(A)は、レプリカiがイベントAを確認した時点とする。ここで、Aはランダムビーコンのアウトプットξr、ブロック提案Br、公証zrのいずれかである。τi(r) := τi(zr-1)と置く。ここで、zr-1はレプリカiが受信するラウンドr - 1についての最初の公証を指す。

従って、τi(r)はレプリカiがラウンドrに突入する時点である。最初の誠実なレプリカ、または最後の誠実なレプリカがイベントを確認する時点を調べるため、次の定義を置く。

定義9.6

例えば、_τ(r)は最初の誠実なレプリカがラウンドrに突入した時点であり、τ(r)は最後の誠実なレプリカがラウンドrに突入した時点である。最後に、攻撃者が初めてイベントを確認あるいは構成する時間も関連する。従って、以下を定義する。

定義9.7

例えば、_τ*(ξr)は攻撃者がランダムビーコンのアウトプットξrを生成しうる最速の時点を指す。

後述の系9.16にて証明するが、プロトコルの進捗は連続である。すなわち、全ての値τi(r)は有限である。読者の検証のため、本節の系9.16までで明らかにする全ての値τi(r)が有限であるという事実は、任意の値τi(A)が無限である可能性がある場合を考え、自明ではないものとしておく。

補題9.8

全てのラウンドrについて、

であり、任意のラウンドrのイベントAについて、定義9.4a)により、

である。

証明

iを誠実なレプリカとし、zr-1τi(zr-1) = _τ(r)であるようなラウンドr - 1についての公証とする。定義9.4b)により、zr-1はネットワーク間でリレーされ、τi(r) + Δまでにその他すべてのレプリカjに到達する。これにより、(9.3)は示された。

さて、Aを定義9.4a)のリレーポリシーに分類されるラウンドrについての任意のイベントとする。もし_τ(r) + Δ ≤ _τ(r + 1)であれば、同じ論理が適用される。事実、この仮定はブロードキャストパスに関わる全てのレプリカがラウンドrに留まっていることを意味するので、定義9.4a)に従ってイベントAをリレーする。これにより、(9.4)は示された。□

(筆者注)

  • 定義9.4a)、b)はリレーポリシーに関する定義。全ての誠実なレプリカは次のアーティファクトをリレーする。
    • a)その時点のラウンドで:有効なブロック提案と、ブロック提案に対する有効な署名
    • b)あらゆるラウンドで:公証と、公証済みブロック
    • 詳しくはDFINITYホワイトペーパー日本語訳13を参照。

9.2.2 最大の進捗(Maximal Progress)

補題9.9(公証, 「速い」制限)

全てのラウンドrについて、

証明

誠実なレプリカは少なくともBlockTimeの間はラウンドrにいた後に限り、ラウンドrについての公証zrに参加する(アルゴリズム1を参照)。不等式(9.5)は、すなわち誰かがラウンドrについての公証zrを確認できる前に、少なくとも1つの誠実なレプリカが必要であることを指す。□

命題9.10(最大の進捗)

BlockTime ≥ Δを仮定する。すると、任意の誠実なレプリカのラウンド数は最大でBlockTime - Δごとに増加する。さらに、任意の時点において2つの誠実なレプリカのラウンド数の差は最大でも1に収まる。

証明

(9.3)及び(9.5)から、次の不等式が得られる。

これが真であるならば(9.3)及び(9.5)も真である。□

系9.11(安全なブロードキャスト)

BlockTime ≥ Δを仮定する。全てのラウンドrと、定義9.4a)に基づく任意のラウンドrのイベントAについて、次が成立する。

この関係式の解釈は次の通りである。ラウンドrのイベントが_τ(r) + (BlockTime - Δ)までにブロードキャストされるならば、そのイベントは必ずネットワークを満たし、かつネットワークを満たすことは_τ(r) + BlockTimeまでに発生する。

証明

_τ(A) ≤ _τ(r) + BlockTime - Δから、

である。ゆえに、(9.4)により、

よって題意は示された。□

(筆者注)

  • (9.3)及び(9.5)から、次の不等式が得られる。
    • まず、不等式(9.3)τ(r) ≤ _τ(r) + Δを変形すると、τ(r) - Δ ≤ _τ(r)となる。
    • 次に、不等式(9.5)_τ(r) + BlockTime ≤ _τ*(r + 1)の_τ(r)に注目して不等式(9.3)の関係性を付け加えると、τ(r) - Δ + BlockTime ≤ _τ(r) + BlockTime ≤ _τ*(r + 1)である。左辺は、τ(r) - Δ + BlockTime = τ(r) + (BlockTime - Δ)である。ゆえに、左辺と右辺に着目すれば、τ(r) + (BlockTime - Δ) ≤ _τ*(r + 1)が導ける。
    • これ以降も不等式の関係から別の不等式を導く論理は使われている。

9.2.3 通常のオペレーション(Normal Operation)

補題9.12(ビーコン, 「遅い」制限)

全てのラウンドrについて、

証明

ランダムビーコンの誠実な各メンバiは時点τi(r)でξrについてのランダムビーコンのシェアをブロードキャストする(第7章3の2を参照)。従って、その他全ての誠実なレプリカはτ(r) + Δまでにξrについての全ての誠実なランダムビーコンのシェアを受け取ることになるので、τ(r) + Δまでにξrを復元する。すなわち、以下が成り立つ。

この主張は、(9.3)が適用された後であれば成り立つ。□

さて、サブセクションの残り時間がBlockTime ≥ 3Δであると仮定する。BlockTime = 3Δであるようなイベントのタイミングを図9に示す。

補題9.13(ブロック, 「遅い」制限)

BlockTime ≥ 3Δを仮定する。全てのラウンドrと、全ての誠実なブロック提案Brについて、次が成り立つ。

証明

ブロック提案Brは誠実なレプリカiからのものであるので、iξrを受け取るとすぐにブロードキャストされる。(本章全体を通して、ブロック生成時間等の処理時間を全般的に無視している点に注意。)すなわち、_τ(Br) ≤ τ(ξr)である。ゆえに、

系9.11においてイベントA = Brとすることにより、この主張は導かれる。□

命題9.14(通常のオペレーション)

BlockTime ≥ 3Δを仮定する。ラウンドrについての最も高い優先度を持つレプリカが誠実であるならば、ラウンドrは通常のオペレーションである。

証明

iを最も高い優先度を持つレプリカとし、iは誠実であると仮定すると、iはラウンドrについて1つのブロックBrだけを提案する。補題9.13が真であるならば、全ての誠実な公証メンバjについてτj(Br) ≤ τj(r) + BlockTimeが成り立つ。アルゴリズム1により、レプリカjはラウンドrに突入後BlockTimeを待ち、その後Brにだけ署名をし、他のブロック提案には署名を行わない。なぜなら、ブロック提案Brの提案者であるレプリカiが取りうる最高の優先度を持つからである。

公証には少なくとも1つの誠実なレプリカの参加が必要であり、全ての誠実なレプリカはブロックBrに限り署名するので、Brは公証されうる可能性のある唯一のブロックである。換言すれば、Brの公証によってしかラウンドrを終了させることはできない。このことがBrに対する署名がネットワークを満たすことと実際にBrが公証されることを保証する。□

(筆者注)

9.2.4 最小の進捗(Minimal Progress)

命題9.15(最小の進捗)

BlockTime ≥ 3Δを仮定する。また、所与のラウンドrにおいて、ランクπr(i) = dであるようなレプリカiは誠実であると仮定する。このとき、以下が成り立つ。

証明

x0 := _τ(r) + BlockTimeと置く。Briがラウンドrについて行った唯一のブロック提案であるとする。補題9.13により、全ての誠実な公証メンバは時点x0までにをBr受け取る。

各時点x ≥ x0について、少なくとも1つの誠実なレプリカに受け取られるラウンドrについての有効なブロック提案の集合Sxを考える。より公式的には、Sx_τ(B) ≤ xを満たすようなラウンドrについての複数のレプリカのブロック提案Bからなる。例えば、Br ∈ Sx0である。次に、以下を定義する。

例えば、Brのランクはdであるので、ƒ(x0) ≤ dである。

x ≥ x0について、関数ƒは非負整数の値を持ち、単調減少関数である。ƒ(x0) ≤ dであるので、ƒ(x1) = ƒ(x1 + Δ)を満たすような時点x0 ≤ x1x0 + が存在する(そうでなければ、全てのx0 ≤ xx0 + dΔについてƒ(x + Δ) ≤ ƒ(x) - 1であるならばƒ(x0 + (d + 1)Δ) < 0となり、矛盾する)。

主張_τi(r + 1) ≤ x0 + (d + 1)Δを立てる。次の式が成り立つので、これにより(9.9)が証明される。

もし、Bからのものではないブロックについての公証がx1 + 2Δよりも前に任意のレプリカに到達するならば、主張は既に証明済みと言える。そうでない場合においても、一般性を失わない。この仮定のもと、(9.4)はイベントBBに対するあらゆる署名に対して適用される。

Bは、rk B = ƒ(x1)であるようなB ∈ Sx1であるする。B ∈ Sx1であるので、_τ(B) ≤ x1である。従って、(9.4)により、

τ(B) ≤ x1 + Δ、及び、rk B = ƒ(x1 + Δ)という事実から、Bは時点x1 + Δにおいて全ての誠実なレプリカから見て最も小さいランクを有することが導かれる。また、x1 + Δ ≥ _τ(r) + BlockTime + Δ ≥ τ(r) + BlockTimeである。つまり、x1 + Δは、全ての誠実なレプリカのBlockTime待機時間の先の時間である。ゆえに、全ての誠実なレプリカはx1 + ΔまでにBに対する署名をブロードキャストし終える。(9.4)により、全ての誠実なレプリカはx1 + 2Δまでにƒ + 1の署名を受け取る。すなわち、τ(r + 1) ≤ x1 + 2Δである。□

証明なしで次のことを述べておく。仮にd = 0であるならば、制限は_τ(r + 1) ≤ _τ(r) + BlockTime + Δに変更される。この制限は、あらゆるdについて厳格に徹底される。

系として、帰納的に、プロトコルの進捗は連続であると結論付けられる。

系9.16

BlockTime ≥ 3Δを仮定する。全てのラウンドr並びに全ての誠実なレプリカiについて、τi(r)は有限である。

(筆者注)

  • x ≥ x0について、関数ƒは非負整数の値を持ち、単調減少関数である。ƒ(x0) ≤ dであるので、ƒ(x1) = ƒ(x1 + Δ)を満たすような時点x0 ≤ x1 ≤x0 + dΔが存在する(そうでなければ、全てのx0 ≤ x ≤x0 + dΔについてƒ(x + Δ) ≤ ƒ(x) - 1であるならばƒ(x0 + (d + 1)Δ) < 0となり、矛盾する)。
    • x ≥ x0についてまず注目したい。定義によりx0_τ(r) + BlockTime、すなわちラウンドr - 1の公証を確認した最速の時点+BlockTimeの時間であるので、それ以降の時点を表している。そして、その後遅れてブロックがやってきた場合どうなるかについて話しているのがこの上述の一連の流れである。
    • ƒ(x0) ≤ dについては、定義ƒ(x) := min{rk B|B ∈ Sx}から読み解く。ƒ(x)は時点xにおいてなされた有効なブロック全ての中から最小のランクを持つものであるので、ƒ(x0)は時点x0においてなされた有効なブロック全ての中から最小のランクを表す。例えば3つブロックがあってランクが0、1、2ならば、0が該当する。当然に、このような有効なブロックの中にランクπr(i) = dであるレプリカiから提案されたブロックが含まれるので、少なくともƒ(x0) ≤ dは必ず成立する。
    • ƒ(x1) = ƒ(x1 + Δ)を満たすような時点x0 ≤ x1 ≤x0 + dΔが存在する(そうでなければ、全てのx0 ≤ x ≤x0 + dΔについてƒ(x + Δ) ≤ ƒ(x) - 1であるならばƒ(x0 + (d + 1)Δ) < 0となり、矛盾する)については次のように読む。
      • Δはネットワークのトラバーサルタイム(伝搬にかかる時間)であるので、ブロックタイム後のある時点x1でもう1Δ分待つ、つまりもう1ブロック出てくるのを待ってもランクが変わらないような時点が必ず存在するということである。後半の()部分についてはそれを背理法的に表現したもので、そのような時間が存在しないならば0より小さいランクを持つブロックが存在することになってしまい、非負整数(0, 1, 2, ...)であることに矛盾する、ということ。

DFINITYホワイトペーパー日本語訳13 ←← 前)|(次 →→ DFINITYホワイトペーパー日本語訳15

免責

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

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

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

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

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