メインコンテンツまでスキップ

2. Cryptographic Components (暗号コンポーネント)

2. Cryptographic Components (暗号コンポーネント)​

2.1. Merkle Hash Trees (メルクルハッシュ木)​

ログは効率的な監査のために二分メルクルハッシュ木 (binary Merkle Hash Tree) を用います。ハッシュアルゴリズムは SHA-256 [FIPS.180-4] です (本実験ではこれに固定されていますが, 各ログがハッシュアルゴリズムを指定できることが想定されています)。メルクルツリーハッシュ (Merkle Tree Hash) の入力はデータエントリのリストであり, これらのエントリはハッシュされてメルクルハッシュ木の葉になります。出力は単一の32バイトのメルクルツリーハッシュです。順序付きリストの n 個の入力 D[n] = {d(0), d(1), ..., d(n-1)} が与えられたとき, メルクルツリーハッシュ (MTH) は次のように定義されます。

空リストのハッシュは空文字列のハッシュです。

MTH({}) = SHA-256().

1エントリのリストのハッシュ (リーフハッシュ (leaf hash) とも呼ばれる) は次のとおりです。

MTH({d(0)}) = SHA-256(0x00 || d(0)).

n > 1 のとき, k を n 未満の最大の2のべき乗とします (すなわち, k < n <= 2k)。n 要素リスト D[n] のメルクルツリーハッシュは次のように再帰的に定義されます。

MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])),

ここで || は連結であり, D[k1:k2] は長さ (k2 - k1) のリスト {d(k1), d(k1+1),..., d(k2-1)} を表します (葉と内部ノードでハッシュ計算が異なることに注意してください。このドメイン分離 (domain separation) は第二原像耐性 (second preimage resistance) に必要です)。

入力リストの長さが2のべき乗である必要はありません。得られるメルクル木は平衡でない場合がありますが, その形状は葉の数によって一意に定まります (注: このメルクル木は本質的には history tree [CrosbyWallach] 提案と同じですが, 本定義は満杯でない木の扱いが異なります)。

2.1.1. Merkle Audit Paths (メルクル監査パス)​

メルクルハッシュ木における葉のメルクル監査パス (Merkle audit path) は, その木のメルクルツリーハッシュを計算するのに必要な追加ノードの最短リストです。木の各ノードは葉ノードであるか, すぐ下 (葉方向) の2ノードから計算されます。木を上る各ステップ (根方向) で, 監査パスのノードがこれまで計算したノードと結合されます。言い換えると, 監査パスは, 葉から根までの経路上のノードを計算するのに欠けているノードのリストです。監査パスから計算した根が真の根と一致すれば, 監査パスはその葉が木に存在する証明です。

木への順序付き入力リスト D[n] = {d(0), ..., d(n-1)} が与えられたとき, (m+1) 番目の入力 d(m) (0 <= m < n) のメルクル監査パス PATH(m, D[n]) は次のように定義されます。

1要素入力リスト D[1] = \{d(0)\} の単一葉へのパスは空です。

PATH(0, {d(0)}) = {}

n > 1 のとき, k を n 未満の最大の2のべき乗とします。n > m なる n 要素リストにおける (m+1) 番目の要素 d(m) のパスは次のように再帰的に定義されます。

PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and

PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k,

ここで : はリストの連結であり, D[k1:k2] は前述どおり長さ (k2 - k1) のリスト {d(k1), d(k1+1),..., d(k2-1)} です。

2.1.2. Merkle Consistency Proofs (メルクル一貫性証明)​

メルクル一貫性証明 (Merkle consistency proofs) は木の追記のみ性を証明します。メルクルツリーハッシュ MTH(D[n]) と, 最初の m 枚の葉について以前公表されたハッシュ MTH(D[0:m]) (m <= n) に対するメルクル一貫性証明は, 両方の木で最初の m 個の入力 D[0:m] が等しいことを検証するのに必要なメルクル木内のノードのリストです。したがって一貫性証明は, MTH(D[n]) を検証するのに十分な中間ノード (入力へのコミットメント) の集合を含み, (その部分集合として) 同じノードで MTH(D[0:m]) を検証できるようにしなければなりません。本書は (一意な) 最小一貫性証明を出力するアルゴリズムを定義します。

