Merkle DAG
A commit does not contain your repository. It contains a hash, which names a tree, which is a list of names, each naming a blob or another tree. Above the leaves nothing holds a copy of anything: every commit and every tree holds names, and the blobs at the bottom hold the file contents themselves. and every name is computed from the contents it names. So changing one byte at the bottom renames everything on the path to the top and leaves everything beside it alone. The ids below are real git ids, computed on this page in git's own object format, and you can check any of them with git hash-object.
New to naming things by their contents? Start here
Give every object a name that is the hash of what is inside it, and two things follow that are not obvious. Identical content gets one name, wherever it came from. And a name cannot be attached to different content later, as long as nobody can find two contents with the same hash: that assumption is the whole security of the arrangement, and it is an assumption rather than a fact.
An object can then hold the names of other objects. Git does not forbid pointing at an object that is missing, so what keeps the graph acyclic is not an ordering rule: it is that a cycle would need a set of objects whose hashes each contain the others, and nobody knows how to build one. That is what makes the graph acyclic without anything enforcing it.
Hard, not impossible
Nothing in this topic is unbreakable, and that is a claim about these machines rather than about cryptography. Each of them rests on an operation that is cheap in one direction and expensive in the other, and expensive means a number of steps so large that doing them costs more than the secret is worth. The one-time pad is the standing exception: it is not hard to break, it is impossible, and it is impractical for almost everything, which is why the rest of this topic buys difficulty instead.
That makes every claim here a claim with a date on it. Secure means secure for this long, against someone with this much to spend, assuming nobody finds a shortcut. The machines in this topic each rest on one of those one-way operations, and each is worth asking the same question about: what exactly would an attacker have to do, and how much of it.
The machine for this idea on its own is Diffie-Hellman, if you would rather press it than read about it.
A repository, named by hashes all the way to the top
1 A blob, named by the hash of what is in it
Three files. A blob is the contents with a header in front of it, and its name is the hash of both, which is why a blob id is not the hash of the file.
| file | size | id | state |
|---|---|---|---|
| README | 25 bytes | b47da403 | unchanged |
| src/main.c | 29 bytes | 78f2de10 | unchanged |
| src/util.c | 23 bytes | e165776b | unchanged |
2 A tree, which is a list of names
A tree is a list of names and modes with the raw bytes of each child id after it. It contains no file contents at all.
| tree | lists | id | state |
|---|---|---|---|
| src/ | main.c 78f2de10, util.c e165776b | 85c800fe | unchanged |
| the root tree | README b47da403, src 85c800fe | 3f3d4a59 | unchanged |
3 A commit, which points at a tree and at its parent
The commit is a few lines of text naming one tree and one parent. This is the whole object, byte for byte.
tree 3f3d4a592d308b4081bc6684dcd05ded622dee71 author Logical Art <hello@logicalart.us> 1136214245 +0000 committer Logical Art <hello@logicalart.us> 1136214245 +0000 a commit
- it names this tree
- 3f3d4a59
- its own size
- 175 bytes, which is the whole of it
- its id
- 098ad6c2c14199bd92df2f31d979216c76d6471a
4 Change one byte and watch every name above it change
| what | was | now | kind |
|---|
- renamed by that edit
- nothing: the contents are back to what they were
- left alone
- 3 of 3 files kept their names
Every id is back to where it started. Not restored from anywhere: the same contents simply have the same name, which is why two clones of a repository agree without comparing anything.
The commit is 175 bytes and contains no file contents whatever. It would still be 175 bytes if these three files were three gigabytes, because what it holds is one name.
What this page checked when it loaded.
| claim | held | measured |
|---|---|---|
| an empty blob hashes to git's published empty-blob id | yes | e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 |
| and a blob of "hello" matches git's id for it | yes | ce013625030ba8dba906f756967f9e9ca394464a |
| the empty tree matches git's id too | yes | 4b825dc642cb6eb9a060e54bf8d69288fbee4904 |
| editing one byte renames its blob, its tree, the root and the commit | yes | src/main.c, src/, the root tree, the commit |
| and renames nothing else | yes | README and src/util.c keep their ids |
| the same contents always have the same name | yes | and one byte of difference is a different name |
All 6 checks held when this page loaded.
What is real here, and what is not
These are real git ids, and the test proves it with git
The object format here is git's: the type, a space, the length, a NUL byte, then the body, hashed whole. Tree entries carry the twenty raw bytes of a child id rather than its hex, which is the detail that most reimplementations get wrong and which produces perfectly plausible ids that git does not agree with. The claims test runs git hash-object on the same bytes and compares, so the witness is a real consumer rather than this file agreeing with itself.
SHA-1 is broken and git still uses it, mostly
A collision in SHA-1 was demonstrated in 2017, and a chosen-prefix collision, the stronger and more dangerous kind, followed in 2020. Git added a hardened variant that detects the known attack, and a SHA-256 object format exists and is not the default. The naming property this page is about does not depend on the hash being collision-resistant, but the security property people often attach to it does, and it is worth not conflating the two.
One directory deep, no packfiles, no history to speak of
A real repository has trees several levels deep, thousands of objects, and stores almost all of them zlib-compressed inside packfiles with deltas between similar objects. None of that changes a single id. It is left out because it would not fit on a screen and because it is a storage question rather than a naming one, which is what this page is about.
The author and the timestamp are fixed on purpose
A commit id depends on its author line and its timestamp, so a page that used the current time would show a different commit id on every reload and could not claim that identical contents give identical names. The timestamp here is 1136214245, which is 2006-01-02T15:04:05Z — the moment Go's time package uses as its reference layout, picked because it is memorable and has nothing to do with git. A real commit made a second later has a different id with no file changed at all, and that is correct rather than a flaw.
Sources
- Git documentation, gitformat-pack. The object format and how objects are stored once there are many of them.
- M. Stevens, E. Bursztein, P. Karpman, A. Albertini and Y. Markov, The First Collision for Full SHA-1, CRYPTO 2017. Why the hash underneath this is no longer trusted for the property people assume it has.
- G. Leurent and T. Peyrin, SHA-1 is a Shambles, EUROCRYPT 2020. The chosen-prefix collision, which is the one that matters for a format that names things by hash.
- Logical Art, the studio this belongs to.