Merkle Trees

A block header is 80 bytes, yet it commits to every transaction in the block. The device that makes this possible is the Merkle tree: hash each transaction to make the leaves, hash pairs of hashes to make parents, repeat until one hash remains — the root.

              ROOT
             /    \
           h12    h34
          /  \    /  \
        h1   h2  h3   h4
        |    |   |    |
       tx1  tx2 tx3  tx4

Two properties justify the extra machinery over "just hash all the transactions together":

• One hash commits to everything. Change any transaction and the change propagates leaf-to-root; the root in the block header no longer matches.
• Membership is provable in log N. To convince someone tx2 is in the tree you don't ship all N transactions — just the sibling hashes along tx2's path (next lesson). For a million transactions: 20 hashes. A flat hash(tx1+tx2+...+txN) commits to everything too, but proving membership would require shipping all N.

That second property is why the pattern is everywhere: Bitcoin SPV wallets verify a payment without downloading the block; Git's commit→tree→blob graph is a Merkle DAG; certificate-transparency logs prove a TLS cert was logged; IPFS addresses content by Merkle hash.

The odd-node rule

Binary trees want even levels. When a level has an odd count, Bitcoin duplicates the last hash and pairs it with itself. This isn't just at the leaves — it applies at every level on the way up. Five transactions: 5 → duplicate → 6 → 3 parents → duplicate → 4 → 2 → 1. Fun fact: this duplication once enabled a real consensus bug (CVE-2012-2459) — two different transaction lists, one with an explicit duplicate, produce the same root. Production Bitcoin has to detect that; our toy doesn't.

This course's conventions

Real Bitcoin hashes raw bytes with double SHA-256. For debuggability, this course hashes text: a leaf is sha256(token) of the ASCII token, and a parent is sha256(left_hex + right_hex) — the two 64-character hex strings concatenated as text, then hashed once.

Note the input format: the transactions arrive on one line, comma-separated (01,02,03), not one per line. An empty input means an empty tree — print sha256(""), the famous e3b0c442... constant.

Your exercise

Compute the Merkle root. The grader's classic catch is the five-leaf test 01,02,03,04,05, expected root a59b7e5a3c7e7f58f0305892ea0cb6b1e867251e9b0ed3090ff00e6a8b4c3de1: it forces duplication at two different levels (5→6 and 3→4), so code that only duplicates at the leaf level — or duplicates once and forgets the loop — passes the three- and four-leaf tests and dies here. Second catch: concatenating raw digest bytes instead of hex strings; every multi-leaf answer shifts. And the empty test must print e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 — not an empty line, not a crash.