Bitcoin Address Collisions.

[marjamrob]

The odds of a collision taking place, by my calculations, assuming 20 Million BTC address, are as follows:

2^256                                                                                                   1
______                                                                       =          ____________________

~20 Million (Estimated BTC Address In Existence)                           5.78960446186581E69

Which is equal to:

           1
__________________                                Or                                         .00000000005064660113837803 %

1974466158682.1443

That is of 1 single collision taking place, so it seems rather unlikely.

Has anyone ever been able to confirm that an address collision took place? I ask because we seem to worry a lot about it, even though the odds seem stacked against such a happening.

[justusranvier]

There are slightly less than 2¹⁶⁰ possible bitcoin addresses, not 2²⁵⁶

[Remember remember the 5th of November]

There are slightly less than 2¹⁶⁰ possible bitcoin addresses, not 2²⁵⁶

Yeah, but there are still ~2^256(not exactly 2^256 private keys due to secpk256k1) so doesn't matter much, because you still need to try numbers from this large pool for the right private key which hashes to some RIPEMD160 hash.

[stdset]

Let's assume there are 2^160 possible, and equally probable to be generated, bitcoin addresses. Let's than assume there are 10 billions people on the planet, and each of them uses 100 new addresses a day. They continue to do so for 1000 years. After that period of time approx 3.65*10^17 addresses will be generated. Next address to be generated has probability of 2.5*10^-31 to collide with one of the existing addresses. That's several orders of magnitude less than 1 divided by Avogadro constant.

[superduh]

What language are we talking in

[Mike Christ]

What language are we talking in

I believe it's known as "bitcointalk"

[stdset]

Moreover, there couldn't be more than 2.1*10^15 bitcoin addresses being used at the same time, because there will not be more than 2.1*10^15 satoshis in the whole system. So, most of those 3.65*10^17 addresses will be empty.

[hazek]

It's going to happen eventually, however not nearly often enough for it to ever be a serious problem.

[AliceWonder]

You can't just do a straight division.

If you have a 30 people in a room, the chances of any two specific people having the same birthday is rather small.
However odds are that there is at least one pair with the same birthday. A collision.

That being said, the odds in bitcoin are still extremely low.

I don't remember my statistics class well enough to remember the formula, but I'm fairly certain it involved factorials.

[AliceWonder]

Oh, and with these addresses that start with a 3 that require multiple signatures to spend, that will increase the number of bitcoin addresses.

An interesting question, if you use a vanity address, how does that effect the odds?

Obviously the pool of addresses that result in that vanity address is smaller, but small enough that crackers could create more successful rainbow tables for vanity addresses?

[phillipsjk]

Collisions are very easy to find if you don't randomly generate the private key:
Brain wallets insecure?

edit: the math is described here:
Birthday Paradox

[stdset]

You can't just do a straight division.

That's why I wrote, "the next address generated", not "probability that any two addresses collide".
Approximate probability of collision between any two addresses can be calculated the following simple way:
obviously, the first address can't collide with another address, probability for the second to collide with the first is 1/2^160, for the third it is 2/2^160, 4'th 3/2^160, it is easy to see, that it is an arithmetical progression.
Total probability that any two addresses collide approximately equals the sum of the progression, and can be written as: P = n^2/2^161, where n - is the amount of bitcoin addresses in use.
For 2.1*10^15 addresses it gives us: 1.5*10^-18
This calculation is simplified a bit. However, the result should be very close to the exact result.

[joewinkler]

You can't just do a straight division.

That's why I wrote, "the next address generated", not "probability that any two addresses collide".
Approximate probability of collision between any two addresses can be calculated the following simple way:
obviously, the first address can't collide with another address, probability for the second to collide with the first is 1/2^160, for the third it is 2/2^160, 4'th 3/2^160, it is easy to see, that it is an arithmetical progression.
Total probability that any two addresses collide approximately equals the sum of the progression, and can be written as: P = n^2/2^161, where n - is the amount of bitcoin addresses in use.
For 2.1*10^15 addresses it gives us: 1.5*10^-18
This calculation is simplified a bit. However, the result should be very close to the exact result.

I do not know exactly this kind of math.
Is   P = n^2/2^161 or P = n^2/(2^160+1) ?

[stdset]

Is   P = n^2/2^161 or P = n^2/(2^160+1) ?

161, that's why I wrote it with bold letters. And anyway, 1 compared to 2^160 is too small, I would neglect it, if it would appear there.

[AliceWonder]

One thing to note about bitcoin is that a large percentage if not most of the addresses used are used once and then completely emptied when the transaction sent to them are spent. So even if there is a random collision, there's a damn good chance it is fairly meaningless and if not meaningless (e.g. first person to have it ends up spending the input) it probably is not a huge loss.

[kjj]

You can't just do a straight division.

That's why I wrote, "the next address generated", not "probability that any two addresses collide".
Approximate probability of collision between any two addresses can be calculated the following simple way:
obviously, the first address can't collide with another address, probability for the second to collide with the first is 1/2^160, for the third it is 2/2^160, 4'th 3/2^160, it is easy to see, that it is an arithmetical progression.
Total probability that any two addresses collide approximately equals the sum of the progression, and can be written as: P = n^2/2^161, where n - is the amount of bitcoin addresses in use.
For 2.1*10^15 addresses it gives us: 1.5*10^-18
This calculation is simplified a bit. However, the result should be very close to the exact result.

The forum supports superscripts.

P = n²/2¹⁶¹

[marcus_of_augustus]

So there is tiny, but possible chance and that you could say to the court ..."Your honour, I have no idea how that bitcoin got in that account, maybe it was random collision?"

[stdset]

So there is tiny, but possible chance and that you could say to the court ..."Your honour, I have no idea how that bitcoin got in that account, maybe it was random collision?"

It's interesting to compare chances of collision of bitcoin addresses to chances of human fingerprints colliding.

[Garr255]

Simple evasion of a collision is dispersing your bitcoin savings in thousands of addresses. Technically if everyone does this the likelihood of a collision is in fact higher but the stakes are less.

As with everything: give and take.

--Garrett

[stdset]

Simple evasion of a collision is dispersing your bitcoin savings in thousands of addresses. Technically if everyone does this the likelihood of a collision is in fact higher but the stakes are less.

As with everything: give and take.

--Garrett

It's important to undestand, we are not talking about some real possibility. Even if we spread all bitcoins as thin as possible, putting 1 satoshi to an address, total probability is about 10^-18. It is essentially zero. And your personal probability of a collision about 5 orders of magnitude less (if you hold huge fortune of some hundreds of BTC and spread them: an address - a satoshi). If you care about such things, you should also care about a meteor hitting you.