Merkle Tree: One Hash Vouches for All the Data

A Merkle tree is a tree-shaped summary of a collection of data blocks. Instead of comparing every block individually or sending the complete collection to a verifier, the blocks are hashed, those hashes are combined in pairs, and the process continues upward until one hash remains: the root hash.

That single root is a compact summary of the entire collection. If one data block changes, the hash on its path to the root changes, and the root changes as well. This gives a practical way to detect edits, compare replicas, and prove that a particular block belongs to a larger collection.

The central construction is simple:

1. Start with the data blocks.
2. Hash each block to create the leaf values.
3. Combine neighboring hashes in pairs.
4. Hash each pair to create the next tree level.
5. Continue until one root hash remains.

A Merkle tree is valuable because it preserves both a summary and a path. The root summarizes all the data, while the path from an individual block to the root provides evidence about that block.

The four-block example​

Consider four data blocks:

A    B    C    D

Let the hash function be $H$. The four leaves are the hashes of the blocks:

h(A)    h(B)    h(C)    h(D)

The first pair, A and B, produces one parent. The second pair, C and D, produces another:

P = hash(h(A) || h(B))
Q = hash(h(C) || h(D))

The two parent values are then combined to produce the root:

R = hash(P || Q)

The complete shape is:

             R
           /   \
          P     Q
        /  \   /  \
     h(A) h(B) h(C) h(D)

Using mathematical notation, the root is

where

and each leaf is the hash of its corresponding data block.

The symbol $\\mathbin{||}$ means that two values are joined in an agreed order before the result is hashed. It does not mean ordinary arithmetic addition. The order matters: the left child is combined first and the right child second.

This four-leaf tree has three levels:

• The leaf level contains the four block hashes.
• The parent level contains the summaries for A, B and C, D.
• The root level contains one summary for all four blocks.

The same pattern extends to larger collections. A root summarizes two subtrees, each subtree summarizes two smaller subtrees, and so on until the leaves represent individual blocks.

What the root represents​

The root is not the original data, and it is not a container that stores every block in readable form. It is a value calculated from the data through repeated hashing. A person who knows only the root does not automatically possess all of the blocks.

Instead, the root provides a reference value. Another party can calculate a root from its own copy of the collection and compare the two roots. A verifier can also calculate a root from one target block and a set of sibling hashes, then compare the result with an expected root.

Suppose one copy contains blocks A, B, C, and D. A second copy computes its own tree. If both roots match, their Merkle summaries match. If the roots differ, some part of the input produced a different result somewhere in the hierarchy.

The root therefore has two closely related roles:

• It summarizes the whole collection with one compact value.
• It provides the endpoint of paths used to locate differences or verify membership.

The root is especially useful when two parties need to compare large collections. They can begin with the small root values and inspect lower levels only when the roots differ.

The Merkle-tree invariant​

A useful way to understand the structure is through its invariant. Every internal node is determined by its two child values. For a binary tree, the rule is

This rule applies at every internal node. The root is obtained by applying it repeatedly from the leaves upward.

Informally:

Every internal node stores the hash of its ordered pair of child values, and the root is the result of applying that rule throughout the tree.

This invariant explains both updates and proofs. If one leaf changes, every ancestor that depends on that leaf must be recalculated. If a verifier knows a target leaf and the sibling at every level, it can recalculate each ancestor until it reaches the root.

For the four-block example, the dependency path for A is:

A -> h(A) -> P -> R

The path for C is:

C -> h(C) -> Q -> R

A node outside the selected path does not need to be recalculated when the selected block changes. It may be needed as a sibling value, but its own stored value remains unchanged.

This local-path property is the central structural advantage of a Merkle tree. The root depends on every leaf, but an update can still be performed by recomputing only the changed leaf and its ancestors.

Why one edit changes one path​

Assume that block B is edited and becomes B'. The leaf hash changes from h(B) to h(B'). Because the parent P depends on both children, it must be recomputed:

The right parent Q summarizes C and D, which were not edited, so it remains unchanged. The root is then recomputed using the new left parent and the unchanged right parent:

The update path is therefore

B -> h(B) -> P -> R

Only the leaf for B, its parent P, and the root receive new values. The subtree containing C and D does not need to be rebuilt.

For a balanced binary tree with $n$ leaves, the height is proportional to $\\log_2 n$. The number of nodes on one root-to-leaf path is therefore also proportional to $\\log n$.

The work needed to recompute the Merkle summary after one leaf edit is

assuming the changed leaf and the existing tree structure are already available.

This complexity statement applies to updating the Merkle-tree summary. It does not claim that every underlying storage system can edit the original data in logarithmic time. The data may have its own storage costs. The statement is that the hash summary can be updated along one path rather than by recomputing every subtree.

