2.1.2. Merkle一致性证明

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是最初请求PROOF的值(意味着子树Merkle树哈希MTH(D[0:m])是已知的),则m = n的子证明为空:

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。