Bitcoin Forum

Has anybody been able to work out the fractional chances of a collision with an existing bitcoin address?

Has anybody got any verifiable proof that it's been done in the past?

What hardware would be capable of even getting close to being able to generate enough addresses to cause a collision, and how would somebody trying to cause a collision notice that they've succeeded?

1. Yes, the math has been done and discussed.
Edit: see eg
https://bitcointalk.org/index.php?topic=104461.0
https://bitcointalk.org/index.php?topic=62.0
2. No (assuming you have a working RNG and non-buggy software.
3. None. If the address had been used they would see it.

Just in case it wasn't quite clear, I was hoping for somebody to post what those chances actually were, or a link to a relevant and verified discussion with actual information on the topic. So far all I've come across is speculation about it.

I was looking them up, if you search for "bitcoin address collision" you'll see links - like the two above.
:-)

It boils down to the birthday paradoxon with 1 in 2¹⁶⁰ instead of 1 in 365. The number of addresses that have a balance is probably among bc.i's stats.


here is another one -> https://bitcointalk.org/index.php?topic=633308.0

With a few basic cryptographic assumptions, the chance of a single randomly (uniformly) generated Bitcoin address colliding with an existing address is simply: [number of existent addresses] / 2¹⁶⁰.

At the moment of writing (block #348386), there are 66 214 306 distinct addresses recorded in the blockchain (93.5% of which are empty by the way).  This yields a probability of about 4.5 * 10^-41 (about 1 in 22 000 trillion trillion trillion).


Not to my knowledge.


Such hardware would need to be able to generate close to 2¹⁶⁰ / [number of existent addresses].

A decent CPU might manage to generate 500 000 addresses per second.  Working with a companion GPU well-suited to the task and you might be looking at 20 million addresses per second.

"What about ASICs?" I hear you ask.  Well, let us suppose that you could design a machine a billion times faster than this for the same mass of hardware and power consumption.  We'll assume the machine can also check addresses against the relatively tiny pre-set list of existing ones as fast as the new ones are generated.

A cluster of these machines capable of "getting close" (lets say having a fair chance of generating a collision within a year) will draw about as much power as consumed in all other human activities combined and weigh about as much as Mount Everest.

I understood Grumpster to be asking about colliding with one of the currently existing addresses rather generating two addresses which collide with one another.  If we're just looking for two distinct private keys which yield the same address then indeed the Birthday Problem applies.  The average number of addresses you'd need to generate to find such a beast is approximately 1.5 trillion trillion (a little bit more than square_root(2¹⁶⁰)).

This problem is far closer to tractable.  All we'd need is about 2 billion gaming rigs running for a year, each with about 20 000 terrabytes of storage.

And that is not mentioning the power drain for this!

Hmm...  Maybe about 30 exajoules (roughly 8000 terrawatt hours).  This is assuming we can be clever about how matching pairs are checked for and most of the drives can be powered down for most of the year.

Switching off both China and the US and diverting the power to the cluster should be sufficient.

And do not forget this people all this is just t point out that Bitcoin is no impossible to break. But again there is nothing "impossible" in security system, It is just relative security to the gain. No one would do such thing to find a collision, This is alot of money for a hackathon to say haha I found a collision haha..... -_-

Just to clarify: there's a wide margin between finding an address collision in this fashion and breaking Bitcoin*.  The latter would at bare minimum require something like the hypothetical futuristic Mount Everest machine I described above.

The cluster could probably be used to solve chess and maybe even run Crysis but it will not break Bitcoin.

*I'm assuming there is no subtle bug which would cause problems should two outputs at the same address be moved simultaneously using different keys.

well............ have you considered ripemd160? I mean it is easier (lol easier) to find collision in 160 than 256.

Here's some super simple code I wrote for a mini bitcoin address collider. I call it mini because it only does 324 address per hour, however the RNG process being used is unclear. If the RNG is flawed there is a better chance of collision.  

Blockchain.info  provides this (https://blockchain.info/q/newkey) which is supposed to create a fresh public/private key pair whenever you call that address. Since the RNG process behind these addresses are unclear is the reason I'm using it. There's a limit of ~1 query per 10 seconds or you'll get banned/blocked which is why this script only does about 320 per hour.  It pulls the new key (assuming RNG is good) and then we use the address info and return the total amount received to that address and plugs everything into a DB. If total amount received is ever greater than 0 then you have a collision. Or you can also query your DB to see if there are any repeats.

Put it in a cron job to run every 5 minutes.

Yes, all this speculation takes RIPEMD-160 into account.  It is because of the RIPEMD-160 that a collision is going to look like having two different private/public keypairs which correspond to the same address.


Cool.  Note that a collider doesn't need high-quality randomness for each address.  Just working through all the private keys in order from 1 to 115792089237316195423570985008687907852837564279074904382605163141518161494336 would be fine (yes, there are quite a lot of different private keys).

Anyway.  At 320 addresses per hour and assuming all else constant, you should be finding an address collision once every 121 billion trillion trillion years on average (similar to the way a new block is generated once every 10 minutes on average so expect some variance).  Notice that you'd actually be generating a collision on average once every 7.8 billion trillion trillion years but because your code checks collisions by checking for a balance and most addresses in the blockchain have a balance of 0 you'll be missing a lot.

I feel it's worth comparing this to Bitcoin block generation.  A script which generates 320 hashes per second will find a block on average once every 72 trillion years.  Given that many CPUs are capable of hashing 10 000 times faster and that an address with non-zero balance contains about 3.2 BTC (compared with the average block payout of about 25 BTC) we see that anyone looking to run this code for profit would be about 100 trillion trillion times better off just CPU mining Bitcoin.

I was simply responding to the OP's question "how would somebody trying to cause a collision notice that they've succeeded?"  What I provided is perfectly valid to his question, it attempts to create a collision based on poor RNG and let's you know if you found one. What you posted everyone already knows.


Yea I quite aware of the # of addresses...


No it doesn't, it checks total amount the address has ever received, in other words checks to see if the address has ever been used.


The script is checking the RNG of blockchain's (https://blockchain.info/q/newkey) tool. It has no extra points of entropy like bitaddress.org and could very well be flawed. Do you know the RNG behind this newkey tool?

My mistake.  A more careful look revealed that indeed you are checking for any addresses which have ever received funds.


I don't know the details of the sources of random used by blockchain.info's newkey.  While I agree that there is the possibility of a flaw in the RNG leading to unexpected long-term behaviour of the script, I maintain that the best way of resolving this potential flaw is to throw out the RNG altogether.  A collision generator has no need for anything random.

I guess the reasoning is that using a potentially flawed generator (that is widely in use) probably increases your probability of finding an address with a balance as opposed to working through the problem space in a pure fashion.  This is only true if the generator is non-random in some repetitive fashion (i.e. it is more likely than purely by chance to repeat some address).  If the generator is simply counting up from 1 for example the key/address would not be repeated (but would still not be random).

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

Ah, yes, I missed that at first too.  The masses of poorly thought-out posts on this forum has encouraged me into the bad habit of skim reading everything not written by a small white-list of known good posters.

Sure.  If the RNG is flawed then the chances of finding a collision are improved.  I agree it's most likely that this newkey function is used under the hood when people create new addresses in their blockchain.info wallets so there should be plenty of addresses containing funds to collide with.

What the probability of collision is is open to speculation.  Theoretically, anything from [number of existing addresses] / 2¹⁶⁰ up to 1 is possible and, absent the code, we only really have the fact that no-one's found a collision so far to guide us.


I agree that the keys would not be repeated and the addresses would not be random.  However, the RIPEMD-160 step (assuming RIPEMD-160 itself is not badly flawed) ensures that the addresses will be seemingly random and address collisions will not be practically predictable (precisely as Bitcoin mining gives rise to unpredictable block generation times).

There are 2¹⁶⁰ addresses.  That means that by the time you've got sqrt(2¹⁶⁰) addresses, assuming uniform distribution (which is valid on cryptographic keys) there are even odds that some two of them have collided.  That means you'd need 2⁸⁰ addresses before a collision occurred.  That's about 1.2 septillion addresses required before a collision between any two becomes likely. 

For some sense of scale, Earth weighs about five times that many kilograms. 

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').

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):



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.

This image should at least be posted once in every "but it's possible for someone to create the same address, right?"-thread:
https://i.imgur.com/VjtG3.jpg

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

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!

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.


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.


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?  ;D

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

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

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.

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:

A lookup of that address:

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

That's a little surprising, right?

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.

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.

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


This point can not be stressed enough... Many years ago ARS published an astonishing fact (http://arstechnica.com/business/2012/02/crypto-shocker-four-of-every-1000-public-keys-provide-no-security/) 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. (http://www.theregister.co.uk/2013/08/12/android_bug_batters_bitcoin_wallets/)

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 (http://arstechnica.com/security/2013/12/we-cannot-trust-intel-and-vias-chip-based-crypto-freebsd-developers-say/) about RNG and some tinfoil hat distrust of them.

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.

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 (https://en.wikipedia.org/wiki/Orders_of_magnitude_(energy)), 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.

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!

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:

2^160 addresses, right. Private keys, no, that's almost 2^256.
No use generating an address if you don't have the private key to it ;)

Basically, you're right, you're probably going to create a collision in a fraction of the time it would take to generate all private keys.
Which would still take longer than the lifetime of our solar system, but might just be in time before hell freezes over. ;)

It could happen. Chances are, you'll be struck by lighting out of a blue sky and at the same time be hit by a meteorite while a chasm in the earth opens up to swallow you whole, just the instant you're trying to spend your newly found wealth. It definitely could happen.

As far as I know the chances of it happening are so small that there is a bigger chance of the earth colliding with an asteroid than the addresses are likely to collide with eachother. :P