Reading the tree from the root downward​

The root can be viewed as a summary of the entire collection. Its left and right children summarize two groups of blocks. Each child then divides its group into smaller groups.

For four blocks, the root represents this partition:

root
├── blocks A and B
└── blocks C and D

The left child divides its group into A and B, while the right child divides its group into C and D.

This recursive partitioning gives each internal node a concrete meaning. The root summarizes the whole range. The left parent summarizes the first half, and the right parent summarizes the second half. At the next level, each parent summarizes a smaller range.

A downward traversal can ask questions such as:

• Does the left subtree match the corresponding subtree in another copy?
• Does the right subtree match?
• Which subtree contains a difference?
• Which sibling summary is needed to verify a target block?

An upward traversal recalculates parent values after a child changes. These two traversal directions support the main operations of a Merkle tree: reconciliation and membership verification.

Comparing two copies from the root​

Suppose two replicas each store the same logical collection. The first replica computes root R1, and the second computes root R2.

If the roots are equal, the two root summaries match:

R1 == R2

If the roots differ, the replicas have different summaries and the comparison must continue into the tree:

R1 != R2

The comparison procedure follows the tree hierarchy:

1. Compare the two roots.
2. If they differ, compare the corresponding left children.
3. Compare the corresponding right children.
4. Follow the child or children whose values differ.
5. Continue until reaching the leaf or leaves associated with the changed block or blocks.

Suppose only B differs between the replicas. The comparison can be visualized as follows:

                 roots differ
                /            \
       left parents differ   right parents match
              /
       A branches match
       B branches differ

The right subtree can stop being explored after its corresponding summaries match. The differing branch is the one that contains the edit.

Step-by-step comparison​

Imagine that replica one contains

A, B, C, D

while replica two contains

A, B', C, D

The leaf hashes for A, C, and D match. The hash for B does not. Consequently:

• The parent summarizing A and B differs.
• The parent summarizing C and D matches.
• The root differs because one of its children differs.

The dependency chain is

The comparison begins with the global summaries and narrows toward the local difference. Matching subtrees can be skipped, while differing subtrees are inspected further.

For a balanced tree with $n$ leaves, following one differing branch requires $O(\\log n)$ levels. If many blocks or regions differ, the total work depends on how many differing branches must be visited. The logarithmic behavior describes the cost of following one path, not necessarily the cost of discovering every difference in a heavily divergent collection.

Replica reconciliation​

Replica reconciliation is the process of helping two copies determine whether they agree and, when they do not, identify the regions that need attention. A Merkle tree supports reconciliation by giving every subtree its own summary.

The root is the first and smallest comparison. If the roots match, the replicas have matching root summaries and no deeper comparison is needed. If the roots differ, the parties compare child summaries. A matching child represents a matching region, while a differing child identifies a region requiring further inspection.

For the four-block tree, the process can be represented as follows:

                 compare root
                 /           \
       compare left pair   compare right pair
          /       \             /       \
       A pair    B pair      C pair    D pair

The labels describe the comparison process rather than additional nodes in the actual tree. The actual nodes contain hash values, and each comparison checks whether corresponding values match.

If only B differs, the left branch eventually exposes that difference. The right branch matches and can be treated as reconciled without comparing C and D individually. For a larger collection, the same process recursively skips matching regions and descends only into differing regions.

This hierarchical behavior is more useful than comparing only a flat list of hashes. A flat list may show that something changed, but the tree groups leaves into progressively smaller regions. Each internal node gives the comparison process a meaningful boundary.

It is important not to overstate the complexity. If one branch differs, a balanced tree offers an $O(\\log n)$ path to that difference. If many branches differ, reconciliation may need to visit many branches. Its total work depends on both tree height and the number and arrangement of differences.

Membership proofs​

A Merkle tree can also prove that a particular block belongs to the collection represented by a known root. The proof does not need to include every leaf. It includes the target block and the sibling hash at each level on the path from that block to the root.

Suppose the target block is B. In the four-block tree, the verifier needs:

• The block B, or its leaf hash h(B).
• The sibling leaf hash h(A).
• The sibling parent hash Q, which summarizes C and D.
• The positional information needed to determine whether the target is the left or right child at each level.

Because B is the right child of P, the verifier first computes

The verifier then combines P, which is the left child of the root, with its sibling Q:

If the calculated root equals the expected root, the supplied path is consistent with that root.

The proof contains one sibling hash for each level on the target's path. A balanced binary tree with $n$ leaves has height proportional to $\\log_2 n$, so the proof uses

sibling hashes rather than all $n$ leaf values.

The proof path for B​

