Merkle Proofs

You hold a block header (80 bytes). A full node claims "your transaction is in this block." Can it prove that without sending you the block? Yes — with the sibling hashes along your transaction's path to the root.

        ROOT
       /    \
      A      B
     / \    / \
    C   D  E   F
    |   |  |   |
   t1  t2 t3  t4

Proof for t2: [C, B]   -- one sibling per level

You compute hash(t2), combine it with C to rebuild D's parent A, combine that with B to rebuild the root, and compare against the root you already trust from the block header. Proof size is log2(N) hashes: 10 for 1,024 transactions, 20 (≈640 bytes) for a million. This is SPV — Simplified Payment Verification, whitepaper section 8 — and it's how phone wallets confirm payments without storing hundreds of gigabytes.

The ordering problem

At each level you must know whether the sibling goes on the left or the right — hash(sib + h) and hash(h + sib) differ. Implementations solve this three ways:

1. Position bits: the proof carries a left/right flag per level (Bitcoin's merkleblock encodes positions in its traversal flags).
2. Fixed convention by index parity.
3. Sorted pairs: always concatenate min(a,b) + max(a,b). No position data needed; the proof is just a bare list of hashes. This is what OpenZeppelin's widely-used MerkleProof contract does — and what this exercise does.

Sorted pairs are the cleanest to implement but discard position information — a verifier can no longer tell where the leaf sat, and real systems must also domain-separate leaves from interior nodes (e.g. prefix a 0x00/0x01 byte, as certificate transparency does) so an attacker can't present an interior hash as a "leaf." Toy scope: we skip that.

Verification, precisely

Walk one test by hand — tx a, siblings [3e23e8..., 3474e6...]: H("a") = ca9781...; first sibling 3e23e8... (which is H("b")) sorts before it, so h = H("3e23e8..." + "ca9781...") = ab19ec...; the second sibling 3474e6... sorts before that ('3' < 'a' in hex text), so the final combine is H("3474e6..." + "ab19ec...") — the root 7ab33b... — VALID. Notice the sort flipped sides between the two levels; that's why hardcoding an order can pass one level and fail the next. Note what a valid proof means — and what it doesn't: it proves this transaction is committed to by this root. It does not prove the transaction is valid, unspent, or that anything is absent from the tree (no non-membership proofs from a plain Merkle tree — you'd need a sorted/Sparse Merkle tree for that).

Your exercise

Input: <tx>|<root>|<sib1>,<sib2>,.... Print VALID or INVALID — uppercase, nothing else. The graded mistake this exercise exists to catch: concatenating in received order, H(h + sib), instead of sorting the pair. Received-order code returns INVALID on the very first test (tx a with the proof above), because H("ca9781..." + "3e23e8...") is a different parent entirely. Second catch: forgetting to hash the leaf before the loop — a is a token, H("a") is the leaf. If your first combine uses the raw token, nothing reaches the root.