3

Just to put a cap, let’s say in 1 million blocks, what is the chance that 2 blocks will share the same nonce value? Has it happened before?

7

Assuming that nonces are randomly distributed (which they should be) and after 1 million blocks that no blocks have the same nonce, the probability of the next block having the same nonce as a block that has already been mined is 1000000/4294967296 = 0.000233, so very low. However as more blocks are being mined, the probability increases. Once there are 4294967296 blocks, the probability of a block sharing a nonce with a different block is guaranteed.

The reasoning for 4294967296 is because the nonce is a 32-bit integer so there are 2^32 possible nonces which is 4294967296.

However, the probability of any 2 blocks having the same nonce is 1/65536 due to the birthday paradox.

There currently have been multiple pairs of blocks that have the same nonce. Some are listed below:

Nnoce: 68229731, blocks [9459, 35238]
Nnoce: 3147243286, blocks [19411, 71181]
Nnoce: 2811235843, blocks [42202, 110904]
Nnoce: 61366272, blocks [100255, 171713]
Nnoce: 74571595, blocks [37187, 176000]
Nnoce: 22876413, blocks [22460, 188416]
Nnoce: 131829089, blocks [40784, 203153]
Nnoce: 2962306894, blocks [136018, 216500]
Nnoce: 3947837747, blocks [222990, 227103]
Nnoce: 194800186, blocks [36506, 243089]
Nnoce: 1388988687, blocks [108366, 251694]
Nnoce: 922984712, blocks [245295, 260005]
Nnoce: 4133916719, blocks [176525, 276110]
Nnoce: 3890141599, blocks [213608, 292419]
Nnoce: 876374308, blocks [18857, 317190]
Nnoce: 70651752, blocks [238831, 322634]
Nnoce: 2359983768, blocks [112651, 325309]
Nnoce: 3421780225, blocks [95525, 328515]
Nnoce: 3787474772, blocks [187117, 346581]
Nnoce: 3956410682, blocks [10506, 350632]
Nnoce: 2756846708, blocks [117891, 355889]
Nnoce: 158953652, blocks [305592, 368094]
Nnoce: 2660238194, blocks [257198, 371219]
Nnoce: 2774929041, blocks [112737, 413142]
Nnoce: 2335903164, blocks [379609, 436786]
Nnoce: 64632759, blocks [60105, 443347]
Nnoce: 2469851573, blocks [225526, 448132]
Nnoce: 84018796, blocks [78009, 453373]
Nnoce: 1935967937, blocks [436055, 454540]
Nnoce: 2900822784, blocks [144802, 457849]
Nnoce: 2434589573, blocks [102268, 467087]
Nnoce: 2965485942, blocks [366411, 481531]
Nnoce: 18390814, blocks [68360, 506618]
Nnoce: 433452460, blocks [157144, 513320]
  • 2
    Actually, because of the birthday paradox, it is overwhelmingly likely that there have been two blocks with the same nonce. With the 500000 blocks so far, if I'm calculating right, the probability is at least 0.999999999999. I'll check the actual values and post an answer. – Nate Eldredge Apr 14 '18 at 3:17
  • Ah, right. The probability of any 2 blocks having the same nonce is 1/2^16 due to the birthday paradox. – Andrew Chow Apr 14 '18 at 3:22
  • The probability that any given pair of blocks have the same nonce is 1/2^32. But there have been roughly 500000^2 pairs of blocks, which is much greater than 2^32. So the expected number of matching pairs so far is 500000^2/2^32 = 58. – Nate Eldredge Apr 14 '18 at 3:28
  • @AndrewChow Ah i see, you initially were calculating the chance of a nonce being shared with any other nonce, not any nonce having a pair with another nonce. The birthday paradox works nicely here, could it be used to predict future nonces? – Childishforlife Apr 16 '18 at 15:25
  • No, the birthday paradox cannot be used to predict which values will collide. – Andrew Chow Apr 16 '18 at 15:31
2

With probability, it is usually easier to find the negative case and subtract from 1.

So what are the chances of dice rolls being unique?

One roll unique:
1

One roll at least one clash:
1 - 1 = 0

Two rolls unique:
1 * 5/6 (only 5 numbers left)

Two rolls at least one clash:
1 - 1 * 5/6

Three rolls unique:
1 * 5/6 * 4/6

Three rolls at least one clash:
1 - 1 * 5/6 * 4/6

So for 32 bit nonces:

1 - 1
1 - 1 * (2^32 - 1)/2^32
1 - 1 * (2^32 - 1)/2^32 * (2^32 - 2)/2^32

So for 500K in 2^32 I wrote this:

var uniqueChance = 1.toDouble()
val max: Double = 4_294_967_296.toDouble()
for (i in 1..500000) {
    uniqueChance *= (max - i) / max
}
println("Chance of unique $uniqueChance")
println("Chance of at least one duplicate ${1 - uniqueChance}")

Which gives:

Chance of unique 2.2900830840065387E-13
Chance of at least one duplicate 0.999999999999771

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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