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

本稿について

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

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

スポンサードサーチ

9 セキュリティ分析（続き）

9.2 タイミングと処理

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

9.2.1 準備（Preliminaries）

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

定義9.5

τ_i(A)は、レプリカiがイベントAを確認した時点とする。ここで、Aはランダムビーコンのアウトプットξ_r、ブロック提案B_r、公証z_rのいずれかである。τ_i(r) := τ_i(z_r-1)と置く。ここで、z_r-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を誠実なレプリカとし、z_r-1をτ_i(z_r-1) = _{_}τ(r)であるようなラウンドr - 1についての公証とする。定義9.4b)により、z_r-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についての公証z_rに参加する（アルゴリズム1を参照）。不等式（9.5）は、すなわち誰かがラウンドrについての公証z_rを確認できる前に、少なくとも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と、全ての誠実なブロック提案B_rについて、次が成り立つ。

証明

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

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

命題9.14（通常のオペレーション）

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

証明

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

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

（筆者注）

• 第7章3の2は署名プロセスに関して述べている項。DFINITYホワイトペーパー日本語訳11を参照。
• アルゴリズム1はブロック公証について処理を記述したアルゴリズム。詳細はDFINITYホワイトペーパー日本語訳7を参照。

9.2.4 最小の進捗（Minimal Progress）

命題9.15（最小の進捗）

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

証明

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

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

例えば、B_rのランクはdであるので、ƒ(x₀) ≤ dである。

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

主張_{_}τ_i(r + 1) ≤ x₀ + (d + 1)Δを立てる。次の式が成り立つので、これにより（9.9）が証明される。

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

Bは、rk B = ƒ(x₁)であるようなB ∈ S_x1であるする。B ∈ S_x1であるので、_{_}τ(B) ≤ x₁である。従って、（9.4）により、

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

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

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

系9.16

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

（筆者注）

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

（DFINITYホワイトペーパー日本語訳13　←←　前）｜（次　→→　DFINITYホワイトペーパー日本語訳15）

免責

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

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