In Bitcoin, what happens if there is no viable nonce?

Question

I'm assuming SHA is perfectly uniform.

In bitcoin, there are $2^{32}$ possible inputs per block, which are mapped to $2^{256}$ possible outputs. So there is a $1/2^{224}$ chance that any randomly picked 256-bit string is a possible output hash of one of the possible nonce values. So that means there are $2^{32}$ possible output 256-bit strings. In other words, a 1-to-1 mapping from nonce to output is very likely.

The $2^{32}$ possible outputs are distributed uniformly. So that means half of them have a 0 in the first bit, and the other half have a 1. That means there are $2^{31}$ possible outputs with a 0 in the first bit. Each leading 0 bit reduces the number possible outputs by half. So with 76 leading zero bits (the current difficulty), there's a $1/2^{44}$ chance that there exists a acceptable nonce.

Another way to see it is that there is a $1/2^{76}$ chance that any nonce is accepted. But there are $2^{32}$ possible nonce values. So the probability that none of those nonces are acceptable would be $(1-1/2^{76})^{2^{32}}$ which equals $1/2^{44}$.

Either way you look at it, there's an extremely small chance that any 32-bit nonce will work.

So what happens if there are no acceptable nonces?

Answer 1

It's important to note that the block hash is over the entire block header, which contains:

• Block Version
• Nonce
• Previous block hash
• Timestamp
• Merkle Root
• nBits

Of these, only the nBits and previous block hash are fixed - all of the others can be manipulated to alter the hashed data at will.

Once all 32 bits of the nonce value have been exhausted (which happens extremely fast on ASICs), miners will simply alter the timestamp, block version, or merkle root (by altering the coinbase transaction or changing their list of selected transactions/their ordering), allowing them to try a new block header with the entire nonce space again.

These alterations are repeated until some combination of the above produces a valid block hash.