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 only about 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 between two blocks 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 called the audit path. Each entry records one hash and which side it sits on, written as a "direction:hash" string:

• 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 entries 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 entries 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 entry, 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 entry places the sibling on the left (SHA256(0x01 || sibling || running)); an r entry places it on the right (SHA256(0x01 || running || sibling)).
3. After the last entry, the running hash is the recomputed root. Compare it to the expected root using a constant-time comparison. If they match, the leaf is proven to be a member of that root.

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.

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

Proving a submission window between two blocks

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 two blocks that bracket your submission, is what establishes a submission window.

• A submitted-after block is captured at submission: the head block’s hash at the moment your data was submitted. This proves your submission happened after that block was finalized.
• A submitted-before block 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 blocks bracket the submission into a narrow window, typically about one minute wide. 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 bracketing blocks, 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 blocks. This includes proving it was submitted after the submitted-after block was finalized and before the submitted-before block was finalized, and therefore that the data existed by the time of the submitted-before block.

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. Defines the audit-path (inclusion proof) structure and the leaf and internal-node domain separation that the verification walk relies on.