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

[molecular]

And then of course you need to consider if there is some correlation between your current location and the chance of being struck by lightning...

I thought about that before. The answer is: in case I'm out in the rain on some field close to a tree, the probability of me actually taking a crap is about 4 times lower than when I'm at home. If you have to crap, you have to crap

So that should get factored in.

[1715536913]

1715536913

[1715536913]

1715536913

[molecular]

Ok, new data, will recalc everything:

• probability of getting struck by lightning in any given year: 1/280000.
• probability of taking a shit at any given point in time: 1/(60*24) = 1/1440 (assuming you take a crap every day and the actual process takes 1 minute)
• probability of getting struck by lightning while taking a crap in any given year: 1/(280000*1440) = 1/1.47E11 = 2.48E-9
• probability of taking a crap while being in a situation where being struck by lightning can actually occur = 1/1440 = 0.25 = 1.74E-4
• probability of finding a collision: 1E-65
• getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(1.74E-4) = 17.3

is my math roughly correct now?

If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".

[FreeMoney]

1 minute is a nice crap, the average is going to be several times longer.

[molecular]

1 minute is a nice crap, the average is going to be several times longer.

I want the lightning to strike while you are actually in the process of pushing. The wiping is irrelevant

Jokes aside: I'm trying to not overestimate, so I took 1 minute. I doubt many will be quicker.

[flynn]

I think Science just made a very impressive progress here.

[novusordo]

Ok, new data, will recalc everything:

• probability of getting struck by lightning in any given year: 1/280000.
• probability of taking a shit at any given point in time: 1/(60*24) = 1/1440 (assuming you take a crap every day and the actual process takes 1 minute)
• probability of getting struck by lightning while taking a crap in any given year: 1/(280000*1440) = 1/1.47E11 = 2.48E-9
• probability of taking a crap while being in a situation where being struck by lightning can actually occur = 1/1440 = 0.25 = 1.74E-4
• probability of finding a collision: 1E-65
• getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(1.74E-4) = 17.3

is my math roughly correct now?

If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".

You, good sir, have surely created the new standard of explaining address collision probability to noobs. I will refer to your great work in any instance I'm asked this question.

[molecular]

You, good sir, have surely created the new standard of explaining address collision probability to noobs. I will refer to your great work in any instance I'm asked this question.

craptastic!

At this point, let me express my sincere thanks to the following people who either laid the foundation for, hardened or otherwise contributed to my work:

• kokojie
• enmaku
• DeathAndTaxes
• paraipan
• runeks
• flynn
• mskwik
• FreeMoney

(I hope I didn't forget anyone)

Thank you guys!

I'm looking forward to further improvements based on my work!

[paraipan]

Ok, new data, will recalc everything:

• probability of getting struck by lightning in any given year: 1/280000.
• probability of taking a shit at any given point in time: 1/(60*24) = 1/1440 (assuming you take a crap every day and the actual process takes 1 minute)
• probability of getting struck by lightning while taking a crap in any given year: 1/(280000*1440) = 1/1.47E11 = 2.48E-9
• probability of taking a crap while being in a situation where being struck by lightning can actually occur = 1/1440 = 0.25 = 1.74E-4
• probability of finding a collision: 1E-65
• getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(1.74E-4) = 17.3

is my math roughly correct now?

If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".

You, good sir, have surely created the new standard of explaining address collision probability to noobs. I will refer to your great work in any instance I'm asked this question.

+1 great work, will save for future reference

[flynn]

We should apply for the Nobel prize

[odolvlobo]

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

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

[paraipan]

A graphical explanation of bitcoin security https://i.imgur.com/VjtG3.jpg

[molecular]

A graphical explanation of bitcoin security https://i.imgur.com/VjtG3.jpg

awesome! where did that come from?

[molecular]

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

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?

[paraipan]

A graphical explanation of bitcoin security https://i.imgur.com/VjtG3.jpg

awesome! where did that come from?

I saw the link on IRC and though I should share, didn't ask where it came from 

[dserrano5]

awesome! where did that come from?

This may be relevant.

[molecular]

awesome! where did that come from?

This may be relevant.

thanks, it is.

[dooglus]

Sorry for the necro-post, but reddit is talking about this thread, and nobody in this thread seems to be close to the truth...

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

There are 2^160  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

This is wrong. It fails to take into account the birthday problem.

When there are 10^10 addresses, there are roughly (10^20)/2 pairs of addresses.

Consider when there are 5 addresses, A through E.

To check for a collision, you need to compare AB, AC, AD, AE, BC, BD, BE, CD, CE, DE - that's 10 pairs of addresses (5*4)/2, or roughly (5^2)/2.

So your answer is off by a factor of roughly 5 billion.

Since there are 2^160 possible addresses, we need around 2^80 of them to have a 50% chance of a collision.

http://diyhpl.us/~bryan/papers2/bitcoin/bitcoin-birthday.pdf does a better job of approximation, but comes up with a similar answer.

Comparatively speaking, your odds of being struck by lightning in a given calendar year are about 1 in 280,000. The odds of winning my local lottery are about 1 in 176,000,000. So finding a collision on your first try is roughly equivalent to being hit by lightning 16,540,000,000,000,000,000,000,000 times per second for an entire year

No. You can say that the odds of being hit by lightning are 16,540,000,000,000,000,000,000,000 times higher than of finding a collision, but your statement isn't true.

A simpler example that we can picture more easily than all those zeroes:

 * I have a 1 in 2 chance of coin coming up tails.
 * I have a 1 in 20 chance of rolling a 6 on a 20 sided die.
 * so tossing "tails" is 10 times more likely than rolling a 6.

From this, using your logic, I am just as likely to toss "tails" 10 times in a row as I am to roll a 6.

But we can see that this isn't true. Tossing "tails" 10 times in a row is a 1 in 1024 event. Rolling a 6 is still only 1 in 20.

[rubygon]

Address collision won't occur. It will be a billionth of billionth of a billionth chance, that an address may collide. Further, the address is backed by public key and private keys. Those keys must be different even if an address collide with another. No need to worry or think about the collision problem. The ECD curve is much larger than the scope we're imagining.

[onlinn]

Since Bitcoin addresses are basically random numbers, it is possible, although extremely unlikely, for two people to independently generate the same address. This is called a collision. If this happens, then both the original owner of the address and the colliding owner could spend money sent to that address. It would not be possible for the colliding person to spend the original owner's entire wallet (or vice versa). If you were to intentionally try to make a collision, it would currently take 2^107 times longer to generate a colliding Bitcoin address than to generate a block. As long as the signing and hashing algorithms remain cryptographically strong, it will likely always be more profitable to collect generations and transaction fees than to try to create collisions.

It is more likely that the Earth is destroyed in the next 5 seconds, than that a collision occur in the next millenium.

[dooglus]

Address collision won't occur. It will be a billionth of billionth of a billionth chance, that an address may collide.

The chance depends on how many addresses there are.

Further, the address is backed by public key and private keys. Those keys must be different even if an address collide with another. No need to worry or think about the collision problem. The ECD curve is much larger than the scope we're imagining.

The ECD curve doesn't matter. We use 160 bit addresses, and that's the space we're looking for collisions in. If two different privkeys give the same address they can still spend each other's funds, since we pay to addresses, not to privkeys or pubkeys.