The target path is

B -> h(B) -> P -> R

The sibling values encountered while moving upward are

h(A), Q

The verifier reconstructs the path as follows:

P = hash(h(A) || h(B))
R = hash(P || Q)

The notation in this code block represents ordered hash combination. The plus sign should not be interpreted as numeric addition if a different diagram uses one as a visual abbreviation.

The verifier does not need the separate values of C and D when it already has Q. The single value Q summarizes that entire sibling subtree. This is the compression effect of the Merkle proof: one sibling summary can stand in for a large region of the collection.

Why sibling hashes are enough​

At every level of a binary tree, the target node has exactly one sibling. If the verifier knows the target value and the sibling value, and knows their left-right order, it can calculate their parent.

For the four-leaf tree, the target path has two levels above the leaf. Therefore, two sibling values are enough to rebuild the root. For a larger balanced tree, the path has more levels, but the number of siblings grows with the height rather than with the total number of leaves.

The proof is therefore a path certificate. At every level, it supplies the missing neighbor needed to calculate the next parent. The verifier starts with the target block, hashes it, combines it with the first sibling, and continues upward.

If the tree height is $h$, verification requires approximately $h$ parent calculations:

for a balanced tree with $n$ leaves.

The proof does not reproduce the entire collection. It provides just enough information to reconstruct the target's path to the known root.

Building the tree​

If there are $n$ leaf blocks, the first level hashes $n$ blocks. The next level combines approximately $n/2$ pairs. The level after that combines approximately $n/4$ pairs, and the process continues until one root remains.

The amount of work is represented by the geometric series

This series is bounded by a constant multiple of $n$, so building the complete tree takes

hashing and combination work.

The exact construction for a number of leaves that is not a power of two requires a convention for handling an unpaired value or an incomplete level. The four-block example avoids this issue because every level pairs evenly:

(A, B) and (C, D)

A producer and a verifier must use the same convention. Otherwise, they may group the leaves differently and calculate different roots even when they begin with the same blocks.

Complexity summary​

The principal operations are related because they follow the tree's height.

Complete construction​

Building a tree from $n$ blocks processes all leaves and internal nodes:

One-block update​

Changing one block recalculates its leaf hash and one ancestor at each level:

for a balanced tree.

One differing branch​

Following one differing branch from the root to a leaf requires one step per level:

If several regions differ, reconciliation may need to follow several branches.

Membership proof​

A proof contains one sibling value per level, and verification recomputes one parent per level:

These bounds explain why a Merkle tree remains useful when the represented collection becomes large. The complete data set may contain many blocks, but one root-to-leaf path remains comparatively short in a balanced tree.

The importance of ordering​

The parent calculation uses an ordered pair:

The following two calculations are structurally different:

hash(left || right)
hash(right || left)

When producing or verifying a membership proof, the verifier must know whether the target is the left or right child at each level. A sibling hash without positional information may not be enough to reconstruct the correct parent.

In the four-block tree, B is the right child of P, so h(A) must be placed before h(B) when calculating P. At the next level, P is the left child of the root, so P must be placed before Q when calculating R.

The path for B includes both facts:

B is right child at the first level
P is left child at the second level

The tree invariant therefore includes ordered placement, not only the set of child values. Changing the order changes the input to the hash function and can change the parent and root.

One root and many local summaries​

It is tempting to think of a Merkle tree as only a mechanism for producing one final hash. That view misses the role of the internal nodes. Every internal node is itself a summary of a subtree.

In the four-block example:

• h(A) summarizes block A.
• h(B) summarizes block B.
• P summarizes the pair A, B.
• h(C) summarizes block C.
• h(D) summarizes block D.
• Q summarizes the pair C, D.
• R summarizes all four blocks.

Because every subtree has a summary, two replicas can compare progressively smaller regions. The root is simply the topmost summary in a hierarchy of summaries.

This hierarchy is what makes a single changed block traceable. A single final hash can reveal that the overall summary changed, but it does not by itself provide intermediate regions to compare. The internal nodes provide those regions and make it possible to descend toward a changed block.

A complete edit-and-proof walkthrough​

Start with the original collection:

A, B, C, D

Its tree is

             R
           /   \
          P     Q
        /  \   /  \
     h(A) h(B) h(C) h(D)

Now replace B with B'. The new tree retains the unchanged values for A, C, and D:

             R'
           /    \
          P'     Q
        /   \   /  \
     h(A) h(B') h(C) h(D)

The changed values are the new leaf h(B'), its parent P', and the new root R'. The right subtree Q is reused because the data under it did not change.

The update calculations are

and

Now imagine proving that B' belongs to the collection represented by R'. The proof supplies B', the sibling leaf hash h(A), and the sibling subtree summary Q.

The verifier calculates the leaf hash and then rebuilds the path:

h(B') = hash(B')
P' = hash(h(A) || h(B'))
R' = hash(P' || Q)

