4 ms·
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 a
by 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 agoSure, 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 agoHeh, 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.