System Design — Merkle Tree

A Merkle tree summarises a large data set in one root hash and lets you prove that a single
item belongs to it with only O(log n) hashes. Git, Cassandra's anti-entropy repair and
blockchains all rely on it.

solve(args, ops) builds new MerkleTree(leaves) — args = [leaves], a non-empty list of strings —
and replays ops:

• root() — the root hash.
• proof(index) — the proof for leaf index: a list of [siblingHash, side] pairs from the leaf

level up to just below the root. side is "L" if the sibling sits on the left of the
running hash, "R" if on the right.

• verify(leaf, proof, root) — true if hashing leaf and then combining it with each sibling

of proof in order gives root.

• update(index, leaf) — replace a leaf, rebuild and return the new root.

Construction (pinned). hash(text) is the 32-bit FNV-1a of the UTF-8 bytes (start
2166136261; per byte h ^= byte; h = h * 16777619 mod 2^32) written as **8 lowercase hex
digits**. A leaf node is hash(leaf). Each level pairs neighbours, and a parent is
hash(leftHex + rightHex) — the concatenation of the two hex strings. If a level has an odd
number of nodes, its last node is duplicated (paired with itself). Repeat until one node is left.

Example — leaves = ["a","b","c"]

root() → "6a4a49b2"
proof(2) → [["e60c2c52","R"],["403816d2","L"]]     // c is paired with its own copy, then with hash(a)+hash(b)