A Merkle tree turns any list of data into one root hash you can trust: change a single byte anywhere and the root changes. Every lesson is one concrete spec with exact hashes, roots, and proofs. Uses a simple, hand-checkable FNV-1a hash instead of SHA-256 so every leaf hash, internal node, root, and proof is a pinned value you can reproduce - the tree structure is identical for any hash function.
Over 23 lessons you build a working Merkle tree library from scratch: a tamper-evident structure that condenses a whole list of data into a single root hash. Change one byte of one item and the root changes; hand someone the root and a short proof and they can confirm an item belongs without seeing the rest of the data. This is the structure behind Git commits, Certificate Transparency logs, Bitcoin blocks, and peer-to-peer file sync.
To keep every value exact and reproducible in any language, the project uses a simple deterministic hash - 32-bit FNV-1a rendered as eight hex digits - instead of a real cryptographic hash. Every leaf hash, internal node, root, and proof in the specs is a concrete number you can recompute by hand. You start with the hash itself and leaf-versus-internal domain separation (a 0x00 prefix for leaves, 0x01 for internal nodes, which blocks a classic forgery), build the tree by hashing all leaves and repeatedly pairing and hashing adjacent hashes up to a single root, handle an odd node at a level by promoting it, then use the root to detect tampering. On top of that you build inclusion (audit) proofs - an ordered list of sibling hashes that lets a verifier recompute the root from one leaf - and finish with an append-only consistency proof and a diff that walks two trees to report exactly which leaves changed. The capstone builds a tree over real data, proves and verifies membership, tampers with a leaf to show detection, and diffs two versions.
This is a teaching-grade library, honest about its scope: it uses FNV-1a rather than SHA-256 (so it is a demonstration of structure, not real cryptographic security - the tree design is hash-agnostic and swapping in SHA-256 changes only the hash function), promotes lone nodes rather than duplicating them the way Bitcoin does, and diffs trees with the same number of leaves. It is exactly the honest core that production systems extend with a real hash, wider consistency proofs, and persistence.
A Merkle tree is built entirely from hashes, so the first thing you need is a hash - a function that turns any bytes into a fixed fingerprint. Today you build a simple, fully deterministic hash you can reproduce by hand.
Turn a byte string into a 32-bit fingerprint using the FNV-1a hash.
A hash takes any bytes and returns a fixed-size fingerprint, in a way that is deterministic (same input, same output) and sensitive (a tiny change in the input scrambles the output). Real Merkle trees use a cryptographic hash like SHA-256, but those produce 32-byte outputs that are impractical to check by hand and behave a little differently in every language. So this project uses FNV-1a, a tiny, well-defined hash that fits in a 32-bit integer and prints as eight hex digits. Every leaf hash, node, root, and proof you meet will be an exact number you can recompute.
The algorithm is two lines in a loop: start from a fixed offset basis, and for each byte XOR it into the running value and then multiply by a fixed prime, letting the 32-bit integer wrap. That is it. The tree you build on top is completely hash-agnostic - swap in SHA-256 and only this one function changes; every structural idea in the rest of the project stays identical.
type Hash uint32func hashBytes(data []byte) Hash {var h uint32 = 0x811c9dc5 // FNV offset basisfor _, b := range data {h ^= uint32(b) // fold in the byteh *= 0x01000193 // FNV prime; uint32 wraps at 2^32}return Hash(h)}
The library implements the core Merkle tree primitives (build, prove, verify, consistency, and diff) with graceful edge-case handling, but it intentionally uses a non-cryptographic 32-bit FNV-1a hash and supports only power-of-two consistency ranges and equal-leaf-count diffs, so it is teaching-grade rather than production-ready.
The paper that introduced the hash tree. Merkle needed to authenticate many messages from one public value; the tree of hashes, with a short authentication path to the root, is the idea this whole project builds.
The clearest practical spec of Merkle audit proofs (inclusion) and consistency proofs (append-only). Section 2 defines the exact tree-hashing and proof algorithms - including the 0x00 leaf and 0x01 node prefixes this project uses for domain separation.
Section 7 (Reclaiming Disk Space) puts a Merkle root in each block header so a transaction can be proven present with a branch of the tree, without storing the whole block. Note Bitcoin duplicates a lone node where this project promotes it.
Content addressing in the wild: Git names every object by the hash of its content, so identical content collapses to one object and any change ripples up to a new commit hash. The same "same content, same hash" property leaf hashing gives you here.
History trees generalize the append-only Merkle log: how to prove an old root is consistent with a new one after appends, which is the consistency-proof idea the diffing chapter sketches.