Bitcoin Forum
December 07, 2016, 08:59:18 AM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 »  All
  Print  
Author Topic: probability that 2 clients generate the same public key?  (Read 4146 times)
conspirosphere.tk
Legendary
*
Offline Offline

Activity: 1862


Revolution will be decentralized


View Profile WWW
February 18, 2012, 02:59:45 PM
 #1

Hi, I seem to understand that public keys are generated randomly by the clients without any check that they already exist/are used, "just because" the chance that 2 or more clients generate the same key is "almost" zero. If correct, could this be a risk for anyone who wants to receive or transfer a serious amount of BTC? And, it would not be the case to implement a check when generating new keys?

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

Posts: 1481101159

View Profile Personal Message (Offline)

Ignore
1481101159
Reply with quote  #2

1481101159
Report to moderator
1481101159
Hero Member
*
Offline Offline

Posts: 1481101159

View Profile Personal Message (Offline)

Ignore
1481101159
Reply with quote  #2

1481101159
Report to moderator
Remember remember the 5th of November
Legendary
*
Offline Offline

Activity: 1526

Reverse engineer from time to time


View Profile
February 18, 2012, 03:06:13 PM
 #2

There are 2 quindecillion possible PRIVATE keys that can be created from what I've been told. At normal rate it would take billions of years to generate them all. In order to generate them all, and considering they are  34 characters long, we would require more space than we have.

BTC:1AiCRMxgf1ptVQwx6hDuKMu4f7F27QmJC2
stevegee58
Hero Member
*****
Offline Offline

Activity: 783



View Profile
February 18, 2012, 03:21:08 PM
 #3

Your chances of hitting the megamillion lottery or being killed by a meteorite are far, far greater.

You are in a maze of twisty little passages, all alike.
FreeMoney
Legendary
*
Offline Offline

Activity: 1246


Strength in numbers


View Profile WWW
February 18, 2012, 03:59:37 PM
 #4

Your chances of hitting the megamillion lottery and being killed by a meteorite are far, far greater.


Play Bitcoin Poker at sealswithclubs.eu. We're active and open to everyone.
drakahn
Hero Member
*****
Offline Offline

Activity: 504



View Profile
February 18, 2012, 04:05:54 PM
 #5

The BTC you would get by causing a collision would be a lot less than if you just mined lol

14ga8dJ6NGpiwQkNTXg7KzwozasfaXNfEU
FreeMoney
Legendary
*
Offline Offline

Activity: 1246


Strength in numbers


View Profile WWW
February 18, 2012, 04:06:58 PM
 #6

Hi, I seem to understand that public keys are generated randomly by the clients without any check that they already exist/are used, "just because" the chance that 2 or more clients generate the same key is "almost" zero. If correct, could this be a risk for anyone who wants to receive or transfer a serious amount of BTC? And, it would not be the case to implement a check when generating new keys?

A check is not possible. Your software doesn't know everyone else's private or public keys, only a subset of public ones. You can't even reliably restrict people from making duplicates of the known ones (in the chain) because Bitcoin is open source, people could just choose to keep the key by removing the check.

You have a much much greater chance of dying on the way to a bank and never getting your money than losing it to this insanely unlikely coincidence.

If you aren't very convinced of the astronomically small likelihood of a collision use vanitygen to try to make 10 chars of a key match and then try 15.

Play Bitcoin Poker at sealswithclubs.eu. We're active and open to everyone.
FreeMoney
Legendary
*
Offline Offline

Activity: 1246


Strength in numbers


View Profile WWW
February 18, 2012, 04:07:56 PM
 #7

The BTC you would get by causing a collision would be a lot less than if you just mined lol

Yeah, the vast majority of the time that you find one of these incredibly unlikely collisions the address is empty anyway.

Play Bitcoin Poker at sealswithclubs.eu. We're active and open to everyone.
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
February 18, 2012, 04:09:34 PM
 #8

