Having read the basics of mining and this about SHA256 (probabilistic?) partial preimage possible? and SAT solving - An alternative to brute force bitcoin mining, I have the following question:
Wouldn't it be better to select a random nonce instead of incrementing the first by one? This way, the miner would make use of the birthday attack, which would make the probabilities of finding it higher (for a given number of trials).
I'm not sure that my understanding is correct.
Wouldn't it be better to select a random nonce instead of incrementing the first by one?
This is often thought of by people who read (or understand) only a garbled version of the original Satoshi paper/design. I'm surprised it seems not to be a dupe here, although it is crossdupe in bitcoin.SX where it is more ontopic:
https://bitcoin.stackexchange.com/questions/80752/why-is-the-nonce-bruteforced-from-0-to-n-while-mining
https://bitcoin.stackexchange.com/questions/78214/how-are-nonces-decided-in-mining
and nearly https://bitcoin.stackexchange.com/questions/41949/what-is-the-precise-nonce-finding-protocol
Put more technically, if miners are racing to find a nonce which makes a particular block header hash to below the target, doesn't it duplicate work to have them all try the same sequence and/or wouldn't at least some do better using different starting points (or sequences)? On that premise, yes it would be better, but that premise is wrong in several ways.
First, even in the original design, independent miners (the only kind Satoshi imagined) don't try to find a nonce for the same block. Miners are incented by receiving a reward for 'solving' a block, and that reward is encoded as a 'coinbase' transaction, which is the first transaction in the block, and thus contributes to the Merkle hash tree root in the block header. Different miners thus use different block headers and even if they all search the same nonce space from 0 to 232-1 they are searching different hash inputs.
Second, since mining became competitive, and especially since it moved to GPUs and then ASICs, mining doesn't really consist of "find a (or the) nonce for a block making it satisfy the difficulty/target". At difficulty significantly more than 1 (and it's currently in the trillions), most possible and attempted blocks are not satisfied by any nonce value. Instead mining consists of "find a block, and particularly an extranonce in coinbase, for which any nonce satisifies the current difficulty/target, and use that nonce". Over 99.999999% of atttempted blocks are losers, and to determine a block is a loser the miner must try all 232 nonces, which takes the same work regardless of the sequence tried.
For pool mining, which has now become popular, there are multiple miners seeking the same reward (i.e. one paid to the pool), and in that case the pool manager does allocate different extranonce ranges to members to avoid duplication and increase the probability that the pool as a whole (though not any specific miner) wins. Since members must communicate with the manager anyway in order to earn rewards for partial solutions, there is no need or benefit of distributed random choice over centralized deterministic choice.
This way, the miner would make use of the birthday attack, which would make the probabilities of finding it higher (for a given number of trials).
Bitcoin mining is not a birthday problem at all. Starting at different points or using different sequences of trials is not a birthday attack, and does not on average improve a birthday attack. It can improve competitive performance in some cases, but as described above none of those cases apply to Bitcoin mining.
