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

[farfiman]

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

It's a lot more likely that you're struck by lightning or a meteor. So get your priorities straight and worry about that.

and even if you are EXTREMELY lucky and hit a collision , chances are there will be zero coins in it. Most addresses are used once ( or a few times ) and have nothing in them...

[FreeMoney]

When we get faster than light travel and trillions of people across the galaxy each need thousands of addresses it is still unlikely. After millions of years when it eventually happens, the average amount in the address will be far far less than 1 satoshi.

[Raize]

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.

Don't we also discard uppercase I's and lowercase L's and O's and zeroes?

[DeathAndTaxes]

Yes but that is just the formatting.  The address is still a 160 bit hash of the public key (plus some version info & checksums) expressed as a modified Base58 string.

[Raize]

Oh duh, it's the Base58Check that does that part.

[Melbustus]

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

Yes. You should play the lottery.

[phatsphere]

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

Yes, especially if you do all the calculations very very deliberately and careful by hand with paper and pencil.

[doobadoo]

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.

Not to hijack the thread, cuz i'm sure other people will read and be curious abut his too: But can some one quickly explain why its also very unlikely to accidentally type a valid Bitcoin address.  They are 33 (32 unique) case-sensitive alpha-numeric digits (Base 58).  Only a subset of all possible combinations are valid addresses.  What is the method and explanation for this?

Can some one also explain how if a public address is a sha hash of a public key, how can an address be signed by the owner of the privkey, if the public address can't be reversed into the full public key  (the key pairs are 256 bit ECDSA right?  Should be loner than 32 characters).

[Boussac]

Not to hijack the thread, cuz i'm sure other people will read and be curious abut his too: But can some one quickly explain why its also very unlikely to accidentally type a valid Bitcoin address.  They are 33 (32 unique) case-sensitive alpha-numeric digits (Base 58).  Only a subset of all possible combinations are valid addresses.  What is the method and explanation for this?

Can some one also explain how if a public address is a sha hash of a public key, how can an address be signed by the owner of the privkey, if the public address can't be reversed into the full public key  (the key pairs are 256 bit ECDSA right?  Should be loner than 32 characters).

Since a bitcoin public key is in fact a pair of coordinates for a point on the elliptic curve, it's not surprising that only a subset of the possible address strings happen to be a hash of valid coordinates.
Plus there is a checksum attached to it.
It would be a miracle to random type a valid bitcoin address.

[DeathAndTaxes]

Not to hijack the thread, cuz i'm sure other people will read and be curious abut his too: But can some one quickly explain why its also very unlikely to accidentally type a valid Bitcoin address.  They are 33 (32 unique) case-sensitive alpha-numeric digits (Base 58).  Only a subset of all possible combinations are valid addresses.  What is the method and explanation for this?

The address contains a 32 bit checksum.  So a typo will most likely result in a bad checksum.  Node compute the checksum to ensure the address is valid so "most" typos will simply produce an invalid address which will be rejected by your client, other nodes, and miners.  In theory you could create a sequence of typos that also produces a valid but incorrect address but the odds are roughly 1 in 4 billion.

Can some one also explain how if a public address is a sha hash of a public key, how can an address be signed by the owner of the privkey, if the public address can't be reversed into the full public key  (the key pairs are 256 bit ECDSA right?  Should be loner than 32 characters).

Technically the address isn't signed.  A message is signed by the private key.  The signature can be verified by the public key.  The signature contains the public key.  The address can be verified by recreating it from the public key.

[Boussac]

To me a "valid" address is one that has a private key.
The checksum verification of an address does not warrant that a private key exist for that address.

Hence my post above: the point represented by the public key MUST be on the ellptic currve.

In short,
1/you can random type an address with a valid checksum
2/ funds can be sent to that address because miners will get it on the blockchain
3/Nobody will ever spend those funds again because there is no private key for that address: the bitcoins on that address are lost for ever

[BkkCoins]

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.

[kerogre256]

There is probability then when you throw ball it will not bounce but go through wall....

[Boussac]

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.

In ECDSA, you start with a large integer as your private key then multiply ("multiplication" here must be understood as a group operator not as arithmetic multiplication) the base point G of your elliptic curve to get the corresponding public key.
Therefore your public key is a point (x,y) on the elliptic curve.

In bitcoin, your address is some hash of you public key.
As a result, if you start from a random string, the likelihood of a collision between said string and a "valid" address depends on how many integers n satisfy the condition "n*G is a point on the curve AND this point hashes to a matching string".
Therefore a brute force algorithm (like vanitygen) might display varying difficulty as a function of the chosen string.

[DeathAndTaxes]

To me a "valid" address is one that has a private key.
The checksum verification of an address does not warrant that a private key exist for that address.

Hence my post above: the point represented by the public key MUST be on the ellptic currve.

In short,
1/you can random type an address with a valid checksum
2/ funds can be sent to that address because miners will get it on the blockchain
3/Nobody will ever spend those funds again because there is no private key for that address: the bitcoins on that address are lost for ever

The network has no method of determining if the private key is "known".  It doesn't matter if a private key was known but no longer is (lost),  is unknown but theoretically possible, or simply impossible (there is no possible 256 bit number which produces that address).

In any address if the private key is currently unknown the coins can't be spent.  If an address confirms to the protocol spec it is valid.

Due to the checksum the probability of entering an valid but incorrect address due to a typo is less than 1 in 4 billion.  Realistically it isn't going to happen.

[kokojie]

I'm also wondering how long it would take to crack an address/key pair. For example, let's say I have a lot of hardware at my disposal, and can generate
1 Billion address/key pair per second. How long would it take to crack a specific address? can some one do a math on this one? I would guess not very long.

[muyuu]

I'm also wondering how long it would take to crack an address/key pair. For example, let's say I have a lot of hardware at my disposal, and can generate
1 Billion address/key pair per second. How long would it take to crack a specific address? can some one do a math on this one? I would guess not very long.

You guess wrong.

1 billion per second is nothing in an address space of size 2^160. It would take ~ 3.4 E+21 times the age of the Universe in average.

Let Wolfram Alpha do it for you http://www.wolframalpha.com/input/?i=(2%5E160)%20%2F%201e%2B9%20seconds%20to%20years

[mila]

You are, however, much better off generating collisions on various deterministic wallets like brainwallets etc... there are plenty of people out there who do not get it why some passwords/keys must be strong.

If lucky you will teach some punks a good lesson BTW.

repeating the obvious: the seed secret for deterministic wallets is the equivalent to password.
not only must it be secret, also difficult to guess.

[flatfly]

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?

Hey, I started this little pet project with you in mind

[molecular]

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?