What are the chances of an address collision? and what happens when it does?

[paraipan]

I'm not saying collisions anywhere close to likely to occur, but...

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%

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?

Hopefully in 1E3 years if a human "stumbles" onto someone else's money they will not touch it, or give it back right away.

"Real is gonna change... just watch"

[runeks]

Chance are negligible. If collision occurs with a funded address, attacker you can transfer funds elsewhere.

Chances are still negligible when 1 billion people are using it?  also can't I just run some kind of bots, that randomly generate addresses to see if
they have funds in them?

Yes, chances remain negligible. You could run your bot, but it'd be a waste of electricity. Chances are you'd wait the lifetime of the universe before finding a collision.

But probability also says, I could have a success on my first run? isn't it?

Sure, you could absolutely find a success on your first run, but let's apply probability to your scenario.

Let's say there are a billion people using 10 addresses each for 10 billion total addresses.

This means that each address you generate has a (1/2^160)*10,000,000,000 possibility of holding a balance, giving your first attempt a 0.0000000000000000000000000000000000000684% chance of finding a collision on your first attempt.

You are correct in stating that with each try it will either happen or it won't, there is no in-between state, and you're correct in stating that it's possible. It's also bad news for the account holder that a collision would give you control of those funds.

Comparatively speaking, your odds of being struck by lightning in a given calendar year are about 1 in 280,000. The odds of winning my local lottery are about 1 in 176,000,000. So finding a collision on your first try is roughly equivalent to being hit by lightning 16,540,000,000,000,000,000,000,000 times per second for an entire year or winning the lottery 830,000,000,000,000,000,000,000,000,000 times.

If you find a collision I would stay indoors and play the lottery.

The highlighted part is wrong. The odds of getting struck by lightning n times is not p*n, it's p^n. Ie. the probability of throwing two sixes in a row with a dice is not 1/12, it's 1/36.

What I'd like to know is why some letters have higher probability than others? Is that because some letters are more likely on the elliptic curve vs not? If you plug sequences into vanitygen it will give different difficulties depending on letter, eg.

11... > 1A...
1Q... > 1D...
1R... > 1Q... and so on.

I made a table of the first three chars after 1 to help me in a project with fast lookup of difficulty calculation. There are broad classes of probabilities depending on what letters are involved. I guess there is some non 1-1 mapping from 2^160 possible addresses and base 58 representations.

It's not related to elliptic curves, as an address is created from a hash, which is basically just random data.
The reason is that the data that is encoded as base58 (and thus becomes an address) is <one byte "version byte">||<20 byte RIPEMD160 public key hash>||<4 byte checksum> where || denotes concatenation.

This version byte is 0 on the main network. So the binary data of an address will always start with 0000 0000. Since this data is converted into a large number, the probability that some of the leading zero bits will be included in the leftmost bits of the large number is greater than none of the leading zero bits being included (since there are eight of them). This results in the probability of the number starting with a small digit being greater.

