Bitcoin Forum

And can we add somthing on the clients to keep an eye for that?

Are you just curious or because it could have a really bad effect?

What would be the outcome anyways? Double spend?

A collision of what? Transaction hashes, block hashes, addresses?

The result will depend on how many items are created in that time. In any case, it's so unlikely that adding a check for it is a waste of time.

I think that the remote possibility of address collision and the ever increasing need for fees are the two biggest obstacles to the wide acceptance of bitcoins. No one will trust bitcoin with any large transactions if there is even the slightest chance of an address collision.

False. I trust it.

I understand math though ymmv.

Not everybody understands (or has the desire to understand) the math. I know that the chances of a collision is so small that it probably will never happen in a billion years. But try to tell that to some non geek.
Would you trust your money to a bank were the clerk just makes up an account number without checking if the number is already in use?

There are currently 329,993 addresses in the Bitcoin network. Say that this number of addresses are created every day for the next 140 years. That's 16,862,642,300 addresses.

The chance that at least two of those addresses collided is about 9.7x10^-29, using the formula here (http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates). Calculation. (http://www.wolframalpha.com/input/?i=1-e^%28-%2816862642300^2%29%2F%282%282^160%29%29%29)

No but only because humans are really bad at producing truly random numbers.

I get that the chance is very, very, very  small. But unless there is no chance at all there is still a chance. All I am saying is that there should be a check to make sure that a new address does not exist already.

I can think of plenty of safe methods that don't involve checking all previous account numbers. One of them would be using really long random strings. Another would be adding 1 to the last issued number. I'd actually be fairly concerned about a bank who's procedure was to compare new numbers to a complete list of old numbers.

People who don't care enough to learn whether the system is sound or not won't be refusing to use it because it isn't sound. They'll make the decision the same way they make their other decisions, asking: What are successful people doing?

There's also a chance your dollars will spontaneously combust... Checking is a waste of time, and if the address already exists when you generate it, then you're the one who gets to steal the previous balance of the address.

The chance is probably way less than the chance that a bank's computers and all of their backups will get destroyed and there will be no way of recovering bank deposits.  Has that prevented people from using banks?

This is ridiculous. Do you apply the zero chance rule to anything else in your life?

The check is impossible. I don't know if you've used the software, but you can generate addresses offline. Even if this wasn't the case having more people making ever larger numbers of comparisons to protect against one person losing the coins in one address less than one time before the heat death of the universe is crazy.

I guess we will have to disagree on that one.

I'm more concerned about somebody else generating a new address that already belongs to me and stealing my balance.

That is what deposit insurance is for.

You think deposit insurance is going to help you if every bank computer and backup is gone?

Buy collision insurance? I'll gladly sell it to you for a one time fee of .1% of insured funds.

How does generating addresses offline help with collisions? They are still not checked if they are duplicates.

I just don't think that bitcoin has any chance of being taken seriously for big amounts as long as there is even a slight chance of a collision.

What's to stop me from repurposing my miners to continuously generate new addresses?  It doesn't seem like it would take long to generate a significant chunk of the key space.

There's no chance that this will ever be profitable.

Don't be ridiculous. It seems you don't really "get that" actually.

There's also a chance that humanity is entirely wiped out by a super meteor falling on earth today. Do you pretend to add "checks" against that, or pass the rest of your life in a meteor-proof bunk?

Lets say you generate 16 billion addresses per second.
Lets say you do this for 400 years.
You now control 1.38196 × 10^-28 ratio of the addresses.
That's 0.0000000000000000000000000138196% of the key space Calculation (http://www.wolframalpha.com/input/?i=%2816000000000*3600*24*365.26*400%29+%2F+%282^160%29).

That's not really a significant chunk. I think there is more of a chance of a gene mutation that would allow a baby to be born as an adult with superpowers, then he or she could just rob banks.

Basically pretty much EVERY bad thing you can have happen to you has a larger chance of happening than an address collision.

EDIT: I must add that generating 16 billion addresses per second is beyond what a standard person can do. 16 billion addresses is 16000000000*160 bits or 298 GB minimum for just the public key portion in your wallet for just one second of those theoretical 400 years. I think most people would run out of resources fairly quick.

Wow, lots of heat in this discussion but not much light.

First, to all the nay-sayers: chill out guys. It's a legitimate question, and just because the chances of collisions happening are extremely small it is important to think about these things. I've seen many references to Steve Gibson's "Security Now" podcast, and those of you who listen regularly will know that Steve beat the odds big time, and generated a block within a couple of weeks, just by CPU mining. If there is a non-zero chance of something happening, we must analyze it to see if it can have any negative effects.

And, by the way, as the number of hashes in the system increases, the probability of a collision drops dramatically, as the birthday problem (http://en.wikipedia.org/wiki/Birthday_problem (http://en.wikipedia.org/wiki/Birthday_problem)) demonstrates.

Now, as theymos pointed out, there are several things that can collide. Let's examine them one at a time.

Block hash
If a miner generates a block that has the same hash as an existing block, it will not get accepted into the block chain. The code that accepts blocks checks the block hash to see if it already has that block. The hash will match an existing block, so the new block will be rejected. This will happen at the mining machine, since the generated block is treated exactly as an incoming block by the software.

Transaction hash
The standard client will reject a new transaction that has the same hash as an existing transaction. Each incoming transaction (including transactions generated by the client) is checked to see if the client currently has it. If it does, the client rejects it as a duplicate. Now, there is a wrinkle to this - one of the optimizations under way is to store only the block headers, and only retrieve transactions that the client actually requires.

Unfortunately, I have to leave for work now. I will finish the rest of this analysis later, unless someone else would care to take it on and continue this for me.
Edit: finishing the rest of it now.

Merkle hash
The Merkle hash for a newly-generated block exactly matches the Merkle hash of an existing block. I can't see any problems with that scenario. The block hash will still be unique, so the new block will be accepted.

One possible attack would be for someone to create a Merkle tree containing a fraudulent transaction, then try to convince other nodes to accept his Merkle tree instead of the actual one. This would only work for clients which store transaction headers only (which is something still in development). However, the whole purpose of hash algorithms is to make it "computationally infeasible" to deliberately create a hash that matches the hash of a different chunk of data. If the current hash algorithm becomes less secure, it's not too hard to switch to a newer algorithm.

Addresses
This has been fairly well covered by others, particularly Nicholas Bell's calculations on how long it would take to generate sufficient addresses to deliberately try to grab someone else's money. So it's not feasible as an attack.

Now, let's examine what would happen if it happened by chance. Suppose you and I hit that once in a billion billion lifetimes of a universe chance, and we both generate the same address. Someone sends 100BTC to that address. Both of our clients would say "Aha, that's for me!" and each of our wallets would show an increase of 100BTC. One of us would be pleasantly surprised that 100BTC suddenly appeared. Whoever spent it first would be successful, and the other one would see a mysterious disappearance of 100BTC.

So this is a theoretical possibility, but there is a far greater probability that you will lose your money through bank error or the bank going bankrupt (which is possible even in countries with strong economies and strong banks - just think of what happened to Lloyd's Bank in England 15 or 20 years ago).


So the bottom line is, yes it is possible that there will be collisions, but there is only one scenario where that could actually do any harm, and the chances of it happening are so close to zero it's not worth worrying about.


I think that covers the possible collisions. Have I missed any?

Maybe somebody could think of a complex heuristic but not doing it was the sane choice IMO. Creating a vulnerability while doing that (and being hit by a meteorite at the same time) still has a much higher probability. I would become a paranoid person after the moment I implemented such a thing for the rest of my life.

EDIT: Uh, the post I replied disappeared. :)

I'm just playing devils advocate... I'm not worried about it one bit.  However, as NicholasBell worked out, there is a chance.  It's just tiny.  I think people just want it acknowledged that it is possible, but very unlikely.  You can't get to 0 with a constant, nonzero number.  You can only get there if it works for every progressively smaller epsilon.  However, expressing exactly how tiny the risk is will help people understand what steps (if any) should be taken to mitigate it.  As I said, I don't think it's big enough to justify any mitigation.

I'm not that great with statistics. Could someone who's better than me put these odds in to perspective for us?
For example if the chance of a collision (transaction) 9.7x10-29 how would that compare to say winning the lottery (US powerball)

Winning it 2 days in a row? Everyday for a week? Month? 700 years?

Flipping a coin and getting heads 1000 times in a row? or 100000 or flipping it every 10 seconds and getting heads  for 6 months?

I realize this number is huge but I think it would be interesting to figure it out in those scenarios just to have something that shows really how rare it is.

According to Wikipedia, probability of hitting the Jackpot in US powerball is 1 in 131,278,024. So the probability of you winning each and every day for more than 20 quintillion years (or 20 million trillion years) is roughly the same as finding a collision. That's about 1.5 billion times the age of our universe. If you win every second, you'll still have to win for 234 trillion years.


Getting heads constantly every second for a time interval that is about a trillion times the age of the universe.

EDIT: Corrected some remarks.

EDIT: These are completely wrong. I made a fool of myself, check out Holy-Fire's reply below. Guys, I have a maths degree, hush.

Jesus Christ. I figured it was something like the lottery everyday for a year, not that long.
I'm going to say that despite it being "possible" planing for it is not worth it.

Now I'm sure someone is going to come along and play Lloyd Christmas and say "So you're saying it's got a chance!"

Adding a check for a sufficiently low probability event means that the overwhelming majority of the time, the CPU or memory glitched, and it is a false alarm.

Adding checks for address hash collisions with existing addresses would not protect you against the creation of an address in the future whose hash collides with yours.

If you ever did generate an address whose hash collided with an existing address, you could steal any bitcoins held by that address. So you might not want to throw this windfall away.

I'm with you, seems like something we wouldn't want to implement but when you say steal the bitcoins do you mean the person who originally had them would lose them or that the amount in the market would just increase by that amount? Basically copying them.

The person who originally had them would lose them.

Ok then we can't look at it like getting lucky if there's a 50/50 chance you're the guy that loses them instead of gets them haha.

Still the odds are so so astronomically high that if you're not willing to risk it you're not thinking clearly.
I think it's funny that the same people that won't risk losing one transaction on the a chance that big would feel safe with their money in a conventional bank.

Thanks again for doing all that math and laying it out there.

Actually, whoever spent the coins first would get them, and the other person would lose them.

why bother when you have better chance that you will die in car collision while stoked by both lightning and meteor at the same time?

How are the addresses generated? By that, I mean, what's used to seed the random number generator?

Obviously it's correct that mathematically, collisions are insanely improbable. But if the method used to generate the random numbers is insecure or compromised then that's a much much greater problem. I think on linux /dev/random uses noise from system devices but is this guaranteed? And how does it work on windows?

Dear god, no, that's completely wrong. You did (1/131M)/(9.7E-29), when it should be log(9.7E-29)/log(1/131M) = 3.45. So it's like winning the lottery 3-4 times in a row.

Again, no. It's like getting 93 heads in a row: log(9.7E-29)/log(0.5).

The point remains, though. That's an extremely small probability. Collisions aren't going to happen and there's no need to be concerned about it (assuming the PRNGs used are half-decent. They don't need to be good).

That's a hell of difference in math.

Not that I don't have faith in either of your calculations but can someone else help settle this?

No, he is right. As I wrote above, I have made a terrible mistake and I'll return my diploma the first chance I get.  :(

Give it to me. I could use an extra degree. :)

