7 ms·

Generate a Git repository with 2^28 commits—one for every 7-character shorthash

232 points by breck 5y ago

emerged 5y ago
To be clear it’s code to generate a repository, not a repository.
- app4soft 5y ago
  Yeah. Linked repo has only 2 commits.[0] [0] https://github.com/not-an-aardvark/every-git-commit-shorthash/commits/main https://github.com/not-an-aardvark/every-git-commit-shorthas...
  - Ericson2314 5y ago
    And those two commits are 00000002bdd056473559d2bd0eb835561b3c874b 00000002f7c605501165ee5e3c2db20ffe178848 What the hell?!
    - surye 5y ago
      Hah, that's clever. The author is using their other toy research tool/project: https://github.com/not-an-aardvark/lucky-commit https://github.com/not-an-aardvark/lucky-commit
      - hpb42 5y ago
        lucky-commit has a very beautiful commit history: only 0000000.
    - redler 5y ago
      It’s commit mining.
      - quickthrower2 5y ago
        That’s worth 1 gitcoin. The bonus is it is double spent to all of us!
- deleted 5y ago
  [deleted]
- lambdaba 5y ago
  There's a packfile and index file in releases: https://github.com/not-an-aardvark/every-git-commit-shorthash/releases https://github.com/not-an-aardvark/every-git-commit-shorthas...
- dang 5y ago
  Ok, we've generated that into the title above.
pronoiac 5y ago
Doing the math, 2 to the 28th is around 268 million.
- 988747 5y ago
  I can imagine a big company with a monorepo (i.e. Google) reaching that number in a few years.
  - wruza 5y ago
    This number may be even lower if you take the birthday problem into account. I’m not a statistics guy to confirm that or to make proper calculations, but I believe it applies to this case as well, because first few bits of a hash are like what a birthday is to an otherwise unique person. https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
  - whatshisface 5y ago
    Generously, there are about 40,000 people at Google who might commit to the monorepo. That's only 6,000 or so commits per person, a fairly achievable number. Although since they're not purposely generating every shorthash, it would take significantly longer for the absolute last unique hash to be created.
    - charcircuit 5y ago
      Don't forget the commits made by programs.
    - yellow_lead 5y ago
      I wonder what the number of commits is before you need to start worrying about 7 character collisions. (Birthday problem anyone?)
      - sltkr 5y ago
        You answered your own question. After 2^14 = 16,384 commits, there is a 50% chance of a collision. So most large repos will have collisions. This isn't a problem for Git. It accepts arbitrary prefixes so you'll just have to type a few more characters if you want to refer to a commit whose 28-bit prefix (7 hex digits) is not unique.
mrkramer 5y ago
So this is basically a proof of work algorithm.
- colejohnson66 5y ago
  Git, but on a Blockchain? /s
  - Cerium 5y ago
    Git is a Blocktree - a type of directed acyclic graph based proof of nothing crypto product that is invulnerable to fork based attacks by supporting it out of the box. /s
    - quickthrower2 5y ago
      So like IOTA! /s
  - tylersmith 5y ago
    I commonly use git as an example the blockchain data structure in use before Bitcoin, and that it's really not the vital part of made Bitcoin innovative. It sure ended up as a powerful brand though.
- posnet 5y ago
  An assignment in one of my university security course was to mine "gitcoin". Which was a git based proof of work, the server would only accept pushes for commits if it had more leading zeros in its hash than the previous commit on that branch.
  - distrill 5y ago
    That sounds like a ton of fun, and tbh way cooler than anything I built in school.
  - ac42 5y ago
    I bet they later spoke about randomised algorithms like[1] [1] https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog
