Git: History as a Merkle DAG and the Collaborative Workflow

0. Key points

• Git is not a sequence of diffs. It is a collection of immutable objects addressed by the hash of their own content. A commit holds a pointer to the entire file tree at that moment, together with pointers to its parent commits.
• Every object is serialised in a form that embeds the hashes of its children, so the object graph is a Merkle DAG. The consequence is that checking a single 40-character commit hash pins down the whole reachable history and every file in it (Theorem 3.3).
• A branch is nothing but a named pointer to a commit. That is why git branch is cheap.
• git merge computes the merge base of two commits (a maximal common ancestor) and then performs a 3-way merge of the base, our version and their version. Saying that the merge base is HEAD itself is the same as saying that HEAD is an ancestor of the other commit, and that is what fast-forward really is (Proposition 5.3).
• The merge base need not be unique. In a history known as a criss-cross there are two or more of them, and which one is chosen changes the outcome of the merge (Proposition 5.5). Git’s default strategy handles this by merging the bases with each other to produce a virtual base.
• Rebasing rewires parents, so it necessarily produces different commits with different hashes (Proposition 5.7). This is exactly why one must not rebase a shared branch.

1. Motivation: what problem does version control solve?

report.docx, report_v2.docx, report_v2_revised.docx, report_final.docx, report_final_really_final.docx. Everyone has produced a sequence of file names like this at some point. It is a naive form of version control, and up to a point it genuinely works. But it cannot answer the following three questions.

1. What is the difference between report_v2.docx and report_v2_revised.docx? File names record no differences.
2. Was report_final.docx made from report_v2.docx or from report_v2_revised.docx? In other words, which file is a descendant of which?
3. When two people edit report_v2.docx at the same time and save separately, how do we keep both sets of changes?

The first is the problem of differences, the second the problem of the structure of history, the third the problem of integrating concurrent edits. A version control system (VCS) is a tool that handles all three at once.

Historically the three were solved in that order. In the early 1970s, Marc Rochkind at Bell Labs built SCCS, which established the idea of collecting the revision history of a file into a single archive file. In the early 1980s, Walter Tichy at Purdue built RCS, which improved on this by keeping the newest version in full and accumulating the differences that lead backwards into the past (reverse deltas). Both sidestep the third problem with locking: whoever wants to edit takes an exclusive lock on the file and everybody else waits.

Locking works when there are a handful of developers. With dozens the queue collapses. So from CVS (late 1980s) onward the policy was reversed: anyone may edit freely, and conflicts are integrated afterwards. This is the same idea as optimistic concurrency control in databases (see also Foundations of database design). The instrument of integration is the 3-way merge treated in the second half of this article.

CVS and its successor Subversion (from 2000) still carried the constraint of centralisation. The history lived only on the server, and committing required the network. Creating a branch meant copying a directory on the server, which was an expensive operation.

In April 2005 the Linux kernel developers lost free use of BitKeeper, the commercial distributed VCS they had been using. Linus Torvalds wrote a replacement in a few weeks. That is Git. The design requirements were explicit: it had to be fast at the scale of tens of thousands of files and hundreds of thousands of commits, every operation had to work without a network, and tampering with history had to be detectable. The third requirement is what turned Git from a mere file-history manager into a data structure built on cryptographic hashing.

Note

“Distributed” means that each developer holds a complete replica of the history. git clone brings down every commit and every version of every file from the server. Consequently git log, git diff and git commit all work offline, and if the server disappears the history survives on somebody’s machine. A central server (GitHub, say) is technically nothing more than a clone that everyone happens to have agreed to treat as the reference.

2. Preliminaries: hash functions and content addressing

The key to understanding Git is the idea of never touching a file by name but always by the hash of its content. We first set up the apparatus.

Definition 2.1（Content-addressable store）

Let $B = \{0,1\}^{*}$ be the set of all finite byte strings and let $b$ be a positive integer. A map $H : B \to \{0,1\}^{b}$ is a cryptographic hash function if the following properties hold (in the computational sense).

• (Collision resistance) One cannot find, with realistic computational resources, a pair $(x, y)$ with $H(x) = H(y)$ and $x \neq y$.
• (Preimage resistance) Given $y \in \{0,1\}^{b}$, one cannot find, with realistic computational resources, an $x$ with $H(x) = y$.

Given a finite set $S \subseteq B$ to be stored, the scheme in which each $x \in S$ is stored under the key $H(x)$ and retrieved by $H(x)$ is called a content-addressable store. In this scheme the key is determined by the content, and if the content changes the key necessarily changes with it.

For a long time Git used SHA-1 ($b = 160$) as its $H$. Hash values are displayed as 40 hexadecimal characters. Let us see numerically how much safety margin “collision resistance” actually buys.

Proposition 2.2（Birthday bound on the collision probability）

Assume that the output of $H$ behaves as a uniform random element of $\{0,1\}^{b}$ (the random oracle model). For $N$ distinct inputs $x_1, \ldots, x_N$, the probability $p$ that a collision occurs somewhere among them satisfies

$$p \;\le\; \binom{N}{2} 2^{-b} \;\le\; \frac{N^{2}}{2^{\,b+1}}.$$

Proof（Proposition 2.2）

For $1 \le i < j \le N$ let $A_{ij}$ be the event "$H(x_i) = H(x_j)$". Since $x_i \neq x_j$, the hypothesis makes $H(x_i)$ and $H(x_j)$ independent and uniform on $\{0,1\}^{b}$, so

$$\Pr[A_{ij}] = \sum_{v \in \{0,1\}^{b}} \Pr[H(x_i) = v]\,\Pr[H(x_j) = v] = 2^{b} \cdot 2^{-b} \cdot 2^{-b} = 2^{-b}.$$

The event we want is $\bigcup_{i<j} A_{ij}$, and since the probability of a union is at most the sum of the probabilities (Boole’s inequality),

$$p \;\le\; \sum_{i<j} \Pr[A_{ij}] = \binom{N}{2} 2^{-b} = \frac{N(N-1)}{2} \cdot 2^{-b} \;\le\; \frac{N^{2}}{2^{\,b+1}}.$$

The last inequality uses $N(N-1) \le N^{2}$.

∎

Let us substitute numbers. The Linux kernel repository holds on the order of $10^{7}$ objects. Estimating conservatively with $N = 10^{9}$ and $b = 160$,

$$p \;\le\; \frac{(10^{9})^{2}}{2^{161}} = \frac{10^{18}}{2.923 \times 10^{48}} \approx 3.4 \times 10^{-31},$$

