The Gold Standard of Information | Merkle Trees, Chunk Identity and Localising Change

Full chapter index

A whole-file checksum compresses a byte sequence into a fixed-size digest. It is excellent for a yes-or-no identity check: recompute with the same algorithm and compare with a trusted expected value. When a 20-gigabyte archive differs, however, the whole-file digest does not say where. You may need to reread or retransmit everything.

A Merkle tree divides the collection into leaves. Leaves might represent fixed-size byte chunks, files, database records or log entries. Pair the leaf hashes, hash each pair into a parent, then repeat. The root commits to all leaves and their order under that construction. Changing one leaf changes every ancestor on its path, but leaves and branches elsewhere remain unchanged.

The hierarchy creates locality. Two replicas can compare roots; if the roots differ, compare child hashes; descend only into differing branches. With a balanced binary tree containing n leaves, a membership path contains about log2(n) sibling hashes. This is why the structure appears in distributed storage, version control and transparency logs.

The root is not a summary a human can interpret. It is a compact cryptographic commitment under assumptions about the hash function and encoding. Keep the manifest that explains what each leaf represents. Without that manifest, a root may be reproducible but operationally useless.

Contents · Next chapter

“Hash the chunks” is incomplete until chunk identity is defined. Fixed-size chunking might use every four mebibytes of a byte stream. Content-defined chunking chooses boundaries from local byte patterns so that inserting bytes near the start does not shift every later boundary. Record-based leaves might use canonical serialisation of a database row.

Include enough context to avoid ambiguity. If a leaf is just H(bytes), two identical chunks at different positions have the same leaf hash. That can be desirable for deduplication, but a proof about position may also need the index, length or type in the encoded leaf. The protocol must say which fields are inside the hash.

Canonicalisation is critical for structured data. JSON objects can be serialised with different whitespace or key order while representing the same abstract values. Decide whether identity means identical bytes or equivalent parsed content. Byte identity is simpler and stronger for preservation. Semantic identity requires a documented canonical form and may erase distinctions that matter later.

Do not change chunk size silently. A four-mebibyte tree and an eight-mebibyte tree over the same file normally have different leaves and roots. Store a tree version, algorithm identifier and chunking rule beside the root. Verification must recreate the same construction, not merely use a function also called “Merkle tree.”

Contents · Previous chapter · Next chapter

An internal node is commonly the hash of its children, but concatenation can be ambiguous if lengths or roles are not fixed. Robust specifications distinguish leaf hashing from node hashing, for example by prefixing different bytes. RFC 6962 uses separate prefixes for leaves and internal nodes in its certificate-transparency tree.

Order matters. H(left || right) is generally different from H(right || left). An unordered-set application needs a different rule, such as sorting child values before hashing, and that choice changes what the root means. For an ordered log or file, preserve the intended order explicitly.

Odd numbers of leaves require a policy. Some systems promote the unpaired node, some duplicate it, and others use a deterministic split as in certificate transparency. None is universally “the Merkle rule.” Verifiers must implement the same rule or they will disagree even on identical leaves.

Domain separation prevents a byte string intended as a leaf from being confused with the concatenation that defines a node. It also makes proof parsing safer. Treat encoding as part of the security design, not as a formatting layer added after the hash function is chosen.

Contents · Previous chapter · Next chapter

Imagine an ordered file split into chunks C0 through C7. Compute leaf hashes L0 = H(leaf-prefix || C0), through L7. Then compute parents P0 = H(node-prefix || L0 || L1), P1 from L2 and L3, P2 from L4 and L5, and P3 from L6 and L7. Next compute Q0 from P0 and P1, Q1 from P2 and P3, and root R from Q0 and Q1.

Suppose C5 changes. L5 changes, so P2 changes, then Q1, then R. L0–L4, L6–L7, P0, P1, P3 and Q0 remain valid. A synchronisation process that already trusts the old and new construction can narrow the difference to the branch containing C5 instead of reading every chunk in depth.

The attached table uses short labels such as a5 and b2 to show this path. They are not collision-resistant values and must never be copied into a real manifest. The point is dependency: each parent is a function of its exact children. A root mismatch means at least one contributing input or rule differs.

