Topic: 2^96 same bitcoin address - page 2. (Read 853 times)

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

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?

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.

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).

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.

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 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://bitcointalksearch.org/topic/why-pairgen-is-fast-5312582

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

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://bitcointalksearch.org/topic/reward-offered-for-hash-collisions-for-sha1-sha256-ripemd160-and-other-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

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 

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.

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)

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 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.

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

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.

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:

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.

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

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.

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