3 ms·

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.

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.