Bitcoin Forum
May 21, 2019, 06:21:05 PM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 4 5 »  All
  Print  
Author Topic: What are the chances of an address collision? and what happens when it does?  (Read 22045 times)
kokojie
Legendary
*
Offline Offline

Activity: 1750
Merit: 1000



View Profile
August 29, 2012, 05:22:22 PM
 #1

What are the chances of an address collision? when for example 1 billion people are using bitcoin and on average they generate 10 address per person.

also what exactly will happen when address collision occurs?

btc: 15sFnThw58hiGHYXyUAasgfauifTEB1ZF6
1558462865
Hero Member
*
Offline Offline

Posts: 1558462865

View Profile Personal Message (Offline)

Ignore
1558462865
Reply with quote  #2

1558462865
Report to moderator
NEW GAME FORMAT
JACKPOT UP TO $8000+
Guess The Symbols Of a Real Ethereum Hash
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1558462865
Hero Member
*
Offline Offline

Posts: 1558462865

View Profile Personal Message (Offline)

Ignore
1558462865
Reply with quote  #2

1558462865
Report to moderator
1558462865
Hero Member
*
Offline Offline

Posts: 1558462865

View Profile Personal Message (Offline)

Ignore
1558462865
Reply with quote  #2

1558462865
Report to moderator
1558462865
Hero Member
*
Offline Offline

Posts: 1558462865

View Profile Personal Message (Offline)

Ignore
1558462865
Reply with quote  #2

1558462865
Report to moderator
Vladimir
Hero Member
*****
Offline Offline

Activity: 812
Merit: 1000


-


View Profile
August 29, 2012, 05:24:02 PM
Last edit: August 29, 2012, 05:37:04 PM by Vladimir
 #2

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


-
kokojie
Legendary
*
Offline Offline

Activity: 1750
Merit: 1000



View Profile
August 29, 2012, 05:25:40 PM
 #3

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?

btc: 15sFnThw58hiGHYXyUAasgfauifTEB1ZF6
enmaku
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500


View Profile
August 29, 2012, 05:26:37 PM
 #4

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%

See why we don't consider collisions an issue?
enmaku
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500


View Profile
August 29, 2012, 05:28:45 PM
 #5

can't I just run some kind of bots, that randomly generate addresses to see if they have funds in them?