Assume the entire bitcoin network's computational power is used for generating addresses, we'd see about 1000 billion addresses generated per second (it's around a factor 10 slower at least than hash testing). Assume this speed is maintained for as long as bitcoin mining is subsidized (until around 2140), we'd see about 4*10^17 addresses.

Since there are around 1.4*10^48 possible addresses, the chance that a duplicate is found can be calculated using the birthday problem as 1-exp(-(4*10^17)^2/(2*1.4*10^48)), or approximately 0.000000000005%, which means one in 20000 billion.

For all intents and purposes this chance can be considered 0.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
MysteryMiner
Legendary
*
Offline Offline

Activity: 910



View Profile
February 18, 2012, 05:20:10 PM
 #9

This all comes down to how good is Bitcoin random number generator. But even considering some weakness of keys, it will take away one or two zeroes from the number 0.000000000005% making it 0.0000000005%

1LEaxxAh1LKFUvDKYVhiMEVAHRM7K5o7cF
science
Member
**
Offline Offline

Activity: 72


View Profile
February 18, 2012, 06:04:39 PM
 #10



Science Smiley

BTC: 1B12Kz4nzkjZPzeKrAJi3fcqJ9CDoGXaup
Mushoz
Hero Member
*****
Offline Offline

Activity: 686


Bitbuy


View Profile WWW
February 18, 2012, 06:49:30 PM
 #11

Assume the entire bitcoin network's computational power is used for generating addresses, we'd see about 1000 billion addresses generated per second (it's around a factor 10 slower at least than hash testing). Assume this speed is maintained for as long as bitcoin mining is subsidized (until around 2140), we'd see about 4*10^17 addresses.

Since there are around 1.4*10^48 possible addresses, the chance that a duplicate is found can be calculated using the birthday problem as 1-exp(-(4*10^17)^2/(2*1.4*10^48)), or approximately 0.000000000005%, which means one in 20000 billion.

For all intents and purposes this chance can be considered 0.


And if this is used as an attack, you aren't there yet with these methods. You would actually have to check every single public key that you just generated to see if there's actually money on it. So you actually have to compare each and every public key with over 1GB of data (The current size of the blockchain), slowing down this "attack" massively. A collision attack just isn't feasible, so no need to worry Smiley

www.bitbuy.nl - Koop eenvoudig, snel en goedkoop bitcoins bij Bitbuy!
ForceField
aka Vitaliy
Sr. Member
****
Offline Offline

Activity: 388



View Profile
February 18, 2012, 08:40:51 PM
 #12

Similarly, what would be the size of a .txt file (in Megabytes) that had ALL possible Addresses & Privkeys in the following format:

For example, a .txt file with the below code is 212 bytes (0.000202178955078072 MB).

Code:
Address: 1BoatSLRHtKNngkdXEeobR76b53LETtpyS
Privkey: 5J4XJRyLVgzbXEgh8VNi4qovLzxRftzMd8a18KkdXv4EqAwX3tS
Address: 1BoatSLRHtKNngkdXEeobR76b53LETtpyT
Privkey: 5J4XJRyLVgzbXEgh8VNi4qovLzxRftzMd8a18KkdXv4EqAwX3tT

PC Hardware & Electronics For BTC     Traded w/: Kansattica | jduck1987 | shakaru | newdude | nitetrader | midievil | blo8i | mb300sd | juggalodarkclow | Garr255 | Tril | Ringmasta | SysRun | CrazyBlane | sokay | BCB | str4wm4n | PinkBatman | Bitobsessed | matauc12 | antimattercrusader | BryanK
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
February 18, 2012, 08:46:00 PM
 #13

Similarly, what would be the size of a .txt file (in Megabytes) that had ALL possible Addresses & Privkeys in the following format:

11705361804156796183489345942421835167357080816800975597555641083563606016 MiB.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
mcorlett
Donator
Sr. Member
*
Offline Offline

Activity: 308



View Profile
February 18, 2012, 08:58:40 PM
 #14

Similarly, what would be the size of a .txt file (in Megabytes) that had ALL possible Addresses & Privkeys in the following format:

For example, a .txt file with the below code is 212 bytes (0.000202178955078072 MB).

Code:
Address: 1BoatSLRHtKNngkdXEeobR76b53LETtpyS
Privkey: 5J4XJRyLVgzbXEgh8VNi4qovLzxRftzMd8a18KkdXv4EqAwX3tS
Address: 1BoatSLRHtKNngkdXEeobR76b53LETtpyT
Privkey: 5J4XJRyLVgzbXEgh8VNi4qovLzxRftzMd8a18KkdXv4EqAwX3tT
Not only do the reoccurring address-privkey strings take up a whole bunch of space, but you may be able to shorten down the private keys further by removing sipa's error correction. If you're generating standard-version addresses, you can strip the prefixing 1 out as well.

Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
February 18, 2012, 09:05:54 PM
 #15

Not only do the reoccurring address-privkey strings take up a whole bunch of space, but you may be able to shorten down the private keys further by removing sipa's error correction. If you're generating standard-version addresses, you can strip the prefixing 1 out as well.

Or you can store everything in binary, without the base58 whatsoever. 32 bytes for a privkey, 20 bytes for an address.

Down to 5742252960529749071145716877414485176439322664845761613895220154201014272 MiB.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
ForceField
aka Vitaliy
Sr. Member
****
Offline Offline

Activity: 388



View Profile
February 18, 2012, 10:38:09 PM
 #16

Similarly, what would be the size of a .txt file (in Megabytes) that had ALL possible Addresses & Privkeys in the following format:
11705361804156796183489345942421835167357080816800975597555641083563606016 MiB.

Are you being sarcastic, or is this seriously a reasonable estimate of the file size?

Would like to see the math behind the result.

PC Hardware & Electronics For BTC     Traded w/: Kansattica | jduck1987 | shakaru | newdude | nitetrader | midievil | blo8i | mb300sd | juggalodarkclow | Garr255 | Tril | Ringmasta | SysRun | CrazyBlane | sokay | BCB | str4wm4n | PinkBatman | Bitobsessed | matauc12 | antimattercrusader | BryanK
drakahn
Hero Member
*****
Offline Offline

Activity: 504



View Profile
February 18, 2012, 10:43:59 PM
 #17

it would be 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 private keys

14ga8dJ6NGpiwQkNTXg7KzwozasfaXNfEU
Mr.Coin
Jr. Member
*
Offline Offline

Activity: 31


View Profile
February 19, 2012, 09:50:08 AM
 #18

I know the chances of 2 exact keys is mindbogglingly small, but what would happen if there were?
vuce
Sr. Member
****
Offline Offline

Activity: 476


View Profile
February 19, 2012, 09:51:27 AM
 #19

I know the chances of 2 exact keys is mindbogglingly small, but what would happen if there were?
they could spend each others coins.
MysteryMiner
Legendary
*
Offline Offline

Activity: 910



View Profile
February 19, 2012, 05:49:18 PM
 #20

I know the chances of 2 exact keys is mindbogglingly small, but what would happen if there were?
they could spend each others coins.
It will look exactly like Allinvains case.

1LEaxxAh1LKFUvDKYVhiMEVAHRM7K5o7cF
Pages: [1] 2 3 »  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!