Now insert a byte into C1 under fixed-size chunking. The changed byte can shift every subsequent chunk boundary, causing many leaves to change. Under content-defined chunking, boundaries may resynchronise after a short region. The tree did not fail; the chunking scheme determined the locality of change. Choose chunking from the repair and comparison behaviour you need.

Contents · Previous chapter · Next chapter

An inclusion proof shows that a particular leaf contributes to a stated root without supplying every other leaf. For C5 in the eight-leaf example, the verifier needs L5’s encoded content or hash, its sibling L4, the sibling subtree P3, and the sibling half Q0. The verifier combines them in the correct left-right order and checks whether the computed root equals the trusted R.

The proof is logarithmic in a balanced tree. Eight leaves need three sibling values; about one million leaves need about twenty. This efficiency supports transparency logs and content systems where a client cannot download the full collection.

A valid inclusion proof establishes inclusion relative to that root and tree size. It does not prove that the leaf statement is factually true, that the root was published honestly, or that no conflicting root was shown to someone else. Certificate-transparency systems add signed tree heads, consistency proofs and cross-checking because the tree alone does not solve those trust problems.

Index and tree size matter. A proof for a leaf in a tree of 1,000 entries should not be replayed as though it referred to a later 2,000-entry tree without a defined consistency relationship. Store or transmit the context that the verification algorithm requires.

Contents · Previous chapter · Next chapter

An append-only log promises that a later tree extends an earlier prefix rather than rewriting history. Comparing two root hashes is not enough: different roots are expected when new leaves are appended. A consistency proof supplies the intermediate nodes needed to show that the earlier tree is a prefix of the later tree under the specified construction.

RFC 6962 and its successor RFC 9162 define Merkle structures for certificate transparency. They separate inclusion—this leaf is in this tree—from consistency—this later tree extends that earlier tree. The distinction transfers to audit logs, ledgers and versioned manifests.

Consistency still depends on trusted or widely witnessed roots. A server could present two internally consistent histories to different clients if clients never compare signed roots. Gossip, monitors or another publication channel make equivocation detectable. The Merkle proof is a compact mathematical witness, not a complete governance system.

For a private archive, the equivalent may be a root signed by an authorised key, stored in an independent register, or anchored in a write-once audit record. Define who is allowed to publish a root, how keys rotate, and how an old trusted root is retained. Cryptographic structure works best when the operational trust path is explicit.

Contents · Previous chapter · Next chapter

The attached fictional comparison begins with Replica A and Replica B. Their roots differ. The left-half hashes match, so the comparison skips chunks C0–C3. The right-half hashes differ. Within that half, the C6–C7 branch matches while the C4–C5 branch differs. One more comparison shows C4 matches and C5 differs.

This search localises disagreement; it does not identify which replica is correct. Correctness requires a trusted manifest, provenance, signatures, backup history or another source. If A and B both changed in different ways, comparison alone only finds divergence.

After replacing C5, recompute L5 and every ancestor to the root. A matching root verifies that the reconstructed leaf set matches the target construction. Also verify length and tree metadata. A system that compares only branch hashes but ignores trailing data or tree size can miss an incomplete or extended collection.

Local repair should be atomic where possible. Write the replacement chunk, verify its leaf, rebuild the affected path, and only then publish the new root or swap the repaired object into service. Interrupted repair must not leave a manifest claiming a root that the stored chunks do not produce.

Contents · Previous chapter · Next chapter

Content-addressed storage names an object by a digest of its content and often its type. Tree objects can then contain names that point to blobs or other trees. Git’s data model is a familiar example: blobs represent file content, trees represent directory structure, and commits point to trees plus history metadata.

This resembles a Merkle directed acyclic graph more than one simple balanced tree. The same content can be shared across versions because unchanged objects keep the same identifiers. A changed file creates a new blob and changes the ancestor tree and commit objects that refer to it, while unrelated blobs remain reusable.

Do not assume every product using hashes has the same security properties. Object identifiers may use different algorithms and encodings. A repository also needs reference integrity, access control and safe transport. The official Git documentation notes that objects can be checked by matching their names to their content, but that property alone does not say which commit should be trusted.

The practical transfer is to separate identity, structure and authority. The object hash answers “which bytes and type?” The tree answers “which objects and arrangement?” A signed tag, protected reference or reviewed release answers “which named state should we accept?” Merging these questions into one word—integrity—hides important failure modes.

