2^96 same bitcoin address

[Kostelooscoin]

Hello we know that there are 2^96 identical bitcoin addresses in the 2^256 private key.
Is it the same for the public keys?

[1714058709]

1714058709

[1714058709]

1714058709

[garlonicon]

Yes, because for each public key there is only one matching private key. Private to public key mapping is unique, 1:1. Public key to address mapping is not, because there are around 2^256 public keys that are mapped into around 2^160 addresses, so there are around 2^96 matching keys for each address, if you assume that they are distributed equally. For some address it may be above or below 2^96, but mathematically you can be 100% sure that there is some address with around 2^96 or more matching keys.

[pooya87]

When you say "addresses" and not specify what type, then the answer is there are a lot more than the size of a RIPEMD160 hash because we have multiple types of addresses and 3 ways to represent public keys each creating a different hash. Then we also have addresses made from hash of the scripts containing the public key so the number grows even more (eg. P2(W)SH) and finally we have brand new addresses using the public key itself known as P2TR or witness version 1 addresses used in Taproot.

In short for each private key there are far more addresses than 2²⁵⁶.

[vjudeu]

Then we also have addresses made from hash of the scripts containing the public key so the number grows even more

Yes, 2^96 applies only to P2PKH or P2WPKH, in case of P2WSH the number of combinations is potentially unlimited, because there are many spendable scripts, for example "<some_public_key> OP_CHECKSIGVERIFY OP_SIZE <less_or_equal_520> OP_EQUALVERIFY OP_HASH256 <some_hash> OP_EQUAL", then you can push any transaction up to 520 bytes on the stack and add your signature. Because MAX_SCRIPT_SIZE is set to something like 10,000 bytes, there could be even 2^80000 possible P2WSH addresses or something like that, so because they are 256-bit addresses, a lot of keys could be used to produce the same address.

[BlackHatCoiner]

And note that this is just for an address type that encodes a RIPEMD-160 hash. In P2WSH, multi-sig addresses are encodings of a 256-bit number and thus, there aren't 2⁹⁶ private keys for each address on average. There isn't even 1 for each address. The total private keys that are valid are slightly lower than 2²⁵⁶.

[Kostelooscoin]

Is it possible to find two public keys with the same bitcoin address ?

[BlackHatCoiner]

Is it possible to find two public keys with the same bitcoin address ?

Yes. Essentially, that's what we've told you. Each private key creates a unique public key that cannot be created from any other private key. Thus, since private keys are around 2²⁵⁶, that's the same number of different public keys that can be hashed.

If you're querying if it's probable, then no. It's highly unlikely to ever find such collision. It's not impossible, though.

[Kostelooscoin]

how do we go from the first public key to the second ? what calculations ?

[DannyHamilton]

It's not impossible, though.

It may not be mathematically/technically impossible, but it's realistically effectively impossible.

Is it possible to find two public keys with the same bitcoin address ?

If you are asking if there is a mathematical non-zero probability that 2 different randomly generated public keys might both end up having the same address, then yes, that's true. It is technically "possible". The probability is 0.00000...lots and lots of zeros...something percent. The number of zeros in that percent is so large that it really doesn't matter.

If you are asking if there is a realistic possibility that it will ever happen with truly random public keys within the time that the universe exists? The answer is no, it is not possible.

Think about it like this.  The oxygen molecules in the room you are in are randomly distributed.  As such, any single arrangement of those molecules throughout the room is equally likely.  Among those overwhelming number of arrangements, there are a small number of arrangements where there isn't enough oxygen near your face for you to survive.  There are trillions and trillions and trillions (and more) arrangements where there is plenty of oxygen near you for you to breathe.  It is mathematically, technically POSSIBLE for you to suffocate in a room that has plenty of oxygen?  Yes.  There is a non-zero probability.  However, I think we can all agree that in reality, it is effectively impossible. You don't spend all day every day wondering if you are suddenly not going to have enough oxygen near you for you to breathe.

If you are asking if there is a known mathematical way to calculate 2 such public keys.  No.  There is not.

[BlackHatCoiner]

how do we go from the first public key to the second ? what calculations ?

What exactly do you want to do? You appear to have many questions which are unrelated with each other.

You should be more explanatory when you're making questions related with these complex terms. For example, “first” or “second” public key doesn't make much sense. Do you mean the public key with private key = 1... 2... 3... etc?

If that's so, you take the private key and multiply it in a special way, called ECC multiplication, with a point in a curve. This point is called G and has the following coordinates:

Code:

x: 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y: 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

Once you multiply an integer with a curve's point you end up with another point in the same curve. For example, 5 times G does:

Code:

x: 2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
y: d8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6

And thus has this public key:

Code:

Uncompressed: 042f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4d8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6
Compressed: 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4

[DannyHamilton]

For example, “first” or “second” public key doesn't make much sense. Do you mean the public key with private key = 1... 2... 3... etc?

