本稿について
本稿では、DFINITY White Paper：Consensus Systemのうち第4章「MODELS AND PRELIMINARIES」のうち、4.3「Cryptographic Primitives」と4.4「DFINITY's Block Chain」の日本語訳を掲載します。
本章は数学的な表記が多く、やや表記に慣れていないと読み解くのが難しくなっています。しかし、単に文中に注を入れていくと冗長になるため、節が終わるごとに数学的表記を噛み砕いて平易な文章（緑字）に直した注記をまとめて入れるようにします。
原文はこちらになります。
スポンサードサーチ
4 モデルと下準備（続き）
4.3 暗号理論のプリミティブ
4.3.1 ハッシュ関数（Hash function）
ビット長lのダイジェストを引数とする衝突耐性のあるハッシュ関数Hがあると仮定する。ここで、lはセキュリティパラメータκと一致する。
4.3.2 擬似乱数（Pseudo-random number）
また、暗号理論的にセキュアな擬似乱数生成器PRGがあると仮定する。PRGはξをシードとして、i = 0, 1, ..., について数列PRG(ξ, i)を生成する。
4.3.3 擬似乱数置換（Pseudo-random permutations）
PRG(ξ, i)は、Fisher-Yatesのシャッフルアルゴリズム[9, Algorithm 3.4.2P]のインプットとして利用されて、母集団Uのランダム置換を生成する。この結果は全単射で{1, ..., |U|} → Uとなる。これをPermU(ξ)と表すこととする。
（筆者注）
- Fisher-Yatesのシャッフルアルゴリズムとは、ある配列からランダムに要素を抽出して順番を入れ替えるアルゴリズム。配列の全ての要素が最低１回ずつ入れ替えの対象となるが、入れ替えられた要素が2回入れ替わることはない。
- この結果は全単射で{1, ..., |U|} → Uとなるについて
- まず全単射とは、ものすごく噛み砕いて言うと、何らかの値をとある関係性に基づいて変換したとき、必ず変換できて、なおかつ変換した後の値が重複しないこと。
- この文脈で言うと、何らかの値＝PRG(ξ, i)、何らかの関係性＝Fisher-Yatesのシャッフルアルゴリズム、変換後の値（の集合）＝U。
- 次に{1, ..., |U|} → Uについて。これは、母集団Uの要素1,2, ..., |U|を変換しても母集団Uのいずれかの要素になるということ。
- この文脈では、先述通りFisher-Yatesのシャッフルアルゴリズムはただ順番を入れ替えるだけなので、母集団Uの要素1,2, ..., |U|を変換しても母集団Uのいずれかの要素になるので、{1, ..., |U|} → Uと表現できる。
4.3.4 ディフィー・ヘルマン（Diffie-Hellman）
攻撃者は計算機的に制限があり、ゆえに計算機的なDiffie-Hellman問題を[2]におけるペアリングを伴う楕円曲線に関して解くことは困難であると仮定する。
4.4 DFINITYのブロックチェーン
次に、DFINITYにおけるブロックチェーンのコンセプトを公式的に定義する。
4.4.1 ブロック（Blocks）
定義4.3
ブロックとは、特別な「ジェネシスブロック」か、またはタプル(p, r, z, d, o)である。ここで、 p ∈ {0, 1}lは前ブロックを参照するハッシュ、r ∈ Nはラウンド数、z ∈ {0, 1}∗は前ブロックの公証、d ∈ {0, 1}∗はデータペイロード（「トランザクション」と「ステート」）、o ∈ Uは生成者（あるいは「所有者」）とする。「公証（notarization）」とは、「公証者」によって生成される前ブロックへの署名である。ブロックB = (p, r, z, d, o)について、prv B := p, nt B := z, rd B := r, dat B := d, own B := oを定義する。
ブロックは、前ブロックの公証zを有しており、前ブロックを参照していることを強調しておく。
（筆者注）
- タプルとは、複数の構成要素からなるものの構成要素数を表す数詞。この文脈では、ブロックがタプル(p, r, z, d, o)であるので、ブロックとは構成要素p, r, z, d, oの5つ組で構成されるもの、となる。
- A := Xとは、記号Aの意味するところをXと定義する、という意味。ゆえに、B = (p, r, z, d, o)について、prv B := p, nt B := z, rd B := r, dat B := d, own B := oを定義する、とは、その前の文脈も含めて細かく分解すると次のような意味になる。
- B = (p, r, z, d, o)について、
⇒ p, r, z, d, oを構成要素として持つブロックBについて、- prv B := p,
⇒ prv Bとは、Bの構成要素p、すなわち、Bの1つ前のブロックを参照するハッシュp ∈ {0, 1}lであり、- nt B := z,
⇒ nt Bとは、Bの構成要素z、すなわち、前ブロックの公証z ∈ {0, 1}∗であり、- rd B := r
⇒ rd Bとは、Bの構成要素r、すなわち、ラウンド数r ∈ Nであり、- dat B := d,
⇒ dat Bとは、Bの構成要素d、すなわち、データペイロードd ∈ {0, 1}∗であり、- own B := oを定義する
⇒ own Bとは、Bの構成要素o、すなわち、生成者あるいは所有者o ∈ Uであるものと定義する
4.4.2 チェーン（Chains）
定義4.4
あるチェーンCで、全てのiについてrd Bi = i、かつ、全てのi > 0についてprv Bi = H(Bi−1)、かつ、全てのi > 0についてnt BiはBi−1の有効な署名であるような有限体のブロック配列(B0, B1, ..., Br)を考える。B0はジェネシスブロックである。末尾のブロックBrはチェーンCの「ヘッド（head）」と言う。いま、len C := r + 1, gen C := B0, head C := Brを定義する。
チェーンのブロックは暗号理論のハッシュで紐づけられているので、チェーンは認証されているデータ構造である。チェーンはそのヘッドによって完全に決定される。それは、以下の命題に基づく。
命題4.5
head C = head C'であるような2つのチェーンC ≠ C'を生成するのは計算機的に実現不可能である。
定義4.6
ユニークに定義されたチェーンCでhead C = BであるようなものをC(B)と記述する。2つのチェーンC、C'が与えられたとき、CがC'のプレフィックスであるならば、C ≤ C′と記述する。
いま、全てのチェーンが同一のジェネシスブロックB0を持つ場合を仮定する。
定義4.7
ブロックからなる任意の空でない集合について、B ∈ Sであるような全てのチェーンC(B)のLCP（largest common prefix）をC(S)と表す。
B ∈ Sであるような全てのC(B)はジェネシスブロックを含むので、チェーンC(S)は定義される。S ⊆ Tであるようなブロックからなる任意の集合S, Tについて、C(T) ≤ C(S)がある。prv S := {prv B | B ∈ S ＼ {B0}} ≠ ∅であるならば、次の式（4.5）が導かれる。
（筆者注）
- len C := r + 1, gen C := B0, head C := Brを定義する
- len C := r + 1,
⇒ len Cとは、Cの構成要素r + 1、すなわち、そのチェーンの長さ（チェーンにあるブロックの数（ジェネシスブロックも含む）と表現しても同じ意味）であり、- gen C := B0,
⇒ gen Cとは、Cの構成要素B0、すなわち、そのチェーンのジェネシスブロックのことであり、- head C := Br
⇒ head Cとは、Bの構成要素Br、すなわち、そのチェーンのヘッド（先頭ブロック、最新ブロックと表現しても同じ意味）のことと定義する- head C = head C'であるような2つのチェーンC ≠ C'を生成するのは計算機的に実現不可能
⇒ チェーンの最新のブロックが同一（すなわち、最新のブロックの構成要素p, r, z, d, oが同じ）でありながらそれより前に何か違いがあるようなチェーンを作るのは計算機的に実現不可能- プレフィックス（prefix）は接頭辞。LCP（largest common prefix）は日本語で書くと最長共通接頭辞...だが、恐らくLCPと書くの方が一般的。
- prv S := {prv B | B ∈ S ＼ {B0}} ≠ ∅であるならば、の式（4.5）が導かれる。
- prv S :=
⇒ prv Sを次のように定義するということ- prv B
⇒（4.4.1の中でも述べたが）Bの構成要素p、すなわち、Bの1つ前のブロックを参照するハッシュp ∈ {0, 1}lということ
- B ∈ S ＼ {B0}
⇒ ブロックBは、集合SからジェネシスブロックB0を除いたもののいずれかのブロックであるということ- ≠ ∅
⇒ 空集合（要素のない集合ではない）ということ。つまり何らかの要素が存在するということ- C(prv S) ≤ C(S)
⇒ prv Sが参照するブロックをヘッドとするチェーンは、Sをヘッドとするチェーンのプレフィックスであるということ- 以上を纏めると、ブロックの集合Sからジェネシスブロックを除いた中のいずれかのブロックのハッシュで、そのハッシュが存在するとき、そのハッシュが参照するブロックをヘッドとするチェーンは、Sをヘッドとするチェーンのプレフィックスである。...となる。
- 次のように具体例をイメージすると分かりやすい。
- あるチェーンC'はB0、B1、B2、...、B9がこの順につながったチェーンで、各ブロックが1つ前のブロックのハッシュを参照している。このチェーンから3個前のブロックを先頭（ヘッド）とするチェーンを切り出すと、このチェーンCはB0、B1、B2、...、B6がこの順でつながったチェーンである。Cのブロック並びにこの順番は全く同様にC'に含まれている。このことをプレフィックスという。そして、C ≤ C′と書くこととする。いま、3個前のブロックとしたが、これは別に1個前でも2個前でも変わらない。そして、C'のブロックが100個になっても1000個になっても先頭からいくつか前のブロックを切り出したチェーンCは全てその順番でC'に含まれるという関係は変わらない。これをC(prv S) ≤ C(S)と書くこととする。
（DFINITYホワイトペーパー日本語訳4 ←← 前）｜（次 →→ DFINITYホワイトペーパー日本語訳6）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。