How Does Git Remember Every Change? Merkle Trees Explained

A version-control system needs more than a list of file names. It needs a reliable way to recognize content, detect changes, connect one state of a project to another, and verify that the history has not been altered unexpectedly. One important idea behind this kind of content-based history is the Merkle tree.

A Merkle tree is a tree of cryptographic hashes. The actual data appears at the leaves, while every parent node stores a hash derived from the hashes below it. Eventually, all of those values contribute to one final value called the root hash. This structure gives a useful property: if even a small piece of data changes, the change can propagate upward through the tree and produce a different root hash. Instead of comparing every byte of every item whenever two collections are checked, a system can compare compact hash values and follow the path to the changed data.

The animated idea described in this topic can be understood as a progression:

1. Start with a hash function.
2. Hash individual pieces of data into leaf nodes.
3. Combine leaf hashes into intermediate nodes.
4. Continue until one root hash remains.
5. Observe how changing one leaf changes its ancestors and therefore the root.
6. Relate this structure to the chain of commits used by Git.

The important lesson is that a Merkle tree does not store a complete history inside one magical value. Instead, it creates a compact, linked summary of underlying content and relationships.

The Role of a Hash Function​

A hash function maps input data to a fixed-size output, often written as a string of hexadecimal characters. For example, a function might accept a file, a text string, or another hash and produce a digest such as:

input data  ->  9f86d081884c7d659a2feaa0c55ad015a3385dd0d4d0fbf...

The exact output depends on the input and the selected hash algorithm. A cryptographic hash is designed so that small input changes usually produce very different-looking outputs. Changing one character, adding a byte, or removing a line can therefore result in a completely different digest.

A hash is not the original data. It is a compact fingerprint or summary. In general, the digest should not be treated as a way to reconstruct the original input. Its usefulness comes from comparison: if two inputs produce different hashes, the inputs are different. If two inputs produce the same cryptographic hash, a system treats them as matching for the purpose of that hash algorithm, while recognizing that no finite hash function can mathematically represent every possible input uniquely.

For a Merkle tree, the hash function is the basic building block. The tree does not need to place all data into one enormous input and calculate a single hash. It hashes smaller pieces first, then hashes combinations of those results. This creates a hierarchy that reflects the structure of the data.

Why Cryptographic Hashes Matter​

Cryptographic hash functions have specific properties that make them suitable for integrity verification:

• Deterministic: The same input always produces the same output.
• Quick to compute: Hashing large amounts of data is fast.
• Avalanche effect: A tiny change in input produces a drastically different output.
• One-way: Computing the original input from the hash is computationally infeasible.
• Collision-resistant: Finding two different inputs that produce the same hash is extremely difficult.

These properties ensure that a hash can serve as a reliable fingerprint for data. In Git, common hash functions include SHA-1 (historically) and SHA-256 (modern implementations). The specific algorithm matters less than understanding that the hash provides a compact, verifiable representation of content.

Leaf Nodes: Hashing the Data Pieces​

The bottom layer of a Merkle tree consists of leaf nodes. Each leaf represents one piece of data. Depending on the application, a piece might be a file, a record, a block, or another logical item.

Imagine four pieces of data:

A, B, C, D

The first step is to hash each one:

H(A), H(B), H(C), H(D)

Here, H means "apply the hash function." The values H(A) through H(D) become the leaves of the tree.

A practical implementation must define what exactly is included in the input to the hash. It might hash only the visible content, or it might include type information, boundaries, metadata, or other structure. The supplied concept focuses on the tree mechanism rather than one particular encoding, so the key point is simple: each leaf is produced from an underlying data item by hashing it.

