Take the 2-minute tour ×
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It's 100% free, no registration required.

Here's a what-if scenario:

Person A has a Bitcoin address with 25BTC. Person B opens up their Bitcoin client:

  • which may or may not have the complete blockchain (the latter would mean no copies of Person A's transactions)

Person B presses "New Address", and Person A's address happens to somehow be generated. Now, the blockchain finishes synchronizing.

What happens? Is this a possibilty, sans the astonishing improbability? After all, random number generation can be influenced.

share|improve this question
7  
They'd be able to spend each other's coins. –  Nick ODell Feb 16 '13 at 20:54
1  
    
doesn't labeling the address help solve some of that problem? –  user14805 Mar 24 at 21:44
    
@rponder No, the labels you attach to some addresses are just on your own computer. –  Murch Mar 24 at 22:28

4 Answers 4

up vote 14 down vote accepted

If this happens, then Person B will be able to spend person A's bitcoins. However, there are only two ways this can happen:

a) Person B generates the same keypair (private key) as person A

or b) Person B generates a different keypair, which (public key) hashes to person A's address (a hash collision)

Take a look at the specification for at bitcoin address: https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

A Bitcoin address is a 160-bit hash of the public portion of a public/private ECDSA keypair

For "a" to happen, person B would need to break "secp256k1". I am no expert on this field, but from what I can find on bitcointalk.org, then the "strength" of this is 2^128 bits. And if you're wondering how strong that is, then look for the video "Exhaustive search attacks" from Dan Boneh. 11 minutes in the video he says "anything that's bigger than 2^90 is considered sufficiently secure" (its about attacking 3DES, which is a symmetric block cipher so I'm not sure it actually apply to secp256k1, but I really have no better argument for why 2^128 is "so secure that you won't never, ever, ever generate the same key as someone else"

And for "b" to happen, you would need to find a collision on RIPEMD-160(SHA-256(pk)). As far as I know, then neither RIPEMD-160 nor SHA-256 is known to have any vulnerabilities to hash collision attacks. So somehow breaking both or randomly generation a key which hashes is exactly the same as another bitcoin address, is highly unlikely.

There is also a chance for you computer to catch on fire, and some of the materials to melt together into a lotto coupon with winning numbers on (and a valid barcode), but it just won't happen because of the chance is so unbelievably small (it's the same with the "click and generate another persons bitcoin address").

EDIT Woops, one important thing: This all assumes that all bitcoin addresses are properly generated using "true random". All brain-addresses and addresses generated using a bad PRG, might be easy to find by either using a flaw in the PRG or exploit the (flaws in the) human brain.

share|improve this answer
2  
Your case "b" is a (multi target) second pre-image, not a collision. You want to match the hash of an existing message you can't influence. A collision would be Person B creating two distinct inputs with the same hash. –  CodesInChaos Mar 19 '13 at 11:51
2  
But are all addresses verified to check for duplicates when the blockchain is synchronised by your address generating client? If there is an address collision, wouldn't it cause serious confusion and possibly substantial financial loss (if funds are transferred to person b's account since they were under the illusion they controlled it?) Can we avoid person b losing funds by alerting them an address they generated, has actually since been detected while they caught up with the blockchain? At least then person b knows to wait for sync before asking for payments to this address. –  deed02392 Oct 20 '13 at 12:16
1  
I'd say "collision" is the right concept here, because any address being regenerated (by anybody) is trouble already. The suggested alternative would imply that a single person would actively try to find such a collision, which I guess could then indeed be described as some kind of ("second"?) pre-image attack. –  pyramids Dec 15 '13 at 15:27
    
I believe case A will be far more common once Bitcoin becomes mainstream. Lots of people will use weak private keys, and plenty of them will use the same as another random guy, resulting in them both spending each other's coins :( –  Joe Pineda Mar 24 at 13:09
    
How can you calculate odds without taking into account processing power and its exponential increase? Yes, bitcoin has some protection against that... but it's a significant factor. An alien civilization with black-hole-like-dense quantum computers have probably already stolen all your coins in some infinity of paralellel universes... bitcoin.stackexchange.com/questions/6062/… –  Dagelf Aug 7 at 11:54

