Is there a formal proof that with N bits to iterate in the nonce of the block, a hash satisfying proof of work will be ever found?

How large that N (number of bits in the nonce) should be to satisfy proof of work in 10 years, 100 years?


No, however, the probability that a satisfactory hash will be found tends to 1 as N approaches infinity. Or, to speak imprecisely, you'll always find one eventually (just maybe not as soon as you'd hope).

Being a cryptographic hash, the output of SHA256 is similar to a pseudorandom number generator. It's not guaranteed that a random number generator will output a number meeting any given difficulty in any finite period of time (unless your difficulty can be defined so that every random number is valid), but you can make all sorts of accurate descriptions of what it will do on average.

This averaging is, of course, how the Bitcoin network is able to keep an average of about 10 minutes per confirmation in the face of a great many variables and unknowns.

Being that there's a maximum generally-accepted block size of 1MB, I suppose it is possible that some blocks are completely insoluble. For example, with N=1,048,576 (1024*1024) and the highest possible difficulty, requiring all zeroes in the hash: each attempt has a 1 in 2^256 probability of working. (let's assume you use up to the whole block for your nonce; maybe not quite realistic, but it's close enough) With 2^1048576 attempts, you'd probably expect something like 2^1048320 of them to succeed. But there is (if I did the math right) an e^-(2^1048320) probability that none of them will work. And it only gets smaller if you have a non-max difficulty. This number is incomprehensibly small, but is not quite 0.

| improve this answer | |
  • The key to understanding is that the hash is indeed a (pseudo)-random value. – alex Mar 14 '14 at 15:29

In addition to the 32-bit nonce in the block header, miners can also update the extraNonce of arbitrary length in the coinbase transaction to get a different merkelRoot, so that a proof of work hash can always be found.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.