What are the odds we'll find a collision by the time the last bitcoin gets mined?

[NicholasBell]

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.

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.

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.

[1713524273]

1713524273

[1713524273]

1713524273

[1713524273]

1713524273

[1713524273]

1713524273

[1713524273]

1713524273

[Jim Hyslop]

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

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) 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?

[gohan]

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

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.

[FooDSt4mP]

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.

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.

[Jered Kenna (TradeHill)]

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.

[gohan]

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?

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.

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?

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.

[Jered Kenna (TradeHill)]

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?

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.

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?

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

EDIT: Corrected some remarks.

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!"

[Hal]

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.

[Jered Kenna (TradeHill)]

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.

[Hal]

The person who originally had them would lose them.

[Jered Kenna (TradeHill)]

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.

[Jim Hyslop]

The person who originally had them would lose them.

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

[m4rkiz]

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.

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?

[bencoder]

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?

[Meni Rosenfeld]

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?

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.

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.

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?

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

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).

[Jered Kenna (TradeHill)]

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?

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.

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.

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?

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

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?

[gohan]

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. 

[Meni Rosenfeld]

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.

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?

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.

[TiagoTiago]

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.

[Meni Rosenfeld]

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.