This is the way I see it. The total number of bitcoins that will ever be mined is 21 million. The smallest bitcoin unit is a satoshi (0.00000001 BTC). If we place all possible satoshis into a wallet of their own, we would get the maximum number of wallets that could have any balance to them (so the actual number of wallets with bitcoins is obviously less). This is 21x10^6(BTC) x 10^8 (satoshi/BTC) = 21 x10^14 wallets. It's a huge number, but it's eclipsed by 2^256 possible wallets. So in this worst case scenario, the probability of guessing a wallet with one satoshi is 21x10^14/(2^256)=1.813595x10^-62. An incredibly small number.

share|improve this answer
3  
By the Birthday Problem, the odds of two people have the same address in that situation would be about 1-e**(-((21*1014)**2)/(2*(2256))) . That's like 1 atom compared to the number of atoms in the Earth. Quite small. –  Eyal May 3 '13 at 7:08
1  
This answer doesn't address the main question "What would happen if two users generated the same address?", rather just evaluates the likelihood of the question being relevant, which the asker already seems to have been aware of. This answer would be a better fit on e.g. How many Bitcoin addresses are there? or Is it possible to brute force bitcoin address creation in order to steal money?. –  Murch Mar 24 at 12:51

I suspect the simple answer is that Person B would be able to spend Person A's bitcoins, as he would show up in the ledger as owning them. Not dissimilar from simply giving someone your wallet.

share|improve this answer
3  
I'm not sure that this is fundamentally different than Nicolai's answer. Nicolai just goes into more details. i.e. whether it was just a public key hash that collided or a true duplicate key pair. As well as details on the improbability of that happening. –  David Ogren May 3 '13 at 13:20

Funny how people claiming to know about crypto can't calculate probabilities.

The address space of 2128 is not the probability or "strength" of anything (other than the probability of picking a value in the address space).

The probability of 2 people having the same bitcoin address is actually a lot higher than people may suspect by (faulty) intuition.

In fact, the likelihood of collision is related to the Birthday Problem (read about it).

As the number of people and addresses generated increases, likelihood of a collision increases close to exponentially.

Given a few million users each generating a new address per month, the likelihood of a collision is such that it could occur several times in a lifetime, especially as we're dealing with hashes (or hashes of hashes).

Make it a billion users and you have regular stories of collisions appearing.

share|improve this answer
5  
Actually, the probability of a collision goes up as the square (i.e. quadratically) of the number of bitcoin addresses used. Not exponentially. Now, with that correction the probability of a collision is approximately zero in the lifetime of the solar system. –  Neal Gafter Feb 17 '13 at 6:47
1  
I believe that I am reading wikipedia there needs to be ~2.2×10^19 bitcoin address until there is a 50% probability that there has been at least one collision. So basically don't worry. –  Peter Micheal Lacey-Bordeaux Feb 18 '13 at 3:05
1  
Birthday problem on 160 bit bitcoin addresses doesn't apply, since collisions are irrelevant. It's a second pre-image attack which has cost (2^160)/n where n is the number of targets. So if all 21 million bitcoins are already mined, you need to calculate (2^160)/(21*10^6) = 7*10^40 = 2^135 hashes per stolen bitcoin. Which is not profitable (by far), even if you assume bitcoin is used for all of our economy. –  CodesInChaos Mar 19 '13 at 11:57
    
-1 for this incorrect answer. Here's my attempt at explaining the issue: Having users generate N addresses (which could be 1000 times the number of users) leads, typically, to approximately one bitcoin address collision in the entire system of addresses (yes, it is bad enough if any two addresses match) once N^2 = 2^160 or N = 2^80. So until we come into the vicinity of a billion times a billion users, we won't see a collision. The only reason we don't have N^2 = 2^256 or N = 2^128 is that the public key is weakened by hashing to a 160 bit public bitcoin address. –  pyramids Dec 15 '13 at 15:20

protected by Community Mar 27 at 21:32

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.