It's just common sense, really. A Bitcoin address is just a 160-bit number. If you want to randomly generate an address and have it exactly match some other address, you need every bit to match. Every bit is like a coin toss, so it's like 160 tosses. The probability for that is 0.5^160 = 6.84E-49. I didn't examine the calculations for the larger 9.7E-29 figure (equal to 93 tosses) but it's probably the chance to succeed in one of a large number of attempts.

it's not 160 tosses, it's two sets of 160 tosses where each toss in each set exactly matches the result of the same toss on the other set.

That's exactly the same as far as probability is concerned. Also, unless I'm misunderstanding something about the protocol (which is likely), the 160-tosses version I described better represents the scenario I gave, of trying to replicate a specific address.

It's the probability of any two addresses matching in a set of ~17 billion random addresses. The probability for finding one specific address is 1 in 2¹⁶⁰ per attempt, as you pointed out.

I want to make sure I have this right since I'm not too good with probability.

The probability of any specific address is 1 in 2^160 or 1.4x10^48 right?
So the more addresses you have out there the higher the chance of a collision right (birthday problem?)
I understand the birthday problem and how it works, combining that with the rate addresses are generated makes my head hurt but inspires me to take a probability class.

Maybe I'm over complicating it or not making it complicated enough. Math is my weakpoint.

