Bitcoin Forum

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?

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.

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²⁵⁶.

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.

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²⁵⁶.

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.

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

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


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.

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:

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:

And thus has this public key:

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?"

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

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?"

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"


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?"

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.

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

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


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 (https://bitcointalk.org/index.php?topic=5364003.msg58104993#msg58104993) 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.

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.

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.

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)

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.

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.

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  8) :o

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

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

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 :D

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

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.

But you don't have to store everything, you can compress things nicely. For example, you can make a binary tree of addresses. Then, lookup is much faster, insertion of a new address is much faster, many things are handled better, if you spend some time on making optimizations, instead of just running brute force on that and making a vector of addresses, just by appending 20-byte chunks. And remember: attacks only get better. I think finding collisions can be optimized in many ways, and then turned to something like 2^81 or maybe 2^82 Proof of Work on that, without requiring any large storage.

It won't matter how much you speed up your comparison process because that is not the bottleneck. The actual bottleneck that makes finding an address collision is the fact that you have to compute the very expensive private key to public key and then perform another expensive hash (SHA256) followed by another expensive hash (RIPEMD160). Expensive in this context is in comparison to the hash-comparing process (your binary search).

Only that is needed in the simplest puzzle (and I think 3KyiQEGqqdb4nqfhUzGKN6KPhXmQsLNpay will be solved first, when it comes to RIPEMD160 puzzles). Then, it is possible to start from any small value and increment that, just to get some coins from OP_RIPEMD160 puzzle. So, starting from 0000000000000000000000000000000000000000000000000000000000000000 and incrementing that will do the trick. Then, expensive ECDSA operation is not needed and expensive SHA256 is also not needed. Of course, RIPEMD160 puzzles are harder, because ASICs are optimized for SHA256d. But still, 2^80 sounds easier than 2^128, and maybe we could simplify that 2^80 into 2^64, as it was in SHA-1. Also, moving 3KyiQEGqqdb4nqfhUzGKN6KPhXmQsLNpay is serious enough to convince people, that we should move to other address types.

That's a different problem though. That's not finding two private keys or public keys which lead to the same address, but rather finding two pieces of arbitrary data which output the same RIPEMD160 digest.

I'm also not sure that finding a single RIPEMD160 collision would necessitate moving to other address types. If SHA256 was not broken, then finding two 32 byte strings which output the same RIPEMD160 digest is useless, since you still can't move from your 32 byte strings back to your public key without breaking SHA256 as well. Unless you simply mean that it is an indication that computing is becoming sufficiently powerful that the security of SHA256 can no longer be assumed?

I don't think so. Given that finding a collision is much more likely than finding a collision with a preselected address, it doesn't matter. Even better: the fact that no collision has been found yet shows we're far from compromising selected addresses. Let's say 2⁸⁰ times farther :)

Yes, we are far. But not 2^80 steps away. Private key for puzzle 2^63 is moved, so it is rather 2^17 times harder, let's say optimistically 2^20 times harder, because it will be a collision, so some additional bits will be needed to get rid of huge storage requirements.

Finding a collision of any of the millions of addresses is definitely more easier than finding a collision of a specific address, but I'm not sure that attacking the former is easier. To do the former, you need to calculate a hash and then check the entire UTXO set, while in the latter, you only calculate the hash and check a single condition.

A collision of a specific address is called preimage. Or rather: second preimage (if you know at least SHA256 that is hidden under some address). And is much more difficult. Quadratically more, so instead of 2^80, you have 2^160, maybe 2^159 for 50% chance.

But i think the word "preselected" is used here to show a difference between choosing some random private key, and choosing some random value that will be directly hashed by RIPEMD160.

