Bitcoin Address Collisions.

[AlexWaters]

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.

[justusranvier]

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

[TippingPoint]

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

Criminal Court - Beyond a reasonable doubt

Civil Court - Preponderance of the evidence

Internet Forum - Good enough

[FreeMoney]

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.

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

[farproc]

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.

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.

[🏰 TradeFortress 🏰]

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.

[DeathAndTaxes]

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.

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.

[🏰 TradeFortress 🏰]

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

[stdset]

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

[Plazmotech]

What language are we talking in

I believe it's known as "bitcointalk"

Or, y'know, math.

[Bitcoinpro]

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.

have you taken into account how many addresses bots will create

[AliceWonder]

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.

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.

[stdset]

have you taken into account how many addresses bots will create

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.

[Remember remember the 5th of November]

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.

[gmaxwell]

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.

[Remember remember the 5th of November]

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.

[DeathAndTaxes]

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.

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.

[gmaxwell]

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.

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.

[gmaxwell]

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.

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

[DeathAndTaxes]

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.

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.