Bitcoin Forum
December 06, 2016, 09:54:30 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 [3] 4 »  All
  Print  
Author Topic: What are the odds we'll find a collision by the time the last bitcoin gets mined?  (Read 6860 times)
theymos
Administrator
Legendary
*
Offline Offline

Activity: 2492


View Profile
March 26, 2011, 09:05:03 PM
 #41

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 2160 per attempt, as you pointed out.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
1481061270
Hero Member
*
Offline Offline

Posts: 1481061270

View Profile Personal Message (Offline)

Ignore
1481061270
Reply with quote  #2

1481061270
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481061270
Hero Member
*
Offline Offline

Posts: 1481061270

View Profile Personal Message (Offline)

Ignore
1481061270
Reply with quote  #2

1481061270
Report to moderator
1481061270
Hero Member
*
Offline Offline

Posts: 1481061270

View Profile Personal Message (Offline)

Ignore
1481061270
Reply with quote  #2

1481061270
Report to moderator
Jered Kenna (TradeHill)
Sr. Member
****
Offline Offline

Activity: 420



View Profile WWW
March 26, 2011, 09:22:34 PM
 #42

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

moneyandtech.com
@moneyandtech @jeredkenna
theymos
Administrator
Legendary
*
Offline Offline

Activity: 2492


View Profile
March 26, 2011, 09:37:32 PM
 #43

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

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

Yes. It is a birthday problem.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
Jim Hyslop
Member
**
Offline Offline

Activity: 98


View Profile
March 27, 2011, 05:26:56 AM
 #44

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

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

Like my answer? Did I help? Tips gratefully accepted here: 1H6wM8Xj8GNrhqWBrnDugd8Vf3nAfZgMnq
theymos
Administrator
Legendary
*
Offline Offline

Activity: 2492


View Profile
March 27, 2011, 06:00:25 AM
 #45

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

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
Alex Beckenham
Full Member
***
Offline Offline

Activity: 154


View Profile
March 27, 2011, 07:49:58 AM
 #46

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
Full Member
***
Offline Offline

Activity: 170


View Profile
March 27, 2011, 10:58:41 PM
 #47

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)
Sr. Member
****
Offline Offline

Activity: 420



View Profile WWW
March 28, 2011, 12:15:13 AM
 #48



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


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.

moneyandtech.com
@moneyandtech @jeredkenna
Alex Beckenham
Full Member
***
Offline Offline

Activity: 154


View Profile
March 28, 2011, 02:44:35 AM
 #49

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
Donator
Legendary
*
Offline Offline

Activity: 1890



View Profile WWW
March 28, 2011, 03:51:04 AM
 #50



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


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.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
nster
Full Member
***
Offline Offline

Activity: 126



View Profile
March 28, 2011, 06:58:29 AM
 #51

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

167q1CHgVjzLCwQwQvJ3tRMUCrjfqvSznd Donations are welcome Smiley Please be kind if I helped
Jered Kenna (TradeHill)
Sr. Member
****
Offline Offline

Activity: 420



View Profile WWW
March 28, 2011, 11:30:58 AM
 #52

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.


moneyandtech.com
@moneyandtech @jeredkenna
river
Guest

March 29, 2011, 05:44:24 AM
 #53

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?Huh?  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 Sad ... 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
Full Member
***
Offline Offline

Activity: 170


View Profile
March 29, 2011, 07:10:28 AM
 #54

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 Sad ...
That explains a lot.
gigabytecoin
Sr. Member
****
Offline Offline

Activity: 280


View Profile
March 29, 2011, 08:26:31 AM
 #55

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
Full Member
***
Offline Offline

Activity: 126



View Profile
March 30, 2011, 08:32:11 AM
 #56

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

167q1CHgVjzLCwQwQvJ3tRMUCrjfqvSznd Donations are welcome Smiley Please be kind if I helped
Jim Hyslop
Member
**
Offline Offline

Activity: 98


View Profile
March 31, 2011, 01:53:53 AM
 #57

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.

Like my answer? Did I help? Tips gratefully accepted here: 1H6wM8Xj8GNrhqWBrnDugd8Vf3nAfZgMnq
Jim Hyslop
Member
**
Offline Offline

Activity: 98


View Profile
March 31, 2011, 02:00:36 AM
 #58

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.

Like my answer? Did I help? Tips gratefully accepted here: 1H6wM8Xj8GNrhqWBrnDugd8Vf3nAfZgMnq
Jered Kenna (TradeHill)
Sr. Member
****
Offline Offline

Activity: 420



View Profile WWW
March 31, 2011, 12:23:23 PM
 #59

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?

moneyandtech.com
@moneyandtech @jeredkenna
Jim Hyslop
Member
**
Offline Offline

Activity: 98


View Profile
April 01, 2011, 12:32:37 AM
 #60

There an ETA on that patch?
I'm not sure if anyone's working on it yet.

Like my answer? Did I help? Tips gratefully accepted here: 1H6wM8Xj8GNrhqWBrnDugd8Vf3nAfZgMnq
Pages: « 1 2 [3] 4 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!