I have a string s and I need to calculate a nonce such that when appending the nonce to the string, the generated hash starts with a given sequence. The hash has 256 bits, so the number of combinations is 2^256. If I set the constraint that a hash begins with two zeroes, then the expected number of tries (each time generating a random nonce) is 4 (1/2 * 1/2 probability) attempting to find a hash that begins with two zeroes.
The way that I am generating the nonce is random. For example, if I set the length of nonce to be 10 bits, then I randomly choose from 2^10 possible combinations each time.
My question is whether there is an ideal length of nonce such that it is not too big (to save computation time), but also it is not too small to avoid collisions, meaning randomly generating the same nonce twice (birthday paradox).