3 ms·

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

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.

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.