a level at which accidental collisions may be treated as impossible. But this holds under the assumption that $H$ behaves like a random function; whether an attacker can deliberately construct a collision is a separate question. We return to this in Remark 2.4.

Example 2.3（Computing a Git object name by hand）

Git does not hash the file content $c$ directly. It hashes the byte string obtained by prefixing the type and the length,

$$\sigma = \texttt{"blob "} \,\Vert\, |c| \,\Vert\, \texttt{NUL} \,\Vert\, c$$

(here $\Vert$ is concatenation, $|c|$ is the decimal representation of the byte count of $c$, and NUL is the single byte 0x00). Take the content test content followed by one newline, that is 13 bytes.

import hashlib

content = b"test content\n"                       # 13 bytes
store = b"blob " + str(len(content)).encode() + b"\x00" + content
print(store)                                       # b'blob 13\x00test content\n'
print(hashlib.sha1(store).hexdigest())
# => d670460b4b4aece5915caf5c68d12f560a9fe3e4

Git itself produces the same value.

$ echo 'test content' | git hash-object --stdin
d670460b4b4aece5915caf5c68d12f560a9fe3e4

With -w the object is actually written, producing a file at the path .git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4. The first two characters become a directory name in order to keep the number of entries in any one directory small. The content is compressed with zlib when stored, but the hash is taken over the uncompressed bytes. That is why the object name does not change when the compression scheme changes.

The same rule lets us compute the name of the tree object representing an empty directory. Its body is 0 bytes, so $\sigma = \texttt{"tree 0"} \Vert \texttt{NUL}$, and hashlib.sha1(b"tree 0\x00").hexdigest() is 4b825dc642cb6eb9a060e54bf8d69288fbee4904. This value is the same in every repository and is often used in scripts as a constant denoting “the empty tree”.

Remark 2.4（SHA-1 collisions and Git's response）

In 2017 Stevens and coauthors actually constructed a full SHA-1 collision: two distinct PDF files with the same SHA-1 value. This is an instance of the hypothesis of Proposition 2.2 failing. Git responds on two fronts. First, since 2017 Git uses by default a SHA-1 implementation with collision detection (sha1collisiondetection), which aborts with an error when it detects the computational patterns characteristic of the known attack. Second, a repository format using SHA-256 is available and can be created with git init --object-format=sha256 (at the time of writing this is still considered experimental). With $b = 256$ the bound at $N = 10^{9}$ becomes $10^{18} / 2^{257} \approx 4.3 \times 10^{-60}$.

3. Git’s data model: four kinds of object and the Merkle DAG

Definition 3.1（Git objects）

The objects that go into Git’s store are of the following four kinds. Each has a byte string $\sigma$ consisting of a header <type> <byte count> followed by NUL and then the body, and its name (object ID) is $h = H(\sigma)$. Once created, an object is never modified.

Type	Body	What it represents
blob	the raw file content (it carries no file name)	the content of one file
tree	a sequence of entries, each being <mode> <name> followed by NUL and a 20-byte object ID, sorted by name	the structure of one directory
commit	one tree ID, zero or more parent commit IDs, author, committer and timestamps, a blank line, and the commit message	the state of the whole project at some moment
tag	the ID and type of the target object, the tag name, the tagger and a message	an annotated tag (it can be signed)

The mode of a tree entry is 100644 for a regular file, 100755 for an executable file, 40000 for a subdirectory, and 120000 for a symbolic link.

What matters is the nesting: a tree contains the IDs of blobs, and a commit contains the IDs of a tree and of its parent commits. Since the name of a child is embedded in the body of its parent, a single byte changed in a child changes the name of the parent too. This structure is called a Merkle DAG.

flowchart LR
H["HEAD"] --> R["refs/heads/main"]
R --> C2["commit C2"]
C2 -->|parent| C1["commit C1"]
C2 -->|tree| T2["tree T2"]
C1 -->|tree| T1["tree T1"]
T2 --> B1["blob B1 : README.md"]
T2 --> B2["blob B2 : main.py (after)"]
T1 --> B1
T1 --> B3["blob B3 : main.py (before)"]

The object graph. An arrow means 'my body contains the hash of the target'. Note that the two trees share the same blob, namely a file whose content did not change.

Definition 3.2（References, branches and HEAD）

A reference (ref) is a name whose value is a commit ID. A reference stored at .git/refs/heads/<name> is a branch; one stored at .git/refs/tags/<name> is a tag. The file .git/HEAD is a special reference: normally it holds an indirect reference to a branch name (a single line ref: refs/heads/main), and that branch is called the current branch. The state in which HEAD holds a commit ID directly is called a detached HEAD.

Creating a commit $c$ consists of writing $c$ into the object store and overwriting the value of the current branch’s reference with the ID of $c$. Objects are immutable; references are mutable.

In Git the only mutable things are references and the index (below); everything else is an immutable object. This separation explains almost all of Git’s behaviour. Creating a branch is instantaneous because it writes a single 41-byte file.

Theorem 3.3（A hash identifies an entire history）

Consider finite sets of objects $O$ and $O'$ (for instance our clone and someone else’s repository). Identify each object $o$ with its serialisation $\sigma(o)$, and assume that $\sigma(o)$ contains the IDs of all the child objects referenced by $o$. Put $h(o) = H(\sigma(o))$ and assume that $H$ is injective on $\{\sigma(o) : o \in O \cup O'\}$ (there is no collision inside this set). Write $R(o)$ for the set of all objects reachable from $o$.

Then, for $o \in O$ and $o' \in O'$,

$$h(o) = h(o') \;\Longrightarrow\; R(o) = R(o').$$

That is, if the object IDs agree, then the sets of objects reachable from them, and their contents, agree completely.

Proof（Theorem 3.3）

First we check that the reference relation is a directed acyclic one. To create an object $o$ one must fix $\sigma(o)$, and for that the IDs of the children of $o$ must already have been determined. Hence, along the order of creation times, a parent is always created after its children, and following a directed path of references makes the creation time strictly decrease. A cycle would make the time strictly decrease and yet return to its starting value, a contradiction. So the graph is a finite DAG, and for each vertex $o$ the maximum length $\ell(o)$ of a directed path leaving $o$ is a well-defined finite number.

We argue by induction on $\ell(o)$.

