Chances of a collision

[DeathAndTaxes]

As pointed out the probability of a 'collision' is 1 in 2⁸⁰ but  a collision isn't useful to attack Bitcoin or steal funds.  Given the magnitude of 2⁸⁰ relative to the number of addresses any collision is almost certain to be between to unused keys very likely between two keys that will never be generated by anyone else.  That doesn't give you any way to disrupt the network or steal funds.   To do that would require not just a collision attack but a preimage attack which has a complexity of 2¹⁶⁰ against a single key and with only a linear reduction if attacking a set of keys (i.e. look for preimage against any 'funded address').

[RealBitcoin]

What about this guys:

http://www.dailymail.co.uk/news/article-2711202/It-cooks-inside-like-microwave-Man-61-survives-struck-lightning-10-TIMES.html

So we know that being hit by lightning 10 times is possible , thus:

A 0.000000000000000000000000000152% chance has already happened, and probably even more times around the world, so i`d say

Anything between  1e-28 and 1e-40 chance is probable to happen in our lifetime.

Now you guys say that (on another thread i saw this):

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%

See why we don't consider collisions an issue?

Thus that is a 1.5e-28 probability that if 1 billion people create addresses, then 1 address can easily be REVEALED!

So consider this, a person can easily create more then 1 addresses, i think the average per person is around 5-6.
(Excluding the fact that there can be malicious guys that create billions of addresses /day, searching for filled balances)

But even if we go with 5-6/life, and looking for 1 billion people (conservative future users of bitcoin).

That is 5,500,000,000 /2^160 = 3.7632527118098114697658753457492e-39

So that is 3.76e-39, and we know around 1e-40 is probable, thus at least 1 unlucky fellow from that 1 billion users will get its account hacked.
And this is only conservatively speaking in a passive situation, involuntary collision (if hackers start to actively search for bitcoin addresses with the purpose of finding them, then we are even more in trouble)

I think the probability should be at most 1e-100, but preferably even lower a 1e-200 to be safe, we need new format of the private key, 2^160 is too little, not to mention, the guy above me said that its only 2^80 which is very unsafe

[coinableS]

What about this guys:

http://www.dailymail.co.uk/news/article-2711202/It-cooks-inside-like-microwave-Man-61-survives-struck-lightning-10-TIMES.html

So we know that being hit by lightning 10 times is possible , thus:

A 0.000000000000000000000000000152% chance has already happened, and probably even more times around the world, so i`d say

Anything between  1e-28 and 1e-40 chance is probable to happen in our lifetime.

Now you guys say that (on another thread i saw this):

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%

See why we don't consider collisions an issue?

Thus that is a 1.5e-28 probability that if 1 billion people create addresses, then 1 address can easily be REVEALED!

So consider this, a person can easily create more then 1 addresses, i think the average per person is around 5-6.
(Excluding the fact that there can be malicious guys that create billions of addresses /day, searching for filled balances)

But even if we go with 5-6/life, and looking for 1 billion people (conservative future users of bitcoin).

That is 5,500,000,000 /2^160 = 3.7632527118098114697658753457492e-39

So that is 3.76e-39, and we know around 1e-40 is probable, thus at least 1 unlucky fellow from that 1 billion users will get its account hacked.
And this is only conservatively speaking in a passive situation, involuntary collision (if hackers start to actively search for bitcoin addresses with the purpose of finding them, then we are even more in trouble)

I think the probability should be at most 1e-100, but preferably even lower a 1e-200 to be safe, we need new format of the private key, 2^160 is too little, not to mention, the guy above me said that its only 2^80 which is very unsafe

You have to "cook the books" for something like that to happen. The person described above had to put himself in positions where conditions where lightning would strike. I'm not saying he did it on purpose, but maybe next time he sees a storm cloud over head and begins to smell ozone he should head inside.  You could do the same with bitcoin and use poor RNG to generate addresses and you then put yourself in a position where a collision is more likely. For instance using the brainwallet "cat" or "satoshi nakamoto" those are technically collisions but they are due to poor RNG not a fault in the bitcoin protocol.

[qwk]

This image should at least be posted once in every "but it's possible for someone to create the same address, right?"-thread:

[DumbFruit]

around 1e-40 is probable,

