Bitcoin Forum

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.

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.

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.

What language are we talking in

I believe it's known as "bitcointalk"

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.

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

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.

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?

Collisions are very easy to find if you don't randomly generate the private key:
Brain wallets insecure? (https://bitcointalk.org/index.php?topic=251037.0)

edit: the math is described here:
Birthday Paradox (https://en.wikipedia.org/wiki/Birthday_paradox)

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

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.

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.

The forum supports superscripts.

P = n²/2¹⁶¹

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.

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.

Can we talk about what happens when there is a collision? I like to envision dividing by zero, a star dying, Roger Ver ascending to heaven, and your computer literally exploding with bitcoins shooting out of it.

http://www.youtube.com/watch?v=jyaLZHiJJnE

Criminal Court - Beyond a reasonable doubt

Civil Court - Preponderance of the evidence

Internet Forum - Good enough

Two people have access to the same empty account and neither knows it. Hardly spectacular.

Or,
someone generates a new address and then finds there is a large balance in it == Someone else awakes in the morning and finds the large balance in his address was transferred to another random address.

Bitcoin address collisions are the things that could happen, but the chances are extremely small that it's not going to happen in practice and if it does have a party.

This.  The fact that it is ~0% not 0% is hard for some people to grasp until you realize the odds of many other things people consider safe are many orders of magnitude more likely.  The odds that an asteroid will wipe out civilization as we know it is trillions of times more likely than the odds of a collision.  The odds that you (the person reading this post right now) already has terminal cancer, just doesn't know it year, and thus the risk of losing funds is pretty much academic isn't just trillions of times more likely it is thousands of quintillions of times more likely.  While I can't quantify it I would be willing to say that I am more likely to eat some random red pill given to me by a stranger and wake up in a Matrix pod then see a random collision in my lifetime.

Of course, that's assuming ECDSA, SHA256, and RIPEMD-160 aren't broken.

And assuming we use reliable enthropy source for ECDSA keys generation. If e.g. everybody starts using brain wallets, collisions of type BW against BW are rather possible (actually, those collisions are likely to be not even collisions but just identical private keys, generated from the same passphrase).

Or, y'know, math.

have you taken into account how many addresses bots will create

Large amounts really should be in one of those addresses that takes multiple private keys to spend.
And don't keep the keys together until you are ready to spend.

Average 100 addresses/day by every person on the planet are likely enough to cover those addresses created automatically by software applications (because average guy is not really going to use that many addresses a day). But that doesn't really matter, because we can't have bitcoins on more than 2.1*10¹⁵ addresses at a time.

I am pretty sure that with multisig txes and so on there won't be a problem, however I am sure people will create and optimize ASICs to generate trillions or more addresses per second.

And in my opinion, you don't need to count to ~2^256 to find a collision. Perhaps even less than half of that may be enough for a single one.

This is just simple math, not "opinion"—  but finding an arbitrary collision isn't relevant, getting two of your own addresses twice accomplishes nothing. You'd need to collide with an address which has been assigned a non-trivial amount of funds... so your trillions per second only gives you a linear speedup.

Assuming Bitcoin takes off, and your salary is 0.000000000000000000000000000000000340 satoshis or an even lower amount, then even 0.50 won't be that bad.

This.  Also even if we look at addresses with a trivial amount of funds there is an upper limit at the number of funded addresses @ 2.1x10^15 addresses.  That would be the rediculous scenario of all Bitcoins mined, all of them in a seperate address holding one satoshi each and the attacker owns none of them. 

Still for the sake of argument 2.1x10^15 addresses in use.  Compared to 2^160 (1.5x10^48) it is a negligible number.  Say 5th of november's trillion addresses per second ASIC did exist and say a trillion idiots bought one and they all ran their machines for the next thousand years.  There is still a less than 1% chance that a single collision worth 1 satoshi would occur.

If collissions do occur it won't be because someone brute forces the addresses it will be because of an as of yet undiscovered flaw in ECDSA or one of the hashing algorithms which allow attacks at many dozens of magnitudes faster than brute force.

Bitcoin cannot represent an amount that small, the maximum number of non-zero outputs is 21e14, and at that point the UTXO size would be about 44 petabytes.

If you want to speculate about tinier amounts inside the Bitcoin system proper, you'd have to hypothesize some hardfork to increase precision. At the same time, even today, with no protocol change you could freely use a 512 bit address (well, assuming you could convince the sending party to write a custom scriptpubkey).

And again: your speed of generation doesn't change the number of valuable utxo that exist; so its still only a linear attack.

Or bad RNGs in crappy JS wallet generators or hardware wallets.

Depends on how unrealistic you think Bitcoin will "take off".  The entire planet uses ~$4 trillion USD worth of currency, if we included demand deposits (M1) that number is still only ~$19T.  If Bitcoin replaced all other forms of currency (and demand deposits) on the planet (likely requiring some many wars to force the last of the resistant to bend to the Bitcoin overlord government) 1 Bitcoin would be worth ~$904,000 USD (in 2012 dollars purchasing power) and 1 satoshi would be worth ~0.9 US cents (2012 dollars purchasing power).  I think as unrealistic as this is (and the every address holds only 1 satoshi) we can consider them the theoretical upper bound.

http://www.bullionbullscanada.com/guest-commentary/dollardaze/5640-growth-of-global-money-supply


Even the M3 is only ~$60T.  This is not an apples to apples comparison because it includes non-currency financial accounts but lets say Bitcoin replaces those as well (there is no good reason just giving you the benefit of the doubt).  Even then 1 S would be worth about 3 US cents (2012 dollars purchasing power).  All private wealth on the planet is ~$135T that isn't even remotely close to currency including everything from real estate, to equity in companies, to debt ownership, to tangible goods (cars, planes, fine art, etc).  Still even if for reasons that escape comprehension the Bitcoin money supply was greater than all wealth on the planet we are still talking about 1 Satoshi is ~ 7 US cents.  The idea that a satoshi would ever represent a significant amount of wealth is just silly. 

i laugh at people who think they are math experts.

there are 2 (followed by 160 zero) possible combinations.. some of you naively believe that if you start at 1 and count upwards it would take 2(followed by 160 zero's) to find a collision.

this would only be the case if the addresses were made in lets say Hex of all F's..

but in reality ITS RANDOM

the addresses can be ANYWHERE between 1 and 2 (followed by 160 zero's).

meaning its just as likely that a randomiser picked 10 as it would pick 100,000,000,000,000.

with an estimated 84mill addresses being used, there is a chance that one of these 'used' addresses is randomised in the low range.

put simply

its random. they are not all clumped up at the far end of the spectrum.

to add to that depending on the degree (amount of significant figures) were used before hashing and converting, can far reduce the potential 'luck'.

this is why i feel the bitcoin foundation are rightly so in adding the new feature for version 0.9 of bitcoin-QT to not require random addresses per transaction.

Nobody said it it is all clumped one end however as pointed out even w/ 1 trillion ASIC address generation machines, each producing (and checking) 1 trillion addresses per second all running non stop for the next 1000 years AND all Bitcoins are evenly divided into the maximum possible addresses with 1 Satoshi each the odds that any machine will find any collision with  funded address in less than 1% in the next 1,000 years.

Sure all public key cryptography is based on "odds".  You could in theory generate a private key in ONE ATTEMPT that matches the one used by google and produce a fake gmail site which validates SSL properly.  However the odds are vanishingly small.  The same thing applies to Bitcoin address collisions.

The odds of anyone finding any collision via brute force in their lifetime is essentially 0%.

Indeed. Probably similar to the odds that you'll be able to walk through a wall suddenly because of quantum fluctuations lining up perfectly.

We live in a probabilistic universe. It's not just bitcoin address generation.

Just FYI, 2¹⁶⁰ != 2*10¹⁶⁰.

Also, 'random' is a double-edged sword. What you gain by having keys fail to cluster near the far end, you lose by having to check each one.

You must laugh at yourself too then.

Queue more laughter. Learn how the power function works please.

2^160 is approximately 10^48 (1 with 48 zeroes). If 84 mill addresses are used (lets say 100 mill for ease of computation), that makes the probability of a new randomly generated address to collide with an existing address equal to 1 : 10^40.

Suppose in the distant future every person in the world (lets say there are 10 B people by then) uses 1000 addresses each, for a total of 10^13 addresses. If every person now has the computer power to generate and test 10^13 addresses per second (that is the size of the entire *huge* global supply of active addresses every second by every person), in one day the odds of finding a collision are approximately 1:10^7, which makes the expected time to find one collision 30000 year at this mindbogglingly high generation rate.

I think we're fairly safe.