Merkle Trees For Digital Record Verification

Merkle Trees Explained: How One Hash Can Verify Thousands of Digital Records

A Merkle tree is a way of combining many hashes into a single hash, called the Merkle root, so that anyone can later prove a specific record was part of the set without seeing the other records. Change one byte in any record and the root changes. That property is why Merkle trees sit underneath Bitcoin, Git, Certificate Transparency logs, and a good number of timestamping systems.

If you only remember one idea from this article, make it this one: the root is a short commitment to everything beneath it. The rest is detail about how that commitment is built and checked.

Start with the problem

Say you have a million records and you want to record, in one tamper-evident place, that they existed in a particular state. The obvious approach is to hash each record and store a million hashes. That works, but it is heavy. You've created a million things to anchor, store, and later compare.

The second obvious approach is to concatenate everything and hash it once. That gives you one small fingerprint, but now proving anything about a single record means handing over all million of them, because the verifier has to recompute the whole thing.

Merkle trees sit between those two. You get one small fingerprint for the whole set, and you can still prove a single record's membership with a handful of hashes.

Building one, one layer at a time

Ralph Merkle described this construction in the late 1970s, and the mechanics are simple enough to do on paper.

Take four files. Hash each one. Those four hashes are the leaves of the tree. Now pair them up: join the first two hashes, hash the result, and you get a parent node. Do the same with the other two. You now have two hashes. Join those and hash once more. That final hash is the Merkle root.

With eight leaves you'd have three layers above them. With a million leaves you'd have about twenty. The tree gets taller very slowly, which is the whole trick.

Real implementations have to decide what to do when the number of leaves is odd. Bitcoin duplicates the last hash and pairs it with itself. Certificate Transparency, as specified in RFC 6962, instead promotes the unpaired node without duplicating it. These are different choices with different consequences, and I'll come back to why that matters.

What a Merkle proof actually is

Here's the part that makes the structure useful for verification.

Suppose you want to prove that file C was one of the four leaves. You don't need to show the verifier files A, B, and D. You give them only the hashes needed to climb from C up to the root: the hash of D (C's sibling), and the combined hash of A and B (the sibling one level up). The verifier hashes C, combines it with D's hash, combines that result with the A+B hash, and checks whether the answer equals the published root.

If it matches, C was in the tree. If anything along the way was altered, it won't.

This is usually called an inclusion proof or audit path. Its length grows with the logarithm of the number of leaves. For a tree of about a million records, the proof is roughly twenty hashes. With SHA-256, each hash is 32 bytes, so that is around 640 bytes to prove membership in a set of a million. The verifier never sees the other records, only hashes of them.

Why timestamping systems like this structure

For timestamping, the expensive and trust-critical step is anchoring: writing something to a blockchain or another hard-to-rewrite record. Anchoring one hash costs the same as anchoring a million if those million are folded into one root.

This is the design behind several well-known timestamping systems. OpenTimestamps, for example, aggregates many submitted hashes into a Merkle tree and commits the root to Bitcoin. Individual users then hold a proof that links their hash up to that anchored root.

The record on the chain says, in effect, "this root existed by this time." Your proof says, "my hash is under that root." Put together, they support the claim that your hash existed at or before that time. Note the careful wording, because it matters for the next section.

What a Merkle proof cannot tell you

A Merkle proof shows that a particular hash was included in a particular set. That is all it shows. It does not tell you:

* who created the file, or who submitted the hash

* whether the content is original or lawfully held

* whether the file was true, accurate, or authentic when it was hashed

* that any court will treat the record in any particular way

Garbage in, garbage out applies. If someone hashes a forged document, the tree will faithfully commit to the forged document. What the structure gives you is integrity and ordering evidence: this exact content, no later than this time. Questions about authorship, ownership, and legal weight are separate, depend on jurisdiction, and need other evidence and, often, legal advice.

Where careless implementations go wrong

Two implementation details show up in the real world more often than people expect.

The first is leaf and node ambiguity. If leaves and internal nodes are hashed the same way, an attacker may be able to present an internal node as if it were a leaf, which is a form of second-preimage attack. RFC 6962 handles this with domain separation: leaves are hashed with a 0x00 prefix and internal nodes with a 0x01 prefix, so the two can never be confused.

The second is the odd-leaf duplication that Bitcoin uses. Duplicating the last node means two different lists of transactions can produce the same root, a weakness that was documented in Bitcoin as CVE-2012-2459. It didn't allow theft, but it showed that "just duplicate the last one" has side effects. It's a good reminder that a Merkle tree is a family of designs, not a single standard.

If you're evaluating any service that claims Merkle-based verification, ask which construction it uses and whether it's documented.

Merkle trees in everyday tools

You've probably relied on this structure without noticing. Git identifies content with hash trees, so a change anywhere in a repository changes the top-level identifier. Certificate Transparency logs use Merkle trees so that anyone can check a certificate was logged and that the log has only been appended to. Bitcoin uses a Merkle root in each block header so lightweight clients can verify a transaction without downloading the full block.

Different goals, same underlying idea: make a large body of data checkable through one short value.

How this connects to Certelo?

Certelo's core flow is built on the same primitive. The file stays on your device, and Certelo calculates its SHA-256 hash locally. That hash is then anchored to the Electra Protocol blockchain, which gives you a record you can later check against the original file, the hash, or the certificate details.

Checking a record yourself

Whatever system issued it, the verification routine for a Merkle-based record looks like this:

1- Take the original file and compute its hash with the same algorithm the system used (SHA-256 in Certelo's case). If the hash differs even slightly, the file isn't the one that was recorded.

2- If an inclusion proof exists, combine your hash with the first sibling hash from the proof, hash the result, and repeat up the list.

3- Compare the final value with the Merkle root recorded on the blockchain.

4- Confirm the blockchain record itself, including its time, through a public explorer or node rather than trusting a screenshot.

The point of step 4 is that you shouldn't need to take anyone's word for it, including the service that issued the proof.

Frequently asked questions

What is a Merkle root?

The single hash at the top of a Merkle tree, produced by repeatedly hashing pairs of hashes. It commits to every leaf beneath it, so any change to any leaf produces a different root.

How long is a Merkle proof?

It grows with the logarithm of the number of leaves. For roughly a million leaves, about twenty hashes are needed, which with SHA-256 is around 640 bytes.

Can a Merkle tree prove who created a file?

No. It proves a hash was included in a set. Authorship and ownership need separate evidence.

What happens if one file in the tree is modified?

Its hash changes, which changes every hash on the path to the root. A proof built for the original file will no longer verify against the recorded root.

Do I need to upload my file to verify a Merkle proof?

Not in principle. Verification needs only the file's hash and the proof's sibling hashes. With Certelo, the original file stays on your device and the hash is computed locally.

Is a Merkle tree the same as a blockchain?

No. A Merkle tree is a data structure. A blockchain is a ledger that often uses Merkle trees inside its blocks. Timestamping services also use them to fold many records into one anchored value.