gopherbro 5y ago
It seems someone write a script for it.
detaro 5y ago
> The repository has so many commits that git push hangs and runs out of memory, presumably because it tries to regenerate a packfile on the fly. Any guesses if this would also happen if you tried to push it bit-by-bit? (although you'd of course need reasonably large groups of commits still, to not end up with an impossible number of pushes)
sverhagen 5y ago
As the README.md acknowledges, the usefulness may be limited, except for the fun in experimentation. What may not be obvious to basic Git users is that, while it may take 2^28 commits to fill up the entire address space of the 7-character shorthash, they are not designed to be unique (they are just the first part of the longer, unique hash). As a result, even relatively small repositories often already have _some_ duplicate shorthashes. And people scripting around their Git shorthashes must be prepared to deal with larger shorthashes, like 8-characters, 9, 10, 11, whatever it takes to disambiguate. My random Git repository of a mere 16865 commits (well, that's just "master") that I'm looking at over here, nothing out of the ordinary, needs shorthashes up to 11 characters to disambiguate all of them. (Not all the clashes may be on the same or main branch.)
- quickthrower2 5y ago
  Does anyone use short hashes for scripting? If the computer is dealing with it, might as well use the whole thing. I only use a short hash for human searching type activities where I sanity check the commit message (I’m probably reviewing code or doing some sort of blame exercise)
  - sverhagen 5y ago
    I have a few places where the shorthash becomes the Docker tag. But you make a good point nonetheless.
    - alex_young 5y ago
      If you're keeping that many docker images around you have other problems to worry about.
      - tedunangst 5y ago
        You can have two colliding short hashes in a row.
        5y ago
jamespwilliams 5y ago
You could set git’s pack.windowMemory option to (say) 128m to avoid git push OOMing. I expect GitHub wouldn’t handle the push well anyway, though, as mentioned.
anyfoo 5y ago
While we're being silly, here's a shell oneliner that outputs its own SHA1 hash[1]: A=shasum; C=echo; I='($C "A$s$A$X C$s$C$X I$s$Q$I$Q$X Q$s$k$Q$k$X k$s$Q$k$Q$X X$s$Q$X$Q$X s$s$Q$s$Q$X $I" | $A)'; Q="'"; k='"'; X=';'; s='='; ($C "A$s$A$X C$s$C$X I$s$Q$I$Q$X Q$s$k$Q$k$X k$s$Q$k$Q$X X$s$Q$X$Q$X s$s$Q$s$Q$X $I" | $A) Note that this is not in any way opening its own source code as a file or through shell magic or something like that, in fact it's not looking at its own code at all. It really generates its own hash computationally out of itself, and would work the same if this was a compiled C program computing (not containing!) the hash of its own source code, even if the source code was thrown away. This may seem impossible at first, but it's really just a funny variant of a quine (a program that prints its own source). http://www.madore.org/~david/computers/quine.html http://www.madore.org/~david/computers/quine.html came up with the idea and explains the concept. [1] You could trivially change it to output its SHA2 hash instead (which just wasn't as common at the time I did this), but then you'd loose the particularly "nice" hash. That property is entirely unrelated to outputting its own hash, and done the same as the commit hashes linked here.
- chii 5y ago
  That is fascinating!
- jcun4128 5y ago
  Cool site but man it's all just text. Semi related: only aware of some concept like hot loading (Java) regarding code that can be modified while it's running. - following idea of code that writes itself.
- H8crilA 5y ago
  Ah yes, the Quine: https://en.m.wikipedia.org/wiki/Quine_(computing) https://en.m.wikipedia.org/wiki/Quine_(computing) You can easily adjust quines to output any f(program_contents), including f=some_hash_function. Also, quines are related to fixed point combinators, the most famous of which is the Y Combinator (in case you didn't know where does the name of this fund/forum come from).
queuebert 5y ago
Rust is now mature enough that subversives are using it.
chovybizzass 5y ago
not-an-aardvark is a legend
est31 5y ago
See also: https://blog.cuviper.com/2013/11/10/how-short-can-git-abbreviate/ https://blog.cuviper.com/2013/11/10/how-short-can-git-abbrev...
a-dub 5y ago
i wonder how git would break in the face of an actual sha-1 collision...
- usr1106 5y ago
  The second file is just not stored, because git thinks it's already there. Nothing complicated there. Discussed here: https://stackoverflow.com/questions/9392365/how-would-git-handle-a-sha-1-collision-on-a-blob https://stackoverflow.com/questions/9392365/how-would-git-ha... It costed 6500 CPU years to create the first collision containing a valid pdf document. Storing both versions into git still works, because git prepends a header before creating the SHA-1 of the blob. I believe because of that it is harder to create a git blob collision than a pdf collision. (I admit I did neither read very carefully nor try to think it through very seriously.)
- swiftcoder 5y ago
  On the other hand, if you are still running subversion, you pretty much lose the repo in this case: https://arstechnica.com/information-technology/2017/02/watershed-sha1-collision-just-broke-the-webkit-repository-others-may-follow/ https://arstechnica.com/information-technology/2017/02/water...
  - COMMENT___ 5y ago
    This was fixed years ago.
    - swiftcoder 5y ago
      Where (years <= 4), sure. 2017 is not exactly ancient history.
curiousllama 5y ago
GitHub devops folks: edge case incoming in 3… 2… 1…

232 points by breck 5y ago

emerged 5y ago

To be clear it’s code to generate a repository, not a repository.

app4soft 5y ago
Yeah. Linked repo has only 2 commits.[0] [0] https://github.com/not-an-aardvark/every-git-commit-shorthash/commits/main https://github.com/not-an-aardvark/every-git-commit-shorthas...
- Ericson2314 5y ago
  And those two commits are 00000002bdd056473559d2bd0eb835561b3c874b 00000002f7c605501165ee5e3c2db20ffe178848 What the hell?!
  - surye 5y ago
    Hah, that's clever. The author is using their other toy research tool/project: https://github.com/not-an-aardvark/lucky-commit https://github.com/not-an-aardvark/lucky-commit
    - hpb42 5y ago
      lucky-commit has a very beautiful commit history: only 0000000.
  - redler 5y ago
    It’s commit mining.
    - quickthrower2 5y ago
      That’s worth 1 gitcoin. The bonus is it is double spent to all of us!
deleted 5y ago
[deleted]
lambdaba 5y ago
There's a packfile and index file in releases: https://github.com/not-an-aardvark/every-git-commit-shorthash/releases https://github.com/not-an-aardvark/every-git-commit-shorthas...
dang 5y ago
Ok, we've generated that into the title above.

pronoiac 5y ago

Doing the math, 2 to the 28th is around 268 million.

988747 5y ago
I can imagine a big company with a monorepo (i.e. Google) reaching that number in a few years.
- wruza 5y ago
  This number may be even lower if you take the birthday problem into account. I’m not a statistics guy to confirm that or to make proper calculations, but I believe it applies to this case as well, because first few bits of a hash are like what a birthday is to an otherwise unique person. https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
- whatshisface 5y ago
  Generously, there are about 40,000 people at Google who might commit to the monorepo. That's only 6,000 or so commits per person, a fairly achievable number. Although since they're not purposely generating every shorthash, it would take significantly longer for the absolute last unique hash to be created.
  - charcircuit 5y ago
    Don't forget the commits made by programs.
  - yellow_lead 5y ago
    I wonder what the number of commits is before you need to start worrying about 7 character collisions. (Birthday problem anyone?)
    - sltkr 5y ago
      You answered your own question. After 2^14 = 16,384 commits, there is a 50% chance of a collision. So most large repos will have collisions. This isn't a problem for Git. It accepts arbitrary prefixes so you'll just have to type a few more characters if you want to refer to a commit whose 28-bit prefix (7 hex digits) is not unique.

mrkramer 5y ago

So this is basically a proof of work algorithm.

colejohnson66 5y ago
Git, but on a Blockchain? /s
- Cerium 5y ago
  Git is a Blocktree - a type of directed acyclic graph based proof of nothing crypto product that is invulnerable to fork based attacks by supporting it out of the box. /s
  - quickthrower2 5y ago
    So like IOTA! /s
- tylersmith 5y ago
  I commonly use git as an example the blockchain data structure in use before Bitcoin, and that it's really not the vital part of made Bitcoin innovative. It sure ended up as a powerful brand though.
posnet 5y ago
An assignment in one of my university security course was to mine "gitcoin". Which was a git based proof of work, the server would only accept pushes for commits if it had more leading zeros in its hash than the previous commit on that branch.
- distrill 5y ago
  That sounds like a ton of fun, and tbh way cooler than anything I built in school.
- ac42 5y ago
  I bet they later spoke about randomised algorithms like[1] [1] https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog

gopherbro 5y ago

It seems someone write a script for it.

detaro 5y ago

> The repository has so many commits that git push hangs and runs out of memory, presumably because it tries to regenerate a packfile on the fly. Any guesses if this would also happen if you tried to push it bit-by-bit? (although you'd of course need reasonably large groups of commits still, to not end up with an impossible number of pushes)

sverhagen 5y ago

As the README.md acknowledges, the usefulness may be limited, except for the fun in experimentation. What may not be obvious to basic Git users is that, while it may take 2^28 commits to fill up the entire address space of the 7-character shorthash, they are not designed to be unique (they are just the first part of the longer, unique hash). As a result, even relatively small repositories often already have _some_ duplicate shorthashes. And people scripting around their Git shorthashes must be prepared to deal with larger shorthashes, like 8-characters, 9, 10, 11, whatever it takes to disambiguate. My random Git repository of a mere 16865 commits (well, that's just "master") that I'm looking at over here, nothing out of the ordinary, needs shorthashes up to 11 characters to disambiguate all of them. (Not all the clashes may be on the same or main branch.)

quickthrower2 5y ago
Does anyone use short hashes for scripting? If the computer is dealing with it, might as well use the whole thing. I only use a short hash for human searching type activities where I sanity check the commit message (I’m probably reviewing code or doing some sort of blame exercise)
- sverhagen 5y ago
  I have a few places where the shorthash becomes the Docker tag. But you make a good point nonetheless.
  - alex_young 5y ago
    If you're keeping that many docker images around you have other problems to worry about.
    - tedunangst 5y ago
      You can have two colliding short hashes in a row.
      - 5y ago

jamespwilliams 5y ago

You could set git’s pack.windowMemory option to (say) 128m to avoid git push OOMing. I expect GitHub wouldn’t handle the push well anyway, though, as mentioned.

anyfoo 5y ago

While we're being silly, here's a shell oneliner that outputs its own SHA1 hash[1]: A=shasum; C=echo; I='($C "A$s$A$X C$s$C$X I$s$Q$I$Q$X Q$s$k$Q$k$X k$s$Q$k$Q$X X$s$Q$X$Q$X s$s$Q$s$Q$X $I" | $A)'; Q="'"; k='"'; X=';'; s='='; ($C "A$s$A$X C$s$C$X I$s$Q$I$Q$X Q$s$k$Q$k$X k$s$Q$k$Q$X X$s$Q$X$Q$X s$s$Q$s$Q$X $I" | $A) Note that this is not in any way opening its own source code as a file or through shell magic or something like that, in fact it's not looking at its own code at all. It really generates its own hash computationally out of itself, and would work the same if this was a compiled C program computing (not containing!) the hash of its own source code, even if the source code was thrown away. This may seem impossible at first, but it's really just a funny variant of a quine (a program that prints its own source). http://www.madore.org/~david/computers/quine.html http://www.madore.org/~david/computers/quine.html came up with the idea and explains the concept. [1] You could trivially change it to output its SHA2 hash instead (which just wasn't as common at the time I did this), but then you'd loose the particularly "nice" hash. That property is entirely unrelated to outputting its own hash, and done the same as the commit hashes linked here.

chii 5y ago
That is fascinating!
jcun4128 5y ago
Cool site but man it's all just text. Semi related: only aware of some concept like hot loading (Java) regarding code that can be modified while it's running. - following idea of code that writes itself.
H8crilA 5y ago
Ah yes, the Quine: https://en.m.wikipedia.org/wiki/Quine_(computing) https://en.m.wikipedia.org/wiki/Quine_(computing) You can easily adjust quines to output any f(program_contents), including f=some_hash_function. Also, quines are related to fixed point combinators, the most famous of which is the Y Combinator (in case you didn't know where does the name of this fund/forum come from).

queuebert 5y ago

Rust is now mature enough that subversives are using it.

chovybizzass 5y ago

not-an-aardvark is a legend

est31 5y ago

See also: https://blog.cuviper.com/2013/11/10/how-short-can-git-abbreviate/ https://blog.cuviper.com/2013/11/10/how-short-can-git-abbrev...

a-dub 5y ago

i wonder how git would break in the face of an actual sha-1 collision...

usr1106 5y ago
The second file is just not stored, because git thinks it's already there. Nothing complicated there. Discussed here: https://stackoverflow.com/questions/9392365/how-would-git-handle-a-sha-1-collision-on-a-blob https://stackoverflow.com/questions/9392365/how-would-git-ha... It costed 6500 CPU years to create the first collision containing a valid pdf document. Storing both versions into git still works, because git prepends a header before creating the SHA-1 of the blob. I believe because of that it is harder to create a git blob collision than a pdf collision. (I admit I did neither read very carefully nor try to think it through very seriously.)
swiftcoder 5y ago
On the other hand, if you are still running subversion, you pretty much lose the repo in this case: https://arstechnica.com/information-technology/2017/02/watershed-sha1-collision-just-broke-the-webkit-repository-others-may-follow/ https://arstechnica.com/information-technology/2017/02/water...
- COMMENT___ 5y ago
  This was fixed years ago.
  - swiftcoder 5y ago
    Where (years <= 4), sure. 2017 is not exactly ancient history.

curiousllama 5y ago

GitHub devops folks: edge case incoming in 3… 2… 1…