Case $\ell(o) = 0$. Then $o$ has no children, so $h(o) = h(o')$ together with the injectivity of $H$ gives $\sigma(o) = \sigma(o')$, that is, $o = o'$ as byte strings. Hence $R(o) = \{o\} = \{o'\} = R(o')$.

Case $\ell(o) = n \ge 1$, assuming the claim for all objects with $\ell$ less than $n$. From $h(o) = h(o')$ and the injectivity of $H$ we get $\sigma(o) = \sigma(o')$. Since $\sigma$ contains the type and the byte count in its header, $o$ and $o'$ have the same type and the same bytes, and in particular the sequence of child object IDs appearing in the body is the same. Call that sequence $h_1, \ldots, h_k$, and let $c_1, \ldots, c_k \in O$ be the children of $o$ and $c'_1, \ldots, c'_k \in O'$ those of $o'$, so that $h(c_j) = h_j = h(c'_j)$. Children are successors of $o$, so $\ell(c_j) \le n - 1$ and the induction hypothesis gives $R(c_j) = R(c'_j)$. Therefore

$$R(o) = \{o\} \cup \bigcup_{j=1}^{k} R(c_j) = \{o'\} \cup \bigcup_{j=1}^{k} R(c'_j) = R(o')$$

(the identity $o = o'$ follows from $\sigma(o) = \sigma(o')$). This completes the induction.

∎

What this theorem means in practice is important enough to be restated. If you receive a single commit ID over a trustworthy channel (a signed tag, spoken aloud, a separate medium), you can verify that not one byte of the entire history and of every file leading to that commit has been tampered with. Should an attacker alter one character in a file in a past commit, the ID of that blob changes, hence the ID of the tree, hence the ID of that commit, hence the IDs of every descendant commit. The command git fsck performs exactly this verification over all objects.

Example 3.4（Why snapshots do not blow up the repository）

Hearing that “a commit is a snapshot of the whole project”, one might expect a project of 1000 files committed 100 times to produce 100000 blobs. It does not. In the content-addressing scheme of Definition 2.1, the same content has the same ID. Committing a change to a single file creates exactly one new blob for the changed file, a new tree for the directory containing it, new trees for its ancestor directories, and one commit. Changing one file at depth $d$ adds $1 + d + 1$ objects, independently of the total number of files. In the object graph shown after Definition 3.1, this is the situation in which the blob B1 for README.md is shared by two trees.

Furthermore, once loose objects accumulate, git gc repacks them into a pack file and delta-compresses objects with similar content against each other. The important point is that these deltas are purely an optimisation of the storage format and carry no historical meaning. The delta base need not be the parent of a commit; it is simply whichever object happens to be similar. In RCS and Subversion the differences were the history; in Git the history is carried by the parent pointers of commits, and differences are merely a matter of compression. Thanks to this separation, what git log displays and what git diff computes can be defined independently of the storage format. The idea of “keeping one copy of identical content and sharing it between versions” is not peculiar to Git: container image layers (Definition 4.1［Docker and Kubernetes］) hold down storage and transfer costs by the same mechanism.

Remark 3.5（The index (the staging area)）

.git/index is a binary file holding a draft of the tree that the next commit will create. It lists the paths in the working tree together with the ID of the corresponding blob, the mode, the modification time and so on. git add reads a file from the working tree, writes a blob, and updates the corresponding line of the index. git commit builds a tree object from the index and creates a commit pointing at it. Having three states — working tree, index and HEAD — is what makes Git hard to learn, but conversely it means that the content of a commit can be assembled independently of the working tree. It is this structure that lets git add -p stage only part of the changes to a single file.

4. The commit graph: ancestry and merge bases

From now on we consider the graph obtained by keeping only the commit objects.

Definition 4.1（The commit graph and ancestry）

Let $G = (C, E)$ be the directed graph whose vertex set $C$ is all the commits of the repository and whose edges $E$ go from each commit to its parents. We call $G$ the commit graph. It is a finite DAG (by the same argument as at the beginning of the proof of Theorem 3.3).

For $a, b \in C$, write $a \preceq b$ when there is a directed path from $b$ to $a$ (paths of length $0$ included), and say that $a$ is an ancestor of $b$. When $a \preceq b$ and $a \neq b$ we write $a \prec b$.

A commit $c$ with $c \preceq a$ and $c \preceq b$ is a common ancestor of $a$ and $b$; the set of all of them is written $\mathrm{CA}(a,b)$. A maximal element of $\mathrm{CA}(a,b)$ with respect to $\preceq$ is called a merge base of $a$ and $b$.

Lemma 4.2（Ancestry is a partial order）

The relation $\preceq$ of Definition 4.1 is a partial order on $C$: it is reflexive, transitive and antisymmetric.

Proof（Lemma 4.2）

Reflexivity. For any $a$ there is a path of length $0$ from $a$ to $a$, so $a \preceq a$.

Transitivity. Suppose $a \preceq b$ and $b \preceq c$. By definition there is a directed path $P_1$ from $c$ to $b$ and a directed path $P_2$ from $b$ to $a$. The endpoint of $P_1$ and the starting point of $P_2$ are both $b$, so they can be concatenated, giving a directed path from $c$ to $a$. Hence $a \preceq c$.

Antisymmetry. Suppose $a \preceq b$ and $b \preceq a$ with $a \neq b$. Concatenating a path from $b$ to $a$ with a path from $a$ to $b$ gives a path from $b$ to $b$. Since $a \neq b$, at least one of the two paths has length at least $1$, so this is a cycle of length at least $1$. That contradicts the fact that $G$ is a DAG (Definition 4.1). Hence $a = b$.

∎

Proposition 4.3（Existence of a merge base）

In a finite commit graph $G = (C, E)$, let $a, b \in C$ have at least one common ancestor, that is, $\mathrm{CA}(a,b) \neq \emptyset$. Then $\mathrm{CA}(a,b)$ has at least one maximal element with respect to $\preceq$. In particular, if every commit of the repository is a descendant of a unique root commit $r$ (a commit with no parent), then any $a, b$ have a merge base.

Proof（Proposition 4.3）

The set $\mathrm{CA}(a,b) \subseteq C$ is finite and, by hypothesis, non-empty. By Lemma 4.2, $\preceq$ is a partial order on $\mathrm{CA}(a,b)$ as well.

We construct a maximal element. Pick any $c_0 \in \mathrm{CA}(a,b)$. If $c_0$ is not maximal there is a $c_1 \in \mathrm{CA}(a,b)$ with $c_0 \prec c_1$. If $c_1$ is not maximal there is a $c_2$ with $c_1 \prec c_2$, and iterating gives a chain $c_0 \prec c_1 \prec c_2 \prec \cdots$. By transitivity $c_i \prec c_j$ for all $i < j$, and by antisymmetry $c_i \neq c_j$ (if $c_i = c_j$ we would have $c_i \prec c_i$, contradicting antisymmetry of $\preceq$). So all terms of the chain are distinct, and finiteness of $\mathrm{CA}(a,b)$ forces the chain to stop after finitely many steps. The term at which it stops is maximal.

For the last statement: if $r$ is an ancestor of every commit then $r \in \mathrm{CA}(a,b)$, so $\mathrm{CA}(a,b) \neq \emptyset$ and the first part applies.

∎

Caution

The hypothesis that a common ancestor exists cannot be dropped. If you try to join the histories of two repositories created by separate git init calls, then $\mathrm{CA}(a,b) = \emptyset$ and no merge base can be defined. In that case Git refuses to proceed, saying fatal: refusing to merge unrelated histories. If you really want to join them, you must explicitly pass git merge --allow-unrelated-histories, which treats the empty tree as the base.

Running git merge-base --all A B displays every merge base Git computed. In ordinary branch usage only one appears, but as we shall see, histories where this fails can be constructed.

5. Merging: 3-way merge, fast-forward and criss-cross

Once the merge base is found, Git compares three states: the base, our version and their version. This is the 3-way merge. We first define it in the abstract.

Definition 5.1（3-way merge）

Fix a finite set $I$ (the set of “positions”: lines, file paths, and so on) and a set $V$ (the values that can occupy a position), and call a map $x : I \to V$ a version. Given a version $b$ (the base) and versions $x, y$, put, for each $i \in I$,

$$D_i \;=\; \{\, x(i),\, y(i) \,\} \setminus \{\, b(i) \,\}.$$

If $|D_i| \le 1$ for every $i \in I$, we say that $x$ and $y$ do not conflict relative to $b$, and define the merge result $m_b(x,y) : I \to V$ by

$$m_b(x,y)(i) \;=\; \begin{cases} v & (\text{if } D_i = \{v\}) \\ b(i) & (\text{if } D_i = \emptyset). \end{cases}$$

If $|D_i| = 2$ for some $i$, we say that a conflict occurs at position $i$.

This definition simply writes down the rule “take whichever of the two versions differs from the base; if two of them differ, hand the decision to a human”. Defining $D_i$ as a set spares us from worrying about overlapping cases and makes properties such as commutativity easy to see.

Proposition 5.2（Basic properties of the 3-way merge）

With the notation of Definition 5.1, the following hold for arbitrary versions $b, x, y$.

1. (Characterisation of conflicts) A conflict occurs at position $i$ if and only if $x(i) \neq b(i)$, $y(i) \neq b(i)$ and $x(i) \neq y(i)$.
2. (Commutativity) If $x, y$ do not conflict relative to $b$, then neither do $y, x$, and $m_b(x,y) = m_b(y,x)$.
3. (The base is a unit) $b$ and $y$ never conflict relative to $b$, and $m_b(b,y) = y$.
4. (Idempotence) $x$ and $x$ never conflict relative to $b$, and $m_b(x,x) = x$.

Proof（Proposition 5.2）

1. $|D_i| = 2$ means that removing $b(i)$ from the set $\{x(i), y(i)\}$ leaves a two-element set. First, $\{x(i), y(i)\}$ must itself have two elements, so $x(i) \neq y(i)$; second, nothing was removed, so $x(i) \neq b(i)$ and $y(i) \neq b(i)$. Conversely, if these three conditions hold then $D_i = \{x(i), y(i)\}$ has two elements.

2. The set $\{x(i), y(i)\}$ appearing in the definition of $D_i$ is invariant under exchanging $x$ and $y$. Hence so are $D_i$, $|D_i|$ and the value $m_b(x,y)(i)$.

3. Taking $x = b$ gives $D_i = \{b(i), y(i)\} \setminus \{b(i)\}$. If $y(i) = b(i)$ then $D_i = \emptyset$ and the definition gives $m_b(b,y)(i) = b(i) = y(i)$. If $y(i) \neq b(i)$ then $D_i = \{y(i)\}$ and $m_b(b,y)(i) = y(i)$. In either case $|D_i| \le 1$, so there is no conflict, and the value equals $y(i)$. Since this holds for every $i$, $m_b(b,y) = y$.

4. Here $D_i = \{x(i)\} \setminus \{b(i)\}$, so $|D_i| \le 1$ and no conflict occurs. If $x(i) \neq b(i)$ then $D_i = \{x(i)\}$ and the value is $x(i)$; if $x(i) = b(i)$ then $D_i = \emptyset$ and the value is $b(i) = x(i)$. Hence $m_b(x,x) = x$.

∎

Property 3 matters more than it looks. It says that if one side has changed nothing relative to the base, the merge simply adopts the other side and can never conflict. That is the theoretical content of fast-forward.

Proposition 5.3（Characterisation of fast-forward）

Let $a$ be the commit that HEAD currently points to and $b$ the commit being merged in, and assume $\mathrm{CA}(a,b) \neq \emptyset$. Then the following are equivalent.

1. $a \preceq b$, that is, $a$ is an ancestor of $b$.
2. $\mathrm{CA}(a,b)$ has exactly one maximal element, namely $a$ (the merge base is $a$ itself).

Moreover, in that case, performing a 3-way merge with the tree of $a$ as the base and the trees of $a$ and $b$ as the two versions produces no conflict and yields exactly the tree of $b$. Hence Git need not create a new commit: it merely overwrites the value of the branch reference from $a$ to $b$. This operation is called fast-forward.

Proof（Proposition 5.3）

1 implies 2. By reflexivity in Lemma 4.2 we have $a \preceq a$, and by hypothesis $a \preceq b$, so $a \in \mathrm{CA}(a,b)$. Next, any $c \in \mathrm{CA}(a,b)$ satisfies $c \preceq a$ by the definition of common ancestor. So $a$ is the greatest element of $\mathrm{CA}(a,b)$, and a greatest element is the unique maximal element. Indeed, if $c$ is maximal then $c \preceq a$, and $c \neq a$ would give $c \prec a$, contradicting maximality of $c$; hence $c = a$. And $a$ itself is maximal: if $a \preceq c'$ for some $c' \in \mathrm{CA}(a,b)$, then also $c' \preceq a$, so antisymmetry gives $c' = a$.

2 implies 1. A maximal element belongs to $\mathrm{CA}(a,b)$, so $a \in \mathrm{CA}(a,b)$, and the definition of common ancestor gives $a \preceq b$.

The second half. Regard a tree as a map from file paths to contents, taking $I$ to be the set of paths and $V$ the set of blob IDs (with a special value assigned to paths that do not exist). The base is the tree of $a$ itself, and the two versions are the tree of $a$ and the tree of $b$. Applying property 3 of Proposition 5.2, with the base version being the tree of $a$, one version being that same tree of $a$ and the other the tree of $b$, we get no conflict and a result equal to the tree of $b$. Since the resulting tree equals that of $b$, and since $a \preceq b$ makes $b$ a descendant of $a$, there is nothing to be gained by creating a new commit with both $a$ and $b$ as parents. Advancing the reference to $b$ suffices.

∎

Example 5.4（When a merge fast-forwards and when it does not）

Suppose feature was branched off main and two commits were made on feature alone. Writing $a$ for the commit that main points to and $b$ for the one feature points to, we have $a \prec b$.

$ git switch main
$ git merge feature
Updating a1b2c3d..d0e1f2a
Fast-forward
 src/auth.py | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

Git reports Fast-forward and creates no merge commit; this is the situation of Proposition 5.3. The history becomes a single straight line, and no record remains that a branch called feature ever existed.

If, on the other hand, somebody else pushed one commit onto main in the meantime, then the commit $a'$ that main points to is not an ancestor of $b$. We have $\mathrm{CA}(a', b) = \{a, \ldots\}$ with maximal element $a$, so condition 2 of Proposition 5.3 fails. A 3-way merge is then performed and a merge commit with two parents is created.

