Knowledge Base

Overview

A Merkle inclusion proof (also called an audit proof) is a short list of hashes that proves one leaf is a member of a Merkle tree with a given root, without revealing or requiring any of the other leaves. Truestamp uses inclusion proofs to show that your data’s hash is one of the leaves committed inside a block. The proof is compact: for a tree with N leaves it contains exactly ceil(log2(N)) hashes, so a proof stays small even when a tree holds millions of leaves. This concept covers what an inclusion proof is, how the audit path is checked, how proving a leaf inside a block establishes a submission window, and the precise set of facts an inclusion proof does and does not establish. For how the tree itself is built (leaf and node hashing, domain separation, ordering), see how the Merkle tree is constructed.

The audit path

An inclusion proof is expressed as an ordered list of sibling hashes. Each step records one hash and which side it sits on, written as a "direction:hash" string. Carrying the side explicitly means a verifier needs nothing but the proof itself: it never has to recover the sides from a leaf index and a tree size.

• direction is l (the sibling is on the left) or r (the sibling is on the right).
• hash is a 64-character lowercase hexadecimal SHA-256 digest.

For example, a two-leaf proof is a single-element list:

["r:5e5caeafc27155c368b6f201107d6f8b270747ce636ac5174a56c6e12ef89ad1"]

The steps are ordered from the bottom of the tree (the leaf’s immediate sibling) up toward the root. Walking the leaf’s position up the tree, at each level the proof records the one sibling hash needed to recompute the parent, so the number of steps equals the tree depth.

Two boundary cases matter:

• A single-leaf tree returns an empty proof [], because the leaf is already the root and no siblings are needed.
• Asking for a key that is not in the tree returns no proof at all (nil in the library), because there is nothing to prove membership of.

The same audit path can also be transmitted in a compact binary form that packs the directions into a bitfield and stores the sibling hashes as raw bytes, for a smaller proof over the wire.

Verifying an inclusion proof

Verification recomputes the root from your leaf and the audit path, then compares the result against the expected root. It never needs any other leaf. The walk is:

1. Start from your data’s hash and compute the leaf hash by prefixing it with the leaf domain byte 0x00 and taking SHA-256.
2. For each audit-path step, combine the running hash with the sibling hash on the recorded side, prefix the pair with the internal-node domain byte 0x01, and take SHA-256. An l step places the sibling on the left (SHA256(0x01 || sibling || running)); an r step places it on the right (SHA256(0x01 || running || sibling)).
3. After the last step, the running hash is the recomputed root. Compare it to the expected root. If they match, the leaf is proven to be a member of that root. Truestamp uses a constant-time comparison here as a matter of habit; both values are public, so nothing is at stake in the timing, but a comparison that decides whether a proof holds is the wrong place to make an exception.

Because the sibling hashes and their sides are fixed, changing your data, a sibling, or a direction changes the recomputed root and the proof fails. The domain-separation prefixes (0x00 for leaves, 0x01 for internal nodes) prevent an internal node from being passed off as a leaf, or vice versa. Those prefixes are described in how the Merkle tree is constructed.

Two limits apply to any proof handed in from outside. One value can never be proved: verification rejects the fixed reserved hash that every padding leaf carries, because a proof presented for it would prove a padding slot rather than a real leaf. That rejection covers the value being proved and nothing else, so the padding leaf’s own hash keeps verifying as an ordinary sibling. Verification also caps a proof at 64 steps, a depth spanning more leaves than any tree that could be built, which bounds the work an untrusted proof can ask for.

A concrete two-leaf example: with leaf hash 2222222222222222222222222222222222222222222222222222222222222222, the audit path ["r:5e5caeafc27155c368b6f201107d6f8b270747ce636ac5174a56c6e12ef89ad1"] recomputes the root 96cfe136315282442cd0133b934dd99622a510c075930239725ced808ce7dfa0.

Proving a submission window

Truestamp builds one Merkle tree per block, so an inclusion proof against a block’s root proves your data’s hash was a leaf committed in that specific block. That single inclusion fact, combined with the public records your submission committed to, is what establishes a submission window.

• The submitted-after edge rests on the witnesses captured at submission: the block then at the head of the ledger, plus the newest observation from each public entropy source that had one. Their hashes are folded into the item’s own fingerprint, and the latest publication time among those records is the edge, so your submission happened after that public moment.
• The submitted-before edge is the block whose Merkle tree contains your leaf. Proving inclusion in that block proves your submission happened before that block was finalized.

Together the two edges pin the submission into a narrow window. The internal window between the two ledger blocks is typically about one minute wide; the edges a stranger confirms rest on the public sources and chains and sit wider. The guarantee is about when your data was submitted, not about when it was first created. For the product-level framing of this window, see the submission window; to run a full check end to end, see how to verify a proof.

What an inclusion proof does and does not establish

An inclusion proof, together with the item’s witnesses and its containing block, establishes a specific and limited set of facts. State these precisely and do not overclaim.

Provable

• Data existence. The data existed, because a matching hash cannot be produced without it.
• Data integrity. The data has not been altered since it was hashed; any change produces a different leaf hash and the proof fails.
• Submission window. The data was submitted within the window between the submitted-after and submitted-before edges. This includes proving it was submitted after the latest public record the item’s fingerprint commits to and before the containing block was finalized, and therefore that the data existed by the time that block was finalized.

Not provable

• Creation time. An inclusion proof cannot show when the data was first created; it may have existed for seconds, years, or centuries before submission.
• Creation lower bound. It cannot show the data did not exist before any given moment.
• Original authorship. Anyone in possession of the data can submit its hash, so inclusion does not prove who authored the data.
• Uniqueness. The same data can be submitted more than once, so inclusion does not prove a single submission.

The rule of thumb: an inclusion proof proves what was submitted and when it was submitted, never when the data was created or who created it. For the broader public statement of these boundaries, see what Truestamp does not prove.

Citations

1. RFC 6962: Certificate Transparency. Source of the leaf and internal-node hashing the verification walk relies on.