Bitcoin Address Collisions. - page 2.

farproc

sr. member

Activity: 406

Merit: 250

ALGORY.io Crowdsale starts on 8/12/2017

Quote from: FreeMoney on July 12, 2013, 04:38:47 PM

Quote from: AlexWaters on July 12, 2013, 02:02:20 PM

Can we talk about what happens when there is a collision? I like to envision dividing by zero, a star dying, Roger Ver ascending to heaven, and your computer literally exploding with bitcoins shooting out of it.

Two people have access to the same empty account and neither knows it. Hardly spectacular.

Or,
someone generates a new address and then finds there is a large balance in it == Someone else awakes in the morning and finds the large balance in his address was transferred to another random address.

FreeMoney

legendary

Activity: 1246

Merit: 1016

Strength in numbers

Quote from: AlexWaters on July 12, 2013, 02:02:20 PM

Can we talk about what happens when there is a collision? I like to envision dividing by zero, a star dying, Roger Ver ascending to heaven, and your computer literally exploding with bitcoins shooting out of it.

Two people have access to the same empty account and neither knows it. Hardly spectacular.

TippingPoint

legendary

Activity: 905

Merit: 1000

Quote from: marcus_of_augustus on July 11, 2013, 09:30:24 PM

So there is tiny, but possible chance and that you could say to the court ..."Your honour, I have no idea how that bitcoin got in that account, maybe it was random collision?"

Criminal Court - Beyond a reasonable doubt

Civil Court - Preponderance of the evidence

Internet Forum - Good enough

justusranvier

legendary

Activity: 1400

Merit: 1013

Quote from: AlexWaters on July 12, 2013, 02:02:20 PM

Can we talk about what happens when there is a collision? I like to envision dividing by zero, a star dying, Roger Ver ascending to heaven, and your computer literally exploding with bitcoins shooting out of it.

http://www.youtube.com/watch?v=jyaLZHiJJnE

AlexWaters

member

Activity: 77

Merit: 11

Twitter:@watersNYC

Can we talk about what happens when there is a collision? I like to envision dividing by zero, a star dying, Roger Ver ascending to heaven, and your computer literally exploding with bitcoins shooting out of it.

stdset

hero member

Activity: 572

Merit: 506

Quote from: Garr255 on July 11, 2013, 10:05:06 PM

Simple evasion of a collision is dispersing your bitcoin savings in thousands of addresses. Technically if everyone does this the likelihood of a collision is in fact higher but the stakes are less.

As with everything: give and take.

--Garrett

It's important to undestand, we are not talking about some real possibility. Even if we spread all bitcoins as thin as possible, putting 1 satoshi to an address, total probability is about 10^-18. It is essentially zero. And your personal probability of a collision about 5 orders of magnitude less (if you hold huge fortune of some hundreds of BTC and spread them: an address - a satoshi). If you care about such things, you should also care about a meteor hitting you.

Garr255

legendary

Activity: 938

Merit: 1000

What's a GPU?

Simple evasion of a collision is dispersing your bitcoin savings in thousands of addresses. Technically if everyone does this the likelihood of a collision is in fact higher but the stakes are less.

As with everything: give and take.

--Garrett

stdset

hero member

Activity: 572

Merit: 506

Quote from: marcus_of_augustus on July 11, 2013, 09:30:24 PM

So there is tiny, but possible chance and that you could say to the court ..."Your honour, I have no idea how that bitcoin got in that account, maybe it was random collision?"

It's interesting to compare chances of collision of bitcoin addresses to chances of human fingerprints colliding.

marcus_of_augustus

legendary

Activity: 3920

Merit: 2349

Eadem mutata resurgo

So there is tiny, but possible chance and that you could say to the court ..."Your honour, I have no idea how that bitcoin got in that account, maybe it was random collision?"

kjj

legendary

Activity: 1302

Merit: 1026

Quote from: stdset on July 11, 2013, 07:12:42 PM

Quote from: AliceWonder on July 11, 2013, 05:57:15 PM

You can't just do a straight division.

That's why I wrote, "the next address generated", not "probability that any two addresses collide".
Approximate probability of collision between any two addresses can be calculated the following simple way:
obviously, the first address can't collide with another address, probability for the second to collide with the first is 1/2^160, for the third it is 2/2^160, 4'th 3/2^160, it is easy to see, that it is an arithmetical progression.
Total probability that any two addresses collide approximately equals the sum of the progression, and can be written as: P = n^2/2^161, where n - is the amount of bitcoin addresses in use.
For 2.1*10^15 addresses it gives us: 1.5*10^-18
This calculation is simplified a bit. However, the result should be very close to the exact result.

