Merkle Trees and Inclusion Proofs in Python From Scratch

A developer demonstrated building a Merkle tree from scratch in Python to generate and verify inclusion proofs for AI retrieval provenance, letting anyone confirm a source document was part of the set a model saw without re-running the pipeline. The implementation uses domain separation with distinct leaf (0x00) and internal node (0x01) prefixes to prevent second-preimage attacks, and promotes lone odd nodes unchanged to the next level. Proofs require only O(log n) sibling hashes, each tagged with its left/right position, so a verifier trusting the root can recompute the path and confirm membership.

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. python 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. python 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: odd node: promote it unchanged 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. php 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 else: promoted odd node, no sibling at this level 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. php 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: php 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 Tamper check: a source that was never retrieved must fail 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.