Skip to main content

2.1.3. Example

2.1.3. Example​

The binary Merkle Tree with 7 leaves:

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

The audit path for d0 is [b, h, l].

The audit path for d3 is [c, g, l].

The audit path for d4 is [f, j, k].

The audit path for d6 is [i, k].

The same tree, built incrementally in four steps:

      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

The consistency proof between hash0 and hash is PROOF(3, D[7]) = [c, d, g, l]. c, g are used to verify hash0, and d, l are additionally used to show hash is consistent with hash0.

The consistency proof between hash1 and hash is PROOF(4, D[7]) = [l]. hash can be verified using hash1=k and l.

The consistency proof between hash2 and hash is PROOF(6, D[7]) = [i, j, k]. k, i are used to verify hash2, and j is additionally used to show hash is consistent with hash2.

Last updated on