How Blockchain Works | Merkle Trees and Small Proofs

A fictional library has eight book-return slips. A reader wants to check whether one particular slip belongs to the collection approved for the day. Sending all eight slips would answer the question, but imagine the collection contained thousands.

The reader’s question is small: is this record connected to that accepted collection? A Merkle tree is a structure that can support this kind of checking with a compact path of fingerprints.

We will build the idea on paper before discussing its use in a blockchain. The library, slips and labels are invented. No real documents or accounts are needed.

Begin by separating the collection from the claim. The whole collection contains many records. The proof concerns one record and a specific summary of that collection. It does not automatically tell the reader everything about every other record.

Contents · Next chapter

Give the eight fictional slips the labels A through H. Imagine applying a cryptographic hash function to each slip’s exact encoded contents. The resulting fingerprints will be our starting values.

A fingerprint is not the book title, the borrower’s identity or a shortened readable version of the slip. It is an output computed from data using a specified method. The digital-fingerprints guide explains why exact input bytes matter.

For this paper exercise, write FA, FB and so on instead of real hash values. These are symbolic teaching labels, not calculated cryptographic outputs.

That choice keeps our attention on the structure. The same idea will work whether a beginner can calculate a hash or not. What matters here is that each starting fingerprint is tied to a particular representation of a particular record.

Contents · Previous chapter · Next chapter

Two people may describe the same book return with different text. One writes “Book 17 returned”; another writes “Returned: book seventeen.” Their meaning can be similar while their bytes differ.

A cryptographic check needs the defined representation, not merely agreement about the sentence’s meaning. Field order, punctuation and encoding can matter according to the construction.

Our fictional library therefore agrees on a format before creating the fingerprints. It does not ask readers to guess which spelling was used.

This is a general checking habit: identify the data format and method alongside the result. A mismatch may come from a wrong record, a different encoding or an incorrect proof. It does not, by itself, identify the cause.

The paper labels hide those details for simplicity. A real implementation cannot leave them undefined, because the verifier must reproduce the required calculations exactly.

Contents · Previous chapter · Next chapter

Place FA beside FB, FC beside FD, FE beside FF and FG beside FH. In our conceptual ordered binary tree, each pair is combined using a defined encoding and hash operation.

Call the resulting parent fingerprints PAB, PCD, PEF and PGH. Each parent depends on its two children. It summarises that pair within this chosen construction.

The word tree describes this branching arrangement. The individual record fingerprints sit at the bottom as leaves. The paired summaries sit above them.

We are not proposing a new cryptographic implementation. Real constructions specify how leaves and internal nodes are distinguished, how inputs are encoded and how pairs are handled. Secure designs cannot rely on an ambiguous instruction such as “just join the strings.”

For a beginner, the important movement is upward: many small fingerprints are combined into fewer fingerprints that depend on the values below.

Contents · Previous chapter · Next chapter

Now combine PAB with PCD to obtain QABCD. Combine PEF with PGH to obtain QEFGH. We have moved from eight starting fingerprints to four parents and then to two higher summaries.

Finally combine QABCD and QEFGH. Call the result R, the root of our fictional tree.

This is not the root of a plant supplying food to its branches. It is the final summary reached by working from the leaves upward. The drawing’s direction is an analogy, not a botanical rule.

The root depends on the records through the defined calculations. If a lower value changes, the values on its path toward the root must be recomputed.

A single root can therefore act as a commitment to a structured collection under the construction’s cryptographic assumptions. It is a compact checkable reference, not a container from which every record can be read.

Contents · Previous chapter · Next chapter

Suppose fictional slip C now says something different. Its fingerprint becomes a different value. The parent combining C and D changes, then the summary combining A through D changes, and finally the root changes.

The right-hand summary for E through H need not be recomputed if those records remain unchanged. This is one reason the tree structure is useful.

Cryptographic hash functions are not magic guarantees that every imaginable pair of inputs has a unique output. Their security relies on relevant properties such as resistance to finding collisions. Our explanation assumes an appropriate construction and hash function.

Do not interpret the symbolic labels as numerical evidence. We have not calculated them. The exercise shows the dependency path: C influences its ancestors. That path is the reason a changed record cannot simply keep the same accepted proof by pretending its old fingerprint still applies.