To create a merge commit even when a fast-forward would be possible, use git merge --no-ff feature. This keeps the extent of the branch in the history and makes git log --first-parent show what was integrated into main, feature by feature. Conversely, if the policy is to keep history linear, one can set git config --global pull.ff only so that anything that cannot fast-forward fails. Which to choose is a matter of team policy.

So far we have tacitly assumed that the merge base is uniquely determined. In general it is not.

flowchart RL
C["C (merge of A and B)"] --> A["A"]
C --> B["B"]
D["D (merge of A and B)"] --> A
D --> B
A --> R["R (root commit)"]
B --> R

A criss-cross merge. Arrows point from a child commit to its parents and time flows from left to right. The common ancestors of C and D are A, B and R, of which two — A and B — are maximal.

Proposition 5.5（The merge result depends on the choice of merge base）

There exists a commit graph with two or more merge bases, together with an assignment of file contents to the commits, such that the 3-way merge does not conflict when one merge base is taken as the base but does conflict when the other is taken.

Proof（Proposition 5.5）

We use the criss-cross graph of the figure. First we compute $\mathrm{CA}(C,D)$. The ancestors of $C$ are $\{C, A, B, R\}$ and those of $D$ are $\{D, A, B, R\}$, so $\mathrm{CA}(C,D) = \{A, B, R\}$. Since $R \prec A$ and $R \prec B$, the commit $R$ is not maximal. The ancestors of $A$ are $\{A, R\}$, which does not contain $B$, and the ancestors of $B$ are $\{B, R\}$, which does not contain $A$; hence $A$ and $B$ are incomparable under $\preceq$ and both are maximal. So there are two merge bases, $A$ and $B$.

