Prove that one transaction is committed by a Merkle root
A Bitcoin block header contains one 32-byte Merkle root, not every transaction ID. An inclusion proof supplies the missing path: the transaction ID, its position, the number of leaves and one sibling hash per tree level. Repeating Bitcoin's pairwise hashing should recover the root in the header.
This guide builds that process with Python's standard library and deterministic synthetic transaction IDs. It does not connect to a node, download a block, create a wallet or move bitcoin. The fixture is safe to delete when you finish.
The implementation follows Bitcoin Core 31.1's Merkle code and Merkle tests, checked on 25 September 2026. Bitcoin Core 31.1 was the current stable release when checked. The exercise also uses the byte-order and odd-leaf rules in the Bitcoin developer reference.
The result is deliberately narrow. A valid branch proves that a value is included in one claimed Merkle root. It does not prove that the root belongs to the best chain, that the block satisfies every consensus rule, or that an omitted transaction does not exist.
Prerequisites and expected result
You need Python 3 and a text editor. No package installation or network connection is required. Save the program below as merkle_proof_check.py in a disposable directory, then run:
python3 merkle_proof_check.py
The tested environment used Python 3.12.14. A successful run prints five transactions, a three-hash branch and this root:
3f36159f47fbb33f41a3409375003e64da72078e547525ccae47307ae329bdf1
It then reports True for the intended proof and False after changing the transaction ID, the position or the first sibling. Assertions enforce all four results. If one fails, investigate the implementation or local edits instead of deleting the assertion.
Read the program before running it. It accepts only locally defined strings, uses no file or network input, and writes only to standard output. If you adapt it to parse external data, add strict hexadecimal length checks and resource limits before treating that input as safe.
The complete program
#!/usr/bin/env python3
"""Build and verify a Bitcoin-style Merkle branch using synthetic txids."""
from __future__ import annotations
from hashlib import sha256
def hash256(data: bytes) -> bytes:
return sha256(sha256(data).digest()).digest()
def make_txid(label: str) -> str:
"""Return a display-order txid for a deterministic synthetic transaction label."""
return hash256(label.encode())[::-1].hex()
def internal_hash(display_hex: str) -> bytes:
"""Convert display-order hex to Bitcoin's internal byte order."""
return bytes.fromhex(display_hex)[::-1]
def display_hash(internal: bytes) -> str:
return internal[::-1].hex()
def merkle_root(txids: list[str]) -> str:
if not txids:
raise ValueError("need at least one txid")
level = [internal_hash(txid) for txid in txids]
while len(level) > 1:
if len(level) % 2:
level.append(level[-1])
level = [hash256(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
return display_hash(level[0])
def merkle_branch(txids: list[str], position: int) -> list[str]:
if not 0 <= position < len(txids):
raise IndexError("position outside txid list")
level = [internal_hash(txid) for txid in txids]
branch: list[str] = []
index = position
while len(level) > 1:
if len(level) % 2:
level.append(level[-1])
branch.append(display_hash(level[index ^ 1]))
level = [hash256(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
index //= 2
return branch
def branch_depth(leaf_count: int) -> int:
depth = 0
while leaf_count > 1:
leaf_count = (leaf_count + 1) // 2
depth += 1
return depth
def verify_branch(
txid: str,
branch: list[str],
position: int,
leaf_count: int,
expected_root: str,
) -> bool:
if leaf_count < 1 or not 0 <= position < leaf_count:
return False
if len(branch) != branch_depth(leaf_count):
return False
current = internal_hash(txid)
index = position
for sibling_hex in branch:
sibling = internal_hash(sibling_hex)
current = hash256(sibling + current) if index & 1 else hash256(current + sibling)
index //= 2
return display_hash(current) == expected_root.lower()
def main() -> None:
txids = [make_txid(f"synthetic-tx-{i}") for i in range(5)]
position = 2
root = merkle_root(txids)
branch = merkle_branch(txids, position)
print(f"transactions: {len(txids)}")
print(f"position: {position}")
print(f"txid: {txids[position]}")
print(f"branch_hashes: {len(branch)}")
print(f"merkle_root: {root}")
proof_valid = verify_branch(txids[position], branch, position, len(txids), root)
print(f"proof_valid: {proof_valid}")
wrong_txid = make_txid("different-synthetic-transaction")
wrong_txid_valid = verify_branch(wrong_txid, branch, position, len(txids), root)
wrong_position_valid = verify_branch(
txids[position], branch, position + 1, len(txids), root
)
print(f"wrong_txid_valid: {wrong_txid_valid}")
print(f"wrong_position_valid: {wrong_position_valid}")
changed_branch = branch.copy()
changed_branch[0] = make_txid("different-sibling")
changed_branch_valid = verify_branch(
txids[position], changed_branch, position, len(txids), root
)
print(f"changed_branch_valid: {changed_branch_valid}")
assert proof_valid
assert not wrong_txid_valid
assert not wrong_position_valid
assert not changed_branch_valid
if __name__ == "__main__":
main()
Read the tree from the leaves upward
make_txid creates reproducible 32-byte values by hashing labels. They resemble transaction IDs but do not represent serialized transactions. That separation keeps the exercise about the tree rather than transaction construction.
Bitcoin software normally displays transaction IDs with their bytes reversed from the internal 32-byte hash representation. internal_hash changes display-order hexadecimal into the bytes used for hashing. display_hash changes the final result back. Reversing the hex characters themselves, or reversing after every SHA-256 round, produces a different tree.
hash256 performs SHA-256 twice. Each pair is concatenated in left-to-right order before hashing. When a level contains an odd number of nodes, the last hash is paired with itself. Five leaves therefore become six inputs at the first level, then three parent nodes. The last parent is duplicated at the next level. The tree reaches one root after three rounds.
index ^ 1 selects the sibling. It changes the last bit of the current index: an even left node selects the following right node, while an odd right node selects the preceding left node. Dividing the index by two moves to the parent position for the next round.
The verifier needs the original position because concatenation order matters. If the current node was on the right, the sibling is hashed first. If it was on the left, the current node is hashed first. This is the same index-bit rule exercised by Bitcoin Core's ComputeMerkleRootFromBranch tests.
Check the output
The complete tested output was:
transactions: 5
position: 2
txid: f542a9f5c9bee4f3adbbe12c4f5f36106f56a73fbfdd3dc136741d06afbd13e0
branch_hashes: 3
merkle_root: 3f36159f47fbb33f41a3409375003e64da72078e547525ccae47307ae329bdf1
proof_valid: True
wrong_txid_valid: False
wrong_position_valid: False
changed_branch_valid: False
The source file's SHA-256 was f8819d70829c7630fab0ca93cf34372e79df34085cc92119205a87e0ddc617fa. The captured output's SHA-256 was 1436f36f5a55de88e7814f83e986c64e2903c1499b40fb90867132e5f2a4f182. These hashes let you distinguish this tested fixture from later edits. They do not authenticate code copied from an untrusted page.
Adapt the fixture carefully
To test another synthetic tree, change the labels or leaf count. To verify data from a real block, obtain the ordered transaction IDs, the target position, the total transaction count and the Merkle root from sources you trust. A branch without its position is ambiguous, and a position without the original transaction ordering is not enough.
Do not treat a block explorer response as independent proof of itself. For stronger verification, get the block header and chain context from your own node, then compare the reconstructed root with the header. Full block validation also checks transaction syntax, scripts, amounts, coinbase rules and the relationship to prior blocks. This script checks none of those.
The Bitcoin whitepaper describes using Merkle branches for simplified payment verification. BIP 37 later specified partial Merkle trees for filtered blocks, but also documents an important limit: a dishonest peer can omit matching transactions. Inclusion evidence is not completeness evidence.
Bitcoin Core's implementation also tracks a mutation condition caused by duplicating identical hashes at the end of a level. The historical issue is associated with CVE-2012-2459. The fixture follows the tree calculation but does not expose Core's mutation flag. Do not use it as a replacement for consensus code or as a parser for untrusted blocks.
Troubleshooting
The root is completely different: check byte order first. Convert each displayed transaction ID to internal bytes before hashing, and reverse only the final root for display.
A tree with an even leaf count works but five leaves fail: duplicate the final node at every odd-sized level, not just the original transaction list.
The correct transaction fails: confirm its zero-based position in the original transaction order. Sorting transaction IDs changes the tree.
A changed position still passes: require the total leaf count and expected branch depth. Position bits beyond the tree depth must not be silently ignored.
Real block data does not match: verify that the first transaction is the coinbase transaction, that you used transaction IDs rather than witness transaction IDs, and that no explorer reordered the list.
What this exercise establishes
The program was executed offline with deterministic synthetic inputs. The intended proof passed, and three negative controls failed. No actual block, transaction, node or wallet was used.
That is enough to demonstrate the mechanism: ordered leaves, internal byte order, double SHA-256, odd-node duplication and left-or-right branch placement. It is not enough to claim that a real payment was confirmed. That conclusion requires an authenticated block header, chain context and the validation guarantees you expect from a node.