Bitcoin Forum
December 04, 2016, 10:17:39 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: Is it possible for two private keys/clients to generate identical BTC address ?  (Read 3619 times)
ShadowOfHarbringer
Legendary
*
Offline Offline

Activity: 1470


Bringing Legendary Har® to you since 1952


View Profile
February 14, 2011, 05:16:36 PM
 #1

As far as i understand, the receiving addresses are generated pseudo-randomly based on private keys which are generated when the bitcoin client is first run.

So,

1. Is it possible (however veeeeery unlikely / low probability) for 2 clients to generate the same adress ?
2. If yes, then what will happen if somebody sends bitcoins to that address ? Will both people receive the coins, none of them or some other weird thing will happen ?

1480846659
Hero Member
*
Offline Offline

Posts: 1480846659

View Profile Personal Message (Offline)

Ignore
1480846659
Reply with quote  #2

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

Posts: 1480846659

View Profile Personal Message (Offline)

Ignore
1480846659
Reply with quote  #2

1480846659
Report to moderator
1480846659
Hero Member
*
Offline Offline

Posts: 1480846659

View Profile Personal Message (Offline)

Ignore
1480846659
Reply with quote  #2

1480846659
Report to moderator
1480846659
Hero Member
*
Offline Offline

Posts: 1480846659

View Profile Personal Message (Offline)

Ignore
1480846659
Reply with quote  #2

1480846659
Report to moderator
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526


View Profile
February 14, 2011, 05:27:56 PM
 #2

1. Yes.

2. Both people will be able to spend the coins. Whoever spends first gets them, the second person to try and spend them will fail to do so.

However the chances of this happening are very low.
ribuck
Donator
Legendary
*
Offline Offline

Activity: 826


View Profile
February 14, 2011, 06:31:35 PM
 #3

Although it's theoretically possible, the chance of this happening is zero for all practical purposes.
Hal
VIP
Sr. Member
*
expert
Offline Offline

Activity: 314



View Profile
February 14, 2011, 07:17:19 PM
 #4

Is it possible for me to win every lottery for the next ten years, just by luck?

If so,what would happen?

Would they stop having lotteries because they assume I cheated?

Would I be worshipped as a god?

Hal Finney
ShadowOfHarbringer
Legendary
*
Offline Offline

Activity: 1470


Bringing Legendary Har® to you since 1952


View Profile
February 14, 2011, 07:27:46 PM
 #5

Although it's theoretically possible, the chance of this happening is zero for all practical purposes.

That depends how many possible combinations there is...
If it is more than number of atoms in the universe, then OK. Otherwise, hmmmm...

ribuck
Donator
Legendary
*
Offline Offline

Activity: 826


View Profile
February 14, 2011, 07:30:53 PM
 #6

Is it possible for me to win every lottery for the next ten years, just by luck?

If so,what would happen?
You would be locked up for fraud, because no jury would believe your appeal to statistics.
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
February 14, 2011, 11:23:15 PM
 #7

If every person on Earth makes ten addresses per second for 20 years (2x1018 total addresses), then the probability that two of these addresses collide is about 1.57x10-12.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
Binford 6100
Hero Member
*****
Offline Offline

Activity: 504


PGP OTC WOT: EB7FCE3D


View Profile
February 15, 2011, 12:05:01 AM
 #8

If every person on Earth makes ten addresses per second for 20 years (2x1018 total addresses), then the probability that two of these addresses collide is about 1.57x10-12.
this is what i like on mathemagic.
you can describe how unprobable something is

You can't build a reputation on what you are going to do.
LZ
Staff
Legendary
*
Offline Offline

Activity: 1456


Satoshi everywhere!


View Profile WWW
February 15, 2011, 01:13:59 AM
 #9

I know that someguy used the same address that I use too. If I will find where I wrote it - I will say you.

"Never invest unless you can afford to lose your entire investment." © S3052
david19801
Newbie
*
Offline Offline

Activity: 16


View Profile
February 19, 2011, 07:40:55 PM
 #10

Is it possible the probabilities are misunderstood, similar in some way to the Birthday problem?  (Where the odds of 2 people in a room having the same birthday are very much reduced from what one would expect)

Generating 10 keys per second is not very much at all.  How many could a modern server generate per second? - 100's? 1,000's?  How about a future server with tech improving at 2x per 18 months PER COMPONENT stacked?
Binford 6100
Hero Member
*****
Offline Offline

Activity: 504


PGP OTC WOT: EB7FCE3D


View Profile
February 19, 2011, 07:57:48 PM
 #11

Generating 10 keys per second is not very much at all.  How many could a modern server generate per second? - 100's? 1,000's?  How about a future server with tech improving at 2x per 18 months PER COMPONENT stacked?

ok, what about the space to store all generated key pairs? it's not only about generating all possible key pairs but also to keep them once you've generated them.

You can't build a reputation on what you are going to do.
david19801
Newbie
*
Offline Offline

Activity: 16