At conception, you could have been one of more than a million different sperm cells trying to make it's way to the egg. There is about a one percent chance that your father would have died before he even met your mother. Your mother happened to excrete the one of two million possible eggs that made you. There was more than a 5% chance that the fertilized egg would have missed implantation.
Just looking at those statistics...
0.000001 * 0.99 *  0.0000005 * 0.95
So there was about a 0.000000000047025% chance that you would exist, looking at one generation. However! This was true of both your mother and father and every pairing going back for the last several hundred thousand years. So if we just look back some 100 generations the likelihood that such a combination would come together throughout the years to produce you is
0.00000000000047025^201

That's 1.37*10^-2478! It's actually significantly less likely than that.

1 in 2^80 is about 8.27*10^-25

So the fact that you exist means that at any given time the same exact address will be found 100 times in a row! According to you, I could say 1.37*10^-2478 is probable, because it happened, and therefore finding a particular address 100 times in a row is also probable.

What you're doing is a subtle form of selection bias. Out of the whole world, and given a long enough time period, matter is going to arrange itself in ways  that are infinitesimally unlikely. Sure it's unlikely that the guy would get hit by lightning that many times, but why select for lightning? At the creation of the universe, what are the odds that a particular electron would end up in a molecule in a cell in his spleen?

It's also a form of gross generalization. You could come up with any number of things that have happened that are much less likely than finding a collision, but so what? That doesn't mean finding a collision is any more likely to happen or less costly to achieve over a given period.

http://www.cdc.gov/nchs/data/nvsr/nvsr53/nvsr53_06.pdf

[Cryddit]

My Grandma Beryl used to say of someone extraordinarily foolish,

"I swear that boy could get hit twice by the same bolt of lightning!"

But she wasn't talking about odds, she was talking about stupidity and failure to learn from a past mistake.

And my Grandpa Charlie?  Her husband?  He actually *DID* get hit by lightning, once, before they married.  But he wasn't a stupid boy; he quit fixing barbed-wire fences when rainstorms were moving in, and never got hit again.

Similarly, people who got hit by address collisions and learned to stop using the native Android RNG without initialization, never got hit again.

So, yeah, lightning strikes occasionally.  It even strikes many times in very predictable spots that stick up high enough and are topped with shiny pointy well-grounded conductors.  You have to learn to NOT STAND on those spots!

[RealBitcoin]

You have to "cook the books" for something like that to happen. The person described above had to put himself in positions where conditions where lightning would strike. I'm not saying he did it on purpose, but maybe next time he sees a storm cloud over head and begins to smell ozone he should head inside.  You could do the same with bitcoin and use poor RNG to generate addresses and you then put yourself in a position where a collision is more likely. For instance using the brainwallet "cat" or "satoshi nakamoto" those are technically collisions but they are due to poor RNG not a fault in the bitcoin protocol.

I`m sure he didnt do it on purpose, no person would want to get struck by lightning. And i`m sure that the probability weights in stupid people mobile phoning when weather comes. After all many people are struck by lighning while phoning, so i`m sure the probability counts that in too

Thus weather you search for being struck by lighning or not, the probabilities are still around that.

This image should at least be posted once in every "but it's possible for someone to create the same address, right?"-thread:

We are not counting until 2^160, we are picking random combinations from that pool, there are odds that you pick satoshis address (with the 1 million bitcoins on it) on the first pick.

Sure the odds are low, but i demonstrated with the example above that its possible, and very probable during the course of our lifetime.

1 person out of 1 billion will be very unlucky and will get its bitcoin stolen, if not more. Because random picking has actually only 2^80 odds, targeted picking has 2^160.

At conception....

I`m not sure if sperm cells are that different between eachother, maybe i would have had a little other tone of my haircolor, but its not that big of a difference.

But we are not talking about probable events that happen many times, so far i only know that there is 1 person that is myself, i dont know of 2 of me being born lol.

But with lightning strikes, there are atleast 3000-4000 strikes happening /year, so that is a repeating phenomenon.

The same with bitcoin addresses, many malicious hackers randomly generating addresses, and 1 lucky idiot will find satoshis 1 million bitcoins, is probable.

I suggest a e-200 probability, why take any chances? 

[TrueBeliever]

I think that it is safe to say, for all intents and purposes, that the chance of a collision happening is 0.

yes that is correct to quite a large number of significant digits.

[tspacepilot]

If the generator is simply counting up from 1 for example the key/address would not be repeated (but would still not be random).

This really makes me wonder what the lowest value private key is that has been used on the network.  I guess I'd have to start iterating to find out (unless someone has already done this).

[BitUsher]

https://www.youtube.com/watch?v=ZloHVKk7DHk

Is a good video explaining the maths and why a collision is insanely improbable that you may as well suggest impossible.

[tspacepilot]

