Lesson 14 · Verifying a proof - Build a Merkle Tree

Verifying a proof

A proof is only useful if a verifier holding just the root can recompute it from one leaf. Today you build VerifyProof.

The goal

Recompute the root from a leaf and its proof, and compare to the trusted root.

Start here - the target

TO DO

Scenario: VerifyProof folds a leaf up to the root

Giventhe trusted root 0xfd610c23 and leaf 0 proof [(0x6bfe63ee, right), (0x1cde9a86, right)]

WhenVerifyProof folds HashLeaf("alice") up through the steps

Thenthe recomputed hash equals 0xfd610c23 and it returns true

AndVerifyProof of "carol" with proof [(0x68cf0725, right), (0xebb8e925, left)] against the same root also returns true

Background

Verification is the mirror of generation. Start by hashing the leaf data (with the 0x00 prefix, exactly as the tree did), then fold in each proof step: if the sibling was on the right, compute HashNode(current, sibling); if on the left, HashNode(sibling, current). After the last step you have recomputed a root, and if it equals the trusted root, the leaf is proven to be in the tree.

This is the moment the whole structure pays off: the verifier never saw the other leaves, never rebuilt the tree, and used only a handful of hashes, yet is certain alice is leaf 0 under root 0xfd610c23. The SiblingRight flag is load-bearing - get the order wrong on any step and the recomputed root will not match. Next you will watch verification correctly reject forgeries.

Make it work

func VerifyProof(root Hash, leaf []byte, proof []ProofStep) bool {
  h := HashLeaf(leaf)
  for _, s := range proof {
    if s.SiblingRight {
      h = HashNode(h, s.Sibling) // sibling on the right
    } else {
      h = HashNode(s.Sibling, h) // sibling on the left
    }
  }
  return h == root
}

CheckpointDONE

A leaf plus its proof recomputes the root and verifies against it. Commit and stop here.