I kept running into the same question while building AI retrieval systems: how do you prove, after the fact, that a particular source document was actually part of the set the model saw? You want a compact receipt that anyone can check without re-running your whole pipeline. Merkle trees are the classic answer, and once I built one by hand I realized the idea is much simpler than the cryptography reputation suggests.
In this tutorial I will build a Merkle tree from scratch in Python, generate an inclusion proof for a single leaf, and verify that proof standalone. I will use retrieval provenance as the running example, but the technique applies to any situation where you want to commit to a set of items and later prove membership: transaction logs, file backups, certificate transparency, and so on.
A Merkle tree hashes your data in a binary tree. The leaves are hashes of your items. Each internal node is the hash of its two children concatenated. The single hash at the top, the Merkle root, is a fingerprint of the entire set. Change any item, and the root changes.
The magic is the inclusion proof. To prove a leaf is in the tree, you do not need the whole tree. You only need the sibling hashes along the path from that leaf up to the root. That is O(log n) hashes. A verifier who trusts the root can recompute their way up and confirm they arrive at the same root.
Before any code, two things separate a toy Merkle tree from a correct one.
First, domain separation. If you hash leaves and internal nodes the same way, an attacker can present an internal node as if it were a leaf. This is the classic second-preimage weakness. The fix is to prefix a different byte before hashing leaves versus internal nodes. I use 0x00 for leaves and 0x01 for internal nodes.
Second, odd-node handling. When a level has an odd number of nodes, one node has no sibling to pair with. Different systems handle this differently. I promote the lone node unchanged to the next level. This is simple and deterministic, though I will flag a caveat about it later.
Let me start with the two hashing primitives.
import hashlib
LEAF_PREFIX = b"\x00"
NODE_PREFIX = b"\x01"
def hash_leaf(data: bytes) -> bytes:
return hashlib.sha256(LEAF_PREFIX + data).digest()
def hash_node(left: bytes, right: bytes) -> bytes:
return hashlib.sha256(NODE_PREFIX + left + right).digest()
Now the tree. I build it level by level, keeping every level so I can generate proofs later.
class MerkleTree:
def __init__(self, items: list[bytes]):
if not items:
raise ValueError("cannot build a Merkle tree over zero items")
self.leaves = [hash_leaf(item) for item in items]
self.levels = self._build(self.leaves)
def _build(self, leaves: list[bytes]) -> list[list[bytes]]:
levels = [leaves]
current = leaves
while len(current) > 1:
nxt = []
for i in range(0, len(current), 2):
if i + 1 < len(current):
nxt.append(hash_node(current[i], current[i + 1]))
else:
nxt.append(current[i])
levels.append(nxt)
current = nxt
return levels
@property
def root(self) -> bytes:
return self.levels[-1][0]
The levels list holds the leaf hashes at index 0, then each successive parent level, ending with a single-element level that holds the root.
A proof is the list of sibling hashes on the way up, each tagged with whether it sits on the left or right. The verifier needs the side so it concatenates in the correct order.
def proof(self, index: int) -> list[tuple[str, bytes]]:
if not 0 <= index < len(self.leaves):
raise IndexError("leaf index out of range")
path = []
for level in self.levels[:-1]:
is_right_node = index % 2
if is_right_node:
sibling_index = index - 1
path.append(("left", level[sibling_index]))
else:
sibling_index = index + 1
if sibling_index < len(level):
path.append(("right", level[sibling_index]))
index //= 2
return path
When our node is on the right, its sibling is to the left, and vice versa. If our node is a left node at the end of an odd level, it has no sibling and was promoted, so we add nothing for that level. We then move up by halving the index.
This is the part that makes Merkle trees useful. Verification needs only three things: the original item, the proof, and the trusted root. No tree, no other items.
def verify_proof(item: bytes, proof: list[tuple[str, bytes]], root: bytes) -> bool:
computed = hash_leaf(item)
for side, sibling in proof:
if side == "left":
computed = hash_node(sibling, computed)
else:
computed = hash_node(computed, computed if False else sibling)
return computed == root
Let me clean that verify up, since the ternary is noise:
def verify_proof(item: bytes, proof: list[tuple[str, bytes]], root: bytes) -> bool:
computed = hash_leaf(item)
for side, sibling in proof:
if side == "left":
computed = hash_node(sibling, computed)
else:
computed = hash_node(computed, sibling)
return computed == root
The verifier hashes the item as a leaf, then walks the proof, folding in each sibling on the correct side, and checks whether it lands on the root.
Now the concrete use case. Say a RAG system retrieved five source chunks to answer a question. We want a receipt proving that one specific chunk, say the one the answer cited, was in that retrieval set.
sources = [
b"doc:handbook#p12 :: refunds within 30 days",
b"doc:handbook#p13 :: return shipping is prepaid",
b"doc:policy#p4 :: no refunds on final-sale items",
b"doc:faq#q9 :: exchanges allowed within 60 days",
b"doc:handbook#p14 :: store credit never expires",
]
tree = MerkleTree(sources)
root = tree.root # publish or log this as the retrieval commitment
cited_index = 2
cited_source = sources[cited_index]
receipt = tree.proof(cited_index)
print("root:", root.hex())
print("verified:", verify_proof(cited_source, receipt, root))
fake = b"doc:policy#p4 :: refunds on final-sale items are fine"
print("tampered:", verify_proof(fake, receipt, root))
Running this prints verified: True and tampered: False. The tampered line proves the point: flip a single word in the source and the proof no longer reconstructs the root. If you log the root at retrieval time, anyone holding a source and its receipt can later confirm it was genuinely part of that set, without access to your database or the other four chunks. That is exactly the property I wanted for retrieval provenance in my project answerproof.
The odd-node promotion I used is simple, but it is worth knowing its weakness. Because a promoted node is carried up unchanged, a tree over an odd count can, in adversarial constructions, share structure with a differently shaped tree, which is the root of the well known CVE-2012-2459 style ambiguity in some Merkle implementations. For a trusted producer logging its own retrieval sets this is fine. If you need to defend against a malicious tree builder, use a scheme that removes the ambiguity: duplicate the lone node instead of promoting it, or better, prepend the leaf count to what you hash and reject proofs whose length does not match the committed size. Domain separation, which I did include, already blocks the leaf-versus-node confusion, so we are only talking about the shape ambiguity here.
That is a complete, correct Merkle tree in well under a hundred lines: domain-separated leaf and node hashing, level-by-level construction with odd-node promotion, logarithmic inclusion proofs, and standalone verification that needs nothing but the item, the receipt, and the root. The technique is general, but retrieval provenance made it click for me: a tiny receipt that survives long after the pipeline that produced it.
If you want to see this idea wired into a real retrieval-answer flow, the provenance work lives in github.com/AgentPostmortem/answerproof. Clone the snippets above, break something on purpose, and watch the root refuse to lie.