If the calculated value equals the expected new root, the path is consistent with that root. The same tree structure that made the update local also made the membership proof short.

Practical limitations and assumptions​

The logarithmic statements rely on a balanced binary shape. A balanced tree has height proportional to $\\log n$. If the structure became a long chain, its height could approach $n$, and path-based operations would lose their logarithmic behavior.

The parties must also agree on the tree construction rules. These rules include at least the grouping of leaves, the order of left and right children, and the treatment of a collection whose size does not produce complete pairs at every level.

The four-block example is straightforward because the leaves pair evenly:

(A, B) and (C, D)

For another collection size, the construction must specify what happens to an unpaired block or incomplete level. The exact rule is part of the definition of that Merkle tree. A verifier using a different rule may calculate a different root from the same data.

A membership proof also needs enough positional information to reconstruct left-right ordering. A list of sibling values without their positions may be insufficient when the target alternates between left-child and right-child positions along its path.

Finally, a root is a summary, not a replacement for the original data. It helps another party compare or verify a block, but a party that needs the block must still obtain the block itself or receive it as part of the proof process.

Merkle trees and Bitcoin light wallets​

The supplied description identifies Bitcoin light wallets as a use case for Merkle trees. The reason follows directly from the membership-proof property. A light wallet can work with a root and a path of sibling hashes instead of receiving every block represented by the tree.

The basic pattern is:

1. A root summarizes a larger collection.
2. A particular block is supplied with sibling hashes.
3. The wallet recomputes the path upward.
4. The resulting root is compared with the expected root.

For a balanced tree, the evidence for one item is logarithmic in the number of leaves. It is therefore much smaller than sending a complete list of all represented blocks. The tree does not eliminate the need for an expected root or a consistent construction rule; it supplies the compact path connecting one item to that root.

The important idea is structural rather than tied to a particular implementation. A large collection is represented by nested summaries. A verifier can check one block by reproducing only the summaries along that block's path.

A mental model: nested folders of summaries​

Imagine four documents named A, B, C, and D stored in nested folders:

• One folder contains A and B.
• Another folder contains C and D.
• A top-level folder contains both folders.

Each folder receives a summary derived from its contents. The top-level summary changes if a document inside either folder changes. To investigate a difference, compare the top-level folders, then the relevant subfolder, and then the document. To prove that one document belongs, provide the summaries of neighboring folders along the path.

The analogy does not mean that the root stores the documents. It means that each level summarizes a region and that the summaries are nested. The value of the Merkle tree comes from this nesting.

The folder analogy also clarifies why a sibling hash can represent many blocks. If a target block is in the left folder, the summary of the entire right folder can serve as one sibling value at the top level. The verifier does not need to receive every document in that right folder merely to rebuild the top-level summary.

Practical takeaways​

The most important ideas are structural:

• A Merkle tree begins with leaf hashes of data blocks.
• Internal nodes combine child hashes in ordered pairs.
• The root is the final summary of the whole collection.
• An edit changes the leaf and the ancestors on its path to the root.
• Two replicas can compare roots first, then descend only into differing branches.
• A membership proof uses the target block and one sibling hash per level.
• Positional information is needed to distinguish left-child and right-child steps.
• For a balanced tree with $n$ leaves, a path and its proof have length $O(\\log n)$.
• Building the complete tree from $n$ leaves takes $O(n)$ work.
• The grouping and tree-construction convention must be consistent between parties.

The four-block tree makes all of these points visible. A and B form one branch, C and D form another, and the two branches meet at the root. Change B, and only the path through B, P, and R changes. Compare two roots, and follow the branch whose summaries differ. Prove that B belongs, and provide the sibling values needed to rebuild the root.

Conclusion​

A Merkle tree turns a collection of data blocks into a hierarchy of hash summaries. Its root provides one compact value for the entire collection, while its internal nodes preserve the structure needed for comparison and verification.

With four blocks, the construction is easy to see: hash the blocks, combine A with B, combine C with D, and combine those two parent hashes into one root. The same pattern scales to larger balanced collections.

The main advantage is that global information can be checked through a local path. A single edit affects one path to the root. A replica comparison can descend only through branches whose summaries differ. A membership proof needs only logarithmically many sibling hashes.

That combination of a compact root, hierarchical summaries, local update paths, and short proofs is why Merkle trees support replica reconciliation and Bitcoin light wallets. One root does not contain all the data, but it provides a structured summary of the data and a route for checking individual parts.