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

本稿について

本稿では、DFINITY White Paper：Consensus Systemのうち第4章「MODELS AND PRELIMINARIES」のうち、4.1「System Model」と4.2「Threat Model」の日本語訳を掲載します。

本章は数学的な表記が多く、やや表記に慣れていないと読み解くのが難しくなっています。しかし、単に文中に注を入れていくと冗長になるため、節が終わるごとに数学的表記を噛み砕いて平易な文章（緑字）に直した注記をまとめて入れるようにします。

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

スポンサードサーチ

4 モデルと下準備

4.1 システムモデル

4.1.1 レプリカ（Replicas）

ここからクライアントを「レプリカ（replicas）」と呼び、それらについて1, 2, ... （∈ N）と番号を振る。Uを番号の付いた全レプリカの有限集合とする（UはUniverse＝母集団にちなむ）。i ∈ Uであるレプリカは公開鍵と秘密鍵のペア（pk_i, sk_i）を持つ。集合{pk_i | i ∈ U }は既知であり、全てのi ∈ Uで合意される²ものと仮定する。

（脚注2）

実際、合意は全てのレプリカをレプリカの公開鍵とともにブロックチェーンに登録することで実現する。

（筆者注）

• それらについて1, 2, ... （∈ N）と番号を振る...の∈ Nは自然数であるということ。
• i ∈ Uであるレプリカは公開鍵と秘密鍵のペア（pk_i, sk_i）を持つ
  ⇒　母集団Uに属する全てのレプリカは公開鍵と秘密鍵のペア（pk_i, sk_i）を持つ
• 集合{pk_i | i ∈ U }は既知であり、全てのi ∈ Uで合意されるものと仮定する
  ⇒　母集団Uに属する各レプリカが持つ公開鍵は、他の全てのレプリカに知られていて、かつ合意を得ているものと仮定する

4.1.2 認証（Authentication）

全てのプロトコルメッセージは、そのメッセージを発行したレプリカによって署名される。レプリカは、メッセージがi ∈ Uであるsk_iで署名がされている場合にのみメッセージを受け取り、行動する。

（筆者注）

• レプリカは、メッセージがi ∈ Uであるsk_iで署名がされている場合にのみ
  ⇒　母集団Uに属する何らかのレプリカの秘密鍵で署名がされている場合にのみ

4.1.3 群（Groups）

任意の時点で、いくつかまたは全てのi ∈ Uは1つ以上の部分集合（「群（groups）」という）G₁, G₂, ... ⊆ Uに組み入れられ、そのうちの1つだけ（「コミティ（committee）」という）がアクティブとなって進行を行いコンセンサスを実現する。全ての群G_jは同じサイズnを持つと仮定する。nは「群のサイズ（group size）」と呼ばれるシステム変数である。

（筆者注）

• 「群（group）」は代数学的における概念で、ある演算の定義された集合において結合法則、単位元の存在、逆元の存在が成り立つ集合のことを指す。
  • 抽象的な概念であるため難しいが、とある演算に便利なものの集合くらいに捉えておくとよい。よく分からない場合は単純に何かの便利なグループくらいの認識でよい。
    • この方（びりあるさん）のブログが非常に分かりやすいので、群について知りたい方はご参考に。
• いくつかまたは全てのi ∈ Uは1つ以上の部分集合G₁, G₂, ... ⊆ Uに組み入れられ
  ⇒　母集団Uに属するレプリカのいくつかまたは全ては、母集団U以下の大きさを持つ群のうち1つ以上に組み入れられ

4.1.4 同期（Synchrony）

DFINITYの実用性のため、「準同期的（semi-synchronous）」ネットワークを仮定する。準同期的ネットワークにおいて、ネットワークのトラバーサルタイムは確率分布が既知のランダム変数Yによってモデル化できるものとする。次に、DFINITYプロトコルはシステムワイドな2つのタイムアウト定数BlockTimeとTを、Yの確率分布とシステムのセキュリティパラメータに基づいて選ぶ。第9章の公式のセキュリティ分析では、ランダム変数Yに関する上界Δが既知である同期的ネットワークの場合について証明を与えている。

2つの定数はそれぞれ、BlockTimeがシステムのライブネスを、Tがシステムのセーフティを表す。タイムアウト時計はロカールの「イベント（events）」、すなわちメッセージの受信に基づいて動き始める。このプロトコルはグローバルタイムに依存することもなければ、レプリカ間の同期時計を推測することもない。

システムは「ラウンド（rounds）」ごとに進展していく。レプリカはイベントに基づいて次のラウンドへ進む。異なるレプリカでラウンドが同期することは想定されていない。

（筆者注）

• ランダム変数Yに関する上界Δが既知である
  ⇒　確率分布が既知のランダム変数Yが取りうる値のうちどんな値をとったとしても"ある値"以上にはならないときの、この"ある値"が分かっている

4.2 脅威モデル

4.2.1 ビザンチンなレプリカ（Byzantine replicas）

プロトコルに忠実に従うレプリカを「誠実である、誠実な（honest）」などと表現し、それ以外の全てのレプリカを「ビザンチンである、ビザンチンな（byzantine）」などと表現する。i ∈ Uであるビザンチンなレプリカは任意のふるまいをする可能性がある。例えば、ビザンチンなレプリカはプロトコルへの参加を拒否したり、他のビザンチンなレプリカと結託して組織的な攻撃をシステムに対して実行する可能性がある。

4.2.2 攻撃の強さ（Adversarial strength）

任意のG ⊆ Uについて、ƒ(G)をGに含まれるビザンチンなレプリカの数を表すものとする。