If the generator is simply counting up from 1 for example the key/address would not be repeated (but would still not be random).

This really makes me wonder what the lowest value private key is that has been used on the network.  I guess I'd have to start iterating to find out (unless someone has already done this).

I looked into this and made a little loop to generate bitcoin addresses from private keys.  I didn't get very far at all before I found one which has been used.  It looks to me like someone sends funds to the bitcoin address generated from the private key "1" every so often!

Output of my script:

Code:

A private key:  0000000000000000000000000000000000000000000000000000000000000001
The corresponding WIF:  5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf
The corresponding bitcoin pubkey:  0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
The corresponding bitcoin address:  1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

A lookup of that address:

https://blockchain.info/address/1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

That's a little surprising, right?

[Enzyme]

As pointed out the probability of a 'collision' is 1 in 2⁸⁰ but  a collision isn't useful to attack Bitcoin or steal funds.  Given the magnitude of 2⁸⁰ relative to the number of addresses any collision is almost certain to be between to unused keys very likely between two keys that will never be generated by anyone else.  That doesn't give you any way to disrupt the network or steal funds.   To do that would require not just a collision attack but a preimage attack which has a complexity of 2¹⁶⁰ against a single key and with only a linear reduction if attacking a set of keys (i.e. look for preimage against any 'funded address').

This is true. I wouldn't worry about a collision in your lifetime, however if an exploit was to be found with the cryptography, that would be a different story.

[shorena]

If the generator is simply counting up from 1 for example the key/address would not be repeated (but would still not be random).

This really makes me wonder what the lowest value private key is that has been used on the network.  I guess I'd have to start iterating to find out (unless someone has already done this).

I looked into this and made a little loop to generate bitcoin addresses from private keys.  I didn't get very far at all before I found one which has been used.  It looks to me like someone sends funds to the bitcoin address generated from the private key "1" every so often!

Output of my script:

Code:

A private key:  0000000000000000000000000000000000000000000000000000000000000001
The corresponding WIF:  5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf
The corresponding bitcoin pubkey:  0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
The corresponding bitcoin address:  1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

A lookup of that address:

https://blockchain.info/address/1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

That's a little surprising, right?

Nope, try other numbers that people assign a meaning to (13,17,42,1337,666,8, etc.) and I assure you will find they have been used as well.

[brianddk]

As stated many many times already... the uniqueness of the address is dependent on the randomness of your RNG..

