Knowledge Base

Browse the concepts behind Truestamp. Follow the links between concepts, or search across everything.

Merkle Inclusion Proofs

How a Truestamp inclusion proof, {leaf_index, path, tree_size} of RFC 9162, proves a record hash is a leaf of a block's or an epoch's tree, the walk and its 32-step cap, the committed leaf count, how a submission window follows, and what is and is not provable.

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 at two levels: to show that a subject’s record hash (an item’s item_hash or an entropy observation’s observation_hash) is a leaf of a block’s tree, and that a block’s block_hash is a leaf of an epoch’s tree, whose hash is written to Stellar and Bitcoin. For a tree of N leaves a path holds at most ceil(log2(N)) hashes, so a proof stays small even when a tree holds millions of leaves. This concept covers the proof’s form, how it is checked, how a submission window follows from it, and what 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 proof’s form

An inclusion proof is the inclusion proof of RFC 9162 section 2.1.3: a JSON object with exactly three members.

{"leaf_index": 0, "path": ["5e5caeafc27155c368b6f201107d6f8b270747ce636ac5174a56c6e12ef89ad1"], "tree_size": 2}
  • leaf_index is the leaf’s position in the tree, counted from 0.
  • tree_size is the number of leaves in the tree.
  • path is the list of sibling hashes from the leaf up to the root, each 64 lowercase hexadecimal characters, at most 32 of them.

The path carries no left or right markers. The index and the size fix which side each sibling sits on, and how many siblings the path must hold, so a path of the wrong length is refused before any hash is read.

Two boundary cases matter:

  • A tree with a single leaf gives the proof {"leaf_index": 0, "path": [], "tree_size": 1}: the leaf hash is already the root, and no siblings are needed.
  • Asking for a key the tree does not hold gives no proof at all, because there is nothing to prove membership of.

Every proof Truestamp serves carries each inclusion proof in this form, as its inclusion_proof member: a subject’s into its block, an observation’s into a beacon’s block, and each commitment entry’s into its epoch. Truestamp stores the same proof in a fixed-width binary form, described in Merkle proof encodings.

Verifying an inclusion proof

Verification recomputes the root from the leaf and the path, then compares the result with the root the tree’s record holds. It never needs any other leaf. The walk is RFC 9162 section 2.1.3.2, where each hash is the 32 bytes its hex spells and halving rounds down:

  1. If leaf_index is not below tree_size, or path has more than 32 hashes, fail.
  2. Set fn = leaf_index, sn = tree_size - 1 and r = SHA-256(0x00 || leaf), the leaf hash under the leaf prefix.
  3. For each hash p of path, in order: fail if sn is 0. If fn is odd or fn = sn, set r = SHA-256(0x01 || p || r), the sibling on the left, and then, while fn is even and not 0, halve fn and sn. Otherwise set r = SHA-256(0x01 || r || p), the sibling on the right. Then halve fn and sn once.
  4. After the last hash, fail unless sn is 0. The result is r.

The result must equal the record’s merkle_root, compared in constant time. 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.

Three rules sit around the walk:

  • Start from a recomputed value. The leaf a walk starts from is the hash the verifier computed from the record the proof carries, never a hash the proof declares. A walk from a declared value would accept a genuine hash grafted beside a forged record.
  • Check the size. The walk checks that the path fits the index and the size, not that the size is the tree’s true size: the same path can reach the same root under another size, and the last of three leaves also walks as index 1 of two. So the proof’s tree_size must also equal the leaf_count that the tree’s record holds beside its root, the block record for a block’s tree and the epoch record for an epoch’s. A record whose leaf_count is 0, as every genesis and key-event block’s is, fails every inclusion proof into it.
  • Bound the work. No path may hold more than 32 hashes, enough for a tree of over four billion leaves, which bounds the hashing an untrusted proof can ask for. Truestamp never commits a tree larger than that.

The prefixes 0x00 for leaves and 0x01 for internal nodes prevent an internal node from being passed off as a leaf, or the reverse; they are described in how the Merkle tree is constructed.

A concrete two-leaf example: with leaf hash 2222222222222222222222222222222222222222222222222222222222222222, the proof {"leaf_index": 0, "path": ["5e5caeafc27155c368b6f201107d6f8b270747ce636ac5174a56c6e12ef89ad1"], "tree_size": 2} walks to the root 96cfe136315282442cd0133b934dd99622a510c075930239725ced808ce7dfa0: the leaf is at index 0 of 2, so its sibling sits on the right, and the root is SHA-256(0x01 || SHA-256(0x00 || leaf) || sibling).

Proving a submission window

An inclusion proof against a block’s root proves the subject’s record hash is a leaf of that block. A second inclusion proof, in each of the block’s commitment entries, proves the block’s hash is a leaf of an epoch, and the epoch’s hash is the value a Stellar transaction or a Bitcoin transaction holds. That chain of hashes, combined with the public records an item names, is what establishes a submission window, and a verifier draws both edges from reads it makes during verification:

  • The submitted-before edge rests on the commitments. The subject is in the block, the block is in the epoch, and the epoch’s hash is on a public chain, so the subject was submitted before the Stellar ledger that holds the transaction closed, or before the Bitcoin block that holds it was mined. A verifier reads the ledger’s close time from Stellar, or the median time past of the Bitcoin block 10 above the transaction’s, and takes the earliest it confirmed.
  • The submitted-after edge rests on the witnesses an item named at submission: the newest observation from each public entropy source that had one. Their hashes are part of the item’s own record, so the item depends on their values, and no one could know those values before their sources published them. A verifier reads each one back from its source (the NIST pulse time, the Stellar ledger close time, or the Bitcoin block’s median time past) and takes the latest it confirmed. The block that was the head of Truestamp’s ledger at submission is named too, but gives no edge, since no public source holds its time.

Truestamp’s own records place a submission within about a minute of the block that includes it, but those are records, not edges. The edges a stranger confirms rest on 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 block’s commitments, 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: after the latest public value the item’s record names was published, and before the public transaction that holds its epoch’s hash, and therefore the data existed by then.

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.
  • That it did not exist earlier. 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 9162: Certificate Transparency Version 2.0. Section 2.1.3 defines the inclusion proof and the verification walk above, over the leaf and internal-node hashing of section 2.1.1.
  2. RFC 6962: Certificate Transparency. The original definition of the same Merkle Tree Hash and audit paths.