仮定1

次の式（4.1）を満たすようなβ > 2が存在する。

このとき、1/βを「攻撃の強さ（adversarial strength）」という。実際、仮定1は何らかの形のシビルアタック耐性³と合わせた経済的インセンティブを通じて達成される。

（脚注3）

シビルアタック耐性は、例えば、各レプリカがステークを保証金として預け入れなければならないようにすることで実現する。仮定1は、誠実な参加者によって少なくとも1/βのステークが保証金として預けられている、という仮定に置き換えることができる。

（筆者注）

• 次の式（4.1）を満たすようなβ > 2が存在する
  ⇒　母集団Uに存在する「ビザンチンな」レプリカの数に2より大きな数値βを掛けても母集団の数を超えないようなβが存在する
  ⇒　（次の表現でも同じ）母集団Uに存在する「ビザンチンな」レプリカの数は少なくとも母集団の数の半分より小さい状況である

4.2.3 誠実な群（Honest groups）

nを群のサイズとする。このとき、次の式（4.2）を満たすような群Gを「誠実である」と言う。

第5章7で述べるプロトコルは次の仮定に基づく。

仮定2

システム内で利用される群Gは、全て「誠実な」群である。

（筆者注）

• 次の式（4.2）を満たすような群Gを「誠実である」と言う
  ⇒　ある群に存在するビザンチンなレプリカの数を2倍しても群のサイズの方が大きい場合、その群は「誠実である」と言う
  ⇒　（次の表現でも同じ）群を構成するレプリカの過半数が「誠実である」場合にその群は「誠実である」と言う

4.2.4 標本（Random samples）

仮定1について、母集団Uは誠実であるとする。システム内で利用される各群G ⊆ Uは、母集団Uから無作為抽出されたサイズnの標本である。nについて、Gが誠実である確率Prob[G honest]は次のように計算できる。

命題4.1

CDF_hg(x, n, M, N)は超幾何分布の累積分布関数を表すものとする。ここで、Nは母集団のサイズ、Mは母集団の成功数⁴、nは標本のサイズ、xは標本の成功数のうち取りうる最大値とする。このとき、確率Prob[G honest]は、

許容可能な「失敗確率（failure probability）」ρが与えられたとき、Prob[G honest] > 1 − ρ, 各G ⊆ Uである標本Gで|G| = nを満たすような最小の群のサイズn = n(β, ρ, |U|)について式（4.3）を解くことができる。|U| = 10⁴とし、ρとβを異なる値とした場合の結果を図3に示す。

母集団のサイズが無限に大きくなるにつれて、超幾何分布は二項分布に収束する。従って、|U|が無限に大きくなるのであれば、次の命題4.2が得られる。

命題4.2

CDF_binom(x, n, p)は二項分布の累積分布関数を表すものとする。ここで、pは抽出ごとの「成功確率（success probability）」、nは標本のサイズ、xは標本の成功数のうち取りうる最大値とする。このとき、確率Prob[G honest]は、

ρが与えられたとき、nに関して式（4.3）を解き、全ての|U|の値についてn(β, ρ) ≥ n(β, ρ, |U|)を満たす最小の群のサイズn(β, ρ)を求めることができる。

ρとβを異なる値とした場合の結果を図4に示す。結果が示す通り、ρの値の範囲において、群のサイズは − log₂ρで近似できる。結果として表される群のサイズは本資料で述べるプロトコルに関して実用的である。⁵

（脚注4）

DFINITYでは、MはUにおけるビザンチンなレプリカの数と定義できる。

（脚注5）

本資料で説明する主なプロトコルはいわゆる「ノンインタラクティブ」である。サイズが1000である群については実装してテストが完了しており、問題ないことが証明されている。DFINITYは、群のサイズ400程度でネットワークのラウンチを計画している。

（筆者注）

• 数式（4.3）Prob[G honest] = CDF_hg(⌈n/2⌉ − 1, n, ⌊|U|/β⌋, |U|). を噛み砕いて表現すると
  ⇒　Gが「誠実である」確率は、標本の成功数を⌈n/2⌉ − 1、標本のサイズをn、母集団の成功数を⌊|U|/β⌋、母集団のサイズを|U|とする超幾何分布の累積分布関数で表すことができる
  ⇒　Gが「誠実である」確率は、標本の成功数を「n/2以上の最小の整数から1を引いたもの」 、標本のサイズをn、母集団の成功数を「母集団の数|U|をβで割った商以下の最大の整数」、母集団のサイズを|U|とする超幾何分布の累積分布関数で表すことができる
  • 例えば、|U|=1000, n=21, β=3であるとすれば、Prob[G honest] = CDF_hg(47, 21, 333, 1000)となる。
• 数式（4.4）Prob[G honest] ≥ CDF_binom(⌈n/2⌉ − 1,n, 1/β)　についても同様に噛み砕いて考えると、
  ⇒　Gが「誠実である」確率は、標本の成功数を「n/2以上の最小の整数から1を引いたもの」 、標本のサイズをn、成功確率を1/βとする二項分布の累積分布関数で表すことができる
• 命題4.1で出てきている失敗確率ρ（ロー）と命題4.2で一時的に出てきている成功確率p（ピー）は見間違いやすいので注意。

4.2.5 適応的な攻撃者（Adaptive adversary）

攻撃者は「緩やかに適応していく（mildly adaptive）」と想定している。つまり、攻撃者は緩やかに群を侵食していく可能性があるが、侵食には当該の群のアクティビティ期間よりも長い時間を要するということである。

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

免責

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

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