Is it possible for two private keys/clients to generate identical BTC address ?

[ShadowOfHarbringer]

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 ?

[1714854107]

1714854107

[1714854107]

1714854107

[1714854107]

1714854107

[1714854107]

1714854107

[Mike Hearn]

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]

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

[Hal]

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?

[ShadowOfHarbringer]

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]

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]

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

[Binford 6100]

If every person on Earth makes ten addresses per second for 20 years (2x10¹⁸ 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

[LZ]

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

[david19801]

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]

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.

[david19801]

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]

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 10¹⁵ bytes.

There are 2¹⁶⁰ possible BTC addresses, each of which is 160 bits == 20 bytes long.

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

[david19801]

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]

UUIDs have 2¹²⁸ possible identifiers. They are also designed to be collision-proof. Wikipedia says:

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 2¹⁶⁰ 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.

[ribuck]

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 10³⁵ addresses to find each spendable one. Suppose you can check a million addresses per second, this is going to take you more than 10²¹ years.

If everyone in the world is trying to crack this at the same time, it will still take around 10¹² years. And when someone finally cracks it, after paying the electricity bill for 10¹² 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]

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]

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]

Nice move, you win

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]

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.