Bitcoin Forum
March 19, 2024, 03:24:05 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 »  All
  Print  
Author Topic: Bitcoin Address Collisions.  (Read 3926 times)
marjamrob (OP)
Full Member
***
Offline Offline

Activity: 140
Merit: 100



View Profile
July 11, 2013, 09:48:14 PM
 #1

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.
1710818645
Hero Member
*
Offline Offline

Posts: 1710818645

View Profile Personal Message (Offline)

Ignore
1710818645
Reply with quote  #2

1710818645
Report to moderator
1710818645
Hero Member
*
Offline Offline

Posts: 1710818645

View Profile Personal Message (Offline)

Ignore
1710818645
Reply with quote  #2

1710818645
Report to moderator
The forum strives to allow free discussion of any ideas. All policies are built around this principle. This doesn't mean you can post garbage, though: posts should actually contain ideas, and these ideas should be argued reasonably.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1710818645
Hero Member
*
Offline Offline

Posts: 1710818645

View Profile Personal Message (Offline)

Ignore
1710818645
Reply with quote  #2

1710818645
Report to moderator
1710818645
Hero Member
*
Offline Offline

Posts: 1710818645

View Profile Personal Message (Offline)

Ignore
1710818645
Reply with quote  #2

1710818645
Report to moderator
justusranvier
Legendary
*
Offline Offline

Activity: 1400
Merit: 1006



View Profile
July 11, 2013, 09:56:53 PM
 #2

There are slightly less than 2160 possible bitcoin addresses, not 2256
Remember remember the 5th of November
Legendary
*
Offline Offline

Activity: 1862
Merit: 1011

Reverse engineer from time to time


View Profile
July 11, 2013, 10:04:47 PM
 #3

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
Hero Member
*****
Offline Offline

Activity: 572
Merit: 506



View Profile
July 11, 2013, 10:11:13 PM
 #4

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
Hero Member
*****
Offline Offline

Activity: 602
Merit: 500


View Profile
July 11, 2013, 10:14:50 PM
 #5

What language are we talking in

ok
Mike Christ
aka snapsunny
Legendary
*
Offline Offline

Activity: 1078
Merit: 1003



View Profile
July 11, 2013, 10:22:28 PM
 #6

What language are we talking in

I believe it's known as "bitcointalk"

stdset
Hero Member
*****
Offline Offline

Activity: 572
Merit: 506



View Profile
July 11, 2013, 10:44:20 PM
 #7

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 Offline

Activity: 1078
Merit: 1002


View Profile
July 11, 2013, 10:53:20 PM
 #8

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
Full Member
***
Offline Offline

Activity: 168
Merit: 100



View Profile
July 11, 2013, 10:57:15 PM
 #9

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.

QuarkCoin - what I believe bitcoin was intended to be. On reddit: http://www.reddit.com/r/QuarkCoin/
AliceWonder
Full Member
***
Offline Offline

Activity: 168
Merit: 100



View Profile
July 11, 2013, 10:58:35 PM
 #10

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?

QuarkCoin - what I believe bitcoin was intended to be. On reddit: http://www.reddit.com/r/QuarkCoin/
phillipsjk
Legendary
*
Offline Offline

Activity: 1008
Merit: 1001

Let the chips fall where they may.


View Profile WWW
July 11, 2013, 11:00:41 PM
 #11

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
Hero Member
*****
Offline Offline

Activity: 572
Merit: 506



View Profile
July 12, 2013, 12:12:42 AM
Last edit: July 12, 2013, 12:25:01 AM by stdset
 #12

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
Sr. Member
****
Offline Offline

Activity: 388
Merit: 250



View Profile
July 12, 2013, 12:44:09 AM
 #13

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

⚤♥ SKXnk8NfcmnufppRmyAGpEqUsVkuTJbmxz SXC | ₲ SLvNp5QWmZVHFrYKeFyRS5AoJJZqPwTT4V GRC | Ψ AbjccCitKYV2nPbfqZycVt3GggB3bZ435G XPM | Ᵽ P8iKPd37WL432bXFAfZMSkA5LW2iytYXbr PPC | ℕ NJXzxntcNVPev8tsf5PwDPLCHP3oTS2BFA NMC | Ł LT8jLGNBPCiBafC2wVjpehP4UMwJkY2nHb LTC | Ď DJXUkQxF6AeCnb81wmQxmaS6dJF6dBfkro DOGE | ฿ 1JxyLg4TKcULz3fvit4kdrtTYAVkLHahvD BTC | Đ 1Jx1t3XPpxjQmtZWve9qzTnzNheBR3WGBm DVC | Earn Devcoins by Writing | sexcoin.wiki | sexcoin.sexy | sexco.in | sexcoin.co.in | sexcoin.in | sexcoin.online | sexcoin.space | sexcoin.eu | sex-coin.de
stdset
Hero Member
*****
Offline Offline

Activity: 572
Merit: 506



View Profile
July 12, 2013, 12:50:44 AM
 #14

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
Full Member
***
Offline Offline

Activity: 168
Merit: 100



View Profile
July 12, 2013, 12:57:19 AM
 #15

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.

QuarkCoin - what I believe bitcoin was intended to be. On reddit: http://www.reddit.com/r/QuarkCoin/
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1024



View Profile
July 12, 2013, 01:01:36 AM
 #16

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 = n2/2161

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
marcus_of_augustus
Legendary
*
Offline Offline

Activity: 3920
Merit: 2347


Eadem mutata resurgo


View Profile
July 12, 2013, 02:30:24 AM
 #17

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
Hero Member
*****
Offline Offline

Activity: 572
Merit: 506



View Profile
July 12, 2013, 02:54:40 AM
 #18

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 Offline

Activity: 938
Merit: 1000


What's a GPU?


View Profile
July 12, 2013, 03:05:06 AM
 #19

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
Hero Member
*****
Offline Offline

Activity: 572
Merit: 506



View Profile
July 12, 2013, 03:24:06 AM
 #20

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.

Pages: [1] 2 3 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!