Topic: What are the chances of an address collision? and what happens when it does? - page 2. (Read 22435 times)
November 03, 2012, 05:45:32 PM
November 03, 2012, 05:40:48 PM
I'm not saying collisions anywhere close to likely to occur, but...
This is the chance of finding a collision when generating 1 address.
The chance of a collision occuring "at all" is higher.
Let's assume (worst case) we use bitcoin for 1E3 years and there are 1E10 people populating earth at any point in time who will generate on average 1E3 addresses during their lifetimes.
What are the chances of a collision to occur under these assumptions?
Given your example of 1 billion users at 10 addresses each:
There are 2^160 or about 1,460,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible addresses
In your scenario, 1,000,000,000 people are using 10 addresses each for a total of 10,000,000,000 possible addresses
10,000,000,000 / 2^160 should yield the probability of a collision occurring
10,000,000,000 / 2^160 = 0.00000000000000000000000000000000000000684
So the chances of a collision occurring in your scenario are approximately 0.000000000000000000000000000000000000684%
There are 2^160 or about 1,460,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible addresses
In your scenario, 1,000,000,000 people are using 10 addresses each for a total of 10,000,000,000 possible addresses
10,000,000,000 / 2^160 should yield the probability of a collision occurring
10,000,000,000 / 2^160 = 0.00000000000000000000000000000000000000684
So the chances of a collision occurring in your scenario are approximately 0.000000000000000000000000000000000000684%
This is the chance of finding a collision when generating 1 address.
The chance of a collision occuring "at all" is higher.
Let's assume (worst case) we use bitcoin for 1E3 years and there are 1E10 people populating earth at any point in time who will generate on average 1E3 addresses during their lifetimes.
What are the chances of a collision to occur under these assumptions?
The probability of a collision is found by a standard formula: p = 1 - k! / Nk-1(N-k)!, where k is the number of hashes generated (100x1010x103) and N is the number of possible hashes (2160).
This is a difficult number to calculate, but there is a good approximation: p = 1 - e-k(k-1)/2N
But even that value is difficult to compute because of the precision needed. Here is another approximation p = k2/2N.
So the answer is that the probability of at least one collision is approximately 7x10-19 or 0.00000000000000007%
See: http://preshing.com/20110504/hash-collision-probabilities
November 03, 2012, 05:37:02 PM
We should apply for the Nobel prize
November 03, 2012, 05:31:21 PM
Ok, new data, will recalc everything:
is my math roughly correct now?
If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".
- probability of getting struck by lightning in any given year: 1/280000.
- probability of taking a shit at any given point in time: 1/(60*24) = 1/1440 (assuming you take a crap every day and the actual process takes 1 minute)
- probability of getting struck by lightning while taking a crap in any given year: 1/(280000*1440) = 1/1.47E11 = 2.48E-9
- probability of taking a crap while being in a situation where being struck by lightning can actually occur = 1/1440 = 0.25 = 1.74E-4
- probability of finding a collision: 1E-65
- getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(1.74E-4) = 17.3
is my math roughly correct now?
If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".
You, good sir, have surely created the new standard of explaining address collision probability to noobs. I will refer to your great work in any instance I'm asked this question.
+1 great work, will save for future reference
November 03, 2012, 05:27:07 PM
You, good sir, have surely created the new standard of explaining address collision probability to noobs. I will refer to your great work in any instance I'm asked this question.
craptastic!
At this point, let me express my sincere thanks to the following people who either laid the foundation for, hardened or otherwise contributed to my work:
- kokojie
- enmaku
- DeathAndTaxes
- paraipan
- runeks
- flynn
- mskwik
- FreeMoney
(I hope I didn't forget anyone)
Thank you guys!
I'm looking forward to further improvements based on my work!
November 03, 2012, 04:46:52 PM
Ok, new data, will recalc everything:
is my math roughly correct now?
If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".
- probability of getting struck by lightning in any given year: 1/280000.
- probability of taking a shit at any given point in time: 1/(60*24) = 1/1440 (assuming you take a crap every day and the actual process takes 1 minute)
- probability of getting struck by lightning while taking a crap in any given year: 1/(280000*1440) = 1/1.47E11 = 2.48E-9
- probability of taking a crap while being in a situation where being struck by lightning can actually occur = 1/1440 = 0.25 = 1.74E-4
- probability of finding a collision: 1E-65
- getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(1.74E-4) = 17.3
is my math roughly correct now?
If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".
You, good sir, have surely created the new standard of explaining address collision probability to noobs. I will refer to your great work in any instance I'm asked this question.
November 03, 2012, 02:58:25 PM
I think Science just made a very impressive progress here.
November 03, 2012, 02:54:27 PM
1 minute is a nice crap, the average is going to be several times longer.
I want the lightning to strike while you are actually in the process of pushing. The wiping is irrelevant
Jokes aside: I'm trying to not overestimate, so I took 1 minute. I doubt many will be quicker.
November 03, 2012, 02:51:33 PM
1 minute is a nice crap, the average is going to be several times longer.
November 03, 2012, 02:45:18 PM
Ok, new data, will recalc everything:
is my math roughly correct now?
If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".
- probability of getting struck by lightning in any given year: 1/280000.
- probability of taking a shit at any given point in time: 1/(60*24) = 1/1440 (assuming you take a crap every day and the actual process takes 1 minute)
- probability of getting struck by lightning while taking a crap in any given year: 1/(280000*1440) = 1/1.47E11 = 2.48E-9
- probability of taking a crap while being in a situation where being struck by lightning can actually occur = 1/1440 = 0.25 = 1.74E-4
- probability of finding a collision: 1E-65
- getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(1.74E-4) = 17.3
is my math roughly correct now?
If so, I can say: "Finding a collision is about as likely as being struck by lightning while taking a crap every year for 17 years in a row".
November 03, 2012, 02:40:26 PM
And then of course you need to consider if there is some correlation between your current location and the chance of being struck by lightning...
I thought about that before. The answer is: in case I'm out in the rain on some field close to a tree, the probability of me actually taking a crap is about 4 times lower than when I'm at home. If you have to crap, you have to crap
So that should get factored in.
November 03, 2012, 02:40:05 PM
probability of taking a shit at any given point in time: 1/(60*24) here I still disagree with your previous post
You are correct as I said before p_shit = 1/(60*24)
Wait, let me reconsider.
probability of getting struck by lightning in any given year: 1/280000. (your number)
probability of getting struck by lightning in any given day: 1/(365*280000).
probability of taking a shit at any given point in time: 1/(60*24) here I still disagree with your previous post
prob to be stuck on a particular day = p_day = 1/(60*24*280000*365) right I forgot 1/365 here
probability of getting struck by lightning in any given year: 1/280000. (your number)
probability of getting struck by lightning in any given day: 1/(365*280000).
probability of taking a shit at any given point in time: 1/(60*24) here I still disagree with your previous post
prob to be stuck on a particular day = p_day = 1/(60*24*280000*365) right I forgot 1/365 here
that one is still wrong, correct is:
p_day = 1 - ( 1 - p_year ) ^ 365 ) <- I know you know that formula
by your logic:
p_day = p_year / 365
p_year = p_day * 365
you would be SURE to get hit by lightning within 280000 years:
p_280000 = p_year * 280000 = 1
Damn, you're right
altho with small numbers like this, it's about the same.( because 1-p ~ 1)
November 03, 2012, 02:35:21 PM
And then of course you need to consider if there is some correlation between your current location and the chance of being struck by lightning...
November 03, 2012, 02:32:35 PM
probability of taking a shit at any given point in time: 1/(60*24) here I still disagree with your previous post
You are correct as I said before p_shit = 1/(60*24)
Wait, let me reconsider.
probability of getting struck by lightning in any given year: 1/280000. (your number)
probability of getting struck by lightning in any given day: 1/(365*280000).
probability of taking a shit at any given point in time: 1/(60*24) here I still disagree with your previous post
prob to be stuck on a particular day = p_day = 1/(60*24*280000*365) right I forgot 1/365 here
probability of getting struck by lightning in any given year: 1/280000. (your number)
probability of getting struck by lightning in any given day: 1/(365*280000).
probability of taking a shit at any given point in time: 1/(60*24) here I still disagree with your previous post
prob to be stuck on a particular day = p_day = 1/(60*24*280000*365) right I forgot 1/365 here
that one is still wrong, correct is:
p_day = 1 - ( 1 - p_year ) ^ 365 ) <- I know you know that formula
by your logic:
p_day = p_year / 365
p_year = p_day * 365
you would be SURE to get hit by lightning within 280000 years:
p_280000 = p_year * 280000 = 1
November 03, 2012, 02:25:15 PM
Wait, let me reconsider.
probability of getting struck by lightning in any given year: 1/280000. (your number)
probability of getting struck by lightning in any given day: 1/(365*280000).
probability of taking a shit at any given point in time: 1/(60*24) here I still disagree with your previous post
prob to be stuck on a particular day = p_day = 1/(60*24*280000*365) right I forgot 1/365 here
probability of getting struck by lightning in any given year: 1/280000. (your number)
probability of getting struck by lightning in any given day: 1/(365*280000).
probability of taking a shit at any given point in time: 1/(60*24) here I still disagree with your previous post
prob to be stuck on a particular day = p_day = 1/(60*24*280000*365) right I forgot 1/365 here
November 03, 2012, 02:00:41 PM
@molecular
ha ok, I get it now.
So
should be :
prob to be stuck on a particular day = p_day = 1/(60*24*280000)
probability of NOT getting stuck on a particular day = 1-p_day
probability of NOT getting struck by lightning while taking a crap in any given year = (1-p_day)^365
probability of getting struck by lightning while taking a crap in any given year = 1-((1-p_day)^365)
note that p_day is much lower that the prob. to be stuck in a year, since you get another 'chance' every other day of the year ...
not so easy huh ?
ha ok, I get it now.
So
Quote
probability of getting struck by lightning while taking a crap in any given year: 1/(280000*525600) = 1/1.47E11 = 6.8E-12
should be :
prob to be stuck on a particular day = p_day = 1/(60*24*280000)
probability of NOT getting stuck on a particular day = 1-p_day
probability of NOT getting struck by lightning while taking a crap in any given year = (1-p_day)^365
probability of getting struck by lightning while taking a crap in any given year = 1-((1-p_day)^365)
note that p_day is much lower that the prob. to be stuck in a year, since you get another 'chance' every other day of the year ...
not so easy huh ?
Apart from the fact that the probability to be taking a crap at any given point in time is not 1.0/525600 but 1.0/(24*60) as a previous poster pointed out: I still think my version is correct.
The bold part above seems wrong to me. How does the minute come into play?
If you want to calculate the probability of getting struck on a particular day, you'd have to solve:
p_year = 1 - ( (1 - p_day) ^ 365 )
to p_day, right?
If my algebra skills arent complete crap, this should be:
p_day = 1 - ( (1 - p_year) ^ 1/365 )
Is it possible that you made the mistake you're saying I made? That'd be hilarious. I might be confused, though. Probability theory tends to confuse the crap out of me
November 03, 2012, 01:08:23 PM
@molecular
ha ok, I get it now.
So
should be :
prob to be stuck on a particular day = p_day = 1/(60*24*280000)
probability of NOT getting stuck on a particular day = 1-p_day
probability of NOT getting struck by lightning while taking a crap in any given year = (1-p_day)^365
probability of getting struck by lightning while taking a crap in any given year = 1-((1-p_day)^365)
note that p_day is much lower that the prob. to be stuck in a year, since you get another 'chance' every other day of the year ...
not so easy huh ?
ha ok, I get it now.
So
Quote
probability of getting struck by lightning while taking a crap in any given year: 1/(280000*525600) = 1/1.47E11 = 6.8E-12
should be :
prob to be stuck on a particular day = p_day = 1/(60*24*280000)
probability of NOT getting stuck on a particular day = 1-p_day
probability of NOT getting struck by lightning while taking a crap in any given year = (1-p_day)^365
probability of getting struck by lightning while taking a crap in any given year = 1-((1-p_day)^365)
note that p_day is much lower that the prob. to be stuck in a year, since you get another 'chance' every other day of the year ...
not so easy huh ?
November 03, 2012, 12:41:55 PM
Quote
* getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(6.8E-12) = 5.8
I don't get why you put logs here
perhaps because we're talking about taking a crap?
lmao!
I solved the equation
1E-65 = 6.8E-12 ^ y
via
log(1E-65) = y * log(6.3E-12)
to
y = log(1E-65) / log(6.3E-12)
The first thing I don't get is this :
Quote
probability of taking a shit at any given point in time: 1/(60*24*365) = 1/525600 (assuming you take a crap every day and the actual process takes 1 minute)
If you take one shit a day, that prob is 1/(60*24) to me
oops. You are right. I'll have to correct that.
THe second thing I don't get is this
I don't understand why "y" would have something to do with the number of years to get your result.
Quote
1E-65 = 6.8E-12 ^ y
I don't understand why "y" would have something to do with the number of years to get your result.
My thinking here is this (it might well be wrong): let's say p_ss = 6.8E-12 (probability of getting struck while shitting during 1 year), then p_ss * p_ss is the probability of getting struck while shitting this year and then again next year. So p_ss ^ y is the probability of getting struck while shitting y consecutive number of years in a row. Correct?
I don't mean to be sarcastic or anything, and I might be slow - this is saturday evening to me, I am probably need to focus.
No, man. Thanks a lot for checking my stuff. As can be seen that's much needed.
November 03, 2012, 10:41:45 AM
Quote
* getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(6.8E-12) = 5.8
I don't get why you put logs here
perhaps because we're talking about taking a crap?
lmao!
I solved the equation
1E-65 = 6.8E-12 ^ y
via
log(1E-65) = y * log(6.3E-12)
to
y = log(1E-65) / log(6.3E-12)
The first thing I don't get is this :
Quote
probability of taking a shit at any given point in time: 1/(60*24*365) = 1/525600 (assuming you take a crap every day and the actual process takes 1 minute)
If you take one shit a day, that prob is 1/(60*24) to me
THe second thing I don't get is this
Quote
1E-65 = 6.8E-12 ^ y
I don't understand why "y" would have something to do with the number of years to get your result.
I don't mean to be sarcastic or anything, and I might be slow - this is saturday evening to me, I am probably need to focus.
November 03, 2012, 10:27:46 AM
Quote
* getting hit by lightning while taking a crap for how many years in a row is equally probable as finding a collision: log(1E-65) / log(6.8E-12) = 5.8
I don't get why you put logs here
perhaps because we're talking about taking a crap?
lmao!
I solved the equation
1E-65 = 6.8E-12 ^ y
via
log(1E-65) = y * log(6.3E-12)
to
y = log(1E-65) / log(6.3E-12)
Jump to: