Outdated Drivers Are Slowing You Down
One free scan finds every outdated or missing driver and matches the right update for your exact hardware.Free scan · exact hardware matchWindows Errors? Fix Them Before They Spread
Repair common Windows errors and clear accumulated junk for a smoother, more stable PC - no reinstall needed.Free scan · no reinstallTo build and verify a Merkle inclusion proof, hash each entry as a leaf, combine sibling hashes up to a known root, and use the leaf’s index and total tree size to preserve the tree’s exact shape. This tutorial implements the Certificate Transparency construction defined by RFC 9162: SHA-256, a 0x00 leaf prefix, a 0x01 internal-node prefix, and recursive splits that do not pad the tree.
What a Merkle inclusion proof establishes
A Merkle tree commits to an ordered collection of entries with one root hash. An inclusion proof is an ordered sequence of sibling subtree hashes: together with the entry, its zero-based index, and the tree size, those hashes let a verifier recompute the root without receiving every entry.
As an Amazon Associate I earn from qualifying purchases.
If the recomputed root matches an expected root, the entry is included relative to that root. The hash check does not establish who produced the root or whether it is current or trustworthy; the surrounding application must authenticate the root.
The implementation below follows RFC 9162’s Certificate Transparency tree. Merkle trees used by other systems may differ in tree shape, hash prefixes, digest choice, and proof format, so proofs are not automatically interchangeable.
#1 Best Overall
How RFC 9162 defines the tree
Inputs and hashes are byte strings. Let HASH be SHA-256 and || denote byte concatenation. The empty tree hash is HASH(b""); a single entry d has hash HASH(0x00 || d). For more than one entry, split the ordered list at the largest power of two strictly smaller than its length. The root is the hash of 0x01 followed by the left and right subtree hashes.
The distinct leaf and internal-node prefixes provide domain separation. The recursive split gives a defined shape for any positive number of entries; it does not pad an incomplete level to a power of two. RFC 9162 states that the prefix distinction is required for second-preimage resistance. See RFC 9162.
How do I build a Merkle tree in Python?
This recursive implementation makes the split rule explicit. It accepts a list of byte strings and returns the root digest as raw bytes.
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:
# Precondition: 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 text entries, encode them before hashing; for example, use text.encode("utf-8"). For structured records, define a stable serialization first. Do not concatenate hexadecimal display strings where raw digest bytes are required. This example fixes SHA-256 for clarity; a production API should document its digest, input encoding, errors, and resource limits.
How do I generate a Merkle proof?
At each recursive split, follow the subtree containing the target index and add the hash of the other subtree. The function below returns sibling hashes in bottom-up order, which is the order consumed by the verifier.
def inclusion_proof(entries: list[bytes], index: int) -> list[bytes]:
n = len(entries)
if n == 0 or index < 0 or index >= n:
raise ValueError("index must refer to an entry in a non-empty tree")
if n == 1:
return []
k = largest_power_of_two_less_than(n)
if index < k:
proof = inclusion_proof(entries[:k], index)
proof.append(tree_hash(entries[k:]))
return proof
proof = inclusion_proof(entries[k:], index - k)
proof.append(tree_hash(entries[:k]))
return proofThe one-entry tree has an empty proof because its leaf hash is already the root. In a larger tree, the proof contains only the missing sibling subtree hashes, not the other original entries. RFC 9162 describes an inclusion proof as the shortest list of additional nodes needed to compute the tree hash.
How do I verify a Merkle inclusion proof?
The verifier needs the raw entry bytes, zero-based leaf index, total tree size, ordered proof hashes, and expected root. Orientation cannot be determined by sorting hashes or assuming every level is a complete binary tree. RFC 9162’s verification algorithm uses both the index and tree size to decide whether each sibling is on the left or right.
The Tool Desk
Outbyte Driver Updater FREEScan for outdated or missing drivers - takes under a minuteDriver Scan →Outbyte PC Repair FREERepair Windows errors before they cause bigger problemsFix Now →def verify_inclusion(
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
root = 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:
root = node_hash(sibling, root)
while (fn & 1) == 0 and fn != 0:
fn >>= 1
sn >>= 1
else:
root = node_hash(root, sibling)
fn >>= 1
sn >>= 1
return sn == 0 and proof_pos == len(proof) and root == expected_rootExample use with an odd number of entries:
entries = [b"alpha", b"bravo", b"charlie", b"delta", b"echo"]
index = 3
root = tree_hash(entries)
proof = inclusion_proof(entries, index)
assert verify_inclusion(
entries[index], index, len(entries), proof, root
)The verifier rejects an out-of-range index, a missing proof element, and unused extra elements. It also requires the path to finish at the root. Proof elements are raw digest bytes; a serialized network or API format may encode them differently, but that encoding must be decoded consistently before verification.
Independent reader supportYour contribution helps us test, update, and keep practical guides available for everyone.Boundary cases and common mistakes
- Empty tree: RFC 9162 defines its tree hash as
HASH(b""), but there is no entry index for an inclusion proof. - One entry: the root is its prefixed leaf hash and the proof is empty.
- Non-power-of-two size: apply the RFC’s largest-power-of-two split at each recursive call. Padding changes the tree definition and root.
- Wrong sibling order: use the index and tree size to recover left/right orientation; an incorrectly oriented hash produces a different root.
- Missing or conflated prefixes: this departs from the RFC construction and changes its hash inputs.
- Ambiguous entry bytes: choose a deterministic encoding for strings or structured records before hashing.
- Untrusted root: a successful comparison only proves agreement with the supplied root; it does not authenticate that root.
Inclusion proofs are not consistency proofs
An inclusion proof answers whether one entry belongs under one tree root. A consistency proof answers a different question: whether a later tree preserves an earlier tree’s entries as a prefix. RFC 6962 (June 2013) gives an upper bound of ceil(log2(n)) + 1 proof nodes for a consistency proof for a tree of n leaves. See RFC 6962.
To assess whether a log has rewritten history, inclusion alone is insufficient: tree heads must be compared with consistency proofs and the deployment’s trust mechanism. RFC 9162 also specifies consistency proofs for Certificate Transparency.
Quick Recap
Adapting the example safely
- Keep the entry ordering fixed; changing it changes the root and the index-to-path relationship.
- Document the hash function and byte encoding as part of the data format, not as an invisible implementation detail.
- Obtain and authenticate the expected root through the application’s trust model before treating inclusion as meaningful.
- Do not assume another library or protocol uses RFC 9162’s prefixes, recursive shape, proof ordering, or consistency semantics. The pymerkle project is one Python implementation to explore, not proof that its format matches every other system.
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.
Free tools Windows power users keep installed
One-click scans. No signup required.
