How does the mechanism work?
Bitcoin’s transaction tree starts from the transaction identifiers in block order. Each identifier is 32 bytes. Concatenate the raw bytes of adjacent identifiers, apply double SHA-256 to each pair, and repeat with the resulting hashes. Do not concatenate the printed hexadecimal strings: text encoding would give different input bytes. Internal byte order must also be consistent with the serialization being used.
The final root occupies 32 bytes in the 80-byte block header. Changing a committed transaction changes its identifier, then the parent on its branch, then the root. The fixed-size root lets the header commit to a transaction list of varying length. It does not store a reversible compressed copy of those transactions.
An inclusion proof supplies the sibling at each level and the left-or-right position needed to combine it with the running hash. Starting with the transaction identifier, calculate each parent until you reach the candidate root. A matching result connects the identifier to that root under the hash assumptions. You still need a reason to trust the header and the chain containing it.
Order matters in the construction. A left sibling and a right sibling are not interchangeable merely because both are hashes of the same width. A proof needs enough position information to reproduce the ordered concatenations. Likewise, verifying that a transaction identifier reaches a root does not tell you the payment’s meaning until you inspect the transaction bytes that produce that identifier. Keep the evidence chain explicit: bytes identify a transaction, a branch connects it to a root, a header commits to that root, and validated chain context establishes inclusion. Skipping a link changes what has actually been proved.
How do the protocol numbers work in an example?
Use an invented block containing four transactions with identifiers A, B, C and D. Each label stands for a full 32-byte value, not the literal letter. Compute P = doubleSHA256(A || B) and Q = doubleSHA256(C || D). Each input pair is 64 bytes. Then compute R = doubleSHA256(P || Q). R is the header’s Merkle root.
To prove inclusion of C, supply D as its right sibling and P as the left sibling of the next level. You calculate Q from C and D, then R from P and Q. The sibling data is 64 bytes in this example, excluding position and transaction data. Supplying all the other transactions is unnecessary for this membership calculation.
If a level has an odd number of hashes, Bitcoin duplicates its last hash for pairing. With A, B and C, the last pair is C || C. That construction needs care because some differently shaped lists can share a root through duplication. Validation includes checks for mutated transaction trees; the root alone does not independently encode every fact about list length.
Common misunderstandings
Membership is not full transaction validity. A proof does not establish that the inputs existed, signatures passed or issuance was within bounds. It shows a relationship to a supplied root. Full block validation answers the wider question.
A proof against an arbitrary header is not proof of confirmation. You must establish the header’s position in a valid accepted history and the work behind that history. A malicious sender can create a perfectly consistent tree for a block that no validating node would accept.
The root cannot reveal an omitted transaction’s contents. If you need to inspect an amount or spending condition, obtain the transaction itself and check its identifier. The proof then connects that inspected object to the commitment, instead of replacing the object with a short label.
Check yourself
For C in the four-transaction example, must the proof include both A and B separately?
Reveal the answer
No. Their parent P is sufficient as the sibling at the upper level. D supplies the sibling at the lower level. You still need the transaction C, positions and the relevant header context.
What does this diagram leave out?
The ordinary transaction Merkle tree uses txids, which exclude witness data for witness transactions. SegWit adds a separate witness commitment mechanism. Keep those commitments distinct when deciding which data a proof actually covers.
In the Bitcoin family
The Bitcoin Ecosystem project describes BitcoinQu1 (BTC1q) as “The Quantum-Secure Ledger”. Its stated purpose is to future-proof Bitcoin’s value proposition against the threat of quantum computing, with supply wording “21 Million”.
Which primary sources define the rules?
Sources: Transaction Merkle tree construction; Odd-leaf handling and mutation detection; Witness commitment.
Source: Bitcoin Ecosystem project descriptions.