1. Derive a formula for the probability of a private key collision (2 or more private keys are the same), in terms of $N$ and $K$.

This is what's known as the birthday problem.

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 \left(\genfrac{}{}{0ex}{}{N}{K}\right)}{N^K}$

where $K!$ is the factorial of K and $\left(\genfrac{}{}{0ex}{}{N}{K}\right)$ 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 \left(\genfrac{}{}{0ex}{}{N}{K}\right)}{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.

2. 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.

3. 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?

$\frac{K}{8\cdot 10^9}\approx 1.90\cdot 10^{27}\approx 2^{90.6}$

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.

Keep in mind that while there are almost $2^{256}$ valid private keys, there are actually less Bitcoin addresses. For example singlesig native Segwit addresses (bc1q...) are a bech32 representation of a 160 bit hash.

This means that there are only $2^{160}$ different singlesig native Segwit addresses. So the probability of guessing a private key for a certain Segwit address is actually $\frac{1}{2^{160}}$.

I copy pasted you're question into Claude 3.5, but none of the formulas were copied, nonetheless I think it got it right.

Response:

I notice some mathematical expressions might have been cut off in your message. From context, this appears to be about Bitcoin private key collisions and the birthday problem. Let me help fill in the details:

Bitcoin has 2^256 possible private keys (this is the total number of possible keys in the keyspace). Let's call the number of randomly generated keys n.

Let's solve this step by step:

1. This is a variation of the birthday problem. The probability of a collision can be calculated using:

P(collision) = 1 - P(no collision)

2. The probability of no collision when choosing n keys from 2^256 possibilities is:

P(no collision) = (2^256)/(2^256) × (2^256-1)/(2^256) × ... × (2^256-(n-1))/(2^256)

This can be rewritten as:

P(no collision) = ∏(i=0 to n-1) (1 - i/2^256)

3. For small probabilities relative to the size of the keyspace, we can use the approximation:

P(collision) ≈ n^2 / (2 × 2^256)

4. For a 0.1% chance of collision, we want:

0.001 = n^2 / (2 × 2^256)

Solving for n: n = √(0.001 × 2 × 2^256) n ≈ 2^128 × √0.002 n ≈ 4.8 × 10^38 keys

5. For 8 billion people: 4.8 × 10^38 ÷ 8 × 10^9 ≈ 6 × 10^28 keys per person

These calculations assume we're using the approximation formula, which is valid when the probability is small relative to the keyspace (which it is in this case).

This demonstrates why Bitcoin private key collisions are practically impossible - even with billions of people generating enormous numbers of keys, the probability of a collision remains infinitesimally small due to the massive keyspace of 2^256.

Note: I performed these calculations directly. While they should be accurate given the approximation formula used, for absolute precision with such large numbers, you might want to verify with specialized cryptographic software or mathematical tools.