4 ms·

What happens when the shortened version becomes ambiguous? For instance that's commit 9e02977bfad006af328add9434c8bffa40e053bb. What happens when someone crea

by faho 4y ago

What happens when the shortened version becomes ambiguous? For instance that's commit 9e02977bfad006af328add9434c8bffa40e053bb. What happens when someone creates a commit and that happens to have 9e02977bfa-e-something? I'm not even sure what github does here. Does it just refuse to select a commit or give you a list of candidates and you have to check the date (given that your link presumably was unambiguous when you wrote it)?

anamexis 4y ago
With a 10 digit hash like that, collisions are already extremely unlikely, on the order of 1 in a trillion.
- CodesInChaos 4y ago
  Most repositories contain more than 2 commits.
  - anamexis 4y ago
    Fine, 3 in a trillion.
    - CodesInChaos 4y ago
      You're right that the chance that two specific 10 digit hashes collide is 1 in a trillion. But the chance of a collision between a specific commit and any other commit goes up linearly, so for the Linux repository it's about 1 million / 1 trillion so 1 in a million. The chance of a collision between a any two commits goes up quadratically (while it's small), and becomes ~50% when you reach the square-root of 1 trillion, i.e. 1 million. So there is a good chance the Linux repository already contains colliding 10 digit hashes, and if they don't exist yet, it'll likely happen during the next couple of years.
      - faho 4y ago
        What you are alluding to is the "Birthday problem". https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
      - anamexis 4y ago
        Yes, there is a good chance there is already a 10 digit hash collision in the Linux repository. But if you pick an arbitrary commit to cite in a research paper, it's still 1 in a million that that particular commit has a collision. And this is for a repo which has to be in the 99.999th percentile of number of commits.
- faho 4y ago
  The linux kernel had 3 of those, in 2013: https://blog.cuviper.com/2013/11/10/how-short-can-git-abbreviate/ https://blog.cuviper.com/2013/11/10/how-short-can-git-abbrev... By now it's up to at least 7 (going by my clone of 5.12-rc1 that I had lying around), and it's becoming more likely. Those collisions happened with objects other than commits (of which there are more), but that's by no means guaranteed.
madsbuch 4y ago
You can do the math and calculate risk of collisions. And then put that in relation to the context: It is a single repository, probably with very few commits since it is research and not a highly active commercial product. You could probably cut the commit hash to 4 characters and still not have collisions for this application (ie. 1 / 65536 chance of collision @ 4 characters), or even fewer
- faho 4y ago
  That's assuming researches would only link to research repositories, instead of doing research on actual applications - including massive things like the linux kernel.
bhaak 4y ago
GitHub only parses commit hashes with at least 7 characters. IIRC I read somewhere that this was considered a safe lower boundary but my googlefu couldn't come up with a site that shows the math. The chances of a hash collision by chance with 10 characters are basically impossible (unless sha1 is broken further and it's a malicious repository). The master branch of the linux kernel has a little bit over 1 million commits (measured with git log --format=oneline | wc -l). With "git log --format=oneline | cut -b 1-4 | uniq -c | sort -n | tail -n30" you can verify that it has 25 prefix collisions with a 4 character prefix. With 5 it's still 4 collisions, with 6 there are none.
- faho 4y ago
  >The master branch of the linux kernel has a little bit over 1 million commits (measured with git log --format=oneline | wc -l). The master branch is irrelevant - github links to commits don't include the branch (and the way git works, commits don't really have "a branch"): https://github.com/torvalds/linux/commit/ac632c504d0b881d7cfb44e3fdde3ec30eb548d9 https://github.com/torvalds/linux/commit/ac632c504d0b881d7cf... >With "git log --format=oneline | cut -b 1-4 | uniq -c | sort -n | tail -n30" you can verify that it has 25 prefix collisions with a 4 character prefix. With 5 it's still 4 collisions, with 6 there are none. I'm sorry to say, your script doesn't work. You need to `sort` before `uniq` as that only counts adjacent duplicates. The linux kernel as of 5.12-rc1 had 25 prefix collisions for the prefix "ffeb" alone (and 33 for "e3f2"). Here are the full shas: ffeb03cfe2b49b73da7b325a31714003761fc6d5 ffebecd9d49542046c5ecbb410af01e016636e19 ffeb1e9e897b8d36b197275592d121c96d3bdb95 ffebbecaaa86f7cde4a6a813bed14f9d56e7c373 ffeb595d84811dde16a28b33d8a7cf26d51d51b3 ffebbaedc8616cffe648202e364dce6a045d65a2 ffebe74b7c95a41d2d0ac70a44d410e0efa37ad8 ffebc8c0344934db710afc76e3bfda11a823bb3d ffebb83b34f843aadcbd3e03c4e449da14d0870d ffeb6437f018f072a330ad5911036fd020b35ac3 ffeb883e5662e94b14948078e85812261277ad67 ffebf5f391dfa9da3e086abad3eef7d3e5300249 ffebfc364dcaa5dea1a589d42207834b028df789 ffeb13aab68e2d0082cbb147dc765beb092f83f4 ffebeb46dd34736c90ffbca1ccb0bef8f4827c44 ffeb40515971c9860ff671bb074689db15e18831 ffebad7948ee0e9c619ae6e87d99437d907fc7e3 ffeb501c6cba803eefc46b570feccffe61a6d883 ffeb33d20c6217bb8f0ab46d3f1396021c00c24f ffeb80fc30acbf6bd51cb47a1815f621a9d017dc ffeb414a59291d5891f09727beb793c109f19f08 ffebedb7ab3f7964a70a1771547b26af38a189d2 ffebabe0bf0de9ee500d4605d6acb71e1ee3b79f ffeb9ec72e18e16d0b0835d959cdf01650758638 ffeb874b2b893aea7d10b0b088e06a7b1ded2a3e with 5 characters there are 8 for b91e1. With 6 characters there are 5 for 120bda: 120bdafaece72056e48d97809c5abe172824a7f6 120bdac7376a36418eb1d55e0161dc0e660a45c3 120bdaa47cdd1ca37ce938c888bb08e33e6181a8 120bda35ff8514c937dac6d4e5c7dc6c01c699ac 120bda20c6f64b32e8bfbdd7b34feafaa5f5332e and a total of 28606 colliding 6-digit prefixes. There are 9 colliding 9-digit prefixes and no 10-digit prefix. (found with `git rev-list --all --no-abbrev-commit | sort | cut -b 1-4 | uniq -c` and variations on that theme)

