Pages:
Author

Topic: Bitcoin Address Collisions. (Read 3941 times)

hero member
Activity: 728
Merit: 500
July 18, 2013, 02:09:39 AM
#45
i laugh at people who think they are math experts.
You must laugh at yourself too then.

Quote
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.
Queue more laughter. Learn how the power function works please.

Quote
with an estimated 84mill addresses being used, there is a chance that one of these 'used' addresses is randomised in the low range.
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.
kjj
legendary
Activity: 1302
Merit: 1026
July 18, 2013, 12:15:59 AM
#44
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.

Just FYI, 2160 != 2*10160.

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.
legendary
Activity: 1722
Merit: 1004
July 17, 2013, 06:23:40 PM
#43
...However the odds are vanishingly small.  The same thing applies to Bitcoin address collisions...

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.
donator
Activity: 1218
Merit: 1079
Gerald Davis
July 17, 2013, 06:07:37 PM
#42
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%.
legendary
Activity: 4410
Merit: 4766
July 17, 2013, 06:02:06 PM
#41
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.
donator
Activity: 1218
Merit: 1079
Gerald Davis
July 17, 2013, 05:28:11 PM
#40
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. 
staff
Activity: 4284
Merit: 8808
July 17, 2013, 05:27:21 PM
#39
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.
staff
Activity: 4284
Merit: 8808
July 17, 2013, 05:26:28 PM
#38
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.
donator
Activity: 1218
Merit: 1079
Gerald Davis
July 17, 2013, 05:25:16 PM
#37
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.
legendary
Activity: 1862
Merit: 1011
Reverse engineer from time to time
July 17, 2013, 05:11:06 PM
#36
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.
staff
Activity: 4284
Merit: 8808
July 17, 2013, 05:07:51 PM
#35
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.
legendary
Activity: 1862
Merit: 1011
Reverse engineer from time to time
July 17, 2013, 04:59:14 PM
#34
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.
hero member
Activity: 572
Merit: 506
July 17, 2013, 04:44:12 PM
#33
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*1015 addresses at a time.
full member
Activity: 168
Merit: 100
July 15, 2013, 01:08:05 AM
#32
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.
legendary
Activity: 1344
Merit: 1000
July 14, 2013, 10:43:43 PM
#31
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
jr. member
Activity: 54
Merit: 1
July 14, 2013, 08:13:08 PM
#30
What language are we talking in

I believe it's known as "bitcointalk"

Or, y'know, math.
hero member
Activity: 572
Merit: 506
July 13, 2013, 01:49:30 AM
#29
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).
vip
Activity: 1316
Merit: 1043
👻
July 13, 2013, 01:19:26 AM
#28
Of course, that's assuming ECDSA, SHA256, and RIPEMD-160 aren't broken.
donator
Activity: 1218
Merit: 1079
Gerald Davis
July 13, 2013, 01:15:14 AM
#27
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.

vip
Activity: 1316
Merit: 1043
👻
July 13, 2013, 12:50:39 AM
#26
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.
Pages:
Jump to: