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]です。

同じツリーを4つのステップで段階的に構築：

      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]です。hashはhash1=kとlを使用して検証できます。

hash2とhashの間の一貫性証明はPROOF(6, D[7]) = [i, j, k]です。k、iはhash2を検証するために使用され、jはさらにhashがhash2と一貫していることを示すために使用されます。