2.1. Merkleハッシュツリー

2.1. Merkleハッシュツリー

ログは効率的な監査のためにバイナリMerkleハッシュツリーを使用します。ハッシュアルゴリズムはSHA-256 [FIPS.180-4]です（これはこの実験では固定されていますが、各ログがハッシュアルゴリズムを指定できることが想定されています）。Merkleツリーハッシュへの入力はデータエントリのリストです。これらのエントリはハッシュ化されてMerkleハッシュツリーの葉を形成します。出力は単一の32バイトのMerkleツリーハッシュです。n個の入力の順序付きリストD[n] = {d(0), d(1), ..., d(n-1)}が与えられた場合、Merkleツリーハッシュ（MTH）は次のように定義されます：

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

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

1つのエントリを持つリストのハッシュ（リーフハッシュとも呼ばれる）は：

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

n > 1の場合、kをnより小さい2の最大のべき乗とします（すなわち、k < n <= 2k）。n要素リストD[n]のMerkleツリーハッシュは、次のように再帰的に定義されます：

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)}を表します。（葉とノードのハッシュ計算は異なることに注意してください。このドメイン分離は、第二原像抵抗性を与えるために必要です。）

入力リストの長さが2のべき乗である必要はないことに注意してください。結果として得られるMerkleツリーはバランスが取れていない場合がありますが、その形状は葉の数によって一意に決定されます。（注：このMerkleツリーは本質的にhistory tree [CrosbyWallach]の提案と同じですが、完全でないツリーの処理方法が異なります。）