3 ms·

The most recent commit [1] which id has 13 leading zeroes is believed to be the lowest SHA-1 hash in Github in my cursory analysis. [1] https://github.com/seun

The most recent commit [1] which id has 13 leading zeroes is believed to be the lowest SHA-1 hash in Github in my cursory analysis. [1] https://github.com/seungwonpark/kudeki-chain/commit/00000000000004a9b86e267361898666ede4eaaa https://github.com/seungwonpark/kudeki-chain/commit/00000000...

OskarS 7y ago
That would be another fun version of this: “each commit is smaller/larger than the previous commit”
- xiphias2 7y ago
  It wouldn't be that much different as commiting is getting exponentially harder in both cases.
  - H8crilA 7y ago
    I think it would converge to a similar value rather quickly. Someone with access to fast hashing would vastly overtake the crowd and keep his #1 spot until a bigger fish appears.
  - hyperpallium 7y ago
    I must be missing something... how is higher (or lower) hash getting exponentially harder? For each extra leading 0, there are 1/16 as many hashes available as the previous one - so that is exponentially harder. But higher could be just by 1, and which is almost exactly the same difficulty... I guess, it would usually be randomly distribited in the remaining range, uniformly, so on average, the range would 1/2 as many each time. Which is also exponential (though, not as fast as 1/16). Is that the reasoning?
    - superkuh 7y ago
      average number of days before you find a given prefix ~= ((86,400 seconds in a day)(hashes per second))/(1/singlecharbit^num_prefix_chars)
    - bmurray7jhu 7y ago
      For growing hashes, we can limit the growth of the search complexity by choosing to accept a more constrained range of hashes in each iteration. Suppose H is an L-bit hash function and let H_n be the commit hash at the nth iteration. If we seek to generate H_n subject only to the constraint H_n+1 > H_n, the search complexity grows exponentially as you describe above. But suppose we search subject to the additional constraint H_n < H_n+1 < min(H_n + k, 2^L) for some constant k. So long as 2^L - H_n > k, the search complexity for H_n+1 is only dependent on the constant k and the number of bits of the hash function, L.
      - xiphias2 7y ago
        Sure, it works, but it doens't have the fun of the problem starting easy and getting harder over time. Setting k as sqrt(2^L-H_n) would be fun middle ground probably, though I'm lazy to analyze its properties.
      - hyperpallium 7y ago
        Heh, you made me consider if kudeki-chain also restricted the range (though not to a constant): One could read the title as exactly n leading zeros, but of course, it just means it has n leading zeros (that is, it may have more, too) - and the py code is implemented that way. So, for example, if you started with 16 leading zeros, it could be used for the first 16 commits. work = len(sha1) - len(sha1.lstrip('0')) ... assert commit_num <= work, "Not enough work done." https://github.com/seungwonpark/kudeki-chain/blob/master/manage.py https://github.com/seungwonpark/kudeki-chain/blob/master/man... BTW cute that assert is exactly appropriate for the ci tests, for determining whether it is accepted as a commit.
rwmj 7y ago
Do you work for github or is there some other way to view commit hashes across the whole of github? Also what happens if two unrelated git hashes collide on github?
- lifthrasiir 7y ago
  I have verified the fact via ghtorrent [1] when the previous commit (with 12 zeroes) was introduced (Korean tweet with a simple script [2]). However I haven't verified the current commit yet, hence the "cursory" analysis. On the git commit id collision, I don't know about the actual mitigation deployed in Github but they are certainly aware of the possibility [3]. [1] http://ghtorrent.org/ http://ghtorrent.org/ (Note that what I really used is a stripped down version with only commit ids, so this also contributes to a word "cursory" in my cursory analysis.) [2] https://twitter.com/senokay/status/1131826418340356096 https://twitter.com/senokay/status/1131826418340356096 [3] https://github.blog/2017-03-20-sha-1-collision-detection-on-github-com/ https://github.blog/2017-03-20-sha-1-collision-detection-on-...

OskarS 7y ago

That would be another fun version of this: “each commit is smaller/larger than the previous commit”

xiphias2 7y ago
It wouldn't be that much different as commiting is getting exponentially harder in both cases.
- H8crilA 7y ago
  I think it would converge to a similar value rather quickly. Someone with access to fast hashing would vastly overtake the crowd and keep his #1 spot until a bigger fish appears.
- hyperpallium 7y ago
  I must be missing something... how is higher (or lower) hash getting exponentially harder? For each extra leading 0, there are 1/16 as many hashes available as the previous one - so that is exponentially harder. But higher could be just by 1, and which is almost exactly the same difficulty... I guess, it would usually be randomly distribited in the remaining range, uniformly, so on average, the range would 1/2 as many each time. Which is also exponential (though, not as fast as 1/16). Is that the reasoning?
  - superkuh 7y ago
    average number of days before you find a given prefix ~= ((86,400 seconds in a day)(hashes per second))/(1/singlecharbit^num_prefix_chars)
  - bmurray7jhu 7y ago
    For growing hashes, we can limit the growth of the search complexity by choosing to accept a more constrained range of hashes in each iteration. Suppose H is an L-bit hash function and let H_n be the commit hash at the nth iteration. If we seek to generate H_n subject only to the constraint H_n+1 > H_n, the search complexity grows exponentially as you describe above. But suppose we search subject to the additional constraint H_n < H_n+1 < min(H_n + k, 2^L) for some constant k. So long as 2^L - H_n > k, the search complexity for H_n+1 is only dependent on the constant k and the number of bits of the hash function, L.
    - xiphias2 7y ago
      Sure, it works, but it doens't have the fun of the problem starting easy and getting harder over time. Setting k as sqrt(2^L-H_n) would be fun middle ground probably, though I'm lazy to analyze its properties.
    - hyperpallium 7y ago
      Heh, you made me consider if kudeki-chain also restricted the range (though not to a constant): One could read the title as exactly n leading zeros, but of course, it just means it has n leading zeros (that is, it may have more, too) - and the py code is implemented that way. So, for example, if you started with 16 leading zeros, it could be used for the first 16 commits. work = len(sha1) - len(sha1.lstrip('0')) ... assert commit_num <= work, "Not enough work done." https://github.com/seungwonpark/kudeki-chain/blob/master/manage.py https://github.com/seungwonpark/kudeki-chain/blob/master/man... BTW cute that assert is exactly appropriate for the ci tests, for determining whether it is accepted as a commit.

rwmj 7y ago

Do you work for github or is there some other way to view commit hashes across the whole of github? Also what happens if two unrelated git hashes collide on github?

lifthrasiir 7y ago
I have verified the fact via ghtorrent [1] when the previous commit (with 12 zeroes) was introduced (Korean tweet with a simple script [2]). However I haven't verified the current commit yet, hence the "cursory" analysis. On the git commit id collision, I don't know about the actual mitigation deployed in Github but they are certainly aware of the possibility [3]. [1] http://ghtorrent.org/ http://ghtorrent.org/ (Note that what I really used is a stripped down version with only commit ids, so this also contributes to a word "cursory" in my cursory analysis.) [2] https://twitter.com/senokay/status/1131826418340356096 https://twitter.com/senokay/status/1131826418340356096 [3] https://github.blog/2017-03-20-sha-1-collision-detection-on-github-com/ https://github.blog/2017-03-20-sha-1-collision-detection-on-...