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

possible private keys. Suppose

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

1331 sats \ 1 reply \ @shafemtol 17 Dec

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.

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.

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.

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.

30 sats \ 3 replies \ @Filiprogrammer 17 Dec

Keep in mind that while there are almost

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

different singlesig native Segwit addresses. So the probability of guessing a private key for a certain Segwit address is actually

30 sats \ 1 reply \ @Filiprogrammer 17 Dec

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

We get

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

So each person would have to generate approximately

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

Thanks for that important clarification

0 sats \ 1 reply \ @satcat 17 Dec

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

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

and

>:(

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