2.1.1. Merkle監査パス

2.1.1. Merkle監査パス

MerkleハッシュツリーにおけるリーフのMerkle監査パスは、そのツリーのMerkleツリーハッシュを計算するために必要なMerkleツリー内の追加ノードの最短リストです。ツリー内の各ノードは、リーフノードであるか、その直下（すなわち、葉に向かって）の2つのノードから計算されます。ツリーを上に向かって（ルートに向かって）各ステップで、監査パスからのノードが、これまでに計算されたノードと結合されます。言い換えれば、監査パスは、リーフからツリーのルートまで導くノードを計算するために必要な欠落ノードのリストから構成されます。監査パスから計算されたルートが真のルートと一致する場合、監査パスはそのリーフがツリーに存在することの証明です。

ツリーへのn個の入力の順序付きリストD[n] = {d(0), ..., d(n-1)}が与えられた場合、(m+1)番目の入力d(m)、0 <= m < nに対するMerkle監査パスPATH(m, D[n])は次のように定義されます：

1要素の入力リストD[1] = {d(0)}を持つツリー内の単一のリーフのパスは空です：

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

n > 1の場合、kをnより小さい2の最大のべき乗とします。n > m要素のリスト内の(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)}を表します。