pull down to refresh

1331 sats \ 1 reply \ @shafemtol 17 Dec \ on: [Bitcoin Puzzle] Probability of private key collisions, part 1 bitcoin
  1. Derive a formula for the probability of a private key collision (2 or more private keys are the same), in terms of and .
This is what's known as the birthday problem.
For two private keys, the probability of the two not colliding is . If they are not colliding, then for a third key, the probability of it not colliding with one of the two existing keys is . For keys, the probability of no collision is:
where is the factorial of K and is the binomial coefficient.
The probability of a private key collision is the complement of this:
Due to the large and the use of factorial and binomial coefficient, this quickly becomes impossible to compute as grows, long before can even be represented as anything less than 1.0 in a standard 64-bit float.
For , as will be the case here, a very good approximation is:
This is because for . More details on deriving this approximation can be found in the Wikipedia article.
  1. How many private keys would have to be generated for there to be a 0.1% chance of a collision?
Given , we need to find . Using the approximation above:
With a private key space of , approximately or 15.2 undecillion (i.e. 15.2 billion billion billion billion) private keys would have to be generated for there to be a 0.1% chance of collision.
  1. Assuming 8 billion people in the world, how many keys would each person have to generate for there to be a 0.1% chance of a collision?
For there to be a 0.1% chance of a collision among all the generated keys, each person would have to generate approximately or 1.9 octillion (i.e. 1.9 billion billion billion) keys.
For comparison, bitcoin miners have performed a total of approximately hashing operations to get to the current block height. In other words, generating the amount of keypairs necessary for a chance of a single collision would require each and every person in the world to perform computational work comparable to that of all PoW performed on Bitcoin to date.
write
preview
0 sats \ 0 replies \ @SimpleStacker OP 17 Dec
Good job. I had to double check whether "15.2 undecillion" was correct, but it was!
And, nice way of putting things into perspective regarding how unlikely it is to have collisions. Well done.
reply