2.1.2. Merkle一貫性証明

Merkle一貫性証明は、ツリーの追加専用プロパティを証明します。MerkleツリーハッシュMTH(D[n])と、最初のm個の葉の以前に公表されたハッシュMTH(D[0:m])、m <= nに対するMerkle一貫性証明は、最初のm個の入力D[0:m]が両方のツリーで等しいことを検証するために必要なMerkleツリー内のノードのリストです。したがって、一貫性証明は、MTH(D[n])を検証するのに十分な中間ノード（すなわち、入力へのコミットメント）のセットを含む必要があり、（そのサブセットの）同じノードがMTH(D[0:m])を検証するために使用できるようにする必要があります。（一意の）最小一貫性証明を出力するアルゴリズムを定義します。

ツリーへのn個の入力の順序付きリストD[n] = {d(0), ..., d(n-1)}が与えられた場合、以前のMerkleツリーハッシュMTH(D[0:m])、0 < m < nに対するMerkle一貫性証明PROOF(m, D[n])は次のように定義されます：

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

m = nの部分証明は、mがPROOFが最初に要求された値である場合（すなわち、サブツリーMerkleツリーハッシュMTH(D[0:m])が既知であることを意味する）、空です：

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

m = nの部分証明は、入力D[0:m]をコミットするMerkleツリーハッシュです。それ以外の場合：

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.2. Merkle一貫性証明​

2.1.2. Merkle一貫性証明