marjamrob (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 09:48:14 PM |
|
The odds of a collision taking place, by my calculations, assuming 20 Million BTC address, are as follows:
2^256 1 ______ = ____________________
~20 Million (Estimated BTC Address In Existence) 5.78960446186581E69
Which is equal to:
1 __________________ Or .00000000005064660113837803 %
1974466158682.1443
That is of 1 single collision taking place, so it seems rather unlikely.
Has anyone ever been able to confirm that an address collision took place? I ask because we seem to worry a lot about it, even though the odds seem stacked against such a happening.
|
|
|
|
justusranvier
Legendary
Offline
Activity: 1400
Merit: 1013
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 09:56:53 PM |
|
There are slightly less than 2160 possible bitcoin addresses, not 2256
|
|
|
|
Remember remember the 5th of November
Legendary
Offline
Activity: 1862
Merit: 1011
Reverse engineer from time to time
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 10:04:47 PM |
|
There are slightly less than 2160 possible bitcoin addresses, not 2256
Yeah, but there are still ~2^256(not exactly 2^256 private keys due to secpk256k1) so doesn't matter much, because you still need to try numbers from this large pool for the right private key which hashes to some RIPEMD160 hash.
|
BTC:1AiCRMxgf1ptVQwx6hDuKMu4f7F27QmJC2
|
|
|
stdset
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 10:11:13 PM |
|
Let's assume there are 2^160 possible, and equally probable to be generated, bitcoin addresses. Let's than assume there are 10 billions people on the planet, and each of them uses 100 new addresses a day. They continue to do so for 1000 years. After that period of time approx 3.65*10^17 addresses will be generated. Next address to be generated has probability of 2.5*10^-31 to collide with one of the existing addresses. That's several orders of magnitude less than 1 divided by Avogadro constant.
|
|
|
|
superduh
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 10:14:50 PM |
|
What language are we talking in
|
ok
|
|
|
Mike Christ
aka snapsunny
Legendary
Offline
Activity: 1078
Merit: 1003
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 10:22:28 PM |
|
What language are we talking in
I believe it's known as "bitcointalk"
|
|
|
|
stdset
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 10:44:20 PM |
|
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.
|
|
|
|
hazek
Legendary
Offline
Activity: 1078
Merit: 1003
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 10:53:20 PM |
|
It's going to happen eventually, however not nearly often enough for it to ever be a serious problem.
|
My personality type: INTJ - please forgive my weaknesses (Not naturally in tune with others feelings; may be insensitive at times, tend to respond to conflict with logic and reason, tend to believe I'm always right)
If however you enjoyed my post: 15j781DjuJeVsZgYbDVt2NZsGrWKRWFHpp
|
|
|
AliceWonder
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 10:57:15 PM |
|
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.
|
|
|
|
AliceWonder
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 10:58:35 PM |
|
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?
|
|
|
|
phillipsjk
Legendary
Offline
Activity: 1008
Merit: 1001
Let the chips fall where they may.
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 11, 2013, 11:00:41 PM |
|
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
|
James' OpenPGP public key fingerprint: EB14 9E5B F80C 1F2D 3EBE 0A2F B3DE 81FF 7B9D 5160
|
|
|
stdset
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 12:12:42 AM Last edit: July 12, 2013, 12:25:01 AM by stdset |
|
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.
|
|
|
|
joewinkler
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 12:44:09 AM |
|
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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 12:50:44 AM |
|
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.
|
|
|
|
AliceWonder
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 12:57:19 AM |
|
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.
|
|
|
|
kjj
Legendary
Offline
Activity: 1302
Merit: 1026
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 01:01:36 AM |
|
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/2 161
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
marcus_of_augustus
Legendary
Offline
Activity: 3920
Merit: 2349
Eadem mutata resurgo
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 02:30:24 AM |
|
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?"
|
|
|
|
stdset
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 02:54:40 AM |
|
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.
|
|
|
|
Garr255
Legendary
Offline
Activity: 938
Merit: 1000
What's a GPU?
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 03:05:06 AM |
|
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
|
“First they ignore you, then they laugh at you, then they fight you, then you win.” -- Mahatma Gandhi
Average time between signing on to bitcointalk: Two weeks. Please don't expect responses any faster than that!
|
|
|
stdset
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 12, 2013, 03:24:06 AM |
|
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.
|
|
|
|
|