Topic: possible to use up ALL wallet address combinations? (Read 4276 times)

Right. It's telling that we are arguing about the number of atoms in the universe, etc. A collision is simply not something we should be worrying about before disruptive technology such as quantum computing or the invalidation of mathematical theories established before Christ (Euclid 300 BCE).

In order for brute forcing a collision to be more profitable than generating a block, then the current target divided by the number of money-holding addresses (10M?) must be less than one, but it's currently something like 1594393648759678455702984006915721031668773442824246741.

Ack! You're right. I confused powers of 10 with powers of 2.

In any event, creating a 160-bit hash collision is vastly easier than anything that would constitute an attack on bitcoin, and nobody's even close to doing that yet. And even if they did, we'd just respond by using the full 256-bit public key.

Sorry JoelKatz. I know you mean to say "It's highly unlikely" (TM), but you're way overestimating the address space which is numerous orders of magnitude LESS than the number of atoms in the universe (what I think you mean by particle), so if every atom generated just ONE address, the vast majority of them would be expected to collide with others. In fact, unique values would be exceedingly rare.

Is it possible that some individual on the planet has a unique birthday?


This estimate is accurate to about one order of magnitude. If every atom of the Earth generated ONE address, then the chance of collision approaches 100% and only about half of all addresses would be expected to be unique.

A random collision is useless. Take that 38,000 years, make it 38,000,000,000,000,000 years. CPU power doubling, ehh I still think we're safe...for now. =)

I guess I'm the moderate, then, for predicting failure in 38,000 years 

So far the technology seemed to have been able to double available computation power every 18 to 24 months, how would that reduce the time for getting a collision?

I love it, forum posts consist of either

1) Bitcoin won't last more than 1 month
or
2) Bitcoin breaks after 1,000,000,000,000,000,000,000,000,000,000,000,000 years

I dunno dude I've been repeatedly hitting refresh at instawallet.org...

Can anyone confirm if this is possible?


First who uses them wins.

Well, what's the consequences IF wallet addresses are reused?

Do we get X times the amount transacted, one in each wallet or do they simply become invalidate coins or the winner is whoever uses those coins first?

The size of the 160 bit SHA-1 key space is in the same order of magnitude as the number of atoms in the Earth (~10^50)

Request to merge with topic 27277. http://forum.bitcoin.org/index.php?topic=27277.msg344652#msg344652

I'd be comfortable with an address space equal to the number of atoms in my toilet bowl.

Good points, but it's not so much the worry about a rare event, but about whether someone can, with sufficient devoition and accessible means, cause the event.  If people just generate keys as needed, that's no big deal; the question, rather, is how much damage someone can do if they deliberately generate as many keys as possible, optimizing the hardware/software specifically for this application.

Some further related worries:

1) The collision calculations assume effectively random selection of addresses.  If there's any correlation between how bitcoin clients choose addresses, the collision probability is much higher.  How does the main client ensure high-quality randomness?

2) Is every value from 0 to 2^160 really usable as an ECDSA public key?  I mean, with RSA, you can't just pick any ol' 4096-bit number as your public key modulus: it has to be the product of two "big", "high-quality", "compatible" semi-primes (though I don't know how much this collapses the keyspace).  Can I securely use 1 as much bitcoin public key?

3) Aren't these keypairs the same as those used in any application of 160-bit ECDSA?  Meaning that any user of a 160-bit ECDSA keypair -- not just those who use it for bitcoin -- represents a potential collision?  Meaning that we have to worry not just about Bitcoiners using up the keyspace, but Bitcoiners plus every other user of that signature algorithm that's 160-bit?

Sounds profitable

A simple collision would not gain you very much. You would need a collision with an already used address or otherwise you would not be able to cause any harm or profit anything from it. This is why the Birthday attack does not help you here.

Since such threads pop up every once in a while: I always find it funny how people tend to overestimate the probability of some extremely rare event. I mean, mankind is probably more likely to get extinct by the impact of a green striped meteorite tomorrow and I don't see anyone worrying about that (ok, this is the Bitcoin forum - I guess there are other forums where people actually do worry about green striped meteorites

Anyway, I guess we're safe regarding the keysize for the time being, barring some cryptoanalytic breakthrough of course.

Correct me if I'm wrong, but the relevant metric (under the paranoia security model) is the average time to find a collision, not time to exhaust the address space.  And I thought that that value was equal to the square root of the size of the address space, which, per Maged's post's value, would be ~1.2 x 10^24.

So if a network of comparable size to that of bitcoin miners instead devoted itself to generating addresses, they could feasibly get ~1 trillion/sec.  This would get a collision in ~38,000 years.  Not bad, but a lot sooner that the obscenely huge numbers posted in the thread.

Also, in order for an upgrade to larger keysizes, everyone would have to void the balances held by their existing addresses and transfer them to the larger-key addresses, and have those transfers incorporated into the blockchain, all before anyone could spend they coins in a collided address.

So, I've been kind of worried that maybe the ECDSA keysize was chosen to be a bit too small.  Well ... several bits too small 

(Still sort of a crypto newb, please don't take offense, just let me know if I'm relying on questionable assumptions here.)

remotely relevant and quite funny: http://xkcd.com/865/

If address collisions where likely, you could bruteforce keys to bitcoins. 2^160: too big a search space. ou can start vanitygen on a search, though and it will find the key to any address, just takes some time:

Using vanitygen, my computer can generate over 1.5 million addresses a second, and I think some people are getting several million using their GPU. So we may be able to get down to only 10⁴⁷ years or so.

If anything it should be (24+25+9)^34 = 58^34 ~ 9.05 * 10^59. But as Maged says the correct calculation is 2^160. And we're not ever going to run out of addresses.

If mankind doesn't restructure the entire human body, it's unlikely our species can survive more than 10^9 years from now on earth. If we don't fuck up everything before, obviously. Just as a side note.

If every particle in the known universe could create a billion addresses a second for the entire age of the universe, they would generate about one-quintillionth of the possible addresses.