View Profile
February 19, 2011, 08:06:22 PM
 #12

A committed individual or organization could easily aquire network storage in the Petabytes.  I think that would be more than enough to get a sizable operation started.
Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652


Chief Scientist


View Profile WWW
February 19, 2011, 08:12:37 PM
 #13

A committed individual or organization could easily aquire network storage in the Petabytes.  I think that would be more than enough to get a sizable operation started.

1 petabyte is 1015 bytes.

There are 2160 possible BTC addresses, each of which is 160 bits == 20 bytes long.

So to store all of them you need 2160x20 bytes, which is 29,230,032,746,618,058,364,073,696,654,325,660 petabytes.


How often do you get the chance to work on a potentially world-changing project?
david19801
Newbie
*
Offline Offline

Activity: 16


View Profile
February 19, 2011, 08:21:19 PM
 #14

In which case, why bother storing at all?

If our committed individual merely cycles until hitting an account with some "cash", cleans it out, then moves on to the next.  I see it is still highly likely they would not hit anything worth their time, currently.  However, further down the line, with many many addresses being used and serious money at stake, one can imagine this becoming more and more plausible as an organised, (illegal), revenue stream.

In which case, it becomes a matter of simply how many BTC address can you compute and check per second say.  The situation under which will only get worse as technology advances.

Bear in mind, we are not looking for a single address among the clouds here.  We are looking for -any- address containing BTC.


Addition - If this becomes widespread, users would spread their BTC across multiple addresses, which effectively makes finding an account with BTC easier, but at the same time, reduces the proftability of any particular "hit".
theymos
Administrator
Legendary
*
expert
Offline Offline

Activity: 2492


View Profile
February 19, 2011, 08:27:06 PM
 #15

UUIDs have 2128 possible identifiers. They are also designed to be collision-proof. Wikipedia says:

Quote
To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion, that means the probability is about 0.00000000006 (6 × 10−11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%. The probability of one duplicate would be about 50% if every person on earth owns 600 million UUIDs.

Compare this to Bitcoin's 2160 possible addresses. Bitcoin has:
1461501637330902918203684832716283019655932542976 addresses
UUIDs have:
340282366920938463463374607431768211456 identifiers

Is it possible the probabilities are misunderstood, similar in some way to the Birthday problem?  (Where the odds of 2 people in a room having the same birthday are very much reduced from what one would expect)

I took that into account in my "ten addresses per second" example.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
ribuck
Donator
Legendary
*
Offline Offline

Activity: 826


View Profile
February 19, 2011, 08:36:41 PM
 #16

Bear in mind, we are not looking for a single address among the clouds here.  We are looking for -any- address containing BTC.

Suppose each of the 7 billion people in the world has 1000 unspent addresses. On average you would need to try more than 1035 addresses to find each spendable one. Suppose you can check a million addresses per second, this is going to take you more than 1021 years.

If everyone in the world is trying to crack this at the same time, it will still take around 1012 years. And when someone finally cracks it, after paying the electricity bill for 1012 years, they might be disappointed to find that the key unlocks just 0.05 BTC from the Bitcoin Faucet. Even if it's ten million bitcoins, it's not going to pay the electricity bill for 7 billion computers running for a trillion years.
david19801
Newbie
*
Offline Offline

Activity: 16


View Profile
February 19, 2011, 08:44:40 PM
 #17

For a system such as this, I think absolute uniqueness is a necessity.

I do completely agree with what you say, under current CPU models.  However, take this scenario: BTC becomes the world currency, then quantum computing becomes a reality.  Now what do we all do?

But then, how would one implement absolute uniqueness into the BTC system without using a central store?
ribuck
Donator
Legendary
*
Offline Offline

Activity: 826


View Profile
February 19, 2011, 08:50:28 PM
 #18

But then, how would one implement absolute uniqueness into the BTC system without using a central store?

Exactly. The system must be probabalistic because there is no central key store. But so what?

If quantum computing becomes practical, we can switch to quantum keys and spend our existing wallets to one of those newfangled keys.
david19801
Newbie
*
Offline Offline

Activity: 16


View Profile
February 19, 2011, 09:02:38 PM
 #19

Nice move, you win Wink

Going back the the OP question.  I'm new here, but from what i've heard a BTC address consists of a public and private component.

What would be the security risks of having a pack of every public key publicly available.  Then, when creating a new individual address, the public part of the newly generated address can be checked for uniqueness against the pack of public keys?  Thereby guaranteeing uniqueness of the whole address...
Hal
VIP
Sr. Member
*
expert
Offline Offline

Activity: 314



View Profile
February 19, 2011, 09:04:26 PM
 #20

Bitcoin addresses are 160-bit hashes of keys which have 256 bits of uniqueness. We could switch to a 256-bit hash pretty easily (or even not use a hash, just use the 256-bit x coordinate of the public key). The scriptPubkey could use OP_HASH256 instead of OP_HASH160 to reduce the risk of collisions. Addresses would be a few characters longer.

Hal Finney
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!