by faho 4y ago

anamexis 4y ago

With a 10 digit hash like that, collisions are already extremely unlikely, on the order of 1 in a trillion.

CodesInChaos 4y ago
Most repositories contain more than 2 commits.
- anamexis 4y ago
  Fine, 3 in a trillion.
  - CodesInChaos 4y ago
    You're right that the chance that two specific 10 digit hashes collide is 1 in a trillion. But the chance of a collision between a specific commit and any other commit goes up linearly, so for the Linux repository it's about 1 million / 1 trillion so 1 in a million. The chance of a collision between a any two commits goes up quadratically (while it's small), and becomes ~50% when you reach the square-root of 1 trillion, i.e. 1 million. So there is a good chance the Linux repository already contains colliding 10 digit hashes, and if they don't exist yet, it'll likely happen during the next couple of years.
    - faho 4y ago
      What you are alluding to is the "Birthday problem". https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
    - anamexis 4y ago
      Yes, there is a good chance there is already a 10 digit hash collision in the Linux repository. But if you pick an arbitrary commit to cite in a research paper, it's still 1 in a million that that particular commit has a collision. And this is for a repo which has to be in the 99.999th percentile of number of commits.
faho 4y ago
The linux kernel had 3 of those, in 2013: https://blog.cuviper.com/2013/11/10/how-short-can-git-abbreviate/ https://blog.cuviper.com/2013/11/10/how-short-can-git-abbrev... By now it's up to at least 7 (going by my clone of 5.12-rc1 that I had lying around), and it's becoming more likely. Those collisions happened with objects other than commits (of which there are more), but that's by no means guaranteed.

madsbuch 4y ago

You can do the math and calculate risk of collisions. And then put that in relation to the context: It is a single repository, probably with very few commits since it is research and not a highly active commercial product. You could probably cut the commit hash to 4 characters and still not have collisions for this application (ie. 1 / 65536 chance of collision @ 4 characters), or even fewer

faho 4y ago
That's assuming researches would only link to research repositories, instead of doing research on actual applications - including massive things like the linux kernel.

bhaak 4y ago

GitHub only parses commit hashes with at least 7 characters. IIRC I read somewhere that this was considered a safe lower boundary but my googlefu couldn't come up with a site that shows the math. The chances of a hash collision by chance with 10 characters are basically impossible (unless sha1 is broken further and it's a malicious repository). The master branch of the linux kernel has a little bit over 1 million commits (measured with git log --format=oneline | wc -l). With "git log --format=oneline | cut -b 1-4 | uniq -c | sort -n | tail -n30" you can verify that it has 25 prefix collisions with a 4 character prefix. With 5 it's still 4 collisions, with 6 there are none.