Next we assign contents. Let the set of positions be $I = \{1\}$ (a file with a single line) and the set of values $V = \{0, 1, 2\}$, and define the version of each commit as follows.

Commit	Value	Explanation
$R$	$0$	the starting point
$A$	$1$	this line was changed from $0$ to $1$
$B$	$0$	this line was untouched; only another file was changed
$C$	$1$	the merge of $A$ and $B$ was adopted as is
$D$	$2$	after merging $A$ and $B$, this line was changed to $2$

Let us check that $C$ and $D$ are consistent. Merging $A$ and $B$ with base $R$ gives, by Definition 5.1, $D_1 = \{1, 0\} \setminus \{0\} = \{1\}$, so there is no conflict and the result is $1$. The commit $C$ adopted this as is and so has value $1$, while $D$ then edited the line and so has value $2$; both are commits that can genuinely be created.

Now merge $C$ and $D$.

Taking $A$ (value $1$) as the base. Then $D_1 = \{C(1), D(1)\} \setminus \{A(1)\} = \{1, 2\} \setminus \{1\} = \{2\}$, so $|D_1| = 1$, there is no conflict, and the result is $2$.

Taking $B$ (value $0$) as the base. Then $D_1 = \{1, 2\} \setminus \{0\} = \{1, 2\}$, so $|D_1| = 2$: the three conditions of property 1 of Proposition 5.2 ($1 \neq 0$, $2 \neq 0$, $1 \neq 2$) all hold and there is a conflict.

Thus the merge of the same two commits is either “no conflict, result $2$” or “a conflict”, depending on the choice of base.

∎

Remark 5.6（How Git handles several merge bases）

As Proposition 5.5 shows, picking one of several merge bases is arbitrary. Git’s default merge strategy instead merges the merge bases with each other recursively to build a single virtual base, and performs the 3-way merge against that. In the example above, merging $A$ (value $1$) and $B$ (value $0$) with base $R$ (value $0$) yields a virtual base of value $1$, and using it to merge $C$ and $D$ gives $2$ without a conflict.

This strategy was long called recursive, but since Git 2.34 (2021) the rewritten implementation ort (Ostensibly Recursive’s Twin) has been the default. The underlying idea is the same, with improvements in performance and rename detection. Passing git merge -s resolve switches to the older strategy, which merely picks one of the several merge bases, and the difference described above can then be observed.

Proposition 5.7（Rebasing always creates different commits）

