Lesson 12 · A proof step - Build a Merkle Tree

A proof step

An inclusion proof is a path of sibling hashes from a leaf up to the root. Today you take the first step - recording a leaf's sibling and which side it is on.

The goal

Record the sibling hash and its side for a leaf at the bottom level.

Start here - the target

TO DO

Scenario: A proof step is a sibling hash plus its side

Giventhe tree Build(["alice", "bob", "carol", "dave"])

Whenthe bottom-level sibling of leaf 0 ("alice") is recorded as a proof step

Thenthe step holds sibling hash 0x6bfe63ee marked as being on the right

Andthe sibling of leaf 1 ("bob") is 0x00063049 marked as being on the left

Background

An inclusion proof (also called an audit proof) convinces someone who has only the root that a particular leaf is really in the tree. It works by handing them just enough hashes to recompute the root themselves, walking up from the leaf. The unit of that path is one proof step: the sibling hash at each level, plus which side the sibling is on.

The side is not optional bookkeeping. HashNode(l, r) differs from HashNode(r, l), so to recompute a parent the verifier must know whether to hash HashNode(me, sibling) or HashNode(sibling, me). At the bottom level a leaf at an even index pairs with the leaf on its right; an odd index pairs with the one on its left. Today you just capture one step; next lesson you walk the whole path.

Make it work

type ProofStep struct {
  Sibling      Hash
  SiblingRight bool // true if the sibling sits to our right
}
// at level 0: even index -> sibling is index+1 on the right;
//             odd index  -> sibling is index-1 on the left.

CheckpointDONE

A single proof step records a sibling hash and which side it is on. Commit and stop here.