DesignFlix 23: How a Merkle Proof Checks One File

How can we check one file in a huge download without downloading everything else?

A checksum seems like a good start. But if there's one checksum for the entire bundle, checking it means having the entire bundle. A Merkle tree gives us another option: verify the file we need using a few extra hashes and a trusted reference.

Let's build a four-file bundle first. The large-scale version uses the same idea, with more levels.

A hash tells us whether bytes changed

Suppose the bundle contains four reports: inventory, orders, payments and a summary. We hash each report's bytes with SHA-256, producing four fixed-size values.

Changing a report changes the input to its hash. A secure cryptographic hash is designed to make it infeasible to find different inputs with the same result. For our check, the important thing is that we compare the exact bytes, including details such as line endings.

These four hashes become the bottom row of our tree. We combine the inventory and order hashes, then the payment and summary hashes. Finally, we combine those two results. The single value at the top is the Merkle root.

Now the root depends on all four reports. If the payment report changes, its hash changes, the right-hand pair changes, and the root changes. We don't need to rebuild unrelated branches when their hashes are already available.

Build a tree with agreed rules

A hash function alone isn't the whole recipe. Both sides also need to agree on record order and how to distinguish a report from a pair of hashes.

This small Python example uses separate prefixes for leaves and branches, following the construction in RFC 6962:

from hashlib import sha256

reports = [b"Inventory", b"Orders", b"Payments", b"Summary"]
leaves = [sha256(b"\x00" + report).digest() for report in reports]

def branch(left, right):
    return sha256(b"\x01" + left + right).digest()

left = branch(leaves[0], leaves[1])
right = branch(leaves[2], leaves[3])
approved_root = branch(left, right)

The prefixes make leaf input and branch input different kinds of thing. The order matters too: putting the right hash before the left hash gives us a different input.

This is one specific tree construction, not a Bitcoin implementation. Real protocols define their own hashing, ordering and treatment of uneven trees. We need to follow the protocol we're verifying, rather than mixing recipes that happen to use the same name.

Verify the payment report without the other reports

Here's where the tree earns its place. We download the payment report, but we don't want the inventory, order or summary files.

To rebuild its route to the root, we need only:

• The hash of its neighbour, the summary report.
• The already-combined hash of the inventory and order reports.
• The position information that tells us which side each hash belongs on.

For our four-report example, those positions are fixed in the code:

def root_from_payment(download, summary_hash, left_hash):
    payment_hash = sha256(b"\x00" + download).digest()
    return branch(left_hash, branch(payment_hash, summary_hash))

assert root_from_payment(b"Payments", leaves[3], left) == approved_root
assert root_from_payment(b"Changed payments", leaves[3], left) != approved_root

The two supplied hashes are the proof. We hash our downloaded file, rebuild the right branch, then combine it with the left branch. Matching the approved root tells us that these bytes fit that tree.

Notice what we didn't need: the other three reports. Their hashes were enough to fill in the parts of the path we couldn't calculate ourselves.

The hashes, chico. They never lie.

Bigger bundles need more levels, not every file

For a balanced binary tree with around a million leaves, a membership proof needs roughly twenty sibling hashes. The number grows with the tree's depth, so doubling the number of files adds about one level.

We still have to hash the file we're checking. Someone also had to read the data to build the tree initially. The saving is in verifying one part later, when transferring and hashing the whole bundle would be wasteful.

That's why the idea is useful in distributed storage and blockchain systems. Bitcoin's simplified payment verification uses a Merkle branch to establish transaction inclusion in a block. Inclusion is one check in that process; it doesn't independently establish every rule needed to accept a transaction or block.

Who gave us the root?

There's a catch that no amount of neat hashing fixes.

If someone changes the report and sends a matching new root, what are we actually verifying?

We're checking membership in their new tree. The calculation can be perfectly correct while the reference is wrong.

Get the approved root through a channel you trust, such as an authenticated publication or a verified signature. Then compare the download and its proof against that reference. A root supplied by the same untrusted party as the file doesn't establish that the bundle is the one you intended to receive.

Try the change for yourself

Run the example, change the payment bytes, and watch the second assertion catch it. Then generate a whole new root for the altered bundle. The altered file will fit that new tree, which makes the trust question much easier to see.

A Merkle tree makes checking a small part of a large dataset practical. Its strongest lesson is the combination of those two requirements: a short proof we can calculate, and an approved root we have a reason to trust.