Bitcoin Forum
April 21, 2018, 05:41:09 PM *
News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: « 1 [2]  All
  Print  
Author Topic: By 2140 or later, what will the chance of a collision be?  (Read 3245 times)
Dabs
Staff
Legendary
*
Offline Offline

Activity: 2016
Merit: 1093



View Profile
October 25, 2016, 06:55:04 PM
 #21

There will never be a collision.

How about a bet?


Rico


I'll take on that bet. However there must be a finite time; or deadline.. The odds are against me, so I'm not willing to wait a hundred years.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
1524332469
Hero Member
*
Offline Offline

Posts: 1524332469

View Profile Personal Message (Offline)

Ignore
1524332469
Reply with quote  #2

1524332469
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1524332469
Hero Member
*
Offline Offline

Posts: 1524332469

View Profile Personal Message (Offline)

Ignore
1524332469
Reply with quote  #2

1524332469
Report to moderator
1524332469
Hero Member
*
Offline Offline

Posts: 1524332469

View Profile Personal Message (Offline)

Ignore
1524332469
Reply with quote  #2

1524332469
Report to moderator
1524332469
Hero Member
*
Offline Offline

Posts: 1524332469

View Profile Personal Message (Offline)

Ignore
1524332469
Reply with quote  #2

1524332469
Report to moderator
rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
October 25, 2016, 08:17:32 PM
 #22


Collisions will occur (and have occurred) when people use random number generators with poor entropy, brain-wallets, or when they use poorly created wallet software.

That's not the definition of a collision.

The definition of a collision is: 2 different private keys will compute into one hash160.

I'm not the youngest anymore, but I'm quite confident we will see such a collision within the next 25 years.


Rico

edit: Huh Danny? You teleported away?

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
DannyHamilton
Legendary
*
Offline Offline

Activity: 2128
Merit: 1321



View Profile
October 25, 2016, 08:25:11 PM
 #23


Collisions will occur (and have occurred) when people use random number generators with poor entropy, brain-wallets, or when they use poorly created wallet software.

That's not the definition of a collision.

The definition of a collision is: 2 different private keys will compute into one hash160.

I'm not the youngest anymore, but I'm quite confident we will see such a collision within the next 25 years.


Rico

Ah!  So we aren't concerned about 2 people generating the same private key?

Ok then, I'll happily take that bet.  How much do you want to put on it, and what timeframe?  You'd have a better chance of winning if you bet that all human life on the earth will be destroyed by an asteroid in the next 25 years.

rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
October 25, 2016, 08:51:16 PM
 #24

Ah!  So we aren't concerned about 2 people generating the same private key?

Ok then, I'll happily take that bet.  How much do you want to put on it, and what timeframe?  You'd have a better chance of winning if you bet that all human life on the earth will be destroyed by an asteroid in the next 25 years.

Well - I am not concerned about anything.  Smiley

I thought about 25y timeframe, because compared with the "There will never be a collision." statement which provoked my reaction, this is very very soon. As for the sum to put on it, let me do some research 1st like what is usual in these "scientific" bets
https://en.wikipedia.org/wiki/David_Levy_(chess_player)#Computer_chess_bet
or rewards for solutions to "problems"
https://en.wikipedia.org/wiki/Paul_Erd%C5%91s#Erd.C5.91s.27_problems

so between $500 and $5000 of todays $?


BTW: Betting on the destruction of mankind is quite pointless if even one of the betting parties is human.


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
Syke
Legendary
*
Offline Offline

Activity: 2576
Merit: 1003


View Profile
October 25, 2016, 09:29:40 PM
 #25

There will never be a collision.
How about a bet?

In case it wasn't clear, I mean a collision of randomly-generated keys. Poorly generated keys like brain wallets are prone to collision.

Buy & Hold
Dabs
Staff
Legendary
*
Offline Offline

Activity: 2016
Merit: 1093



View Profile
October 25, 2016, 09:48:46 PM
 #26

I'll join the bet. Or, if you like, I can escrow the bet. I'll hold between 1 BTC to 10 BTC (each side contributes 5 BTC each).... And just so this is all fun, let's make it a multi-sig address. 3 of 6. Each one holds 2 keys, and of those 1 key held by an heir (in case you die in 25 years).

