# Git: History as a Merkle DAG and the Collaborative Workflow > Git's content-addressable store and commit DAG, with proofs that one hash fixes an entire history, that fast-forward is an ancestry condition, and that merge bases are not unique. > https://rikai.mugen-giken.com/en/computer-science/software-engineering/version-control-git ## 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** (). - 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 (). - 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 (). 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 (). 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](/en/computer-science/software-engineering/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. ## 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. 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. 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}}. $$ 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 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 . 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. ```python 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. ```bash $ 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". 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 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 The objects that go into Git's store are of the following four kinds. Each has a byte string $\sigma$ consisting of a header ` ` 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 ` ` 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.

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)"]`} /> A **reference** (ref) is a name whose value is a commit ID. A reference stored at `.git/refs/heads/` is a **branch**; one stored at `.git/refs/tags/` 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. 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. 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. `.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. 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 ). 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$. The relation $\preceq$ of is a partial order on $C$: it is reflexive, transitive and antisymmetric. **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 (). Hence $a = b$. 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. The set $\mathrm{CA}(a,b) \subseteq C$ is finite and, by hypothesis, non-empty. By , $\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. 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. 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. With the notation of , 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$. **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. 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**. **1 implies 2.** By reflexivity in 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 , 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. 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$. ```bash $ 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 . 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 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.

A["A"] C --> B["B"] D["D (merge of A and B)"] --> A D --> B A --> R["R (root commit)"] B --> R`} /> 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. 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 , $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 ($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. As 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. 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 ). 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')$. 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 `, 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 , 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 ). ## 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` ```text .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`. ```bash $ 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 1755907200 +0900 committer Hanako Yamada 1755907200 +0900 Add rate limiting to the login path ``` This is exactly the structure tabulated in . 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 ` | 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 ` | create a branch and move to it | create `refs/heads/` with the current commit ID and point HEAD at it | | `git merge ` | integrate another branch | compute the merge base and perform either a fast-forward or a 3-way merge | | `git rebase ` | replant your commits on a new foundation | recreate the commits with new parents and point the branch reference at the new tip | | `git fetch ` | 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 ` | 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. ### 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 () is treated in [Virtualisation technology (Docker and Kubernetes)](/en/computer-science/software-engineering/containers-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. Here is what actually happens when step 8 conflicts. ```bash $ 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. ```text <<<<<<< 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 : a place where both sides changed the base value (say `MAX_ATTEMPTS = 10`) in different ways. To see all three versions, run ```bash $ 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. ```bash $ 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 (), so restoring the original state is just a matter of moving references back. ## 7. Exercises Determine the value printed by `echo 'hello world' | git hash-object --stdin` using the rule of . 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". `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"`. ```python 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 , **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 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. 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 , decide whether running `git merge E` while on `D` fast-forwards. 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 . As for fast-forward: by , 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 ). 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$. 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 . Fix a position $i$ and abbreviate $\beta = b(i)$, $\xi = x(i)$, $\eta = y(i)$, $\zeta = z(i)$. By , $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. 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**. 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 , and describe what kind of accident `--force-with-lease` prevents. A rebase rewires the parent of each commit. By , 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 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 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](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](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](https://doi.org/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](https://doi.org/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](https://doi.org/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](https://doi.org/10.1007/978-3-319-63688-7_19) — the construction of the collision mentioned in . - Eugene W. Myers, "An O(ND) Difference Algorithm and Its Variations", *Algorithmica* 1 (1986), 251–266. [DOI: 10.1007/BF01840446](https://doi.org/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 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. ```bash $ 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 ` in the output are the orphaned commits. Inspect one with `git show ` and, if needed, rescue it with `git switch -c rescue `. **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)](/computer-science/software-engineering/cloud-computing) (availability is defined in , and the computation showing that more replicas raise availability is ); for what `git push` actually says on the wire, see [Networking (TCP/IP)](/computer-science/software-engineering/networking-tcp-ip) ().