Merkle trees: reconstruct a root, then ask what it proves

Suppose a server gives you one transaction from a block containing thousands. Downloading every transaction would let you recompute the block's commitment, but defeats the point of a small client. A Merkle proof supplies just the missing sibling hashes along one path.

The useful skill is separating three questions: how is the tree built, does this path reproduce the expected root, and why should you trust that root? The exercise answers the first two. The third belongs to block and chain validation.

Prerequisites: byte concatenation, hash functions, and zero-based indexing. You do not need a pointer-based tree. Arrays of hashes are enough.

Define the bytes before drawing the tree

Let H(x)=SHA256(SHA256(x)). In this exercise:

• A leaf is raw bytes; its initial hash is H(leaf).
• A parent is H(leftHash || rightHash), where each child contributes 32 raw bytes.
• Preserve child order. Do not sort the children or concatenate hex strings.
• At each level with an odd count greater than one, duplicate its final hash.
• Stop at one hash. A one-leaf root is H(leaf), without another duplication.
• An empty list returns the all-zero 32-byte value by API convention.

These conventions are part of the algorithm. Hashing displayed transaction IDs, hashing an already hashed leaf again, or changing odd-node treatment builds a different commitment.

Build five leaves by hand

Call the leaf hashes a,b,c,d,e. Use H(a||b) as notation for hashing the 64-byte concatenation.

Level 0:  a          b          c          d          e
Level 1:      p=H(a||b)             q=H(c||d)           r=H(e||e)
Level 2:             u=H(p||q)                         v=H(r||r)
Level 3:                         root=H(u||v)

There are five hashes at level 0, so duplicate e. There are three at level 1, so duplicate r too. Odd duplication is a per-level rule; padding the leaf list once is not the general construction.

The invariant at the start of a level is that every entry commits to its ordered subtree under these rules. Pairing adjacent entries preserves that invariant at the next level. The number of entries changes from n to ceil(n/2), so repeated pairing terminates at the root.

Derive a proof from the same reduction

A proof step holds a sibling hash and Left, meaning the sibling is on the left. For leaf e, starting at index 4:

Current level	Current index	Sibling supplied	Left?	Parent index
a,b,c,d,e,e	4	e	false	2
p,q,r,r	2	r	false	1
u,v	1	u	true	0

After odd duplication, index ^ 1 selects the sibling: adjacent even/odd indices differ only in their low bit. Move to the parent with integer division by two.

Verification starts at h=H(leaf). For each step:

if step.Left: h = H(step.Hash || h)
else:         h = H(h || step.Hash)

After the first step for e, h=r; after the second, h=v; after the third, h=root. Comparing against the expected root finishes the check.

Why does this work? At every step the verifier reconstructs the exact parent the full tree would build, assuming its sibling hash is correct. By induction, its final value is the root of that supplied path. Collision resistance supports the commitment argument; the mechanical equality test itself is just deterministic hashing.

Boundary cases reveal the contract

For a one-leaf tree, a valid proof has zero steps: verification compares H(leaf) directly with the root. An invalid index also returns nil from MerkleProof. An empty proof is not an error code. Callers know the requested index and list length when generating it; verification simply checks the supplied path.

The verifier takes neither an index nor a leaf count. Direction bits describe a path, but the API cannot separately validate a claimed list length, claimed position, or canonical tree shape. Do not present a successful return as evidence for metadata the function never received.

A changed leaf, sibling, direction, or expected root normally breaks verification. Choose distinct sibling hashes when testing direction: swapping two identical hashes changes nothing.

A deterministic tree does not uniquely encode every list

The odd-duplication rule has a structural ambiguity. Compare the three-leaf list [A,B,C] with [A,B,C,C]:

three leaves: root = H(H(a||b) || H(c||c))
four leaves:  root = H(H(a||b) || H(c||c))

The roots are exactly equal. No hash collision was found: both algorithms hashed exactly the same bytes. Thus “duplication avoids ambiguous shapes” is false, and a root alone does not prove the original transaction count. Bitcoin Core documents this duplicate-subtree issue and checks for mutation separately.

Keep this exercise's established construction, including its ambiguity. MerkleRoot has no mutation-status return and VerifyMerkleProof has no tree-size argument. A production validation protocol needs rules beyond these three functions. Different Merkle designs use explicit lengths or distinguish leaf and internal-node hashing; changing those conventions here would change all roots and proofs.

Root trust and transaction validity are separate

A dishonest server can construct a perfectly valid path to a root it invented. Verification is useful when you already have an independently accepted root, for example from a header validated according to the surrounding protocol.

Even against that root, a path check does not execute scripts, check spendability, prevent double spends, or choose the best chain. It checks a hashing relationship. Keep those responsibilities separate when you reach block assembly and chain selection.

For a protocol description of transaction trees in headers, see the Bitcoin developer reference. This exercise starts with raw leaf bytes and uses a simplified proof API; it does not parse a network proof message.

Cost: generating a proof is different from verifying it

For n leaves containing B total bytes, computing all leaf hashes costs O(B), and reducing the levels costs O(n) fixed-size parent hashes. A level-array implementation uses O(n) temporary hash storage.

Generating a proof while constructing the tree still costs O(B+n). Its output contains only ceil(log2(n)) sibling hashes for n>=1; proof size does not imply logarithmic construction work. With a retained tree, later proof lookup can take O(log n).

Verification hashes the leaf and one fixed-size pair per supplied step: O(leaf bytes + k), where k is the proof length, with constant working space beyond the proof. A generated proof has k=ceil(log2(n)); the verifier also accepts arbitrary step lists and does not know n. Empty and single-leaf trees need their explicit boundary rules.

Reconstruction lab

1. In the five-leaf diagram, write the proof for b, including all three direction flags.
2. A verifier sorts each pair before hashing. Why is that wrong for this format?
3. A server claims a successful proof establishes that the original list contained exactly three leaves. Give a counterexample.
4. Why can testing only Verify(leaf, MerkleProof(...), MerkleRoot(...)) miss a bug?

Model answers

1. Siblings are a on the left, q on the right, and v on the right: flags true,false,false. The reconstructed hashes are p,u,root.
2. The tree commits through ordered concatenation. Sorting discards the specified ordering and generally produces a different root. Direction bits tell you which order to use.
3. [A,B,C] and [A,B,C,C] have the same root. The verifier also receives no leaf-count argument.
4. All three functions could share the same wrong odd-node or byte-encoding convention. Independently assemble a three- or five-leaf root using SHA-256 and explicit concatenations, then verify handcrafted paths against it.

Implement Merkle Root and Proofs, then use the checkpoint to test path reconstruction and the limits of the result.