🌳 Merkle Tree — Hash Trees & Proofs

The simulation swaps in a small, fast FNV-1a-style mixing function that produces a 4-hex-digit id instead of a full 256-bit SHA-256 digest, purely so the hashes are readable on screen and recompute instantly as you type. The tree-building algorithm, the tamper-evidence property, and the O(log n) proof logic are identical to production systems; only the underlying hash function differs.

At any level with an odd node count, the simulation's buildTree function pairs the last node with a copy of itself before hashing, which is exactly the duplicate-last-node rule used in real Merkle tree implementations such as Bitcoin's. This keeps every level binary so the tree always reduces cleanly to a single root, regardless of whether the leaf count (2 to 16 in this demo) is a power of two.

Editing a leaf triggers markChangedPath, which walks from that leaf up to the root marking every ancestor red to show which hashes were recomputed. Clicking Verify leaf instead triggers buildProof, which marks the path to the root in purple and marks the sibling hash needed at each level in amber — the minimal set of extra hashes a verifier needs to recompute the root from that one leaf, without seeing any other block.

Each level of the tree halves the number of nodes, so a tree of n leaves has about log2(n) levels. A proof needs exactly one sibling hash per level on the path from leaf to root, so its size grows logarithmically rather than linearly with the number of leaves — for a million leaves that is roughly 20 hashes, letting a light client verify inclusion without downloading the other 999,999 blocks.

In principle a hash collision could make two different datasets produce the same root, but with a cryptographically secure hash such as SHA-256 this is computationally infeasible — the demo's simplified FNV-1a-style function is not collision-resistant and is used here only for speed and readability, never for real integrity guarantees.