Quote from: Sukrim on May 25, 2011, 12:51:08 AM

Think of a hash as a much more complicated sum of digits:

1337 --> 14

I now can easily verify that 1+3+3+7 = 14

However, I can NOT say if this 14 is derived from 95, 1733, 842, 7700000 or any other number that happens to have a sum of digits equaling 14.

That's entirely true, and is relevant for most applications of cryptographic hash functions. But in this case, we have that nonce value that is completely open to us, and we're only trying to find any one hash among a huge number of acceptable hashes.

For a simplistic example, consider our hash function to be the sum of digits as above, but keep taking the sum of digits until only one digit remains. 1337 -> 14 -> 5, 983542 -> 31 -> 4, 183954235098345 -> 69 -> 15 -> 6.

Now say that we want to get a hash that is 9; that is, we're setting the difficulty such that only roughly one in nine streams of digits will be accepted. We then take some content that is known, add a couple of nonce digits to the beginning of the known stream of digits, and generate the hash to find out if it is accepted. That's the essence of the current process used by miners. For the given hash function and difficulty, we'd need to perform on average 9 hashes with random 2-digit nonces before finding a match.

But Peter proposes the following: Let's assume that our hash is 9, since in the end that's what it'll have to be anyway. Now say we're trying to hash ??8645, where ?? are the two nonce digits. We can reverse this in the following manner: We know that the given digits add up to 23, which will then add up to 5. We can then see that we're 4 short, so if our two nonce digits contributed four more, we'd have our hash. So we choose our nonce to be 13 and end up with 138645 -> 27 -> 9. We've found a nonce that produces an acceptable hash in roughly the time it takes to do just a single hash, rather than having to do on average 9 hashes. (Even in this case it's probably more complicated than the specific example I picked, but I'm still pretty sure it would be proportional to the time complexity of a single hash, and would be independent of the difficulty intended by limiting the range of acceptable hashes.)

Given the much higher rarities of randomly finding an acceptable hash in the current Bitcoin mining environment, if that could be reduced down to anything even remotely close to being proportional to the time it takes to perform a single hash, that would completely ruin the whole point. But offhand I don't know if it's actually feasible, given modern day cryptographically strong hash algorithms, to take an assumed hash and a mostly known stream of content, and then reverse the process to find out what the small unknown bit of content needs to be to "solve the equation". Seeing as how the process is substantially different from what is typically considered within the field of cryptography however, I wouldn't be surprised if the Bitcoin situation provides significantly weaker security than is currently presumed.