For two private keys, the probability of the two not colliding is \frac{N-1}{N}. If they are not colliding, then for a third key, the probability of it not colliding with one of the two existing keys is \frac{N-2}{N}. For K keys, the probability of no collision is:
P(\bar C) = \frac{N-1}{N}\times\frac{N-2}{N}\times\cdots\times\frac{N-K+1}{N} = \frac{K!\cdot\binom{N}{K}}{N^K}
where K! is the factorial of K and \binom{N}{K} is the binomial coefficient.
The probability of a private key collision is the complement of this:
P(C) = 1-P(\bar C) = 1-\frac{K!\cdot\binom{N}{K}}{N^K}
Due to the large N and the use of factorial and binomial coefficient, this quickly becomes impossible to compute as K grows, long before P(\bar C) can even be represented as anything less than 1.0 in a standard 64-bit float.
For K \ll N, as will be the case here, a very good approximation is:
P(C) \approx 1 - e^{-\frac{K(K-1)}{2N}}
This is because 1 - x \approx e^{-x} for |x| \ll 1. More details on deriving this approximation can be found in the Wikipedia article.
How many private keys would have to be generated for there to be a 0.1% chance of a collision?
Given P(C) = 0.1\%, we need to find K. Using the approximation above:
1 - e^{-\frac{K(K-1)}{2N}} \approx 0.1\%e^{-\frac{K(K-1)}{2N}} \approx 0.999\frac{K(K-1)}{2N} \approx -\ln(0.999)K(K-1) \approx -2N\ln(0.999) \approx 2.317000478165382653381910211899300708 \cdot 10^{74}K \approx 15221696614258814787271388067615960467 \approx 2^{123.5}
With a private key space of N=2^{256}, approximately 2^{123.5} 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.
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 2^{90.6} or 1.9 octillion (i.e. 1.9 billion billion billion) keys.
For comparison, bitcoin miners have performed a total of approximately 2^{95.3} 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.
\frac{N-1}{N}. If they are not colliding, then for a third key, the probability of it not colliding with one of the two existing keys is\frac{N-2}{N}. ForKkeys, the probability of no collision is:P(\bar C) = \frac{N-1}{N}\times\frac{N-2}{N}\times\cdots\times\frac{N-K+1}{N} = \frac{K!\cdot\binom{N}{K}}{N^K}K!is the factorial of K and\binom{N}{K}is the binomial coefficient.P(C) = 1-P(\bar C) = 1-\frac{K!\cdot\binom{N}{K}}{N^K}Nand the use of factorial and binomial coefficient, this quickly becomes impossible to compute asKgrows, long beforeP(\bar C)can even be represented as anything less than 1.0 in a standard 64-bit float.K \ll N, as will be the case here, a very good approximation is:P(C) \approx 1 - e^{-\frac{K(K-1)}{2N}}1 - x \approx e^{-x}for|x| \ll 1. More details on deriving this approximation can be found in the Wikipedia article.P(C) = 0.1\%, we need to findK. Using the approximation above:1 - e^{-\frac{K(K-1)}{2N}} \approx 0.1\%e^{-\frac{K(K-1)}{2N}} \approx 0.999\frac{K(K-1)}{2N} \approx -\ln(0.999)K(K-1) \approx -2N\ln(0.999) \approx 2.317000478165382653381910211899300708 \cdot 10^{74}K \approx 15221696614258814787271388067615960467 \approx 2^{123.5}N=2^{256}, approximately2^{123.5}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.\frac{K}{8 \cdot 10^9} \approx 1.90 \cdot 10^{27} \approx 2^{90.6}2^{90.6}or 1.9 octillion (i.e. 1.9 billion billion billion) keys.2^{95.3}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.