If the content represented by B changes, the corresponding leaf changes from H(B) to H(B'). The other leaves remain the same:

H(A), H(B'), H(C), H(D)

That one changed leaf is enough to affect the parent nodes above it.

Leaf Construction in Practice​

In Git, leaves might represent individual files or file metadata. The hash of a file's content becomes its leaf value. If a file is modified, its hash changes immediately. This is why Git can quickly detect which files have been modified: it compares the stored hash of a file with the hash of the current file content.

The leaf layer is where the tree connects to actual data. Everything above the leaves is derived from these leaf hashes through repeated hashing operations.

Intermediate Nodes: Hashing Hashes​

After calculating the leaves, the tree combines them in pairs. A common binary Merkle tree combines neighboring values by concatenating them and hashing the result:

P1 = H(H(A) || H(B))
P2 = H(H(C) || H(D))

The symbol || means concatenation. P1 is the parent of the first two leaves, and P2 is the parent of the second two leaves.

The tree now looks conceptually like this:

          root
         /    \
       P1      P2
      /  \    /  \
    H(A) H(B) H(C) H(D)

There are now two intermediate values, P1 and P2. The process continues by hashing those values together:

root = H(P1 || P2)

The root is therefore a summary of the summaries, which themselves summarize the data. The root does not directly show which item changed, and it does not contain the original data in readable form. Instead, it acts as a compact value that depends on the entire arrangement of leaves and all the combinations used to build the tree.

The word "tree" describes these parent-child relationships. Leaves are at the bottom, internal nodes are above them, and the root is at the top. In a binary Merkle tree, each internal node commonly has two children, although practical designs can use other branching arrangements.

Building the Tree Layer by Layer​

The tree construction process is systematic:

1. Layer 0 (leaves): Hash each data item individually.
2. Layer 1: Pair adjacent leaf hashes and hash each pair.
3. Layer 2: Pair adjacent layer-1 hashes and hash each pair.
4. Continue: Repeat until only one hash remains.

For a tree with 8 leaves, the structure would be:

Layer 3 (root):           R
                         / \
                        /   \
Layer 2:              P1     P2
                     /  \   /  \
Layer 1:           P3   P4 P5  P6
                  / \ / \ / \ / \
Layer 0 (leaves): L1 L2 L3 L4 L5 L6 L7 L8

Each parent is computed from exactly two children. This binary structure is common but not universal; some systems use different branching factors.

Why a Small Change Reaches the Root​

Suppose the original tree contains A, B, C, and D. Now change only B to B'.

The leaf for B changes:

H(B)  ->  H(B')

Because P1 depends on both H(A) and H(B), it also changes:

H(H(A) || H(B))
    ->
H(H(A) || H(B'))

The second parent, P2, depends only on C and D, so it stays the same. However, the root depends on both parents. Since P1 is different, the root becomes different as well:

H(P1 || P2)  ->  H(P1' || P2)

This is the central visual idea behind the change-propagation animation. The changed leaf is at the bottom, its parent changes next, and then the changed value travels upward until it reaches the root. Nodes that are not ancestors of the changed leaf can remain unchanged.

This propagation gives the root a strong dependency relationship with the complete set of leaves. If the data, ordering, or relevant structure changes, the root hash can change too. Comparing old and new roots can therefore reveal that the represented state is not identical.

The root is not a detailed difference report. It answers a higher-level question: "Does this represented structure produce the same summary?" If the roots differ, a system can inspect lower levels to locate the difference.

The Path of Change​

When a single leaf changes, only the nodes on the path from that leaf to the root are affected. For a balanced binary tree with n leaves, this path contains approximately log₂(n) nodes. This is why Merkle trees are efficient: most of the tree remains unchanged and does not need to be recalculated.

For example, in a tree with 1,000,000 leaves, changing one leaf affects only about 20 nodes (since log₂(1,000,000) ≈ 20). The remaining nodes can be reused from the previous tree state.

Finding a Difference by Following the Tree​

Consider two trees that have the same root in one comparison and different roots in another. If the roots differ, compare their child nodes. If the left children match but the right children differ, the difference must be somewhere in the right subtree. Continue comparing children until the differing leaf or leaves are found.

For the four-leaf example, the process can be described as follows:

1. Compare the two root hashes.
2. If they match, the represented tree summaries match.
3. If they differ, compare the two root children.
4. Ignore a child pair that matches.
5. Recurse into a child pair that differs.
6. Continue until reaching a leaf.

This is useful because the tree narrows the search. A direct comparison might inspect every item. A tree-based comparison can use matching subtree hashes to skip entire regions that are already known to match.

For a balanced binary tree with n leaves, the height is approximately log₂(n). A path from the root to one leaf therefore contains logarithmically many levels. The exact amount of work depends on the comparison task, the number of changed regions, and the way the tree is stored, but the hierarchy provides a natural route for locating differences without treating the entire collection as one undifferentiated block.

Practical Efficiency Gains​

Consider synchronizing two large file systems. A naive approach would compare every file byte-by-byte. With Merkle trees:

• Compare root hashes: O(1) operation.
• If roots match, no further work needed.
• If roots differ, recursively compare children, skipping entire subtrees that match.
• In the best case (only one file changed), the algorithm finds the difference in O(log n) comparisons.
• In the worst case (many files changed), the algorithm still avoids redundant comparisons of unchanged regions.

This is one reason Merkle trees are valuable in systems that need verification, synchronization, or content comparison. Matching subtree hashes allow large unchanged portions to be recognized as units.

The Meaning of the Root Hash​

The root hash is the final result of applying the tree-building process to the leaves. It represents the content and arrangement that contributed to those leaves. If the inputs are changed, the root is expected to change. If the same inputs are placed in a different order and the tree construction preserves order, the root can also change.

That last point matters: a Merkle tree can represent more than a set of values. It can represent an ordered sequence or a structured collection, depending on how leaves are assigned and combined. The rules for ordering, pairing, and handling an odd number of leaves must be defined by the design.

For example, a tree with leaves arranged as:

A, B, C, D

is not automatically equivalent to one arranged as:

D, C, B, A

Even if both trees contain the same items, their parent combinations can differ. The root is meaningful only together with the construction rules that produced it.

A root hash is therefore best understood as a compact commitment to a particular tree structure. It is useful for checking whether another calculation produces the same result under the same rules.

Root Hash as a Fingerprint​

The root hash serves as a fingerprint for the entire tree. Two important properties follow:

1. Uniqueness (with high probability): Different tree contents almost always produce different root hashes.
2. Stability: The same tree contents always produce the same root hash.

These properties make the root hash useful as a reference point. A system can store the root hash and later verify that a tree has not been modified by recomputing the root and comparing it with the stored value.

Connecting the Idea to Git's Commit Chain​

The title connects Merkle trees to Git and asks how Git can remember every change. The supplied description specifically highlights the Git commit chain. The useful conceptual connection is that commits form linked historical states, and hashes can identify content and relationships between states.

A commit chain can be pictured as a sequence:

commit 1  ->  commit 2  ->  commit 3  ->  commit 4

Each commit represents a point in the project's history. A later commit can refer back to an earlier commit, creating a relationship between successive states. If a commit's identifying information depends on its content and its relationship to an earlier commit, then changing an earlier part of the chain can affect the identifiers that follow it.

This resembles the change-propagation idea in a Merkle tree. In a tree, a changed leaf affects its parent, then the parent's parent, and finally the root. In a linked history, a changed earlier element can affect the identifiers or relationships of later elements that depend on it. In both cases, hashes make structural relationships visible through compact values.

How Git Uses Hashing​

Git's internal model uses hashes extensively:

• Blob objects: Represent file contents. The hash of a blob is its unique identifier.
• Tree objects: Represent directory structures. A tree hash depends on the hashes of its contents.
• Commit objects: Represent snapshots of the project. A commit hash depends on the tree it points to and the parent commit it references.
• Commit chain: Each commit references its parent, forming a linked list. Changing any commit changes its hash, which breaks the reference from the next commit.

This design ensures that the commit history is tamper-evident. If someone tries to modify an old commit, its hash changes, which breaks the chain of references. The integrity of the entire history can be verified by checking that each commit's hash matches its content and that each commit correctly references its parent.

It is important not to reduce the entire Git model to a single ordinary binary Merkle tree. Git's complete internal design has its own object and history structures. For the purpose of understanding the described animation, the safe and useful abstraction is this: Git's commit chain uses content-based identifiers and links between historical states, while Merkle-tree reasoning explains why hashing structured data can make changes detectable and relationships verifiable.

The commit chain also helps explain why history is more than a folder containing the latest files. A current project state is one point in a sequence of states. Each commit provides a named historical point, and the chain records how one point relates to another.

"Remembering" Is Not the Same as Storing Everything in a Hash​

The phrase "How Does Git Remember Every Change?" can be misleading if interpreted literally. A hash does not contain every earlier version in a form that can be decoded from the root. A Merkle root is a summary, not a complete archive.

To remember history, a version-control system needs both stored historical information and relationships among historical states. Hashes help identify and connect those pieces. They make it possible to refer to a particular content state or commit using a compact identifier and to notice when a referenced structure no longer matches its expected value.

A useful mental model is:

stored data + structured relationships + hashes = verifiable history

The hashes contribute integrity and identity-like references. The stored objects or states contribute the information needed to inspect history. The chain or tree contributes organization. No single part should be mistaken for the entire system.

This distinction is practical. If someone asks whether a root hash can reconstruct all files or all commits, the answer is no. The root can help verify or compare a structure, but the underlying data and the rules used to interpret it are still required.

What a Hash Actually Stores​

A hash stores:

• A fixed-size fingerprint of the data.
• Information about the structure used to compute it.
• Nothing about the original data itself (it is one-way).

A hash does not store:

• The original data.
• A compressed version of the data.
• Enough information to reconstruct the data.
• A list of changes.

Understanding this distinction prevents confusion about what hashes can and cannot do.

A Small Worked Example​

Suppose four leaves represent four pieces of project data:

L1 = file A content
L2 = file B content
L3 = file C content
L4 = file D content

The tree construction is:

h1 = H(L1)
h2 = H(L2)
h3 = H(L3)
h4 = H(L4)

p1 = H(h1 || h2)
p2 = H(h3 || h4)

r = H(p1 || p2)

Now change only the second piece:

L2 -> L2'

Recalculate the affected values:

h2' = H(L2')
p1' = H(h1 || h2')
r'  = H(p1' || p2)

The values h1, h3, h4, and p2 can remain the same. The changed path is:

L2 -> h2 -> p1 -> r

This path is the simplest way to visualize propagation. The change does not need to recalculate the unrelated right-hand subtree in this example. The new root r' summarizes the new overall state.

If two systems share the same construction rules and compare r with r', they immediately know that the represented states differ. To investigate further, they compare p1 and p2. Since p2 matches and p1 differs, they inspect the children of p1, quickly isolating the second leaf.

Numerical Example with Actual Hashes​

To make this concrete, imagine using a simplified hash function (not cryptographically secure, just for illustration):

H(x) = (sum of ASCII values of x) mod 256

With data:

L1 = "apple"   -> h1 = H("apple") = 97+112+112+108+101 = 530 mod 256 = 18
L2 = "banana"  -> h2 = H("banana") = 98+97+110+97+110+97 = 609 mod 256 = 97
L3 = "cherry"  -> h3 = H("cherry") = 99+104+101+114+114+121 = 653 mod 256 = 141
L4 = "date"    -> h4 = H("date") = 100+97+116+101 = 414 mod 256 = 158

Parent nodes:

p1 = H("18" || "97") = H("1897") = 1+8+9+7 = 25
p2 = H("141" || "158") = H("141158") = 1+4+1+1+5+8 = 20

r = H("25" || "20") = H("2520") = 2+5+2+0 = 9

Now change L2 to "blueberry":

h2' = H("blueberry") = 98+108+117+101+98+101+114+114+121 = 972 mod 256 = 204

p1' = H("18" || "204") = H("18204") = 1+8+2+0+4 = 15

r' = H("15" || "20") = H("1520") = 1+5+2+0 = 8

The root changed from 9 to 8. By comparing intermediate nodes, we can trace the change back to the second leaf.

Practical Takeaways for Software Engineers​

The Merkle-tree idea is useful whenever data is large, structured, and subject to comparison or verification.

Use hashes as summaries, not as original data​

A digest is compact and convenient, but it is not a substitute for storing the content that the digest represents. Preserve the underlying data when it must later be read, restored, or examined. Never assume that a hash can be reversed to recover the original data.

Define the construction rules precisely​

A tree is meaningful only when the system agrees on how to encode leaves, order items, pair children, and handle incomplete levels. Two implementations can process the same visible items but produce different roots if their rules differ. Document the exact algorithm used to build the tree.

Expect changes to propagate​

When one input changes, every ancestor on its path can change. This is a feature: it makes the overall summary sensitive to lower-level differences. Plan for this when designing systems that depend on hash stability.

Use matching subtrees to skip work​

If a subtree hash matches between two structures, the contents represented by that subtree can be treated as matching under the same assumptions. This is the main efficiency advantage of hierarchical hashing. Implement tree comparison algorithms that exploit this property.

Separate integrity from history storage​

Hashes help detect differences and link related states, but a complete version history also depends on retaining the states and relationships needed to inspect that history. Do not rely on hashes alone to preserve history; store the actual data as well.

Think in terms of commitments​

The root hash can be viewed as a compact commitment to the tree's contents and arrangement. Later, another calculation can be compared with that commitment to check whether the same structure is represented. Use root hashes as reference points for verification.

Consider performance implications​

Merkle trees are efficient for large datasets, but the efficiency depends on the tree structure and the comparison patterns. For small datasets, the overhead of tree construction might outweigh the benefits. Choose data structures based on actual use cases.

Final Perspective​

A Merkle tree turns many pieces of data into a hierarchy of hashes. Leaves summarize individual items. Intermediate nodes summarize groups of items. The root summarizes the entire structure. When one leaf changes, the difference propagates through its ancestors and produces a new root.

That simple pattern explains why hash-linked structures are useful for tracking and verifying change. The tree provides a way to organize data comparisons, while the hash function provides compact values that reveal whether corresponding parts agree. The Git connection comes through the commit chain: historical states can be linked and identified using content-based relationships, making changes and history easier to reason about.

The most important mental picture is the path from a small change to a global summary:

changed data
    ↓
changed leaf hash
    ↓
changed parent hash
    ↓
changed higher-level hash
    ↓
changed root or later linked identifier

Once this picture is clear, the animation's main ideas become easier to follow. A Merkle tree is not a mysterious record of every byte. It is a carefully constructed hierarchy that lets a system summarize, compare, and connect structured data. Git's commit chain can then be understood through the same broader principle: hashes are most powerful when they are combined with meaningful relationships among the pieces of history.

When you next use Git to check out a commit, view the history, or verify the integrity of a repository, you are benefiting from these ideas. The commit hash you see is a fingerprint of that commit's content and its place in history. The chain of commits is a linked structure where each commit references its parent. Together, hashing and linking create a system where every change is detectable and the entire history is verifiable. That is how Git remembers every change.