Contents · Previous chapter · Next chapter

Collision resistance makes it difficult to find two different inputs with the same digest. Second-preimage resistance makes it difficult to replace a chosen input with another having the same digest. Real designs also need unambiguous encoding, safe algorithms and implementation correctness.

A Merkle tree does not encrypt content. Leaf hashes may leak equality, and small predictable records can be guessed and hashed. Salting or keyed hashes may be appropriate for privacy, but they change deduplication and verification workflows. Do not publish roots or proofs from sensitive datasets without a threat analysis.

Algorithm agility should be explicit rather than improvised after deprecation. Store the algorithm identifier and tree version with each root. A migration may compute old and new trees over the same canonical leaves, preserve both roots for a transition, and sign the relationship. Never relabel an old digest as though it were produced by a new function.

Trusted roots can be compromised by key theft or administrative error. Keep timestamps, signer identity, revocation or rotation records and independent copies. Cryptography narrows the question from “did anything change?” to “does this data match the state committed by this authority at this time?” It does not make the authority infallible.

Contents · Previous chapter · Next chapter

Design verification around evidence that can be retained. A run record should include object identifier, expected root, observed root, algorithm, tree version, chunking rule, tree size, timestamp, software version and outcome. For a mismatch, keep the path or leaf indices that differed and the repair source.

Sample verification can reduce routine cost, but it cannot establish whole-tree equality unless the proof selection and trusted root support the intended claim. Full root recomputation reads every leaf input. A remote inclusion proof verifies a selected leaf against a root. Say which was performed.

The existing guide to checksums and silent change explains baselines, manifests and fixity. Merkle verification builds on that discipline. If the baseline root was never captured or authenticated, the tree cannot recover the missing provenance.

Test failure handling. A verifier that reports “mismatch” but cannot quarantine, retry, retrieve an independent copy or escalate will accumulate ignored alerts. Define safe states and make the repair path observable. A security control is only as dependable as its response to a negative result.

Contents · Previous chapter · Next chapter

Practice one: two archives have matching roots, but one uses four-mebibyte leaves and the other claims eight-mebibyte leaves. The comparison is invalid unless the constructions are actually equivalent under a documented rule. Matching printed strings without matching metadata is not proof of identical archives.

Practice two: an inclusion proof verifies a course result in a published tree. This proves that the encoded leaf was committed under the trusted root. It does not prove the grade was correctly awarded or that the student identity was encoded accurately. Those are source-data and governance questions.

Practice three: a branch comparison localises a mismatch to C12. Replica A matches last week’s signed root; Replica B has a newer unsigned root and a plausible edit. Do not overwrite automatically. Establish which state is authorised, preserve both, and update the trusted root through the normal release process.

Transfer the tree idea to grouped evidence. Whenever a summary depends hierarchically on many items, ask what each leaf means, whether order matters, and who vouches for the root. Merkle trees make those dependencies efficient and tamper-evident; they do not remove the need to define the evidence.

Contents · Previous chapter · Next chapter

Does a matching Merkle root prove two stores are identical?

It provides strong evidence that the encoded leaves and structure match under the same collision-resistant construction. Confirm algorithm, tree version, leaf definition, order and tree size.

Can a Merkle proof tell me which copy is correct?

No. It shows inclusion or consistency relative to a root. Correctness requires a trusted root and provenance.

Why not use one checksum for the whole file?

Use one when whole-object identity is all you need. A tree is valuable when you need efficient inclusion proofs, comparison, synchronisation or local repair.

Is a Merkle root a digital signature?

No. A root is a hash commitment. Sign it or authenticate it through another trusted channel when authority matters.

Authoritative reading includes RFC 9162, Certificate Transparency Version 2.0, the earlier explanatory construction in RFC 6962, and the official Git data model documentation. Apply the exact specification of the system you operate; Merkle trees are a family of constructions, not one interchangeable file format.

Return to The Gold Standard of Information for the subject map and to digital archiving services for authenticity, findability and long-term access around the cryptographic layer. The next useful move is to write a one-page tree specification: leaf bytes, chunk rule, algorithm, prefixes, order, odd-node rule, root authentication and failure response. If two engineers can independently produce the same root and explain what it commits to, the design is ready for a real test.

Contents · Previous chapter · Return to the Information guide