Merkle trees

A Merkle tree commits to an ordered collection of byte strings. Leaves are hashed, internal nodes hash child commitments, and a root summarizes one precisely defined snapshot.

The tree definition is part of the protocol

There is no universal rule for leaf framing, child order, or an odd number of leaves. The verifier must implement the same construction as the producer.

RFC 6962 uses domain separation:

LeafHash(d) = SHA-256(0x00 || d)
NodeHash(left, right) = SHA-256(0x01 || left || right)

Its recursive split rule does not mean "duplicate the last leaf." Other systems may define another rule, but producer and verifier must pin it.

What a root proves

Given a trusted root, tree size, leaf index, and a valid inclusion path, a verifier can check that a leaf was committed at that position. In a balanced binary tree the proof is logarithmic in the number of leaves. RFC 6962 consistency proofs can show that a newer append-only tree extends an older one.

A root alone does not prove freshness, availability, semantic validity, or who authorized the root. Those require a trusted checkpoint, signature/log policy, and a freshness contract.

Deterministic input contract

Pin all of the following:

• canonical serialization and Unicode/number rules;
• leaf ordering and duplicate handling;
• hash algorithm and domain separation;
• tree shape and odd-leaf rule;
• snapshot/version and partition boundaries.

Hash a frozen snapshot. Concurrent changes after that snapshot belong to a later root; they must not be silently mixed into a proof.

Security and operations

Collision resistance is the integrity assumption. It does not replace authentication of the root. Store the root with algorithm, tree size, schema, and snapshot metadata. Treat proof parsing as untrusted input and bound path length before allocating memory.

Diagram scenarios

The diagram implements the RFC 6962 framing model, inclusion verification, tamper detection, append-only consistency verification, and fail-closed context checks.

Related concept

Interactive scenarios