Bitcoin Address Collisions

Although extremely unlikely, what would happen if two Bitcoin clients generated the same Bitcoin address? Would payments be delivered to whichever client encountered the payment first? If there is a mechanism in place to prevent such collisions, please explain it.

For two addresses to be equal, two identical private/public elliptical curve (ec 😊) keys have to be generated. Without looking at the source code, let’s assume the probability for this is 2^(-128) for a keyspace of 128 bits. See here for a perspective on how probable it is with a 122 bit collision.

However, if something similar to the Debian ssl-scandal happens, similar keys could indeed be generated. The effect of an individual generating an existing key, is (if I understand it correctly) in effect to make a copy of wallet.dat. Not good at all, but not devastating for all the members of the p2p network.

Are you referring to the private key which is generated the first time a person runs Bitcoin? If someone were to successfully duplicate someone else’s key then after they downloaded all the blocks, they would have the same balance as the person with the original key. That’s what you’re saying, right?

I was referring to the custom Bitcoin addresses which you can label with the name of the person who is going to send you bitcoins so that you know from whom the payment came. I think these addresses are generated from the private key mentioned previously. I’m wondering about collisions because although they are very unique, they are easily generated over and over again by all by all bitcoin clients.

Are you referring to the private key which is generated the first time a person runs Bitcoin? If someone were to successfully duplicate someone else’s key then after they downloaded all the blocks, they would have the same balance as the person with the original key. That’s what you’re saying, right?

Yes, that is correct. They would share the wallet, and it becomes a race on spending the money first.

I was referring to the custom Bitcoin addresses which you can label with the name of the person who is going to send you bitcoins so that you know from whom the payment came. I think these addresses are generated from the private key mentioned previously. I’m wondering about collisions because although they are very unique, they are easily generated over and over again by all by all bitcoin clients.

If I read the source code correctly, keys are always made in pairs. That means, every address has an associated private key. When you click “New Address”, you call GenerateKey in main.cpp, which generates a new key pair. So the duplicate address is ultimately a duplicate public key. Which is very unlikely.

While keys still are “easily generated”, you should have to generate a whole lot of keys before a collision. While I am not certain, it seems that the keys generated have a space of 256 bits, which is a lot more than the 122 bits put in perspective in the wikipedia article on uuids. Remember, 123 bits have half the probability of collision as 122 bit, 124 half of that again etc.

There’s a separate public/private keypair for every bitcoin address.  You don’t have a single private key that unlocks everything.  Bitcoin addresses are a 160-bit hash of the public key, everything else in the system is 256-bit.

If there was a collision, the collider could spend any money sent to that address.  Just money sent to that address, not the whole wallet.

If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block.  You could have got a lot more money by generating blocks.

The random seed is very thorough.  On Windows, it uses all the performance monitor data that measures every bit of disk performance, network card metrics, cpu time, paging etc. since your computer started.  Linux has a built-in entropy collector.  Adding to that, every time you move your mouse inside the Bitcoin window you’re generating entropy, and entropy is captured from the timing of disk ops.

Thanks for the explanation. I think it all makes sense.

Are generated bitcoins encrypted with whichever address is currently displayed in the main Bitcoin window? I may have mentioned this in an email message quite a while ago, but it would be cool for some very future version to allow people to see which of their bitcoins are encrypted with which of their addresses.

Are generated bitcoins encrypted with whichever address is currently displayed in the main Bitcoin window?

No, each generated transaction uses a new, single-use address.

Nothing uses the address in the main window, it’s just there for convenience for you to copy.  0.2.5 has a “New…” button next to it to make it easy to change each time you use it.

Are we using a 160 bit hash (which provides for the possibility of a collision) vs a 224/256 bit hash (no possibility of a collision) so that bitcoin addresses can be shorter in length? If so, is it possible for us to transition to using a 256 bit hash at some later date?

I don’t buy the argument that it’s TOO computationally expensive to intentionally create a collision. We have already seen the use of GPUs radically alter the bitcoin mining paradigm. In the future, we may well see devices designed specifically for the task of performing hashing functions. Perhaps those devices already exist.

Why build the opportunity for fraud into bitcoin? I don’t think we need to be concerned about the number of characters of a bitcoin address when we’re copying and pasting them or using QR codes anway.

Are we using a 160 bit hash (which provides for the possibility of a collision) vs a 224/256 bit hash (no possibility of a collision) so that bitcoin addresses can be shorter in length? If so, is it possible for us to transition to using a 256 bit hash at some later date?

I don’t buy the argument that it’s TOO computationally expensive to intentionally create a collision. We have already seen the use of GPUs radically alter the bitcoin mining paradigm. In the future, we may well see devices designed specifically for the task of performing hashing functions. Perhaps those devices already exist.

Why build the opportunity for fraud into bitcoin? I don’t think we need to be concerned about the number of characters of a bitcoin address when we’re copying and pasting them or using QR codes anway.

Don’t worry, “If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block.”. This means, if you have a computer that is 1 million times as powerfull as all current miners combined, it will still take an average of 1,618,542,460,620,902,128,345,579,373 years to generate a collision.

Even if Moores law holds true in the most generous way, we still have over 100 years left before this becomes feasable.

And also: yes, devices designed specifically for performing bitcoin mining exist (Artforz had himself some ASICs (custom chips) made)

Or it could happen by some freak accident 5 minutes from now.

Your response was aimed at strengthening the computationally expensive argument.

Why are we using a 160 bit hash instead of something that is more resistant to collisions? Will we be able to move to a 224/256 bit hash if and when the need arises, even if it’s 100 years from now?

If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block. You could have got a lot more money by generating blocks.

What if your network of computers already generated and tested all the possible blocks? Sure the address haystack of possibilities is much bigger and harder to test… but if the other haystack(block generating) has bean fully counted what else is there to do?

Quote from: satoshi on February 23, 2010, 4:26:09 PM UTC

If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block. You could have got a lot more money by generating blocks.

What if your network of computers already generated and tested all the possible blocks? Sure the address haystack of possibilities is much bigger and harder to test… but if the other haystack(block generating) has bean fully counted what else is there to do?

This is sillier than asking what happens after all the atoms have been examined. Nothing, nothing happens. Even if you could look at the entire space eventually (you cannot, one trillion of you cannot) you can’t remember it either.