Re: What are the chances of an address collision? and what happens when it does?

Quote from: odolvlobo on November 03, 2012, 10:40:48 PM

Quote from: molecular on October 31, 2012, 08:04:37 PM

I'm not saying collisions anywhere close to likely to occur, but...

Quote from: enmaku on August 29, 2012, 05:26:37 PM

Given your example of 1 billion users at 10 addresses each:

There are 2^160 or about 1,460,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible addresses
In your scenario, 1,000,000,000 people are using 10 addresses each for a total of 10,000,000,000 possible addresses
10,000,000,000 / 2^160 should yield the probability of a collision occurring
10,000,000,000 / 2^160 = 0.00000000000000000000000000000000000000684

So the chances of a collision occurring in your scenario are approximately 0.000000000000000000000000000000000000684%

This is the chance of finding a collision when generating 1 address.

The chance of a collision occuring "at all" is higher.

Let's assume (worst case) we use bitcoin for 1E3 years and there are 1E10 people populating earth at any point in time who will generate on average 1E3 addresses during their lifetimes.

What are the chances of a collision to occur under these assumptions?

The probability of a collision is found by a standard formula: p = 1 - k! / N^k-1(N-k)!, where k is the number of hashes generated (100x10¹⁰x10³) and N is the number of possible hashes (2¹⁶⁰).

This is a difficult number to calculate, but there is a good approximation: p = 1 - e^-k(k-1)/2N

But even that value is difficult to compute because of the precision needed. Here is another approximation p = k²/2N.

So the answer is that the probability of at least one collision is approximately 7x10^-19 or 0.00000000000000007%

See: http://preshing.com/20110504/hash-collision-probabilities

thanks odolvlobo, this is very helpful info.

Since this is the probability of a collision to be found anywhere within the network (right?), I should probably either compare this to the probability of anyone getting struck by lightning, or I should compare the probability of a particular indivudual finding a collision with the probability of said individual getting struck by lightning?