See this question on the StackExchange site for a rundown of why brute-forcing private keys (which is essentially what you're describing) is also a no-go.
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1001


View Profile
August 29, 2012, 05:29:12 PM
 #6

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
kokojie
Legendary
*
Offline Offline

Activity: 1750
Merit: 1000



View Profile
August 29, 2012, 05:30:44 PM
 #7

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?

btc: 15sFnThw58hiGHYXyUAasgfauifTEB1ZF6
enmaku
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500


View Profile
August 29, 2012, 05:32:23 PM
 #8

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.

Not to mention that even if you could find addresses, if the block reward went to zero TODAY without a billion people using Bitcoin, even today's minute amounts of transaction fees would still be worth more per cpu/gpu/fpga cycle than if you'd spent that same cycle looking for populated addresses. Given that the same equipment you'd use in such an address search should, because of the similarity of the tasks, be capable of mining as well, it would be more profitable to use that equipment for mining purposes.
Realpra
Hero Member
*****
Offline Offline

Activity: 819
Merit: 1000


View Profile
August 29, 2012, 05:33:34 PM
 #9

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

In conclusion don't store everything on one address. (Also minimizes risk of a given generator being malignant.)

Cheap and sexy Bitcoin card/hardware wallet, buy here:
http://BlochsTech.com
hashman
Legendary
*
Offline Offline

Activity: 1113
Merit: 1000


Stake & Vote or Become a IoTeX Delegate!


View Profile
August 29, 2012, 05:34:14 PM
 #10

Every time this questions pops up people start flooding the board with zeros.  Scientific notation people!

I grabbed this response from stackexchange, Thomas Pornin:

Quote

If we have a "perfect" hash function with output size n, and we have p messages to hash (individual message length is not important), then probability of collision is about p^2 / 2^(n+1) (this is an approximation which is valid for "small" p, i.e. substantially smaller than 2n/2). For instance, with SHA-256 (n=256) and one billion messages (p=109) then the probability is about 4.3*10-60.

A mass-murderer space rock happens about once every 30 million years on average. This leads to a probability of such an event occurring in the next second to about 10-15. That's 45 orders of magnitude more probable than the SHA-256 collision [in 1b messages]. Briefly stated, if you find SHA-256 collisions scary then your priorities are wrong.





               `^cder.         
          '-`ryRQQ#@@#O}-       
       .)ydi`!]PQQ#@@@@@#d}!   
  `:'`rU9660ZL:')TZ@@@@@@####O)
  `lVx<,:xWg@@@#g)iQB##@@##@@@M
  `lVcyWRBsy@@Q8Z*iQQQQB##@@@@M
  `x|G#@@@m)T<:<v~iB##@@#QQB#@M
     `)I$#m,-' `>]ZB#@@@#QQQB#3
  .>LKlxxxx_`<YUaKOQQQB#BB####P
:V5MMMTx^=*` .~xeaOQQg$RB@@@##P
 .<}ab*' .QQK\_`;<YMRO66B@@@@B}
     .`  .Q#@#Q3v`rcvvY3B#Mx_   
         .OKx*rxv`x66OX]=`     
               .!`xRdyr,       
                  !<'

IoTeX





▬▬INTERNET OF TRUSTED THINGS.▬▬
▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬.
▬▬▬▬BECOME A MEMBER TODAY▬▬▬.





        ▄███████████████████▄
        █████████████████████
▄█████  █████████████████████
██████  ████             ████
███     █████████████████████
██████  ████             ████
██████  █████████████████████
███     █████████████████████
███████ ▀███████████████████▀
▀███████▄▄▄▄▄▄▄       ▀████
  ████▌                 ██   
  ▐██▌                       
   █▌








TWITTER
MEDIUM
REDDIT
TELEGRAM
FORUM
BITCOINTALK
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1005


Gerald Davis


View Profile
August 29, 2012, 05:35:42 PM
 #11

The odds in colliding with a specific address is 1 in 2^160.

If there are a billion users and each have one million active addresses (1 quadrillion funded addresses in the blockchain) the odds in colliding with any address would be roughly 1 in 2^110 (1*10^33).

Vanitygen can produce 20 million keypairs per second.  Lets say you build a super ASIC on 12nm (4 generations ahead of current tech) process that could create, validate, and steal one trillion keypairs per second (1 TK/s). That would be about 50,000x more powerful than faster GPU today.  Lets also say you built a thousand of them and ran them continually with no downtime 24/7/365.   In 1 year you could brute force 3*10^28 possible addresses.  

If there are 1 quadrillion funded addresses you would still have a ~1% chance of colliding with a random funded address in the next 1,000 years.

TL/DR Vlad's answer works.
Quote
Chance are negligible. If collision occurs with a funded address, attacker you can transfer funds elsewhere.
muyuu
Donator
Legendary
*
Offline Offline

Activity: 966
Merit: 1000



View Profile
August 29, 2012, 05:37:36 PM
 #12

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.

GPG ID: 7294199D - OTC ID: muyuu (470F97EB7294199D)
forum tea fund BTC 1Epv7KHbNjYzqYVhTCgXWYhGSkv7BuKGEU DOGE DF1eTJ2vsxjHpmmbKu9jpqsrg5uyQLWksM CAP F1MzvmmHwP2UhFq82NQT7qDU9NQ8oQbtkQ
enmaku
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500


View Profile
August 29, 2012, 05:42:52 PM
 #13

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.
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1005


Gerald Davis


View Profile
August 29, 2012, 05:44:45 PM
 #14

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.

enmaku
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500


View Profile
August 29, 2012, 05:47:26 PM
 #15

Every time this questions pops up people start flooding the board with zeros.  Scientific notation people!

That's because most folks who don't already understand how big 2^160 is also don't understand how small 3e-38 is. The zeroes drive the point home.
Vladimir
Hero Member
*****
Offline Offline

Activity: 812
Merit: 1000


-


View Profile
August 29, 2012, 05:47:58 PM
 #16

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.



-
CoinDiver
Hero Member
*****
Offline Offline

Activity: 778
Merit: 1002


View Profile
August 29, 2012, 05:50:59 PM
 #17

approximately 3,720 to 1

http://mises.org/daily/3229
BTC:1PEyEKyVZgUvV4moXvCD5rQN21QETGPpLc
foggyb
Legendary
*
Offline Offline

Activity: 1386
Merit: 1000


View Profile
August 29, 2012, 05:52:13 PM
 #18

Generating the addresses is one thing....

What if checking the balance for each and every key takes just as long? It might take 10x as long.

Gabi
Legendary
*
Offline Offline

Activity: 1148
Merit: 1008


If you want to walk on water, get out of the boat


View Profile
August 29, 2012, 05:58:22 PM
 #19

An address collision would be a SHA256 collision

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


enmaku
Hero Member
*****
Offline Offline

Activity: 742
Merit: 500


View Profile
August 29, 2012, 06:04:03 PM
 #20

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.
Pages: [1] 2 3 4 5 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!