The way I understand it is that you have only one condition to check each time. Not 42,201,340 (https://blockchair.com/bitcoin/addresses).

You can easily keep the 42 million hashes in memory and the memory comparison is not expensive at all, it takes a second to go through the list. Not to mention that the search can be optimized as it was mentioned earlier. You just sort it and then decide what part of the array you should look into and decrease the comparisons from 42 million to around 100 or something.

What algorithm or tool so far that can do 2^160 or 2^96 search range. Only thing I can think is vanitygen and vanity search.

Nothing. There is no tool which can search a 2¹⁶⁰ space to find one of the (on average) 2⁹⁶ private keys for a given address, because doing that much work is simply not possible. It doesn't matter if you were to write the most efficient tool in the history of computing; the amount of energy required to search even a fraction of this space would be enough to boil the oceans.

Feel free to set up vanitygen or vanity search to start indefinitely searching for a private key, if you like. All you will achieve is burnt out hardware and a large electricity bill.

When the UTXO set is large enough, such as right now, with quite a few tens of thousands (if not hundreds) of unspent outputs, the time spent burning CPU cycles to check equalities (even if it's just a plain assembler CMP/JEQ and your CPU is using the most optimized branch predictions) will simply be too much to finish before checking a random address for equality with a single one.

So finding any collision in the UTXO set has a vastly lower search space but it also has a vastly greater sarch time.

For the record: there are 42 million (http://addresses.loyce.club/total_number_of_funded_addresses.txt) addresses with unspent outputs.

What is OP mean?

Did I understand correctly?

private key 2**256  (256 bit) will behave  2**96 address duplicate address
 order = 115792089237316195423570985008687907852837564279074904382605163141518161494337

but address = can have 2**160 = 1461501637330902918203684832716283019655932542976
some private key will get the same address?

Yes, many private keys will create the same address. It's called a collision, but you can't find them.

Math become even more weird if you take into account that each private key produces 1 public key, but then public key may be presented in 2 forms (compressed/uncompressed). Each of that form could be converted into one sha256 value. Then, another operation converts both of that values into ripemd160.
In other words, as number of sha256 results is similar to number of private keys, because we use 2 forms of public keys, we may have the first collision here. Then, limiting results even more to hash160, we may have more collisions. We may assume that for example address from one compressed key, could be also generated by uncompressed key form different private key.
But, the best part is that we do not know exactly where collisions are and how many. Maybe there is "a lot" of collisions during for sha256 but none for ripemd160 (because duplicates were exhausted in previous step)?
And that is for talking about legacy addresses. For SegWit, where more sha256 are used, distribution of collision could be completely different.

Why are they more? The steps are the same until RIPEMD-160, then it starts having a different path where there are different representations involved. Also, why would the distribution of collision be different? It doesn't matter if it uses SHA256(x) or SHA256(SHA256(x)), the odds remain the same, while the cost of address generation increases.

In my opinion each time you give algorithm the chance for a collision, each time it may happen. In your second example we may have the situation where sha256(x) and sha256(y) produce the same hash SHA256(SHA256(x)) = SHA256(SHA256(y)).

Id like to know how many possible addresses are there with 2 consecutive characters. and 3 and 4 etc.. does it decrease by 1/2 on every step?

side question:
Also does it have any meaning if you have a 02 publickey and 03 publickey .. but  are a identical with the the exception of 02 03 - they result in the same btc address
i was under the impression they cannot match in this manner?  

does that apply for pubkeys  as well ?

See Bitaddress.org > Wallet Details: Pubkeys are 130 characters HEX (or 66 compressed), private keys are only 64 characters HEX. That means there are 256 times more pubkeys than privkeys. I don't know if different private keys can still give the same pubkey though.

I'm not an expert in Elliptic Curve Cryptography, but it seems like it would be a pretty big problem if 2 different private keys each resulted in the same public key?

I say that because my understanding is that the private key is an integer that indicates how many times to add the base point, and that the public key is just the coordinates of the point you end up at after completing that addition.

Doesn't that imply that if private key X and private key Y have the same public key (arrive at the same point), then private key X+1 and private key Y+1 would ALSO be matching public keys?  More importantly, for ANY integer N, X+N and Y+N would be matching public keys?

Even worse, assuming that Y is the SMALLEST private key that generates a repeat public key, that would imply that there is a cycle of exactly Y-X private keys that simply repeats over and over throughout ALL the remaining private keys.  That would mean that the effective private key range would not be the order of the chosen elliptic curve, but rather the potentially MUCH smaller value Y-X.

In reality, after a bit more thought, saying that 2 different private keys result in the same public key implies that there are 2 different points on the curve X and Y for which a straight line drawn through X and the base point hits the curve at the exact same place as a line drawn through Y and the base point.  Given the way that straight lines work, and how they only intersect elliptic curves at a maximum of 3 points, it seems the only way that can happen is if either X or Y IS the base point, meaning you've reached the order of the curve.

Sorry. Now that I've written all that (and worked through my thoughts as I went), I think I'm saying that I'm pretty confident that 2 different private keys within the range of the order of the curve can NOT both result in the same public key?

okay i understand that ... but what about 02 and 03 pubkey (compressed) being identical?  resulting in the same address...   dont know the private key.
02abcd1234567
03abcd1234567
would this not be a example of inverse relation on the curve? They are 2 different points correct?
one is a lower bit than the other which is the only difference.
 
Ive just never seen 02 and 03 being the same ... until recent

Given that Base58 has 58 characters, then there is a roughly 1 in 58 chance for the next character to match the preceding one. I say roughly because you are encoding a hex number in Base58 so it is not an exact process, and there are limits on the range of addresses.

This should not happen. It could happen, but would mean you had found the world's first SHA256 or RIPEMD160 collision. Exponentially more likely than that is that either you or the software you are using have made a mistake.

They can not. Ignoring the distinction between compressed and uncompressed public keys for a moment, then there is a one to one relationship between private keys and public keys.

They should not result in the same address. Can you share these two pubkeys so we can check?

It is not simply a lower bit. The 0x02 bit tells us that the omitted y coordinate is even, while 0x03 tells us it is odd. This means these are two separate points on the curve, with the same x coordinate, but the y coordinate reflected over the x axis.

By negating the private key (modulo n), you negate the public key. This means your two keys 02abcd1234567 and 03abcd1234567 come from two different private keys, which are the negation of each other.

Note none of this applies to newer taproot public keys, which only use even y coordinates and omit the parity byte altogether.