2^96 same bitcoin address

[vjudeu]

Without storing the addresses, you'll need to find much more of them to find a match.

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.

[1713856356]

1713856356

[1713856356]

1713856356

[1713856356]

1713856356

[1713856356]

1713856356

[pooya87]

Without storing the addresses, you'll need to find much more of them to find a match.

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

[vjudeu]

followed by another expensive hash (RIPEMD160)

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.

[o_e_l_e_o]

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?

[LoyceV]

I'm also not sure that finding a single RIPEMD160 collision would necessitate moving to other address types.

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

[garlonicon]

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.

[BlackHatCoiner]

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.

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.

[garlonicon]

a collision of a specific address

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.

[BlackHatCoiner]

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.

[pooya87]

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

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.

[bigvito19]

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.

[o_e_l_e_o]

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.

[NotATether]

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.

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.

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.

[LoyceV]

When the UTXO set is large enough, such as right now, with quite a few tens of thousands (if not hundreds) of unspent outputs

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

[fxsniper]

2^96 same bitcoin address

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?

[LoyceV]

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.

[PawGo]

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.

[BlackHatCoiner]

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.

[PawGo]

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

[MikeJ_NpC]

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?