Contents · Previous chapter · Next chapter

In our ordered tree, the left and right positions matter. Combining FA then FB follows a specified operation; the verifier needs the correct orientation along the path.

Some real constructions use a different convention, such as sorting paired values. That changes what information the proof must supply and which kinds of ordering claims it supports.

Never infer the convention from the tree drawing alone. The construction must define it.

Our library might care about both membership and position. A design that treats the collection as an unordered set may answer membership without preserving the same ordering meaning.

For beginners, write “ordered teaching tree” beside the diagram. This reminds you that the example uses one choice, not a universal rule for all Merkle structures. Knowing which choices are fixed is part of understanding what the resulting proof actually establishes.

Contents · Previous chapter · Next chapter

The reader now has slip C and wants to connect it to root R. They can compute FC from the correctly encoded slip. What other information is needed?

In our eight-leaf ordered tree, supply FD, then PAB, then QEFGH, with the orientation required at each step. First FC combines with FD to rebuild PCD. Then PAB combines with PCD to rebuild QABCD. Finally QABCD combines with QEFGH to rebuild a candidate root.

Compare that candidate with the accepted R. The proof is the path information needed to perform this check.

The reader did not download every slip. They used the target slip and sibling summaries along its route upward.

Keep the word accepted in view. A match matters only relative to the intended root. A proof for a root supplied by an untrusted stranger may describe that stranger’s collection rather than the library’s approved one.

Contents · Previous chapter · Next chapter

At each level, the verifier already has one side of the next pair. It begins with FC. After the first combination it has PCD. After the second it has QABCD.

The proof supplies the missing side at each stage. It does not need to reveal the entire subtree behind that sibling summary to complete this membership check.

Think of the path as a sequence of joins, not a tour through every branch. The goal is to rebuild the relevant root, not reconstruct all the data.

This explains the compactness in our balanced binary example. Eight leaves require three sibling fingerprints on C’s path. The target record and the expected root are separate inputs.

A proof’s exact format depends on the real structure. The conceptual lesson remains useful: a summary of a neighbouring branch can stand in for that branch when calculating the next summary upward.

Contents · Previous chapter · Next chapter

Double our collection from eight leaves to sixteen and keep the same balanced binary arrangement. A leaf’s path gains one additional level. Doubling again adds another level.

This pattern explains why membership paths can be much smaller than the collections they refer to. In a balanced binary tree with a power-of-two leaf count, the number of sibling steps grows with the number of levels rather than with every leaf.

Do not apply that exact count to every structure called a Merkle tree. Different shapes, branching rules and proof formats change the details.

Our paper example is deliberately regular so the relationship is visible. Draw eight leaves, then imagine sixteen. Count levels, not all the boxes.

The advantage is targeted checking: a reader can inspect a particular commitment efficiently. That advantage does not mean the network can dispense with all of the underlying data for every other task.

Contents · Previous chapter · Next chapter

A proof service supplies both a convincing path and a root. The calculation matches. What have we learned?

We have learned that the supplied record and path connect to that supplied root under the specified checking procedure. We have not yet established that the root is the one our task requires.

The fictional library publishes its approved root through an agreed channel. The reader must connect the proof to that reference, including the correct day and collection.

In a blockchain context, that reference might be linked to an accepted block or another authenticated source. The details belong to the particular system.

Write two checks separately: the mathematical path matches; the expected root has the right provenance. Combining them into one vague green tick hides an important boundary. An internally consistent collection can still be the wrong collection for the reader’s question.

Contents · Previous chapter · Next chapter

Suppose the proof for fictional slip C passes against the library’s approved root. It supports inclusion of the encoded record in that committed structure, under the construction’s assumptions.

It does not establish that the book was physically placed on the shelf. It does not prove that the person who wrote the slip was honest. Those are outside facts.

It also does not necessarily establish that C is the only slip with a particular description, unless the construction and additional evidence support such a claim.

The useful beginner sentence is narrow: “This record connects to this authenticated collection summary.”

Narrow does not mean unimportant. A clearly scoped check can be valuable. It becomes misleading when the explanation quietly turns membership evidence into complete evidence of identity, uniqueness, current entitlement or real-world performance. Ask which extra conclusion needs an extra check.

