2.1.1. Merkle审计路径

2.1.1. Merkle审计路径

Merkle哈希树中叶子的Merkle审计路径是计算该树的Merkle树哈希所需的Merkle树中其他节点的最短列表。树中的每个节点要么是叶子节点,要么从其正下方的两个节点计算(即朝向叶子)。在树上的每一步(朝向根),审计路径中的一个节点与到目前为止计算的节点组合。换句话说,审计路径由计算从叶子到树根的节点所需的缺失节点列表组成。如果从审计路径计算的根与真实根匹配,则审计路径是叶子存在于树中的证明。

给定树的n个输入的有序列表D[n] = {d(0), ..., d(n-1)},第(m+1)个输入d(m)(0 <= m < n)的Merkle审计路径PATH(m, D[n])定义如下:

具有单元素输入列表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]) 当m < k时;以及

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

其中:是列表的连接,D[k1:k2]表示长度为(k2 - k1)的列表{d(k1), d(k1+1),..., d(k2-1)}(如前所述)。