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

[theymos]

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

[Jered Kenna (TradeHill)]

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

[theymos]

The probability of any specific address is 1 in 2^160 or 1.4x10^48 right?

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

So the more addresses you have out there the higher the chance of a collision right (birthday problem?)

Yes. It is a birthday problem.

[Jim Hyslop]

The probability of any specific address is 1 in 2^160 or 1.4x10^48 right?

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

So the more addresses you have out there the higher the chance of a collision right (birthday problem?)

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.

[theymos]

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

[Alex Beckenham]

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.

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

[SteveB]

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.

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?

[Jered Kenna (TradeHill)]

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

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.

[Alex Beckenham]

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.

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?

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?

[Meni Rosenfeld]

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

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.

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 to parse "1 in 2^160" in the sense we mean here.

[nster]

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

[Jered Kenna (TradeHill)]

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.

[river]

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.

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?

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.

[SteveB]

Wow, river woke up in a foul mood.

.. look at a picture of me and try to guess how long it's been since I got laid ...

That explains a lot.

[gigabytecoin]

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.

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?

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

[nster]

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.

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?

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

[Jim Hyslop]

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?

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

[Jim Hyslop]

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?

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.

[Jered Kenna (TradeHill)]

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?

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?

[Jim Hyslop]

There an ETA on that patch?

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