You just told him that there are multiple public keys that result in the same address.  You also just told him it was possible to find two public keys with the same bitcoin address. He wants to know how.  When he says "first" and "second", he's talking about the multiple public keys that you just said he could find.
 
Go back and re-read what he's posted.  It seems to me that he's saying the following:

1Q. "Are there an average of 2⁹⁶ different ECDSA Secp256k1 public keys that all result in the same P2PKH Bitcoin Address?"

Hello we know that there are 2^96 identical bitcoin addresses in the 2^256 private key.
Is it the same for the public keys?

1A. He received an answer of "Yes".

Yes, because for each public key there is only one matching private key.

2Q. "Is there a calculation that I can use to find multiple ECDSA Secp256k1 public keys that all result in the same bitcoin P2PKH address?"

Is it possible to find two public keys with the same bitcoin address ?

2A. You misunderstood what he was asking (you thought he wanted to know if this meant that there was a mathematically non-zero probability of a collision.), so you told him "Yes"

Yes. Essentially, that's what we've told you.

3Q. "Ok, since you've just told me that, yes, there is a calculation that I can use to find multiple public keys that all result in the same bitcoin address, can you please tell me how to do that calculation?"

how do we go from the first public key to the second ? what calculations ?

3A.  The problem is that due to the miscommunication, you now don't understand what he's asking for, and he misunderstands what is and isn't possible.

There is no known calculation that can be used to find 2 different public keys that both result in the same Bitcoin Address.  This is because the P2PKH address is the RIPEMD160 HASH of the public key (along with a version number and a checksum), and there is no known calculation that would let you generate 2 different inputs to the RIPEMD160 hash function that would both result in the same output hash value.  The only thing you could do would be to just keep generating random public keys and then generating the hash from that key and checking to see if it matches any of the ones you already generated in the past.  The odds of ever encountering such a collision are so small that it isn't going to happen in the amount of time that humans will exist.  Alternatively, it's always possible that some mathematician may someday find a weakness in the RIPEMD160 hash algorithm that makes it faster and easier to find a collision.  This hasn't happened yet, and there's no way to know ahead of time if or when it might happen.  However, if it does, we can all move our bitcoins to a new address structure that doesn't use RIPEMD160 anymore.

[Kostelooscoin]

how do we go from the first public key to the second ? what calculations ?

What exactly do you want to do? You appear to have many questions which are unrelated with each other.

You should be more explanatory when you're making questions related with these complex terms. For example, “first” or “second” public key doesn't make much sense. Do you mean the public key with private key = 1... 2... 3... etc?

If that's so, you take the private key and multiply it in a special way, called ECC multiplication, with a point in a curve. This point is called G and has the following coordinates:

Code:

x: 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y: 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

Once you multiply an integer with a curve's point you end up with another point in the same curve. For example, 5 times G does:

Code:

x: 2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
y: d8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6

And thus has this public key:

Code:

Uncompressed: 042f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Compressed: 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4

5*79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 = 2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
5*483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 = 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

[BlackHatCoiner]

He wants to know how.

The problem of this brought confusion lies on the badly formulated question of Kostelooscoin. Specifically, this one:

how do we go from the first public key to the second ?

For instance, how can one understand what the first public key is? Even based on the posts of this discussion. It could mean the way we can calculate the distance between two public keys (difference of two x-coordinates) which give the same address or the procedure of ending up to the second public key based on the times G has been multiplied by only having the first public key.

My reply didn't mention that there are TWO public keys with the same bitcoin address, but rather around 2⁹⁶. IF I had said that there're at least two or exactly two, I could have understood the question better, but seeing a “first” and a “second” made me understand they want to know something else.

2Q. "Is there a calculation that I can use to find multiple ECDSA Secp256k1 public keys that all result in the same bitcoin P2PKH address?"

Is it possible to find two public keys with the same bitcoin address ?

2A. You misunderstood what he was asking (you thought he wanted to know if this meant that there was a mathematically non-zero probability of a collision.), so you told him "Yes"

It depends on how you understand the question; I'm not yet convinced that I did it wrong. Kostelooscoin asks if that very condition where two public keys give the same bitcoin address can ever come true; if it's possible to ever be true. That's how I understand it and based on that understanding I replied.

But, NOW that I've seen their latest question, I can acknowledge that their next-to-last question wasn't meant to be answered that way.


So, Kostelooscoin, to sum up;

It is possible to find two or more public keys which give the same bitcoin address, but it is highly unlikely or as said by DannyHamilton, realistically effectively impossible to ever find such couple. If you ever somehow searched the entire range, a COMPLETELY HYPOTHETICAL & FANTASTIC SCENARIO, you'd find on average 2⁹⁶ public keys which give the same address.

There's no way to know or approach the distance between two public keys that once hashed with SHA256 & RIPEMD-160 and encoded with base58 give the same address, unless you start trying (brute forcing) keys until you've indeed found such pair. That's true due to the unpredictability of the final output hash functions provide to us.