2. No (assuming you have a working RNG and non-buggy software.

...If the RNG is flawed there is a better chance of collision.  

This point can not be stressed enough... Many years ago ARS published an astonishing fact that a survey of SSL certificates found an astounding 0.4% collision rate.  Most of these collisions were tracked back to poor (possibly older) RNG.  So although the theoretical collision rate would be the same as identifying and individual atom in the sun, the practical answer is likely a good bit higher.

I would assume the better question would be...

What are the chances of my current RNG generating a collision?  Of course that would depend on your RNG.  Decades from now, it may be found that there existed some flaw in the RNG used in the early part of this century, but for now, most people feel that the RNG that claim to be good, are good.  Of course there are the occasional glorious exceptions to the rule.

EDIT: Also keep in mind that there is a infinitesimal (though non-zero) chance of collision in RIPEMD-160.  Either a colliding RNG or a hashing collision in RIPEMD-160 would both result in an bitcoin address collision.

Another article about RNG and some tinfoil hat distrust of them.

[tspacepilot]

If the generator is simply counting up from 1 for example the key/address would not be repeated (but would still not be random).

This really makes me wonder what the lowest value private key is that has been used on the network.  I guess I'd have to start iterating to find out (unless someone has already done this).

I looked into this and made a little loop to generate bitcoin addresses from private keys.  I didn't get very far at all before I found one which has been used.  It looks to me like someone sends funds to the bitcoin address generated from the private key "1" every so often!

Output of my script:

Code:

A private key:  0000000000000000000000000000000000000000000000000000000000000001
The corresponding WIF:  5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf
The corresponding bitcoin pubkey:  0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
The corresponding bitcoin address:  1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

A lookup of that address:

https://blockchain.info/address/1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

That's a little surprising, right?

Nope, try other numbers that people assign a meaning to (13,17,42,1337,666,8, etc.) and I assure you will find they have been used as well.

Just for fun I made a wallet with the addresses derived from the private keys 1-100.  It's empty at the moment, but it has an impressive log of transactions.  81 of them, the first one on Christmas Day 2013.

[jambola2]

This image should at least be posted once in every "but it's possible for someone to create the same address, right?"-thread:
*snipped image*

The image says 2^256 though
Isn't it just 2^160 for BTC?
That's 2^96 times bigger

It would take a lot lot less time to crack a Bitcoin address than SHA-256 encryption (which is what the infographic talks about)

Let's look at actually counting all of these.
We have an SSD, let's see if we could write and overwrite every possible private key.
As of 2009, there exists a SSD which can write at 6 Gbits/s (6 * 2^30 bits per second)
Also, it takes up 2 watts of power.
According to wikipedia, the sun gives out 3.8 * 10^26 watts
So, we can run 1.9*10^26 of these clearly imperfect SSDs with the sun

We're dealing with 1.9 * 10^26 * 6 * 2^30 bits per second, and we have to deal with 2^160 bits
2^160/(1.9 * 10^26 * 2^30) = 10^12 seconds

This is equal to 40,000 years, definitely within the life time of the sun!
What is more, I'm considering normal inefficient SSDs.

Sure, this is still impossible (when you consider hashing and the need of a perfectly efficient dyson sphere), but the hypothetical presented in the infographic is wrong.

[RealBitcoin]

Ok but you guys are talking about brute force of the unluckyest parameter.

You talk about 40.000 years, which is the unluckyest estimate, for example you got 2^160 combinations, but you always estimate for the unluckiest scenario when you go through all parameters and you find the private key on the last combination.


However that is obviously not always the case, you can find the private key on the first combo, just roll the random string generator, and bam you find an address of 1000BTC.

You are not going through the combinations linearly, as in start with a and go to z, so if the private key is zzzzzzzzzzzz, you find it the last.

You actually pick random strings randomly, thus if your private key is zzzzzzzzzzzzzzzz , then you find it faster, before you need to iterate through all letters.

Furthermore, the probability increases with each iterations since you get more and more addresses, randomly, uncovered.


So if probability on first trial is:       1/(2^160)
on second trial is:       1/(2^160-1)
on third trial is:       1/(2^160-2)

And furthermore, because of variance, you can guess the private key much faster than that.

It's like if you roll a dice and you expect a 5, we know the probability is 1/6, but sometimes you can get 3x 5 in a row.

You also need to factor in consequent lucky permutations! You might guess 1 private address in 40k years, or 3 private addresses one after another!

[tspacepilot]

This image should at least be posted once in every "but it's possible for someone to create the same address, right?"-thread:
*snipped image*

The image says 2^256 though
Isn't it just 2^160 for BTC?

Just for my own clarification, it's 2^160 because of RIPEMD?  Is that correct?  Clearly the private keys are 256 bits.

Thanks for this really informative thread, you guys!

[noideacoin]

Ok but you guys are talking about brute force of the unluckyest parameter.

You talk about 40.000 years, which is the unluckyest estimate, for example you got 2^160 combinations, but you always estimate for the unluckiest scenario when you go through all parameters and you find the private key on the last combination.


However that is obviously not always the case, you can find the private key on the first combo, just roll the random string generator, and bam you find an address of 1000BTC.

You are not going through the combinations linearly, as in start with a and go to z, so if the private key is zzzzzzzzzzzz, you find it the last.

You actually pick random strings randomly, thus if your private key is zzzzzzzzzzzzzzzz , then you find it faster, before you need to iterate through all letters.

Furthermore, the probability increases with each iterations since you get more and more addresses, randomly, uncovered.


So if probability on first trial is:       1/(2^160)
on second trial is:       1/(2^160-1)
on third trial is:       1/(2^160-2)

And furthermore, because of variance, you can guess the private key much faster than that.

It's like if you roll a dice and you expect a 5, we know the probability is 1/6, but sometimes you can get 3x 5 in a row.

You also need to factor in consequent lucky permutations! You might guess 1 private address in 40k years, or 3 private addresses one after another!

https://i.imgur.com/IIZqiDB.jpg

[Muhammed Zakir]

This image should at least be posted once in every "but it's possible for someone to create the same address, right?"-thread:
*snipped image*

The image says 2^256 though
Isn't it just 2^160 for BTC?

Just for my own clarification, it's 2^160 because of RIPEMD?  Is that correct?  Clearly the private keys are 256 bits.

Thanks for this really informative thread, you guys!

Yes.

@jambola2:

So there are 2^160 public keys but only 2^96 private keys? Ho does that add up?
Are there private keys than unlock more than one public key?

There are just under 2^256 private keys, just under 2^256 public keys, and 2^160 addresses. There are some addresses that have more than one corresponding public key and thus more than one corresponding private key.