Why is the probability of finding a winning nonce exactly the same for a new header and a header where you've already tried 1 billion nonces?

Question

I'm referring to this question: When do miners stop waiting for new transactions?

More specifically, this statement from the top answer:

"suppose you have a block header h1 on which you have already tried a billion nonce values, and a header h2 which has just been generated and on which no nonces have been tried yet. If you have the choice as to which one to hash next, which should you choose, for the greatest chance of finding a winning nonce? The answer is, it makes no difference - they both have exactly the same probability. So there is no harm in switching to h2"

I would have thought that the probability would be slightly higher for the first block (h1) as there are 1 billion nonces that you know do not succeed, i.e. fewer winning possibilities.

Complete newbie here and to the bitcoin world so apologies if I'm missing something obvious.

Answer 1

I would have thought that the probability would be slightly higher for the first block (h1) as there are 1 billion nonces that you know do not succeed, i.e. fewer winning possibilities.

Would you agree that every toss of a balanced coin has a 50% probability of coming up heads?

What about if you've previously flipped 9 heads in a row?

A coin has no memory of previous flips, nor does proof-of-work have any memory of previous failed nonces.

Here's a different scenario:

A fishbowl contains 1,000 pieces of paper. Onto 999 of them is printed "lose." On one of them is printed "win."

What's the probability of drawing "win" at the beginning of the game?

1/1,000

What's the probability of drawing "win" after the first unsuccessful round?

1/999

And so on. Your chances of winning improve with every round. The fishbowl has state, and that state carries over to the next round.

Hashing has no state. That's why the miner's chance of finding a proof-of-work on either h1 or h2 is equal.

Answer 2

I think I know the reason behind your confusion here. Here's my interpretation of your original question: "Out of the finite number of things whose combination is being hashed, all else being the same, the nonce is a 32-bit field with a constant number of possibilities: 2^32. Out of these possibilities, if 1 billion are already exhausted, why does it not mean that you'd have a higher probability of finding the 'correct' nonce using this block header as opposed to 'starting from scratch' using a different block header?"

The answer is that even if all the 2^32 possibilities for the nonce -- using a constant set of block header, timestamp, etc. -- were exhausted, it doesn't mean that one of the hashes you computed would satisfy the difficulty criterion; you might have to keep going by changing the transactions or timestamp and iterating over the nonce possibilities again.

Answer 3

I would have thought that the probability would be slightly higher for the first block (h1) as there are 1 billion nonces that you know do not succeed, i.e. fewer winning possibilities.

For every computation, you have the same probability of generating a valid block hash. Nothing you can do will change this, even if you try every possible nonce value for a given header. Nothing about what you find while testing nonces will tell you anything about what the next nonce value will return as output. Each guess does not get you ‘closer to the goal’, it is just a random chance.

Think of it like this:

• You have a six-sided die (numbered 1 to 6) that you know is fairly weighted. If you roll a 1, you get to make the next block! Every other roll does nothing.

• You roll the die ten times, and don’t get a 1 on any of the rolls.

• Now, on your eleventh roll, you are given the option to switch dice. You can replace the one you were rolling, with a new one that is otherwise the same (also six-sided, printed with 1−6, fairly weighted). Your choice.

What will give you the better odds of rolling a 1? The answer is: it doesn’t matter. The fact that the first die didn’t roll a 1 yet doesn’t influence what the next roll will be. The same goes for the replacement die. Just because it hasn’t been rolled yet, doesn’t make it any more likely to be a 1 (or any other number).

Answer 4

One of the properties we want from cryptographic hash functions (CHF) is that their output looks like random data as much as possible. In particular, when putting two similar messages like header + nonce and header + nonce+1 through a CHF, their digests should not be in anyway more related than two completely unrelated inputs.

If the outputs of SHA256 were to follow some pattern, you would be able to get closer to a solution. This would allow the miner with the most hashrate to win more often than their share of the hashrate. Instead, we want mining to be progress-free: every hashing attempt should have an equal minuscule chance of winning.

It's therefore good that the only way to "predict" the digest of any blocktemplate + nonce is to perform the hash, and therefore, we can think of each hashing attempt as an independent random event—regardless of whether you've tried similar inputs before. (Although the same input will obviously have the same outcome and you'd be duplicating work.)

Let's also look at the magnitudes of the search spaces involved:

The nonce space is 32 bits, i.e. allows for 2³² = 4,294,967,296 different values. The hashrate today is about 175 EH/s, which means that about one in every 175×10¹⁸ H/s × 600 s = 1.05×10²³ H hashing attempts finds a valid block. So clearly, there is not a winning nonce for every block template, in fact, miners exhaust a complete nonce space about 4.07×10¹⁰ times per second.