Merkle trees

Goal: reconstruct a root from one leaf and its siblings.

Keep three questions separate:

How is this tree constructed?
Does this path reproduce the expected root?
Why do we trust that root?

1 / 10

Specify bytes, then hash

H(x) = SHA256(SHA256(x))

Leaf: H(raw bytes).
Parent: H(left 32 bytes || right 32 bytes).
Duplicate the final hash at every odd nonterminal level.
One leaf: its hash. No extra duplication.
Empty list: zero root by convention.

Hex strings and raw hashes are different inputs.

2 / 10

Five leaves require two duplications

a b c d e
p=H(a||b) q=H(c||d) r=H(e||e)
u=H(p||q) v=H(r||r)
root=H(u||v)

Predict: how many steps does the proof for e contain?

Three. One sibling at each reduction level.

3 / 10

Proof for e

Index	Sibling	Sibling on left?
4	e	no
2	r	no
1	u	yes

After duplication: sibling=index ^ 1; parent=index/2.

Direction describes the sibling, not the current node.

4 / 10

Verify one parent at a time

Start h=H(leaf).

Left=true:  h=H(sibling||h)
Left=false: h=H(h||sibling)

For e: H(e||e)=r, H(r||r)=v, H(u||v)=root.

Invariant: h is the reconstructed subtree root at this height.

5 / 10

A zero-step proof can be valid

One leaf: compare H(leaf) with root.

MerkleProof also returns nil for an invalid index.

Therefore an empty proof alone is not an error signal.

The verifier receives no claimed index or leaf count.

6 / 10

Find the ambiguity

[A,B,C]   → H(H(a||b)||H(c||c))
[A,B,C,C] → H(H(a||b)||H(c||c))

Same root, different lists. No hash collision required.

Deterministic odd duplication does not uniquely commit to list length.

7 / 10

What did verification establish?

A hashing path agrees with the supplied root.

It does not establish:

That the root belongs to an accepted chain.
That the transaction is valid or unspent.
The original leaf count.

Those need evidence outside this proof API.

8 / 10

Cost and independent tests

Build root/proof from raw leaves: O(total bytes+n).
Proof output: O(log n) hashes.
Verify: leaf hashing plus O(k) parent hashes for k supplied steps.
Generated proofs have k=ceil(log2(n)); the verifier does not know n.

Test handcrafted roots and paths, direction flips, singleton proofs, and odd duplication at multiple levels. Round trips alone can share a bug.

9 / 10

Reconstruct without the diagram

For five leaves, give b's sibling sequence and flags.

Answer: a,q,v; true,false,false.

Explain why a proof against a server-chosen root cannot establish chain membership.

Exercise · Checkpoint

10 / 10