Contents · Previous chapter · Next chapter

The fictional library approves a morning collection, then adds afternoon slips and creates a new root. A proof linked to the morning root can remain valid for that morning collection.

It is not automatically a proof about the afternoon collection. The question has changed because the reference has changed.

A record may remain present in both versions, but the path information can differ as the structure changes. The verifier needs the root and proof appropriate to the intended version.

This is why evidence notes include context. “The proof passed” is incomplete without naming the collection or state it refers to.

Connect this lesson to block explorers and finality. When a root is attached to a block, the block’s network, identity and accepted status matter. Membership checking answers one part of the task; identifying the relevant ledger state answers another.

Contents · Previous chapter · Next chapter

The library proves that slip C is in its approved collection. A reader asks whether another slip, X, is absent. The proof for C does not answer that question.

Non-membership checking requires a suitable structure and evidence. Certain ordered or keyed constructions can support absence proofs, but an ordinary inclusion path for another record is not enough.

The difference is easy to see in the paper example. Showing one returned book does not show every book that was not returned.

Do not reverse a positive result into a negative claim. Nor should a failed inclusion check be treated as definitive absence when the supplied proof may simply be wrong or use another root.

First state the intended claim. Is it membership, position, absence or something else? Then identify the procedure that establishes that claim. Similar-looking fingerprints do not make these different questions interchangeable.

Contents · Previous chapter · Next chapter

The reader verifies C using a few sibling summaries. They still cannot read every other slip from those summaries.

This is not a flaw in the membership proof. It is outside its purpose. A summary useful for checking a path does not supply every original record needed for other work.

Now imagine the library loses the other slips. R may remain, and C’s proof may still be available, but the librarian cannot simply turn R back into the missing collection.

The next guide studies data availability: can participants obtain the data required for their checking task?

Keep the two properties separate. A commitment helps bind data to a reference. Availability concerns access to the needed data. A system may possess a valid compact reference while lacking the information required to reconstruct or examine the larger state.

Contents · Previous chapter · Next chapter

Our fictional proof reveals slip C because the reader starts with it. The sibling fingerprints hide the full text of neighbouring slips, but that does not make the complete interaction a zero-knowledge proof.

What is revealed depends on the target data, public reference, construction and surrounding request. A small proof may expose less than a whole collection while still disclosing information.

If the target record contains an unnecessary personal detail, proving its inclusion does not remove that detail from the reader’s view.

Connect this to the privacy guide: confidentiality is a separate design question. A membership proof and a zero-knowledge proof have different definitions, although systems can combine techniques for particular purposes.

Use the accurate description first. Say which record is shown and which claim is checked. Do not use the word private merely because many other leaves were not sent to the verifier.

Contents · Previous chapter · Next chapter

Draw eight fictional slips labelled A through H. Above them draw four parents, two higher summaries and one root. Use symbolic names only, clearly marked as not calculated hashes.

Circle C and trace its path upward. At each join, underline the sibling information needed: D’s fingerprint, the AB summary and the EFGH summary. Write the orientation of each join.

Then change the description on C. Mark which ancestors would need recalculation. Leave the unaffected right-hand branch alone.

Finally replace the expected root with a morning root from another imaginary collection. Explain why the same path calculation cannot establish membership in whichever collection you choose afterward.

The exercise is complete without code. Its aim is to make dependencies, reference context and the narrow membership claim visible. Real implementations need a precisely defined cryptographic construction, not these teaching labels.

Contents · Previous chapter · Next chapter

A Merkle proof becomes understandable when you keep three questions together. What record is being checked? Which defined path calculation is used? Where did the expected root come from?

Our library story explains why a short path can connect one record to a much larger collection. It also explains why that connection is not a universal certificate of truth.

A correct path needs the right data representation and construction. A useful result needs an authenticated reference in the intended context. A broader real-world claim needs additional evidence.

You can now read an inclusion-proof claim without assuming that the whole dataset was downloaded or that every outside event was verified. That prepares you for data availability, where the question is no longer only “does this path match?” but “can participants obtain the information they need to check and use the system?”

Contents · Previous chapter · Worked situations