Merkle trees and inclusion proofs

The starting question

A shopkeeper receives a batch of four payments. They want a single short value that changes if any of the four is altered, and that later lets them prove a specific payment belongs to the batch. Hashing the concatenation of the whole batch gives the first property but not the second: to prove one payment, you would have to hand over the other three. The Merkle tree gives both.

The concept (this workshop's toy convention)

Rules that every tool in the course applies:

1. Leaf = SHA-256 of the data's text (for example a transaction).
2. Parent node = SHA-256 of the two child digests concatenated as raw bytes, left then right.
3. If a level has an odd number of nodes, the last one is duplicated.
4. Repeat until a single node remains: the Merkle root.

A worked example: four transactions

Texts: tx0:Amina->Bello:20, tx1:Bello->Chantal:5, tx2:Chantal->Didier:12, tx3:Didier->Amina:7. Digests computed with SHA-256, truncated to 8 hex characters for readability:

The symbol ‖ means concatenation. You can recompute every row with the tools: sha256 for leaves, hexhash for nodes (entering the two full digests one after the other).

What the root guarantees

• If one leaf changes by a single bit, its leaf digest changes, then every node on the path up to the root: the root changes (avalanche effect, workshop 104).
• The root also depends on the order of the leaves: swapping tx0 and tx1 gives another root, because L0 ‖ L1 ≠ L1 ‖ L0.
• This assumes SHA-256 is collision resistant: no one currently knows how to produce two different inputs with the same digest.

A case with an odd number of leaves

With three leaves a, b, c: compute N1 = H(La ‖ Lb), then N2 = H(Lc ‖ Lc) (c is duplicated), then the root H(N1 ‖ N2). With five leaves the duplication occurs at two levels. The merkle-explorer tool shows it: enter 5 leaves and watch the copied nodes.

What this does NOT guarantee

The root says nothing about the validity of the data (a transaction can be fraudulent and still sit prettily in the tree), nor about its origin: it is a digest, not a signature. And the duplication rule has a downside, seen in lesson 3.

Recap

• Root = a 32-byte summary of the whole set, sensitive to every bit and to order.
• Leaf = H(data); node = H(left ‖ right); odd level: duplicate the last node.
• The root proves a set's consistency, not its validity.

The starting question

Didier claims: "my payment tx2 is in this batch whose root is 803bff37…". You do not want to download the four transactions. What do you strictly need to be convinced?

The concept

An inclusion proof for a leaf lists, from the leaf up to the root, the sibling of each node on the path: the digest it is combined with at that level. The verifier receives the data and this list, and recomputes the root.

Side rule, used by the tool and by the exercises: at each level, if the current index is even, the sibling is on the right; if odd, on the left. Then the index is halved (rounded down).

A worked example: proving tx2 (index 2)

Tree from lesson 1. Leaf tx2 has index 2, which is even.

1. Level 0: even index 2 → the sibling is on the right: L3 (f62a1b13…). Compute N2 = SHA-256(L2 ‖ L3). New index: 1.
2. Level 1: odd index 1 → the sibling is on the left: N1 (82bcaf46…). Compute SHA-256(N1 ‖ N2). This is the candidate root.

The proof therefore holds only two digests: L3 and N1, i.e. 64 bytes, not the other three transactions. If the result equals the announced root (803bff37…), the proof is accepted.

Why the proof "binds" the leaf

To forge a proof for other data X', you would need to find siblings such that the recomputation yields the same root. If the tree's structure is fixed without ambiguity, that amounts to finding a collision or a preimage of SHA-256, which no one knows how to do. The proof is then binding for this root, at this position.

Your turn

In merkle-explorer, enter four leaves and click the third: the tool shows its proof and verifies it. Then change one character of the leaf in the proof (without touching the announced root): verification fails. Then change one of the siblings: it fails too.

What the proof does NOT guarantee

• The root itself. If an attacker gives you a fake root with consistent fake proofs, everything looks right. The root must come from a trusted source. In Bitcoin it sits in the 80-byte block header, and a light client follows the header chain with the greatest cumulative work (see section 8 of the Bitcoin paper).
• Transaction validity. The proof says "included", not "compliant with the rules": a light client relies on the fact that a block accepted by the network was validated.
• Absence. No proof is not a proof of absence (see lesson 4 for sorted trees).

Recap

• A proof = the siblings along the path; the verifier recomputes the root.
• Even index → sibling on the right; odd → on the left; index ÷ 2 at each level.
• The proof binds data to a root, but the root must already be trustworthy.

The starting question

A block holds 1,000,000 transactions (a course assumption). How many bytes do you need to prove the inclusion of one transaction? A million? A thousand? Fewer?

The concept

At each level of the tree the number of nodes roughly halves. The path from a leaf to the root therefore crosses as many levels as the number of halvings needed to go from n to 1. For n leaves (n ≥ 2), the proof holds

⌈log₂ n⌉ digests

where ⌈ ⌉ means rounding up. Each SHA-256 digest is 32 bytes.

Worked examples

Doubling the number of leaves adds only one digest to the proof. The million leaves are proved with 640 bytes; for comparison, the full million digests weigh 32 MB. This property is what makes light clients possible on a phone with a limited data plan.

Check with 5 leaves: the levels have 5, 3, 2, then 1 nodes: three steps, and ⌈log₂ 5⌉ = 3. ✔ Duplication does not change the formula: it supplies a sibling (a copy) where one is missing.

Your turn

In the tool, enter 8 leaves: you will see proofs of 3 digests. With 5 leaves (levels of 5, 3, 2, then 1 nodes), proofs have 3 as well; for the last leaf, one of the siblings is a copy of itself. The tool stops at 8 leaves: for 9 leaves (levels of 9, 5, 3, 2, then 1 nodes), count by hand: every proof has 4 digests, which the independent lab will check in code.

A downside of the duplication rule

Take three leaves [a, b, c] and four leaves [a, b, c, c]. In the first case, c is duplicated to form N2 = H(Lc ‖ Lc); in the second, c and its copy form the same pair. The two lists give the same root (in the toy convention, d31a37ef… with text leaves "a", "b", "c"). Two different sets, one root: the root alone cannot tell "3 transactions" from "3 transactions whose last one is repeated". Bitcoin applies this same rule of duplicating the last hash, and the flaw gave rise there to a known vulnerability (block malleability, not a theft of funds) that implementations had to handle; for it to work, the duplicate must pass the other validation rules. Protocols that care detect such duplicates or change the convention.

What this does NOT guarantee

"Small" does not mean "free": the verifier must also know the position (or the sides) and the leaf's data. And proving one transaction says nothing about the others. Related ideas (Merkle trees over redundant data) are also used for data availability sampling in some chain designs; that topic is outside this workshop.

Recap

• A proof has ⌈log₂ n⌉ digests of 32 bytes: 20 for a million leaves, i.e. 640 bytes.
• Doubling the set adds one digest, not twice as many.
• With last-node duplication, two different lists can share a root.

The starting question

In our convention, a leaf is SHA-256(data) and a node is SHA-256(left ‖ right). Both are therefore "SHA-256 of something". Can a verifier confuse a leaf with an internal node? If so, what can an attacker do with that?

The attack, step by step

Take the four-transaction tree (lesson 1) and its root R = 803bff37…

An internal node N1 equals SHA-256(L0 ‖ L1). The bytes L0 ‖ L1 are 64 bytes long. An attacker says: "here is a 64-byte piece of data, equal to L0 ‖ L1, it is my leaf; here is my proof: a single sibling, N2, on the right". The verifier applies the rule:

1. leaf = SHA-256(data) = SHA-256(L0 ‖ L1) = N1;
2. candidate root = SHA-256(N1 ‖ N2) = R ✔.

The proof is accepted because the verifier does not check the proof's length (a verifier that fixed the expected depth, two levels for four leaves, would reject a one-level proof), and yet the "leaf" is not a transaction: it is an internal node in disguise, and the proof has one level instead of two. This is a second-preimage attack on the tree (more precisely, a confusion between levels): the attacker broke no hash function; they exploited an ambiguity of structure.

The defence: domain separation

Prefix the two kinds of hashing with a different byte:

• leaf = SHA-256(0x00 ‖ data)
• node = SHA-256(0x01 ‖ left ‖ right)

Thus a value computed as a leaf cannot be mistaken for a node, or the reverse, because the inputs differ from the very first byte. This is the solution used by the certificate transparency protocol (RFC 6962). Other defences are possible: fix the expected depth of the tree, or require leaves of a length other than 64 bytes. Bitcoin's transaction tree does not use these prefixes; the topic is known to researchers and goes beyond this workshop.

What the proof still does not guarantee

• Even with domain separation, a proof establishes inclusion, not absence: to prove that data is not in a set, one can use a tree whose leaves are sorted: you then prove the inclusion of two consecutive neighbours a < x < b, between which x would have to sit. This is the subject of the independent lab.
• A proof holds only for the given root. A root that changes (a new block) requires new proofs.

Your turn

Do the security exercise: you will run the attack with hexhash on real digests.

Recap

• Without separation, a leaf and an internal node are indistinguishable: a node can pass as a leaf.
• A distinct prefix (0x00 / 0x01) removes the ambiguity.
• An inclusion proof never proves absence.