2.1.3. 示例

2.1.3. 示例

具有7个叶子的二叉Merkle树:

              hash
             /    \
            /      \
           /        \
          /          \
         /            \
        k              l
       / \            / \
      /   \          /   \
     /     \        /     \
    g       h      i      j
   / \     / \    / \     |
   a b     c d    e f     d6
   | |     | |    | |
  d0 d1   d2 d3  d4 d5

d0的审计路径是[b, h, l]。

d3的审计路径是[c, g, l]。

d4的审计路径是[f, j, k]。

d6的审计路径是[i, k]。

同一棵树,分四步增量构建:

      hash0          hash1=k
      / \              /  \
     /   \            /    \
    /     \          /      \
    g      c         g       h
   / \     |        / \     / \
  a b     d2       a b     c d
  | |              | |     | |
 d0 d1            d0 d1   d2 d3

            hash2                    hash
            /  \                    /    \
           /    \                  /      \
          /      \                /        \
         /        \              /          \
        /          \            /            \
       k            i          k              l
      / \          / \        / \            / \
     /   \         e f       /   \          /   \
    /     \        | |      /     \        /     \
   g       h      d4 d5    g       h      i      j
  / \     / \             / \     / \    / \     |
  a b     c d             a b     c d    e f     d6
  | |     | |             | |     | |    | |
 d0 d1   d2 d3           d0 d1   d2 d3  d4 d5

hash0和hash之间的一致性证明是PROOF(3, D[7]) = [c, d, g, l]。c、g用于验证hash0,d、l额外用于显示hash与hash0一致。

hash1和hash之间的一致性证明是PROOF(4, D[7]) = [l]。可以使用hash1=k和l来验证hash。

hash2和hash之间的一致性证明是PROOF(6, D[7]) = [i, j, k]。k、i用于验证hash2,j额外用于显示hash与hash2一致。