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_indexis the leaf’s position in the tree, counted from 0.tree_sizeis the number of leaves in the tree.pathis 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:
- If
leaf_indexis not belowtree_size, orpathhas more than 32 hashes, fail. - Set
fn = leaf_index,sn = tree_size - 1andr = SHA-256(0x00 || leaf), the leaf hash under the leaf prefix. - For each hash
pofpath, in order: fail ifsnis 0. Iffnis odd orfn = sn, setr = SHA-256(0x01 || p || r), the sibling on the left, and then, whilefnis even and not 0, halvefnandsn. Otherwise setr = SHA-256(0x01 || r || p), the sibling on the right. Then halvefnandsnonce. - After the last hash, fail unless
snis 0. The result isr.
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_sizemust also equal theleaf_countthat 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 whoseleaf_countis 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
- 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.
- RFC 6962: Certificate Transparency. The original definition of the same Merkle Tree Hash and audit paths.
- An Introduction to Merkle Patricia Trie
- Angela: A Sparse, Distributed, and Highly Concurrent Merkle Tree
- Audit path
- Commitment
- Comprehensive Guide to Merkle Trees, Merkle Proofs, and Merkle Roots
- Design of a Secure Timestamping Service with Minimal Trust Requirement
- How Does OpenTimestamps Work (r/Bitcoin discussion)
- Improving the Efficiency and Reliability of Digital Time-Stamping
- Inclusion proof
- Item Commitment
- Item Commitment vs Block Commitment
- Merkle Proof Encodings
- Merkle root
- Merkle tree
- Merkle tree - Wikipedia
- Merkle Trees in Git and Bitcoin
- Proof Bundle Wire Format
- Ralph Merkle - Wikipedia
- RFC 6962: Certificate Transparency
- Some Aspects of Merkle Tree - DEV Community
- Stuart Haber - Wikipedia
- Submission window
- Submission Window
- The Epoch and Block Commitment
- The First Blockchain or How to Time-Stamp a Digital Document
- The Item Record and Its Hash
- Truestamp's Merkle Tree
- Using Merkle Trees to Efficiently Detect Data Changes
- Verify a Proof
- What Truestamp Proves
- Why and how Bitcoin uses Merkle trees - Applied Mathematics Consulting
- Why do cryptocurrencies use Merkle trees instead of hashing all the data in the block in one go?