faho 4y ago
>The master branch of the linux kernel has a little bit over 1 million commits (measured with git log --format=oneline | wc -l). The master branch is irrelevant - github links to commits don't include the branch (and the way git works, commits don't really have "a branch"): https://github.com/torvalds/linux/commit/ac632c504d0b881d7cfb44e3fdde3ec30eb548d9 https://github.com/torvalds/linux/commit/ac632c504d0b881d7cf... >With "git log --format=oneline | cut -b 1-4 | uniq -c | sort -n | tail -n30" you can verify that it has 25 prefix collisions with a 4 character prefix. With 5 it's still 4 collisions, with 6 there are none. I'm sorry to say, your script doesn't work. You need to `sort` before `uniq` as that only counts adjacent duplicates. The linux kernel as of 5.12-rc1 had 25 prefix collisions for the prefix "ffeb" alone (and 33 for "e3f2"). Here are the full shas: ffeb03cfe2b49b73da7b325a31714003761fc6d5 ffebecd9d49542046c5ecbb410af01e016636e19 ffeb1e9e897b8d36b197275592d121c96d3bdb95 ffebbecaaa86f7cde4a6a813bed14f9d56e7c373 ffeb595d84811dde16a28b33d8a7cf26d51d51b3 ffebbaedc8616cffe648202e364dce6a045d65a2 ffebe74b7c95a41d2d0ac70a44d410e0efa37ad8 ffebc8c0344934db710afc76e3bfda11a823bb3d ffebb83b34f843aadcbd3e03c4e449da14d0870d ffeb6437f018f072a330ad5911036fd020b35ac3 ffeb883e5662e94b14948078e85812261277ad67 ffebf5f391dfa9da3e086abad3eef7d3e5300249 ffebfc364dcaa5dea1a589d42207834b028df789 ffeb13aab68e2d0082cbb147dc765beb092f83f4 ffebeb46dd34736c90ffbca1ccb0bef8f4827c44 ffeb40515971c9860ff671bb074689db15e18831 ffebad7948ee0e9c619ae6e87d99437d907fc7e3 ffeb501c6cba803eefc46b570feccffe61a6d883 ffeb33d20c6217bb8f0ab46d3f1396021c00c24f ffeb80fc30acbf6bd51cb47a1815f621a9d017dc ffeb414a59291d5891f09727beb793c109f19f08 ffebedb7ab3f7964a70a1771547b26af38a189d2 ffebabe0bf0de9ee500d4605d6acb71e1ee3b79f ffeb9ec72e18e16d0b0835d959cdf01650758638 ffeb874b2b893aea7d10b0b088e06a7b1ded2a3e with 5 characters there are 8 for b91e1. With 6 characters there are 5 for 120bda: 120bdafaece72056e48d97809c5abe172824a7f6 120bdac7376a36418eb1d55e0161dc0e660a45c3 120bdaa47cdd1ca37ce938c888bb08e33e6181a8 120bda35ff8514c937dac6d4e5c7dc6c01c699ac 120bda20c6f64b32e8bfbdd7b34feafaa5f5332e and a total of 28606 colliding 6-digit prefixes. There are 9 colliding 9-digit prefixes and no 10-digit prefix. (found with `git rev-list --all --no-abbrev-commit | sort | cut -b 1-4 | uniq -c` and variations on that theme)