It's ~6.84x10^-49. Did you put "1 in 2^160" in Wolfram Alpha?  ;)


Yes. It is a birthday problem.

That depends. I've lost track of the specific problem being addressed, so pardon me if I'm adding extra detail that isn't necessary.

If you are just trying to find out if any two keys match, then it's the birthday problem, i.e. "do any two people in my class have the same birthday?" If you are trying to match a specific key, then it's a much huger problem to solve - you're now asking "does anyone else in my class have the same birthday as me?"

And the whole problem still has another layer of complexity, because you aren't trying to find just any old block of 160 bits. You're trying to find a 160 bit hash of a much larger public key, for which you also need the private key. So to create a collision, you have to generate a key pair, hash the public key and see if it matches. That's assuming you're trying to deliberately create a duplicate, as opposed to stumbling upon one.

Edit: I realized the public key isn't necessarily larger, it's just different.

I'm talking about the case of any hash matching any other hash. That was my reading of the OP's question.

In addition to that, you should keep in mind the % of transactions that are "my entire life savings". It's far more likely that even if the above scenario took place, it'd be a micro-transaction.

I'm just guessing because I haven't seen studies or stats on this anywhere, but I'd say the majority of transactions are for tiny amounts, then a smaller number of them are for 'large' transactions, then an even smaller number again would be for "this is everything I've got!"-type transactions.

