Maybe there is a possibility to discard unfitting hashes early?

[W-M]

I do not understand cryptographic hashes,especially SHA-256 enough to be an expert on the subject. This is why I would like the opinion(telling me I'm wrong or right) of someone who does fully understand the SHA-256 algorithm and how it is implemented in the Bitcoin Protocol.


The difficulty in Bitcoin Mining is determined by the amount of zero's at the start of a hash. Of course, most elements of the hash influence eachother, but wouldn't it mean a huge increase in mining speed if we could figure out when a hash will turn out not to fit the difficulty?

As far as I know, the SHA-256 algorithm is built from right-to-left(Little Endian to Big Endian): The higher characters are dependent on the lower ones (By using: Higher = Higher + Lower % 2^32) but it does not seem to be the other way around.

This means that whenever we find out that at a certain spot above the difficulty treshold there wont be a zero in the final hash, we can discard this hash and instead move on to the next hash.


Does this make sense? Or did I miss something crucial?

~W-M

[stillfire]

As far as I know, the SHA-256 algorithm is built from right-to-left(Little Endian to Big Endian): The higher characters are dependent on the lower ones (By using: Higher = Higher + Lower % 2^32) but it does not seem to be the other way around.

The SHA-256 is not built from right to left. An important part of a hashing algorithm is "mixing", where input "lines" are crossed left and right so they end up connecting to other output "lines". So if (simplified) bit 0 of the input is a 1 this might cause bit 129 of the output to be 0.

If this was all there was to it, it would be easy to build an algorithm that quickly ruled out unsuitable inputs. But in addition to this, the actual "direction" the bits "move" through the system is controlled by the other bits of the input. So (again simplified) we might see that if input bit 0 is a 1, and input bit 7 is a 1, bit 129 might be 0. But if input bit 7 is a 0, instead bit 201 becomes a 0 and bit 129 is unaffected.

This process is repeated on its own output over and over, until finally you have a situation where there are as many "maps" describing how each 1 input bit affects 1 output bit as there are combinations of other bits in the input. The number of possible maps is Very Large.

As you get closer and closer to the final iteration of the hash, the number internal bit states for which the final output can start with a 0 is rapidly falling off. However the "mathematical equation" for whether we'll have a leading 0 or not, which we could use to test whether we should abort the hash attempt early, is too complex and too slow to evaluate to be worth it. It's faster to just finish the hashing attempt.

[Sukrim]

There are a few operations at the end that can be omitted as far as I understand, mining software does this already for years now though.

The problem is it takes very long until you really know or can at least reasonably guess that indeed there will be no 0 or a lot of 0s at a certain part of the hash.

[W-M]

Thank you very much for your replies. I guess that makes sense. I must have misread about the SHA256 algorithm somewhere, as I did not know that much mixing was involved.

Thank you!