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. Nothing holds a copy of anything: everything holds a name, 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.
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 <[email protected]> 1136214245 +0000 committer Logical Art <[email protected]> 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.