The Tool Desk
Outbyte PC Repair FREERepair Windows errors before they cause bigger problemsFix Now →Outbyte Driver Updater FREEScan for outdated or missing drivers - takes under a minuteDriver Scan →iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
To build and verify an inclusion proof, hash each entry as SHA-256(0x00 || entry), combine child hashes as SHA-256(0x01 || left || right), and use the entry’s zero-based index and total tree size to reconstruct the RFC 9162 tree shape. The code below follows that Certificate Transparency model, including its handling of trees whose leaf count is not a power of two.
What an inclusion proof shows
A Merkle tree commits to an ordered collection of entries with one root hash. An inclusion proof supplies the sibling subtree hashes needed to recompute that root for one entry. It lets a verifier check membership without receiving all the other entries.
A successful check means the entry is consistent with the root the verifier was given. It does not establish who produced that root, whether it is current, or whether a log has preserved its history. Those questions depend on the application’s trust model and, for append-only history, consistency proofs.
Quick wins for a faster PC:
Fix the driver behind crashes, sound loss and screen glitchesFind Drivers →Clear out junk files and repair common Windows errorsFree Scan →What tree definition does this Python example use?
This tutorial uses the Merkle Tree Hash defined in RFC 9162, Certificate Transparency Version 2.0, published by the IETF in December 2021. It uses SHA-256 for the example and treats every entry and digest as bytes. The RFC permits a configured hash function; SHA-256 is the choice here.
#1 Best Overall
- Empty tree:
SHA-256(b""). - Leaf:
SHA-256(b"x00" + entry). - Internal node:
SHA-256(b"x01" + left_hash + right_hash).
The distinct 0x00 and 0x01 prefixes separate leaf hashes from internal-node hashes. The RFC says this domain separation is required for second-preimage resistance. Do not omit the prefixes if you intend to implement this RFC construction.
For a tree with more than one entry, split the ordered list at the largest power of two strictly smaller than its length, recursively hash each side, then hash the two results as a node. This rule defines the shape for any positive leaf count; it does not pad the list to the next power of two.
How do I build a Merkle tree in Python?
The implementation below provides the root calculation and the helper used to choose the RFC split. If your input is text, encode it explicitly, such as with UTF-8, before calling tree_hash. Keep digests as raw bytes; hexadecimal is useful for display but must not be mixed into hash concatenations.
Free tools Windows power users keep installed
One-click scans. No signup required.
import hashlib
def digest(data: bytes) -> bytes:
return hashlib.sha256(data).digest()
def leaf_hash(entry: bytes) -> bytes:
return digest(b"x00" + entry)
def node_hash(left: bytes, right: bytes) -> bytes:
return digest(b"x01" + left + right)
def largest_power_of_two_less_than(n: int) -> int:
"""Return the largest power of two strictly less than n; requires n > 1."""
return 1 << ((n - 1).bit_length() - 1)
def tree_hash(entries: list[bytes]) -> bytes:
if not entries:
return digest(b"")
if len(entries) == 1:
return leaf_hash(entries[0])
k = largest_power_of_two_less_than(len(entries))
return node_hash(tree_hash(entries[:k]), tree_hash(entries[k:]))For example, with five entries the split is four entries on the left and one on the right. The rightmost entry is not paired with a made-up padding leaf. The result differs from roots produced by constructions that pad incomplete levels, so a verifier and tree builder must use the same definition.
This example uses Python’s built-in list[bytes] type-annotation syntax. A production implementation should also define its input serialization, error handling, resource limits, and digest selection for its own application.
How do I generate a Merkle proof?
For an entry at index m in a list of n entries, follow the recursive split containing that entry. At each split, add the hash of the other subtree. The resulting sequence is ordered from the deepest sibling outward, matching the recursive construction.
def inclusion_proof(entries: list[bytes], leaf_index: int) -> list[bytes]:
"""Return sibling subtree hashes for an RFC 9162 inclusion path."""
n = len(entries)
if leaf_index < 0 or leaf_index >= n:
raise ValueError("leaf_index must identify an entry in the tree")
if n == 1:
return []
k = largest_power_of_two_less_than(n)
if leaf_index < k:
proof = inclusion_proof(entries[:k], leaf_index)
proof.append(tree_hash(entries[k:]))
return proof
proof = inclusion_proof(entries[k:], leaf_index - k)
proof.append(tree_hash(entries[:k]))
return proofFor a one-entry tree the proof is empty: the leaf hash is already the root. For other trees, each proof item is a sibling subtree hash, not an original entry. RFC 9162 describes an inclusion proof as the shortest list of additional nodes required to compute the tree hash; see Section 2.1.3 in the RFC 9162 specification.
What’s actually slowing this PC down?
Pick the symptom - the matching free tool is one click away.
How do I verify a Merkle inclusion proof?
The verifier needs the raw entry, its zero-based index, the total tree size, the ordered proof hashes, and the expected root. Index and size are essential: they determine whether each sibling belongs on the left or right under the RFC’s possibly uneven tree shape. Never sort sibling hashes or decide orientation by comparing hash values.
RFC 9162’s verification algorithm tracks the leaf position and the rightmost position in the tree, then consumes proof nodes while updating the running hash. This version mirrors that logic and rejects invalid indices, truncated paths, extra proof nodes, and a result that does not match the expected root.
def verify_inclusion_proof(
entry: bytes,
leaf_index: int,
tree_size: int,
proof: list[bytes],
expected_root: bytes,
) -> bool:
if tree_size <= 0 or leaf_index < 0 or leaf_index >= tree_size:
return False
fn = leaf_index
sn = tree_size - 1
computed = leaf_hash(entry)
proof_pos = 0
while sn > 0:
if proof_pos >= len(proof):
return False
sibling = proof[proof_pos]
proof_pos += 1
if (fn & 1) == 1 or fn == sn:
computed = node_hash(sibling, computed)
while (fn & 1) == 0 and fn != 0:
fn >>= 1
sn >>= 1
else:
computed = node_hash(computed, sibling)
fn >>= 1
sn >>= 1
return proof_pos == len(proof) and computed == expected_rootThe final condition requires both that the path reaches the root (sn == 0) and that every proof item was consumed. A proof with unused trailing hashes is malformed rather than an alternate valid encoding. The index-out-of-range rejection follows RFC 9162’s verifier, which requires failure when the leaf index is greater than or equal to the tree size; see the RFC 9162 inclusion-proof verification procedure.
Putting the pieces together
This small example builds the root, generates a path for the third entry, and verifies it. Python indexes from zero, so index 2 identifies that entry.
entries = [b"record A", b"record B", b"record C", b"record D", b"record E"]
index = 2
root = tree_hash(entries)
proof = inclusion_proof(entries, index)
valid = verify_inclusion_proof(
entry=entries[index],
leaf_index=index,
tree_size=len(entries),
proof=proof,
expected_root=root,
)
print(root.hex())
print(valid) # TrueChanging the entry, index, tree size, proof ordering, or expected root should make verification fail, except where a changed input happens to represent the same bytes or root. The expected root must come from a source your application trusts; this code only checks the cryptographic relationship among its inputs.
Independent reader supportYour contribution helps us test, update, and keep practical guides available for everyone.Boundary cases and common mistakes
- Zero entries: RFC 9162 defines the empty-tree hash as SHA-256 of the empty byte string, but no valid inclusion index exists.
- One entry: the root is the leaf hash, and the inclusion proof is empty.
- Non-power-of-two size: use the largest-power-of-two recursive split. Padding changes the tree definition and root.
- Missing prefixes: omitting or conflating the leaf and node prefixes is not the RFC construction.
- Wrong sibling direction: fold each sibling according to the index-and-size algorithm; hash values themselves do not encode orientation.
- Ambiguous serialization: convert structured records into a well-defined byte representation before hashing. RFC 9162 defines operations on entry byte strings, not your application’s record format.
- Untrusted root: a valid proof only establishes membership relative to the supplied root. Authenticating and assessing that root belongs to the surrounding protocol.
Inclusion proofs are not consistency proofs
An inclusion proof answers whether one entry is under a particular root. A consistency proof answers a different question: whether a later, larger tree preserves the earlier tree’s entries as an unchanged prefix. An inclusion proof alone does not show that a log has not rewritten history.
RFC 6962, the IETF’s June 2013 Certificate Transparency specification, gives a consistency-proof upper bound of ceil(log2(n)) + 1 nodes for a tree of n leaves. That bound is for consistency proofs, not the inclusion path implemented above. Applications concerned with append-only history need to compare tree heads using consistency proofs and their own mechanism for trusting those heads. See the RFC 6962 specification.
How this model differs from other Merkle trees
“Merkle tree” names a broad family, not one universal wire format. Other systems may choose a different tree shape for incomplete levels, omit or change domain-separation prefixes, encode proofs differently, or use another digest. Their proof format cannot be assumed compatible with RFC 9162. A Python project such as pymerkle advertises inclusion and consistency proof support, but its format and behavior should be checked against the particular application and version in use.
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
