Topic: 2^96 same bitcoin address (Read 850 times)

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.

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

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?

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.

does that apply for pubkeys  as well ?

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?  

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

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.

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.

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

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?

For the record: there are 42 million addresses with unspent outputs.

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.

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.

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.

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.

The way I understand it is that you have only one condition to check each time. Not 42,201,340.

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.

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.

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.