General interview: Verify a Merkle inclusion proof

Prompt and scope

This is a cryptographic data-structure and protocol implementation problem. A Merkle inclusion proof sends only the sibling nodes needed to connect a target leaf to a root, rather than the whole tree. RFC 9162 domain-separates leaf and interior-node hashes and requires the verifier to use leaf_index and tree_size when deciding left and right at each level. Assume the client obtained root_hash through a trusted channel; the verifier does not establish that trust.

What the interviewer is testing

Distinguishing leaf hashes, interior hashes, and path direction information.
Using leaf_index and tree_size for bounds and path validation.
Understanding domain separation so leaf bytes cannot be confused with an interior-node input.
Explaining O(log n) proof size and verification time, plus the trusted-root boundary.

Clarifications to ask first

Confirm the tree specification: RFC 9162’s variable-size tree or a fixed full binary tree; leaf canonicalization; hash algorithm and prefix constants; and whether the path is ordered from leaf to root. Also clarify whether append-only consistency proofs or signatures are required, or only one inclusion proof. Without these conventions, a list of hashes does not uniquely define a root.

A 30-second answer

Check 0 <= leaf_index < tree_size and cap path length. Canonicalize the leaf as HASH(0x00 || leaf_bytes), then keep fn = leaf_index, sn = tree_size - 1, and the current hash r. At each level, use the low bit of fn or the condition fn == sn to decide whether the sibling is left or right, hash with the interior prefix 0x01, and shift both indices. Succeed only when sn == 0 and r == root_hash.

Step-by-step solution

1. Fix the input contract and domain separation

The verifier needs a versioned hash algorithm, leaf encoding, path order, and tree-size semantics. RFC 9162’s Merkle Tree Hash uses 0x00 for leaves and 0x01 for interior nodes, preventing the same byte string from being interpreted in two roles. Do not hash leaf || sibling without domain separation or let a caller replace the prefixes arbitrarily.

2. Perform bounds and resource checks first

leaf_index >= tree_size must fail; an empty tree has no valid leaf. Cap the path, for example at ceil(log2(tree_size)) + 1, and require a fixed byte length for each hash. Reject integer overflow, negative encodings, duplicate parsing, and oversized paths so hostile proofs cannot consume unbounded resources. A short path is not automatically valid; the final state must converge to one root.

3. Rebuild the root level by level

For RFC 9162’s variable-size tree, parity alone is insufficient: the boundary condition fn == sn changes the concatenation direction. Shift both fn and sn after each level to map the current node to its parent. Pseudocode:

text

verify(leaf, leafIndex, treeSize, path, expectedRoot):
  if treeSize <= 0 or leafIndex < 0 or leafIndex >= treeSize: return false
  r = HASH(0x00 || leaf)
  fn = leafIndex
  sn = treeSize - 1
  for sibling in path:
    if sn == 0: return false
    if (fn & 1) == 1 or fn == sn:
      r = HASH(0x01 || sibling || r)
    else:
      r = HASH(0x01 || r || sibling)
    fn = fn >> 1
    sn = sn >> 1
  return sn == 0 and r == expectedRoot

4. Check path and tree-size agreement

The proof’s tree_size participates in direction calculation; it is not decorative log metadata. When the path is consumed, sn must be zero. If it remains positive, the proof did not reach the root; if sn is already zero and more siblings remain, reject the proof. A fixed-tree implementation may use different rules, but its generator and verifier must share that tree convention instead of mixing it with RFC 9162 paths.

5. Complexity, communication, and trust

A balanced tree usually has O(log n) sibling hashes. Verification takes O(log n) hash operations and O(1) state beyond the path; communication is O(log n * hashSize). The proof only binds a leaf to the supplied root. If the root came from an untrusted response, an attacker can replace both root and proof. Production protocols protect the root and tree size with signatures, a trusted log head, or authenticated transport.

Model answer

I would bind the verifier to a versioned tree specification. First check tree_size > 0, 0 <= leaf_index < tree_size, hash lengths, and the path budget, then compute r = HASH(0x00 || leaf). Keep fn = leaf_index and sn = tree_size - 1; at each level put the sibling on the left when fn is odd or fn == sn, otherwise on the right, and update with HASH(0x01 || left || right). Shift both indices. At the end, only sn == 0 and equality with the trusted root succeed. Proof size and verification cost are O(log n), while the protocol must authenticate the root, tree size, and path ordering.

Common mistakes

Choosing direction only from index parity and ignoring the variable-tree boundary fn == sn.
Using one hash prefix for leaves and interior nodes, losing domain separation.
Comparing only the rebuilt root without checking leaf bounds, path length, or sn convergence.
Treating an untrusted response’s root as an authentication anchor.
Building with one tree convention and verifying with a different full-binary-tree rule.
Omitting path order, hash byte order, or leaf canonicalization from the versioned contract.

Follow-up questions

How would you verify an append-only consistency proof?

An inclusion proof answers whether one leaf belongs to one root. A consistency proof reconstructs both an old and a new root and proves the old tree is a prefix of the new one. Inputs include old and new sizes, a path, and both trusted roots. Its state transitions differ, so it should not be hidden inside a Boolean-only inclusion function.

Why transmit tree_size instead of only the path?

In a variable-size tree, the last node may have no right sibling at its level. Direction depends on the current subtree boundary. tree_size tells the verifier which nodes exist and prevents extra hashes from being smuggled into a fake root path.

How do you prevent hash-algorithm downgrade?

Version the algorithm identifier, output length, leaf/interior prefixes, and canonicalization. Accept only an allowlist and reject unknown or weak algorithms. A migration creates a new root namespace; digests from different algorithms must not share one tree.

How do duplicate leaves affect the proof?

An inclusion proof binds bytes to a position; it does not prove that the value appears only once. Uniqueness requires a separate key index or set proof. A single Merkle root cannot prove the non-existence of another equal value.

How can a generator be incremental without storing the whole tree?

Keep the newest right-hand subtree digest at each level as a prefix accumulator and merge a new leaf like binary carry propagation. Proving an old leaf still requires retaining the needed siblings or an external store; the root alone cannot recreate a path.

How should the verifier handle an oversized path?

Compute a bound from tree size and hash length before parsing, reject longer paths, and check every element’s fixed length to avoid multiplication overflow. Finish the resource budget before hashing so a malformed proof cannot trigger an infinite loop or large allocation.