I am a bit confused. Why would this process need to be continually re-done? Once you have generated all the hashes of numbers less than 256 bits long, then you instantly (up to the speed of accessing the database entry) know a short preimage for every hash value.
That’s not the idea. The computational problem is simply a proof of work—you create a specific, verifiable string, with a changeable component greater than 256 bits, then hash that string using incrementing values until you find a SHAsum less than a certain value. Knowing a random, short preimage for each possible hash doesn’t help you there, because those will not allow you to create a verifiable string with the correct hash.
Once you have generated all the hashes of numbers less than 256 bits long, then you instantly (up to the speed of accessing the database entry) know a short preimage for every hash value.
Generating all those hashes and storing them? Good luck. 2^256 is about 10^77. For comparison there are on the order of 10^50 atoms on Earth. There’s no way you are making a look-up table for every number less than 256 bits.
Rainbow tables allow you to choose a tradeoff between storage and speed. So if you wanted to do that (which is of course unrelated to Bitcoin), the actual constraint is: (table size) * (number of hash calls to invert one hash value) = 2^256.
So, if you magically transformed the Earth into a giant rainbow table that uses N atoms to store a key value pair, you would have to perform N*10^27 hash calls to invert one hash value. Not very useful in this case.
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.
I am a bit confused. Why would this process need to be continually re-done? Once you have generated all the hashes of numbers less than 256 bits long, then you instantly (up to the speed of accessing the database entry) know a short preimage for every hash value.
That’s not the idea. The computational problem is simply a proof of work—you create a specific, verifiable string, with a changeable component greater than 256 bits, then hash that string using incrementing values until you find a SHAsum less than a certain value. Knowing a random, short preimage for each possible hash doesn’t help you there, because those will not allow you to create a verifiable string with the correct hash.
Generating all those hashes and storing them? Good luck. 2^256 is about 10^77. For comparison there are on the order of 10^50 atoms on Earth. There’s no way you are making a look-up table for every number less than 256 bits.
Rainbow tables allow you to choose a tradeoff between storage and speed. So if you wanted to do that (which is of course unrelated to Bitcoin), the actual constraint is: (table size) * (number of hash calls to invert one hash value) = 2^256.
So, if you magically transformed the Earth into a giant rainbow table that uses N atoms to store a key value pair, you would have to perform N*10^27 hash calls to invert one hash value. Not very useful in this case.
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.