The forum supports superscripts.

P = n²/2¹⁶¹

AliceWonder

full member

Activity: 168

Merit: 100

One thing to note about bitcoin is that a large percentage if not most of the addresses used are used once and then completely emptied when the transaction sent to them are spent. So even if there is a random collision, there's a damn good chance it is fairly meaningless and if not meaningless (e.g. first person to have it ends up spending the input) it probably is not a huge loss.

stdset

hero member

Activity: 572

Merit: 506

Quote from: joewinkler on July 11, 2013, 07:44:09 PM

Is P = n^2/2^161 or P = n^2/(2^160+1) ?

161, that's why I wrote it with bold letters. And anyway, 1 compared to 2^160 is too small, I would neglect it, if it would appear there.

joewinkler

sr. member

Activity: 388

Merit: 250

Quote from: stdset on July 11, 2013, 07:12:42 PM

Quote from: AliceWonder on July 11, 2013, 05:57:15 PM

You can't just do a straight division.

That's why I wrote, "the next address generated", not "probability that any two addresses collide".
Approximate probability of collision between any two addresses can be calculated the following simple way:
obviously, the first address can't collide with another address, probability for the second to collide with the first is 1/2^160, for the third it is 2/2^160, 4'th 3/2^160, it is easy to see, that it is an arithmetical progression.
Total probability that any two addresses collide approximately equals the sum of the progression, and can be written as: P = n^2/2^161, where n - is the amount of bitcoin addresses in use.
For 2.1*10^15 addresses it gives us: 1.5*10^-18
This calculation is simplified a bit. However, the result should be very close to the exact result.

I do not know exactly this kind of math.
Is P = n^2/2^161 or P = n^2/(2^160+1) ?

stdset

hero member

Activity: 572

Merit: 506

Quote from: AliceWonder on July 11, 2013, 05:57:15 PM

You can't just do a straight division.

That's why I wrote, "the next address generated", not "probability that any two addresses collide".
Approximate probability of collision between any two addresses can be calculated the following simple way:
obviously, the first address can't collide with another address, probability for the second to collide with the first is 1/2^160, for the third it is 2/2^160, 4'th 3/2^160, it is easy to see, that it is an arithmetical progression.
Total probability that any two addresses collide approximately equals the sum of the progression, and can be written as: P = n^2/2^161, where n - is the amount of bitcoin addresses in use.
For 2.1*10^15 addresses it gives us: 1.5*10^-18
This calculation is simplified a bit. However, the result should be very close to the exact result.

phillipsjk

legendary

Activity: 1008

Merit: 1001

Let the chips fall where they may.

Collisions are very easy to find if you don't randomly generate the private key:
Brain wallets insecure?

edit: the math is described here:
Birthday Paradox

AliceWonder

full member

Activity: 168

Merit: 100

Oh, and with these addresses that start with a 3 that require multiple signatures to spend, that will increase the number of bitcoin addresses.

An interesting question, if you use a vanity address, how does that effect the odds?

Obviously the pool of addresses that result in that vanity address is smaller, but small enough that crackers could create more successful rainbow tables for vanity addresses?

AliceWonder

full member

Activity: 168

Merit: 100

You can't just do a straight division.

If you have a 30 people in a room, the chances of any two specific people having the same birthday is rather small.
However odds are that there is at least one pair with the same birthday. A collision.

That being said, the odds in bitcoin are still extremely low.

I don't remember my statistics class well enough to remember the formula, but I'm fairly certain it involved factorials.

hazek

legendary

Activity: 1078

Merit: 1003

It's going to happen eventually, however not nearly often enough for it to ever be a serious problem.

stdset

hero member

Activity: 572

Merit: 506

Moreover, there couldn't be more than 2.1*10^15 bitcoin addresses being used at the same time, because there will not be more than 2.1*10^15 satoshis in the whole system. So, most of those 3.65*10^17 addresses will be empty.

Mike Christ

legendary

Activity: 1078

Merit: 1003

Quote from: superduh on July 11, 2013, 05:14:50 PM

What language are we talking in

I believe it's known as "bitcointalk"

Topic: Bitcoin Address Collisions. - page 2. (Read 3941 times)