順序付き入力リスト D[n] = {d(0), ..., d(n-1)} が与えられたとき, 以前のメルクルツリーハッシュ MTH(D[0:m]) (0 < m < n) に対するメルクル一貫性証明 PROOF(m, D[n]) は次のとおりです。

PROOF(m, D[n]) = SUBPROOF(m, D[n], true)

m = n の部分証明は, m がもともと PROOF が要求された値である場合 (部分木のメルクルツリーハッシュ MTH(D[0:m]) が既知であることを意味する) は空です。

SUBPROOF(m, D[m], true) = {}

m = n の部分証明は, 入力 D[0:m] にコミットするメルクルツリーハッシュです。そうでなければ次のとおりです。

SUBPROOF(m, D[m], false) = {MTH(D[m])}

m < n のとき, k を n 未満の最大の2のべき乗とします。部分証明は再帰的に定義されます。

m <= k の場合, 右部分木のエントリ D[k:n] は現在の木にのみ存在します。左部分木のエントリ D[0:k] が一貫していることを証明し, D[k:n] へのコミットメントを追加します。

SUBPROOF(m, D[n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])

m > k の場合, 左部分木のエントリ D[0:k] は両木で同一です。右部分木のエントリ D[k:n] が一貫していることを証明し, D[0:k] へのコミットメントを追加します。

SUBPROOF(m, D[n], b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])

ここで : はリストの連結であり, D[k1:k2] は前述どおり長さ (k2 - k1) のリスト {d(k1), d(k1+1),..., d(k2-1)} です。

得られる証明に含まれるノード数の上界は ceil(log2(n)) + 1 です。

2.1.3. Example (例)​

7枚の葉を持つ二分メルクル木:

              hash
             /    \
            /      \
           /        \
          /          \
         /            \
        k              l
       / \            / \
      /   \          /   \
     /     \        /     \
    g       h      i      j
   / \     / \    / \     |
   a b     c d    e f     d6
   | |     | |    | |
  d0 d1   d2 d3  d4 d5

d0 の監査パスは [b, h, l] です。

d3 の監査パスは [c, g, l] です。

d4 の監査パスは [f, j, k] です。

d6 の監査パスは [i, k] です。

同じ木を4段階で増分的に構築した場合:

    hash0          hash1=k
    / \              /  \
   /   \            /    \
  /     \          /      \
  g      c         g       h
 / \     |        / \     / \
 a b     d2       a b     c d
 | |              | |     | |
d0 d1            d0 d1   d2 d3

          hash2                    hash
          /  \                    /    \
         /    \                  /      \
        /      \                /        \
       /        \              /          \
      /          \            /            \
     /            \          /              \
    k            i          k                l
   / \          / \        / \              / \
  /   \         e f       /   \            /   \
 /     \        | |      /     \          /     \
g       h      d4 d5    g       h        i      j
/ \     / \             / \     / \      / \     |
a b     c d             a b     c d      e f     d6
| |     | |             | |     | |      | |
d0 d1   d2 d3           d0 d1   d2 d3    d4 d5

hash0 と hash の間の一貫性証明は PROOF(3, D[7]) = [c, d, g, l] です。c, g は hash0 の検証に使われ, d, l は追加で hash が hash0 と一貫することを示すのに使われます。

hash1 と hash の間の一貫性証明は PROOF(4, D[7]) = [l] です。hash は hash1=k と l を用いて検証できます。

hash2 と hash の間の一貫性証明は PROOF(6, D[7]) = [i, j, k] です。k, i は hash2 の検証に使われ, j は追加で hash が hash2 と一貫することを示すのに使われます。

2.1.4. Signatures (署名)​

各種データ構造に署名が付されます。ログは, NIST P-256 曲線を用いた楕円曲線署名 (Digital Signature Standard [DSS] の第D.1.2.3節), または少なくとも2048ビットの鍵を用いた RSA 署名 (SHA-256 による RSASSA-PKCS1-V1_5, [RFC3447] の第8.2節) のいずれかを用いなければなりません。

に最終更新