This large number is basically just continually divided by 58, and the *remainder* of this division is then used to determine which character is added to the address string (based on it's index position in the string "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"). This is repeated in a loop until the large number has been reduced to zero. After this *the string is reversed*. This means that the last remainder will be the first character in the address (after the '1' which will always be there because a '1' is prepended to the address for every leading zero-byte, of which there is always one because the "version byte" is always zero on the main network). So since there is a greater probability that the first part of the number is a small digit, there is a greater chance that the first character of the address will be one of the first characters of the string from which characters are selected based on their index position in that string.

[molecular]

Comparatively speaking, your odds of being struck by lightning in a given calendar year are about 1 in 280,000. The odds of winning my local lottery are about 1 in 176,000,000. So finding a collision on your first try is roughly equivalent to being hit by lightning 16,540,000,000,000,000,000,000,000 times per second for an entire year or winning the lottery 830,000,000,000,000,000,000,000,000,000 times.

If you find a collision I would stay indoors and play the lottery.

The highlighted part is wrong. The odds of getting struck by lightning n times is not p*n, it's p^n. Ie. the probability of throwing two sixes in a row with a dice is not 1/12, it's 1/36.
[/quote]

right, so how many lightning strikes per year are we talking to have the same probability of seeing an accidental collision occur between any two generated addresses (assuming 10 billion bitcoin users that each generate 1000 addresses per year)?

[DeathAndTaxes]

The number of addresses generated isn't important it is the number of funded addresses.  A collision with a spent change address that will never be used again isn't very valuable.

So if we assume 1 trillion active addresses (10 billion users with an average of 100 active funded addresses at any point in time). The odds of finding a collision are ~ 1 in 1*10^65.

If the odds of getting hit by lightning are 1 in 280,000 then the odds of getting stuck by lightning 12 times per year is roughly the same as creating a collision with with one of the 1 trillion active addresses.  I don't like lightning comparison because lightning is localized (not randomly distributed).  If we use the lottery example the odds of buying lottery tickets for 8 consecutive games and winning the jackpot on all 8 is roughly the same as finding a single collision.  

I would point out that the single random collision is unlikely to be very profitable.  If there are 1 trillion addresses and all coins are mined the average address will hold ~0.000021 BTC (21 uBTC - microBTC).  Another way to look at it is if we assume in this 10 billion scenario Bitcoin has replaced all global money supplies then the collective value of the network would be on the order of ~$60T (2012 dollars).  At 1 trillion addresses the value of finding that collision (less likely than winning lottery 8 times in a row) would be ~$60.  BTW fun fact that would make the exchange rate $2.857 per uBTC!

[flatfly]

An address collision would be a SHA256 collision

And if you find a SHA256 collision then bitcoin is the last of our problem

Technically it would be a RIPEMD160(SHA256(SHA256())) collision. Not nitpicking, it's an important distinction given that the last step in that process yields 2^160 possible addresses instead of 2^256. 96 bits of keyspace ain't no joke son.

If I understand this right, does this basically mean that each address actually has tons of private keys (only one of which is known)?

[flynn]

An address collision would be a SHA256 collision

And if you find a SHA256 collision then bitcoin is the last of our problem

Technically it would be a RIPEMD160(SHA256(SHA256())) collision. Not nitpicking, it's an important distinction given that the last step in that process yields 2^160 possible addresses instead of 2^256. 96 bits of keyspace ain't no joke son.

If I understand this right, does this basically mean that each address actually has tons of private keys (only one of which is known)?

That reminds me of this joke :

An 80-years old woman is attending a lecture on astronomy, where the astronomer states that our sun will explode and transform itself into a red giant within 5 billion years.

At the end of the lecture, the old lady asks the astronomer :

- How long did you say our sun will last ?
- 5 billion years
- What a relief ! I thought you said 5 millions !

[kjj]

An address collision would be a SHA256 collision

And if you find a SHA256 collision then bitcoin is the last of our problem

Technically it would be a RIPEMD160(SHA256(SHA256())) collision. Not nitpicking, it's an important distinction given that the last step in that process yields 2^160 possible addresses instead of 2^256. 96 bits of keyspace ain't no joke son.

If I understand this right, does this basically mean that each address actually has tons of private keys (only one of which is known)?

Well, probably.  The mapping isn't known to be evenly distributed.  But on average, there should be something like 2⁹⁶ keys per address.

P.S.  It is RIPEMD-160(SHA-256(pubkey)) .  Only two hashes, not three.

[molecular]

The number of addresses generated isn't important it is the number of funded addresses.  A collision with a spent change address that will never be used again isn't very valuable.

So if we assume 1 trillion active addresses (10 billion users with an average of 100 active funded addresses at any point in time). The odds of finding a collision are ~ 1 in 1*10^65.

If the odds of getting hit by lightning are 1 in 280,000 then the odds of getting stuck by lightning 12 times per year is roughly the same as creating a collision with with one of the 1 trillion active addresses.  I don't like lightning comparison because lightning is localized (not randomly distributed).  If we use the lottery example the odds of buying lottery tickets for 8 consecutive games and winning the jackpot on all 8 is roughly the same as finding a single collision.  

I would point out that the single random collision is unlikely to be very profitable.  If there are 1 trillion addresses and all coins are mined the average address will hold ~0.000021 BTC (21 uBTC - microBTC).  Another way to look at it is if we assume in this 10 billion scenario Bitcoin has replaced all global money supplies then the collective value of the network would be on the order of ~$60T (2012 dollars).  At 1 trillion addresses the value of finding that collision (less likely than winning lottery 8 times in a row) would be ~$60.  BTW fun fact that would make the exchange rate $2.857 per uBTC!

thanks, Death&Taxes for doing the math.

What would you suggest to answer to a newbies question: "But wouldn't 2 people accidentally find the same address at some point?"

I still 'd like to be able to answer something like: "It's possible, but it's about as likely as you getting struck by lightning while taking a crap - *pause* - every year for 5 years in a row!". Just don't know.

Let me try to do the math:

• 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*365) = 1/525600 (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*525600) = 1/1.47E11 = 6.8E-12
• 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(6.8E-12) = 5.8

is my math roughly correct?

[molecular]

on a side not: the probability of getting struck by lightning during your 80 year long life is 1/3500???

1.0 / (1.0 - pow((1.0-1.0/280000),80)) = 3500

on the bright side: in case that happens to me the probability of me taking a crap at that time is only 1/525600.

[flynn]

    * 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

[flatfly]

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

[molecular]

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

[flynn]

   * 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 :

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

  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.

[molecular]

   * 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 :

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

  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.

[flynn]

@molecular

ha ok, I get it now.

So

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 ?

[molecular]

@molecular

ha ok, I get it now.

So

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

[flynn]

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

[molecular]

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

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

[mskwik]

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

[flynn]

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

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)