So if you're really that paranoid, you could somewhat reduce your (already insanely low) risk by sending multiple small amounts, instead of one large. (Edit: And by sending any large amounts you receive immediately to a 'savings' address.)

That is exactly what I do. Whenever I receive a payment that is larger than 20BTC, I send it to a savings wallet in smaller chunks.

But here is my question: Let's say I send 10BTC to my savings address. Then I send another 10BTC to the same savings address.
How are these two transactions treated in the savings wallet?
Do they get combined or do they stay separate?
Should there be an address collision (I know, it's very unlikely), are both amounts vulnerable or only one of them?

Haha google, guessing Wolfram Alpha would have the same result. I'll give it a try.
Now why did google give me the wrong answer, 2^160 is pretty simple math.

Good question. Say you had a savings address that had 1000BTC but was pretty much always offline, and you never spent it. Then one day an address collision occurs and someone else out there has the same address as your savings account. Could they instantly be able to spend your 1000BTC from their client, even though you save that money before the collision occurred?

Wrong answer, or wrong question? 2^160 = 1.46*10^48, 0.5^160 = 6.84*10^(-49), and 1 in 1.46*10^48 is 6.84*10^(-49).
Wolfram|Alpha, by the way, fails spectacularly (http://www.wolframalpha.com/input/?i=1+in+2^160) to parse "1 in 2^160" in the sense we mean here.

I don't shower anymore:
Odds of fatally slipping in bath or shower: 2,232 to 1
Odds of drowning in a bathtub: 685,000 to 1

Nor do I ever get out of my anti-lightning cave:
Odds of being struck by lightning: 576,000 to 1

Odds of being killed by lightning: 2,320,000 to 1

Nor do I ever get on a plane:
Odds of being on plane with a drunken pilot: 117 to 1

I think imana be rich soon:
Odds of becoming president: 10,000,000 to 1

Odds of winning the California lottery: 13,000,000 to 1

Odds of becoming a saint: 20,000,000 to 1

BUT MOST OF ALL, I GOTS AN ANTI-METEOR HOUSE!!!:
Odds of a meteor landing on your house: 182,138,880,000,000 to 1
UNDER 5.491x10^-15

It's funny but you've got a really good point.

SteveB ... you know, with all the complaining you do about BTC why the hell are you using it?????  Seriously, I would never do business, or for that matter be friends with someone who only sees the negative side of things.  Life is imperfect, suck it up, deal, and move the @#$ on.  The only absolute in this life is that you will die at some point.  I don't see you bitching about cars, computers, clothing,  electronics etc., etc., etc that are all imperfect.

If you so f%^ scared of loosing some money then why do you have any, of any currency or denomination to begin with, I mean seriously, when I'm trying to get new manufacturers/wholesalers/clients/people/etc .. and they want to know about bitcoin, I refer them to www.bitcoin.org and say .. "every thing you need to know is there, it's your choice, contact me if you interested" and I do NOT answer questions because I do not know everything about them and I'm not going to give out false info. ... simple ... if they are interested they'll do it .. if not .. leave them . move on to the next that WILL be interested and not care about every little perceived flaw in existence.

Your scared about loosing BTC in your wallet .. make a bunch of addresses then divide your own BTC between all your own addresses ... a little here, a little there ... diversify .. minimal risk .. done!

Dude, we all have better things to do ... including you.  You want to worry ... he he he .. look at a picture of me and try to guess how long it's been since I got laid :( ... or look up conspiracies/cops/governments/etc and go nuts .. otherwise  .. it's just money, use it, don't .. whatever  ... just shut the f#@$ up move on.

Wow, river woke up in a foul mood.

That explains a lot.

No, because whatever I deposit into my bank is backed up by at least $100k by the Canadian Deposit Insurance Corporation.

see : http://bitcointalk.org/index.php?topic=4858.msg73851#msg73851

I do not think people are scared to go outside because they are scared of getting hit by lightning, nor does anyone live 20 meters under land in order to not get hit by a meteor

They are kept separate, but both amounts are vulnerable, if the addresses have collided. Better to send them to distinct addresses.

Using the current standard client, yes, but it may not be instantaneous. Currently, every client has a copy of all transactions ever made, so when they generate that address and rescan the wallet, then the client will see the 100BTC transaction, see that the private key for that transaction is in the wallet, and claim the transaction as theirs.

Now, when the "headers-only" patch goes through, then it's less likely but still possible. Depends how the patch is implemented.

There an ETA on that patch?

I'm not sure if anyone's working on it yet.

That number should be enough for you.

That number is smaller than the chance of you getting hit by lightning, your wife/SO stealing all your physical money, your bank account being hacked/robbed, your insurance being canceled, and then your home and car being destroyed... all in the same day.

Nothing has a zero percent chance of happening.  Very small numbers can and do suffice.