The problem lies when both of you or me get hit by the proverbial bus before 25 years is up. I propose an exact time in the future to the minute. Something like October 25, 2041, 12:01 AM or one minute after midnight of that day.

Or think of something along those lines.

If y'all don't know how to multi-sig, I propose a "simple" escrow where I hold the private key. If I die before 25 years, please come to my funeral, the private key will be on my person (engraved on tungsten, worn around my neck, ... or something.)

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
DannyHamilton
Legendary
*
Offline Offline

Activity: 2128
Merit: 1321



View Profile
October 26, 2016, 05:21:12 AM
 #27

I'll join the bet. Or, if you like, I can escrow the bet. I'll hold between 1 BTC to 10 BTC (each side contributes 5 BTC each)....

See, herein lies the problem...

Betting on the destruction of mankind is quite pointless if even one of the betting parties is human.

And betting on the destruction of bitcoin is quite pointless if the parties are using bitcoin as the prize.

If rico666 is correct and he wins the bet (there is a RIPEMD160 collision such that two private keys are shown to result in the same bitcoin address), then faith in bitcoin will be shattered and the amount he will win will be worthless at the time he collects it.

I suspect this is why is stated that the bet would be between $500 and $5000 (instead of stating that the bet would be between 0.7692 BTC and 7.6923 BTC).

rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
October 26, 2016, 06:13:04 AM
 #28

What I think is important to state:

A collision is not the event when

