[Bitcoin Puzzle] Probability of private key collisions, part 1 \ stacker news ~bitcoin

pull down to refresh

[Bitcoin Puzzle] Probability of private key collisions, part 1

531 sats \ 8 comments \ @SimpleStacker 16 Dec 2024 bitcoin

Ok, so this isn't really a puzzle so much as a math problem that will likely involve looking stuff up unless your computer has the ability to calculate incredibly large and small numbers accurately.

But here's the question. 1,000 sats to the first, best, complete answer (with cited sources if you aren't doing the computations yourself).

Suppose Bitcoin has

N = 2^{256}

possible private keys. Suppose

K

private keys are generated, completely at random.

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$ .
How many private keys would have to be generated for there to be a 0.1% chance of a 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?

I will post a part 2, harder version of the problem later....

1,000 sats paid

SimpleStacker's bounties

view all past bounties

1341 sats \ 1 reply \ @shafemtol 17 Dec 2024

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\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?

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

0 sats \ 0 replies \ @SimpleStacker OP 17 Dec 2024

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.

30 sats \ 3 replies \ @Filiprogrammer 17 Dec 2024

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}}

30 sats \ 1 reply \ @Filiprogrammer 17 Dec 2024

So if we adjust the reply from @shafemtol to calculate how many addresses would have to be generated for a collision:

N = 2^{160}

K \approx \sqrt{−2N*ln(0.999)} \approx 2^{75.5}

We get

2^{75.5}

private keys that would have to be generated for there to be a 0.1% chance of a Segwit address collision.

30 sats \ 0 replies \ @Filiprogrammer 17 Dec 2024

\frac{2^{75.51747}}{8*10^9} = 6.759797398 * 10^{12} = 2^{42.62012}

So each person would have to generate approximately

2^{42.6}

or 6.7 trillion keys for there to be a 0.1% chance of a Segwit address collision.

So time to switch to taproot? hmm

0 sats \ 0 replies \ @SimpleStacker OP 17 Dec 2024

Thanks for that important clarification

0 sats \ 1 reply \ @satcat 17 Dec 2024

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:

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

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

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)

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

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

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

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.

0 sats \ 0 replies \ @SimpleStacker OP 17 Dec 2024

Nice try, but Claude's calculations are actually incorrect, not to mention he failed to respect my notational conventions of

N

and

K

>:(

Fwiw, i wouldn't have rewarded the bounty for an AI-generated answer anyway.