Assume that the serialisation $\sigma$ of a commit object is determined by the tree ID, the sequence of parent IDs, the author information, the committer information and the message, and that $H$ is injective on the set of serialisations under consideration (the same hypothesis as in Theorem 3.3). Let $c'$ be the commit obtained from a commit $c$ by replacing its sequence of parents $(p_1, \ldots, p_k)$ by $(p'_1, \ldots, p'_l)$ and leaving everything else unchanged. If $k \neq l$, or if $h(p_j) \neq h(p'_j)$ for some $j$, then $h(c) \neq h(c')$.

Proof（Proposition 5.7）

By hypothesis, $\sigma(c)$ and $\sigma(c')$ differ in the part describing the parent IDs. The parent IDs appear in the body of a commit object as lines parent <ID>, in order, so if $k \neq l$ the number of such lines differs, and if $h(p_j) \neq h(p'_j)$ the content of the $j$-th line differs. Either way $\sigma(c) \neq \sigma(c')$ as byte strings.

Now argue by contraposition. If $h(c) = h(c')$, that is $H(\sigma(c)) = H(\sigma(c'))$, then injectivity of $H$ gives $\sigma(c) = \sigma(c')$, contradicting what we have just shown. Hence $h(c) \neq h(c')$.

∎

git rebase takes each commit of some sequence, reapplies its changes (its difference from its parent) on top of a new foundation, and creates new commits. By Proposition 5.7, a commit after a rebase is a different object with a different ID from the original. The original commits do not disappear; they merely become unreachable from any reference (see the Appendix after Example 6.1).

Caution

A practical rule follows. Never rebase commits that other people have already fetched. If you rebase and then git push --force, the remote branch points at a new sequence of commits. The old sequence is still on other people’s machines, so the next time they run git pull both lineages of commits — two families representing the same changes — enter the history, causing duplication and pointless conflicts later.

If a forced update is unavoidable, use git push --force-with-lease. This is a conditional update meaning “overwrite only if the current remote value matches the value I last observed”, and it prevents the accident of destroying commits that somebody pushed without your knowing. A plain --force overwrites unconditionally.

6. Practice: the commands and the collaborative workflow

We now map the everyday commands onto the model built so far.

6.1. What is inside .git

.git/
├── HEAD              indirect reference to the current branch (e.g. ref: refs/heads/main)
├── config            configuration of this repository (remote URLs and so on)
├── index             the staging area; a draft of the tree the next commit will build
├── objects/          the object store
│   ├── d6/70460b...  a loose object (one object, zlib-compressed)
│   └── pack/         pack files (many objects delta-compressed and bundled)
├── refs/
│   ├── heads/main    a branch; its content is one line holding a commit ID
│   ├── tags/v1.0     a tag
│   └── remotes/origin/main   a remote-tracking branch
└── logs/             the record of how references moved (the reflog)

The contents can be inspected with git cat-file.

$ git cat-file -t HEAD          # show the type
commit
$ git cat-file -p HEAD          # show the content, formatted
tree 9f8e7d6c5b4a39281706f5e4d3c2b1a098765432
parent a1b2c3d4e5f60718293a4b5c6d7e8f9012345678
author Hanako Yamada <hanako@example.com> 1755907200 +0900
committer Hanako Yamada <hanako@example.com> 1755907200 +0900

Add rate limiting to the login path

This is exactly the structure tabulated in Definition 3.1. Following the tree line unfolds the file tree; following the parent line unfolds the history.

6.2. The main commands and their effect on objects and references

Command	What it means to the user	Effect on objects and references
git add <path>	stage a change	write a blob of the content and update the corresponding index entry
git commit -m "..."	record what was staged	build a tree from the index, write a commit whose parent is HEAD, and advance the current branch reference
git switch -c <name>	create a branch and move to it	create refs/heads/<name> with the current commit ID and point HEAD at it
git merge <branch>	integrate another branch	compute the merge base and perform either a fast-forward or a 3-way merge
git rebase <base>	replant your commits on a new foundation	recreate the commits with new parents and point the branch reference at the new tip
git fetch <remote>	obtain the remote’s history	bring in the missing objects and update refs/remotes/...; the working tree and your branches are untouched
git pull	fetch and integrate	run git fetch followed by git merge (or git rebase, depending on configuration)
git push <remote> <branch>	send your history	send objects and advance the remote reference; non-fast-forward updates are rejected by default

It is worth remembering that git fetch changes nothing in the working tree. The procedure “first git fetch, then inspect the other side’s changes with git log --oneline HEAD..origin/main, and only then integrate” is always safe.

Tip

That git push rejects non-fast-forward updates by default is a safety device based on the contrapositive of Proposition 5.3. “The remote’s current commit is not an ancestor of the commit you are trying to send” means that the remote holds commits you do not know about. Overwriting it would lose them. When you see the error, run git fetch first and find out what is going on.

6.3. Collaboration based on pull requests

Let us write out, as Git operations, the flow that has become standard on GitHub and GitLab. We describe the case of a member with write access creating a branch in the same repository (for an outside contributor the only difference is that a fork is created first).

1. Update. git switch main, then git pull. This brings main into line with the latest remote.
2. Create a working branch. git switch -c feature/rate-limit. Choose a branch name that says what the work is.
3. Commit in small pieces. Use git add -p to separate meaningful units and then git commit. A good rule of thumb is that one commit should be a unit that can later be reverted on its own.
4. Publish. git push -u origin feature/rate-limit. The -u option sets the upstream so that plain git push suffices afterwards.
5. Open a pull request (PR). Write what you changed and why. What a diff never tells you is the “why”.
6. Pass the automated checks. CI runs the tests, the static analysis and the build. Fixing the CI environment with containers (Definition 3.1［Docker and Kubernetes］) is treated in Virtualisation technology (Docker and Kubernetes).
7. Respond to review. Add further commits and git push. The PR updates itself.
8. Take in changes to main. If main has advanced during review, run git fetch and then git merge origin/main (or, depending on policy, git rebase origin/main) on the working branch. Resolve conflicts here.
9. Integrate. Merge the PR. GitHub offers three methods: creating a merge commit (which preserves the shape of the history), squashing into a single commit (which keeps main readable), and rebasing the commits into line (which produces a linear history).
10. Clean up. Delete the working branch and run git switch main and git pull locally.

Note

Which integration method to choose comes down to whether you regard the history of main as a record of the work or as a sequence of releasable states. For the former, merge commits are appropriate; for the latter, squashing. What matters is that the team settles on one and applies it uniformly. If methods are mixed, git log stops conveying meaning.

Example 6.1（Resolving a conflict）

Here is what actually happens when step 8 conflicts.

$ git fetch origin
$ git merge origin/main
Auto-merging src/auth.py
CONFLICT (content): Merge conflict in src/auth.py
Automatic merge failed; fix conflicts and then commit the result.

Opening src/auth.py shows the markers Git wrote into it.

<<<<<<< HEAD
MAX_ATTEMPTS = 5
=======
MAX_ATTEMPTS = 3
>>>>>>> origin/main

Between <<<<<<< and ======= is our version; between ======= and >>>>>>> is theirs. This is the situation of property 1 of Proposition 5.2: a place where both sides changed the base value (say MAX_ATTEMPTS = 10) in different ways. To see all three versions, run

$ git checkout --conflict=diff3 src/auth.py

and the base content is displayed as well, separated by |||||||. Which one is right cannot be decided without knowing the intent behind both changes. That is why Git makes no automatic judgement and hands the decision to a human.

Once resolved, remove the markers and do the following.

$ git add src/auth.py          # tell Git "this is how I resolved it"
$ git merge --continue         # create the merge commit (git commit does the same)

To abandon the attempt, git merge --abort restores the state before the merge exactly. This works because objects are immutable (Definition 3.2), so restoring the original state is just a matter of moving references back.

7. Exercises

Exercise 7.1Easy

Determine the value printed by echo 'hello world' | git hash-object --stdin using the rule of Example 2.3. Note that echo appends one newline character. You may use Python’s hashlib for the computation. Also explain why this value is “the same in every repository and at every time”.

Solution

hello world is 11 bytes and the newline is 1 byte, so the content is 12 bytes. The object to be hashed is therefore b"blob 12\x00hello world\n".

import hashlib
content = b"hello world\n"
store = b"blob " + str(len(content)).encode() + b"\x00" + content
print(hashlib.sha1(store).hexdigest())
# => 3b18e512dba79e4c8300dd08aeb37f8e728b8dad

The value is universal because, in the content-addressing scheme of Definition 2.1, the key is determined by the content alone. A blob object contains no file name, no timestamp, no author and no repository identifier (check in the table of Definition 3.1 that it is the tree, not the blob, that carries file names). A file with the same content has the same ID in every repository in the world. This is also the reason git fetch can decide efficiently which objects the other side is missing.

Exercise 7.2Standard

Consider the following commit graph, with edges pointing from child to parent.

• the parent of $A$ is $R$
• the parent of $B$ is $R$
• the parent of $C$ is $A$
• the parents of $D$ are $A$ and $B$ (a merge commit)
• the parents of $E$ are $C$ and $B$ (a merge commit)

Determine $\mathrm{CA}(D, E)$ and list all of its maximal elements (the merge bases). Then, using Proposition 5.3, decide whether running git merge E while on D fast-forwards.

Solution

First compute the ancestor sets. Following parents from $D$ gives $D \to A \to R$ and $D \to B \to R$, so the ancestors of $D$ are $\{D, A, B, R\}$. From $E$ we get $E \to C \to A \to R$ and $E \to B \to R$, so the ancestors of $E$ are $\{E, C, A, B, R\}$. Intersecting,

$$\mathrm{CA}(D, E) = \{A, B, R\}.$$

Now examine maximality. Since $R \prec A$ and $R \prec B$, the commit $R$ is not maximal. The ancestors of $A$ are $\{A, R\}$, which does not contain $B$, so $B \preceq A$ fails; the ancestors of $B$ are $\{B, R\}$, which does not contain $A$, so $A \preceq B$ fails too. Thus $A$ and $B$ are incomparable and both maximal. There are two merge bases, $A$ and $B$, and this history has the same shape as the criss-cross of Proposition 5.5.

As for fast-forward: by Proposition 5.3, a fast-forward happens exactly when the unique maximal element of $\mathrm{CA}(D,E)$ is $D$. Here the maximal elements are $A$ and $B$ — not $D$, and there are two of them. So there is no fast-forward: a 3-way merge is performed and a merge commit with parents $D$ and $E$ is created (provided there is no conflict in the sense of Definition 5.1).

One can also check directly that $E$ is neither an ancestor nor a descendant of $D$: the ancestor set of $D$ does not contain $E$, and the ancestor set of $E$ does not contain $D$.

Exercise 7.3Hard

Given a common base $b$ and three versions $x, y, z$, compare computing $u = m_b(x,y)$ and then $m_b(u, z)$ with computing $w = m_b(y,z)$ and then $m_b(x, w)$. Prove the following.

Putting $S_i = \{x(i), y(i), z(i)\} \setminus \{b(i)\}$ for each position $i$: in either order, a necessary and sufficient condition for no conflict to occur at any stage is that $|S_i| \le 1$ for every $i$; and when there is no conflict, the two final results agree.

In other words, as long as the base is held fixed, the 3-way merge is associative. Explain nevertheless why the order of merges can change the outcome in real Git, in the light of Proposition 5.5.

Solution

Fix a position $i$ and abbreviate $\beta = b(i)$, $\xi = x(i)$, $\eta = y(i)$, $\zeta = z(i)$. By Definition 5.1, $m_b(x,y)(i)$ is $\beta$ if $\{\xi, \eta\} \setminus \{\beta\}$ is empty, is the unique element if that set is a singleton, and is a conflict if it has two elements. This can be restated as follows.

Lemma. If $|\{\xi,\eta\} \setminus \{\beta\}| \le 1$, then $u(i) = m_b(x,y)(i)$ is “the unique value among $\{\xi,\eta\}$ that differs from $\beta$, or $\beta$ if there is no such value”, and in either case $\{u(i)\} \setminus \{\beta\} = \{\xi,\eta\} \setminus \{\beta\}$.

Indeed, if $\{\xi,\eta\}\setminus\{\beta\} = \{v\}$ then $u(i) = v$ and $\{v\}\setminus\{\beta\} = \{v\}$; if $\{\xi,\eta\}\setminus\{\beta\} = \emptyset$ then $u(i) = \beta$ and $\{\beta\}\setminus\{\beta\} = \emptyset$.

Sufficiency, and agreement of the results. Assume $|S_i| \le 1$ for every $i$. Since $\{\xi,\eta\}\setminus\{\beta\} \subseteq S_i$, we have $|\{\xi,\eta\}\setminus\{\beta\}| \le 1$, so $u = m_b(x,y)$ is defined without conflict. By the lemma $\{u(i)\}\setminus\{\beta\} = \{\xi,\eta\}\setminus\{\beta\}$, and therefore

$$\{u(i), \zeta\} \setminus \{\beta\} \;=\; \bigl(\{u(i)\}\setminus\{\beta\}\bigr) \cup \bigl(\{\zeta\}\setminus\{\beta\}\bigr) \;=\; \bigl(\{\xi,\eta\}\setminus\{\beta\}\bigr) \cup \bigl(\{\zeta\}\setminus\{\beta\}\bigr) \;=\; S_i.$$

Since $|S_i| \le 1$ by hypothesis, the second stage does not conflict either, and the result is “the unique element of $S_i$, or $\beta$ if $S_i = \emptyset$”. This expression is symmetric in $x, y, z$, so the other order gives the same value.

Necessity. Suppose $|S_i| \ge 2$ for some $i$; we show that a conflict occurs somewhere in this order. Since $|S_i| \ge 2$, two distinct values different from $\beta$ occur among $\{\xi,\eta,\zeta\}$.

• If $\{\xi,\eta\}\setminus\{\beta\}$ has two elements, then the first stage $m_b(x,y)$ conflicts at position $i$.
• Otherwise $|\{\xi,\eta\}\setminus\{\beta\}| \le 1$, so $u$ is defined, and by the computation above $\{u(i),\zeta\}\setminus\{\beta\} = S_i$. Since $|S_i| \ge 2$ and $|\{u(i),\zeta\}\setminus\{\beta\}| \le 2$, we get $|S_i| = 2$, so the second stage $m_b(u,z)$ conflicts at position $i$.

In either case there is a conflict. The same argument goes through verbatim after permuting $x,y,z$, so the other order conflicts too. This establishes the equivalence.

Why the order matters in Git. What we proved is associativity conditional on holding the base $b$ fixed. Real Git does not hold the base fixed: at each merge it recomputes the merge base from the two commits at hand. Performing one merge creates a new merge commit and changes the shape of the commit graph, so the merge base of the next merge can be a different commit from before. Proposition 5.5 shows concretely that changing the base can change even whether a conflict occurs. Hence the phenomenon “I changed the order in which I integrated and it conflicted” comes not from any failure of associativity in the 3-way merge rule itself, but from the fact that the choice of base depends on the shape of the history.

Exercise 7.4Standard

You and a colleague are working on the same branch feature/x. You run git rebase main and then git push --force. What happens on your colleague’s machine the next time they run git pull? Explain using Proposition 5.7, and describe what kind of accident --force-with-lease prevents.

Solution

A rebase rewires the parent of each commit. By Proposition 5.7, a commit whose sequence of parents has changed necessarily has a different ID. So after the rebase the remote feature/x points at a different sequence of commits from the ones your colleague holds.

When your colleague runs git pull with the default configuration, git fetch is followed by git merge origin/feature/x. Writing $c$ for the old commit their local feature/x points at and $c'$ for the new remote commit, $c \preceq c'$ does not hold (the ancestors of $c'$ do not include $c$). By Proposition 5.3 there is therefore no fast-forward and a 3-way merge is performed. The result is that both lineages of commits representing the same changes remain in the history. Since the same change to the same lines appears twice, depending on the content this produces either a mass of conflicts or, worse, no conflict at all and a change applied twice. If your colleague then pushes, the old commits you thought you had removed come back to the remote.

The correct remedy is for your colleague to git fetch and then replant only their unpushed commits on the new foundation, for instance with git rebase --onto origin/feature/x <old fork point> feature/x. But the principle that avoids the trouble in the first place is not to rebase a shared branch at all.

What --force-with-lease prevents is a different accident. A plain --force overwrites the reference without checking the current remote value at all. If your colleague pushed a new commit between your git fetch and your push, that commit becomes unreachable from every reference and is effectively lost. --force-with-lease attaches the condition that the current remote value equal the value you last fetched. If the condition fails, the push fails, so you cannot unknowingly destroy someone else’s work. This is the same mechanism as a conditional update (compare-and-swap) in optimistic concurrency control.

References

• Scott Chacon, Ben Straub, Pro Git, 2nd ed., Apress, 2014 — Chapter 3, “Git Branching”, and Chapter 10, “Git Internals”. The full text is freely available at https://git-scm.com/book/en/v2. The content of §3 of this article corresponds to Chapter 10.
• The official Git reference, https://git-scm.com/docs — in particular git-merge-base, gitrevisions, githooks, and the hash-function-transition design document.
• Marc J. Rochkind, “The Source Code Control System”, IEEE Transactions on Software Engineering SE-1, no. 4 (1975), 364–370. DOI: 10.1109/TSE.1975.6312866 — the original SCCS paper, which formulates the problem of version control itself.
• Walter F. Tichy, “RCS — A System for Version Control”, Software: Practice and Experience 15, no. 7 (1985), 637–654. DOI: 10.1002/spe.4380150703 — history kept as reverse deltas, and the locking scheme.
• Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce, “A Formal Investigation of Diff3”, in FSTTCS 2007, Lecture Notes in Computer Science 4855, Springer, 2007, 485–496. DOI: 10.1007/978-3-540-77050-3_40 — a paper on the algebraic properties of the 3-way merge (diff3). The formalisation in §5 is a simplification of this line of argument.
• Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov, “The First Collision for Full SHA-1”, in CRYPTO 2017, Lecture Notes in Computer Science 10401, Springer, 2017, 570–596. DOI: 10.1007/978-3-319-63688-7_19 — the construction of the collision mentioned in Remark 2.4.
• Eugene W. Myers, “An O(ND) Difference Algorithm and Its Variations”, Algorithmica 1 (1986), 251–266. DOI: 10.1007/BF01840446 — the diff algorithm git diff uses by default. It supplies the “matching up of positions” that precedes the 3-way merge.

Appendix: Recovering lost work

References move, but objects do not vanish. Whether you threw away commits with git reset --hard or replaced an old sequence of commits with git rebase, what moved — as Definition 3.2 says — was only a reference; the objects remain in the store. If you can find what remains, you can recover.

Look at the reflog first. In .git/logs/ Git records, for each reference, when it moved and from which value to which. This record is the reflog.

$ git reflog
d0e1f2a HEAD@{0}: reset: moving to HEAD~3
9c8b7a6 HEAD@{1}: commit: Add logging for authentication errors
5f4e3d2 HEAD@{2}: commit: Implement rate limiting

Notation such as HEAD@{1} refers to a past position. To return to a discarded commit, run git reset --hard HEAD@{1}; to grow a branch from it, git switch -c rescue HEAD@{1}. The reflog is a local record and is not carried over to anyone who clones from you.

If it is not in the reflog either, use fsck. Objects reachable neither from any reference nor from the reflog can be listed with git fsck --lost-found. Lines reading dangling commit <ID> in the output are the orphaned commits. Inspect one with git show <ID> and, if needed, rescue it with git switch -c rescue <ID>.

But not indefinitely. git gc really does delete unreachable objects after a certain period. By default the reflog of reachable references expires after about 90 days and that of unreachable ones after about 30 days (configurable via gc.reflogExpire and gc.reflogExpireUnreachable). Start looking as soon as you notice an accident, and push important work early. In a distributed VCS the best backup is the existence of another clone. For the availability of the remote itself see Cloud computing (AWS, GCP) (availability is defined in Definition 6.1［クラウドコンピューティング］, and the computation showing that more replicas raise availability is Proposition 6.2［クラウドコンピューティング］); for what git push actually says on the wire, see Networking (TCP/IP) (Definition 2.1［ネットワーク（TCP/IP）］).