Code:
while(1) {
  if (rand(2^256) == rand(2^256) {
    print "We got ourselves a re-used private key!\n";
  }
}

a collision is when

Code:
while(1) {
  for (a = 0 to 2^160) {
    adr1 = ripemd160(sha256(pubkey(a)))
    adr2 = ripemd160(sha256(pubkey(rand(2^256-2^160)+2^160)))
    if (adr1 == adr2) {
      print "We got ourselves a collision!\n";
    }
  }
}

both is pseudo-code of course, one should not make any conclusions about probabilities of events because "one (the second one) seems to take longer".

Personally, I do not see how faith in bitcoin could be shattered if a collision is found, as - hopefully - everyone knows already that because of the 256->160 bit reduction in address generation there inherently are collisions, namely 2^96 private keys per address.

Even if two private keys do map to one address, the public key will still be different and I do not believe that even if cryptographers should have several examples of collisions they would be able to form a reverse-map attack against bitcoin.

Also the problem with "2 randomly generated private keys (using a working rndgen) ending up as one and the same" can never by proven to have happened, while the collision can.

Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
TransaDox
Full Member
***
Offline Offline

Activity: 219
Merit: 100


View Profile
October 26, 2016, 09:06:59 AM
 #29

a collision is when

Code:
while(1) {
  for (a = 0 to 2^160) {
    adr1 = ripemd160(sha256(pubkey(a)))
    adr2 = ripemd160(sha256(pubkey(rand(2^256-2^160)+2^160)))
    if (adr1 == adr2) {
      print "We got ourselves a collision!\n";
    }
  }
}

I think you mean:

Code:
 adr1 = ripemd160(sha256(pubkey(rand(2^256-2^160)+2^160)))
  for (a = 0 to 2^160) {
    adr2 = ripemd160(sha256(pubkey(a)))
    if (adr1 == adr2) {
      print "We got ourselves a collision!\n";
    }
  }
rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
October 26, 2016, 09:51:20 AM
 #30


I think you mean:

Code:
 adr1 = ripemd160(sha256(pubkey(rand(2^256-2^160)+2^160)))
  for (a = 0 to 2^160) {
    adr2 = ripemd160(sha256(pubkey(a)))
    if (adr1 == adr2) {
      print "We got ourselves a collision!\n";
    }
  }

Yep. That's what I mean.


Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1000


View Profile
October 26, 2016, 04:52:36 PM
 #31

FYI:
https://bitcointalk.org/index.php?topic=293382.0
pepethefrog
Member
**
Offline Offline

Activity: 120
Merit: 10


Pepe is NOT a hate symbol


View Profile
November 03, 2016, 08:30:21 AM
 #32

It's not about the chance. If there is a possibility, and if we continue at our current rate, there will be a collision. It's just about when.

Pepe agrees that an infinite number of collisions exist, because the size of the digest of the hash (32 byte) is smaller than all the "infinite" amounts of datasets that can act as input to the hash.
Pepe sees a much bigger problem in keeping track of all the hashes you already tried to actually be able to detect that a collision has been found.
So, next to extremely fast and vast computers you would also need extremely large data storage that can quickly be searched and correlated with the key you are currently generating.

Bipcoin: bip1W2nq2vhM4f6kaHSsVD5J1LdRb1M3mCqftwq6erpEeKzsj8Kjrxy5xUs9VAtF233nNzcMQN2ZQfJ fvi2WensZ5tGJv2ysY8
Pepe is NOT a hate symbol.
calkob
Hero Member
*****
Offline Offline

Activity: 714
Merit: 500


View Profile
November 04, 2016, 09:47:49 PM
 #33

So what if we moved the equivalent of 1 exahash into address generating?

You clearly weren't paying attention when achow101 said:

2^160 is an unimaginably huge number.

The current world population is about 7.4 X 109

Lets somehow imagine that every man, woman, and child in the world is running equipment that continuously generates 1 exa-address per second.  That includes infants, destitute and homeless poor people, and those laying in their deathbed in the hospitals.  EVERY man, woman, and child.

That's 1 X 1017 addresses per second per person times 7.4 X 109 people = 7.4 X 1026 addresses generated worldwide per second.

There are a bit less than 3.16 X 107 seconds in a year.

Lets imagine that these 7.4 X 109 run their equipment continuously 24 hours a day 7 days a week without any interruptions for maintenance for a century (100 years).  That's 3.16 X 109 total seconds.

After all that, a total of a bit less than 2.34 X 1036 addresses will have been generated.

That's completely unrealistic imaginary situation is still less than 0.00000000017 % of all the possible addresses.

Additionally, if you split up all the possible bitcoins that could ever exist into only 1 satoshi per address, you would have an absolute maximum of no more than 2.1 X 1015 addresses that have any value in them at all.  Therefore, even if you somehow beat those astronomical odds and found an address collision, you would be more than 1,000,000,000,000,000,000,000 timed more likely to have collided with an empty address than an address that has any bitcoins in it, and if you did collide with an address with any bitcoins, and if you also somehow beat those astronomical odds it would be extremely likely to have only 1 satoshi in it.

I'm doing this math for you and writing these numbers for you, but I'm concerned that you aren't going to understand just how unlikely this is.  With odds this small, there isn't any real difference from "impossible".  Yes, there are numbers there, but those numbers in the real world are effectively the same as saying it can't happen.

This is the best post i have ever read, thanks Danny  Grin
rico666
Hero Member
*****
Offline Offline

Activity: 910
Merit: 1005


฿ → ∞


View Profile WWW
November 04, 2016, 10:20:44 PM
 #34

You clearly weren't paying attention when achow101 said:
2^160 is an unimaginably huge number.

Lets somehow imagine that every man, woman, and child in the world is running equipment that continuously generates 1 exa-address per second.  That includes infants, destitute and homeless poor people, and those laying in their deathbed in the hospitals.  EVERY man, woman, and child.

That's 1 X 1017 addresses per second per person times 7.4 X 109 people = 7.4 X 1026 addresses generated worldwide per second.
...

This is the best post i have ever read, thanks Danny  Grin

Yeah - it's similar to these child frightening stories or pictures of the sun and some physics yadda.

Of course I can imagine that for someone who doesn't know that Exa means 1018 instead 1017 (hey - it's only one order of magnitude, e.g. 10 years instead of 100 years but who am I to judge), a number like 1048 (roughly 2160) must look pretty unimaginable.

For me, 1048 is pretty imaginable. Intuitively I'd say it's the number of atoms of 1% of the Earth. So what?



Rico

all non self-referential signatures except mine are lame ... oh wait ...   ·  LBC Thread (News)  ·  BURST Activities
Pages: « 1 [2]  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!