In other words, I may start hashing numbers whose distance is 1 such as RIPEMD160(1), RIPEMD160(2), RIPEMD160(3)..., but their hashes will not have a mathematical connection. At least not a connection one has found so far.

[o_e_l_e_o]

Alternatively, it's always possible that some mathematician may someday find a weakness in the RIPEMD160 hash algorithm that makes it faster and easier to find a collision.  This hasn't happened yet, and there's no way to know ahead of time if or when it might happen.  However, if it does, we can all move our bitcoins to a new address structure that doesn't use RIPEMD160 anymore.

Correct me if I'm wrong, but actually, it wouldn't matter if RIPEMD160 was completely broken. Turning a public key in to an address requires first performing SHA256 on the public key before performing RIPEMD160. Even if we were able to find every other RIPEMD160 input which would result in a given output instantaneously, we still would not be able to find public keys collisions because we would still have to brute force the SHA256 function, which is equally impossible.

And even if we did find public keys collisions, we still can't steal the coins without also being able to reverse elliptic curve multiplication, which is similarly impossible for the time being.

5*79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 = 2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
5*483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 = 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

We are talking about multiplication on an elliptic curve here. It is not the same as just arithmetically multiplying two numbers together as you would be used to doing.

To work out 5G, you must first add G to itself to give you 2G. Then add 2G and 2G to give you 4G. Then add 4G and G to give you 5G. To add two points together, such that:

(x_p, y_p) + (x_q, y_q) = (x_r, y_r)

Then you use the following equations, where s is the slope of either a straight line joining those two points, or in the case of adding a point to itself, a line tangent to that point:

x_r = s² - x_p - x_q
y_r = -y_p + s(x_p - x_r)

[vjudeu]

it wouldn't matter if RIPEMD160 was completely broken

Yes, because breaking SHA-256 is way more dangerous. If you know SHA-256(first_public_key) and you can create SHA-256(second_public_key) that has the same hash, then RIPEMD-160(hash) will be the same in both cases, because the same input will be passed to RIPEMD-160. To see some example of what could happen when some hash function will be broken, you can skip some rounds. You can replace 64 rounds SHA-256 with 16 rounds SHA-256, then you can easily produce two different public keys that will result in the same address and easily see the consequences of breaking some hash function.

And even if we did find public keys collisions, we still can't steal the coins without also being able to reverse elliptic curve multiplication, which is similarly impossible for the time being.

It depends how you prepare your input data. If you feed hash function with public keys where you don't know the private key, then yes, after breaking hash functions you still have to deal with breaking that public key. But if you use only public keys where you know the private key, then you don't have to break ECDSA. Of course attacking with random public keys is faster, because you have to check only if some point is valid, and then you usually have to flip only one bit to turn invalid public key into some random valid public key.

[MrFreeDragon]

I  still want to find at least 2 different public keys (better different private keys within the bitcoin elliptic curve order) which lead to the same bitcoin addresses 

[garlonicon]

I  still want to find at least 2 different public keys

You can make it a challenge and put some coins on it. If you want just a collision of any hashed data, then there is a puzzle for that, check address 39VXyuoc6SXYKp9TcAhoiN1mb4ns6z3Yu6 and topic https://bitcointalk.org/index.php?topic=293382

better different private keys within the bitcoin elliptic curve order

If you want to make sure that someone has all needed private keys, then you can slightly modify this script:
address collision checking: OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_HASH160 OP_SWAP OP_HASH160 OP_EQUAL
the same with signature checking: OP_2DUP OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_HASH160 OP_SWAP OP_HASH160 OP_EQUALVERIFY OP_TOALTSTACK OP_CHECKSIGVERIFY OP_FROMALTSTACK OP_CHECKSIG

[LoyceV]

I  still want to find at least 2 different public keys (better different private keys within the bitcoin elliptic curve order) which lead to the same bitcoin addresses  

Based on the birthday paradox, you're likely to find one if you have more than 2⁸⁰ addresses. That's a bit over 10²⁴ addresses. Let's call it 50 YB. Once you're there, all you need to do is sort it and you'll easily find a consecutive duplicate.
I wouldn't hold my breath

[vjudeu]

But you don't need that much space. You only need that much computing power. There are ways to do that if you have less storage, just because a lot of addresses will have the same prefixes, and also you can do your lookup in a deterministic way, for example by choosing some random key and incrementing that.

Also check pairgen and how fast it is when compared to vanitygen: https://bitcointalk.org/index.php?topic=5312582.0

[LoyceV]

But you don't need that much space. You only need that much computing power. There are ways to do that if you have less storage, just because a lot of addresses will have the same prefixes, and also you can do your lookup in a deterministic way, for example by choosing some random key and incrementing that.

Without storing the addresses, you'll need to find much more of them to find a match. If you store 2⁸⁰ addresses (and keep adding more), finding a duplicate becomes inevitable.