Then what method do the Bitcoin users use to find the (sufficiently short) preimage of the hash values they are working, if indeed the problemspace is that big and sha256 is designed so that the mapping from the output to the input is as complex as possible?
And is it possible for a user to generate Bitcoins faster by discovering a better algorithm for inverting sha256 hashes?
I thought that’s what the proof of work entailed. As User:nshepperd put it:
As I understand it, the problem is finding bit strings with a sha256 hash whose (256-bit) numerical value is less than a certain number. In addition, part of what goes into the bit string is the bitcoin address of the person who will keep the newly generated coins.
As best I can tell, it sounds like there some has value, and you must find an inverse (preimage) for it that meets certain criteria (like being less than a certain value). So doesn’t the problem involve finding hash inverses as the proof of work? Or at least computing a huge number of hashes until one is found that matches a target hash?
Oh, so it’s the hash itself that must be less than a specific value, not the preimage of the hash. Still, that can be rephrased as “inverting any one of the hashes that are below a certain value”, which is why I kept mapping it to a hash inversion problem.
And the only known way to do this is to try a large number of bitstrings and see what their hashing yields? Is there a known way to more efficiently search by looking what what bitstrings are likely to have hashes with zeroes in the most significant digits? Could someone improve performance by finding such a method?
Hashcodes do not have unique inverses. The goal is not just to find any bitstring with a haschcode in the target interval (in which case the solutions would be trivially reusable), but to find such a bitstring that contains information, including a hashcode of the previous block (so you can’t get a head start before that block is computed) and transactions to be recorded (so your block is actually useful to the community).
Oh, so it’s the hash itself that must be less than a specific value, not the preimage of the hash. Still, that can be rephrased as “inverting any one of the hashes that are below a certain value”, which is why I kept mapping it to a hash inversion problem.
Yes, but much easier. Let’s say for example, that you want the first 3 digits of your hash to be zero. Then if the hashes are randomly distributed (and they should be) such a hash will occur once every 1000 hashes. In contrast, trying to invert a specific hash is much more difficult.
And the only known way to do this is to try a large number of bitstrings and see what their hashing yields? Is there a known way to more efficiently search by looking what what bitstrings are likely to have hashes with zeroes in the most significant digits? Could someone improve performance by finding such a method?
If there were a way to quickly figure out which hashes have a lot of zeros that would probably be close to making the hash cryptographically broken. Finding such a method isn’t the same as finding collisions but it is in the same class of general results. I don’t know the exact details of the process used but I’d be surprised if there were any known way of approaching this other than direct computation.
Then what method do the Bitcoin users use to find the (sufficiently short) preimage of the hash values they are working, if indeed the problemspace is that big and sha256 is designed so that the mapping from the output to the input is as complex as possible?
And is it possible for a user to generate Bitcoins faster by discovering a better algorithm for inverting sha256 hashes?
I must be missing something. Why do you think they are inverting the hashes?
I thought that’s what the proof of work entailed. As User:nshepperd put it:
As best I can tell, it sounds like there some has value, and you must find an inverse (preimage) for it that meets certain criteria (like being less than a certain value). So doesn’t the problem involve finding hash inverses as the proof of work? Or at least computing a huge number of hashes until one is found that matches a target hash?
If I’m reading this correctly you don’t need a specific hash result, just a hash that is less than a specific number. That’s much easier to find.
Oh, so it’s the hash itself that must be less than a specific value, not the preimage of the hash. Still, that can be rephrased as “inverting any one of the hashes that are below a certain value”, which is why I kept mapping it to a hash inversion problem.
And the only known way to do this is to try a large number of bitstrings and see what their hashing yields? Is there a known way to more efficiently search by looking what what bitstrings are likely to have hashes with zeroes in the most significant digits? Could someone improve performance by finding such a method?
Hashcodes do not have unique inverses. The goal is not just to find any bitstring with a haschcode in the target interval (in which case the solutions would be trivially reusable), but to find such a bitstring that contains information, including a hashcode of the previous block (so you can’t get a head start before that block is computed) and transactions to be recorded (so your block is actually useful to the community).
Yes, but much easier. Let’s say for example, that you want the first 3 digits of your hash to be zero. Then if the hashes are randomly distributed (and they should be) such a hash will occur once every 1000 hashes. In contrast, trying to invert a specific hash is much more difficult.
If there were a way to quickly figure out which hashes have a lot of zeros that would probably be close to making the hash cryptographically broken. Finding such a method isn’t the same as finding collisions but it is in the same class of general results. I don’t know the exact details of the process used but I’d be surprised if there were any known way of approaching this other than direct computation.