Bitcoin address collision

[seoincorporation]

I have a crazy theory, and I hope you can prove I'm wrong.

We have address collusion, that means two different private keys can give us the same address.

all the possible address can be written in Hex Private Key starting from:

Code:

0000000000000000000000000000000000000000000000000000000000000001

With that private key we get the RIPEMD-160 hash

Code:

91b24bf9f5288532960ac687abb035127b1d28a5

Since the address came from that RIPEMD-160 hash then there should be a collision, and the fun fact is that we should be able to calculate how many times each address collide.

We will find the same address 900000000000000000000000 times approx (in Hex) with different private keys if we can see the full list.

[pooya87]

Since the address came from that RIPEMD-160 hash then there should be a collusion,

Obviously when the hash digest size is smaller than the input message size, there is collision! Our "message" is the public key which is normally 264 bit (33 byte compressed) while the hash is usually 160 bit.

and the fun fact is that we should be able to calculate how many times each address collide.

We can not calculate the exact number since we are not "mapping" keys to addresses with a fixed ratio. We are computing the hash which is random.

Imagine if your message is 4 bits (0 to 15) but your hash is 2 bits (0 to 3), using first bits of HASH160 the result looks like this:

Code:

Msg: hash
0: 3
1: 1
2: 2
3: 1
4: 1
5: 0
6: 3
7: 0
8: 1
9: 2
10: 1
11: 2
12: 1
13: 2
14: 3
15: 0

As you can see we have collision and 0 is repeated 3 times but 1 is repeated 6 times.

Interestingly enough even without a bigger message size there still can be collision (message from 0 to 3 has no hash equal to 0 and 2x 1s). This means even if we used a bigger hash (256 bit or 512 bit) there could still be collision but with a smaller chance (with smaller hash the collision is guaranteed but not with bigger hash).

When it comes to bitcoin addresses the only reason why it doesn't happen in practice is because 2¹⁶⁰ is too huge for it to happen.

[nc50lc]

We have address collusion, that means two different private keys can give us the same address.
-snip-

Yes, there in fact old topics that discussed this.
Here's one example: There are more private keys than addresses ?

But I think you mean "collision" instead of "collusion": Google: define collusion

[seoincorporation]

Imagine if your message is 4 bits (0 to 15) but your hash is 2 bits (0 to 3), using first bits of HASH160 the result looks like this:
...
As you can see we have collision and 0 is repeated 3 times but 1 is repeated 6 times.

I know, there is no the same number for all, but since the universe is so big then the collision should be close to that number. That's why i say aprox.

But I think you mean "collision" instead of "collusion": Google: define collusion

I didn't know there was already a topic about it, i search before starting this one but couldn't find it, thanks for sharing the link.

And i already fix the title. 

[pooya87]

I know, there is no the same number for all, but since the universe is so big then the collision should be close to that number. That's why i say aprox.

You are right, due to the big size of the digest size the number should be close. I was mainly trying to point out the collision chance exists even when the digest is the same size as message.

[PrimeNumber7]

We will find the same address 900000000000000000000000 times approx (in Hex) with different private keys if we can see the full list.

To most people, this looks like a large number, but when compared to the number of potential private keys, it is not. For all intents and purposes, there will never be a collusion of two private keys mapping to the same address.

[BlackHatCoiner]

Since the address came from that RIPEMD-160 hash then there should be a collision

You can't prove two different private keys exist and collide to this very RIPEMD-160 hash, unless you find these two. You only know that there are collisions, because the range of private keys is larger than 2¹⁶⁰, so some have to return the same results like other. It is extremely likely that every RIPEMD-160 hash can come from more than 1 private key. In fact, it's likely that every such hash can come from about 2⁹⁶ Bitcoin private keys.

What you also can't prove is that there's a 100% chance for a RIPEMD-160 hash to come from any private key.

[digaran]

Didn't want to create a new topic, so here it comes.

What would happen if there are 2 identical addresses receiving funds? Since they haven't spent anything, we don't know their public keys which are obviously different, but the nodes/explorers don't know they have different private/ public key pairs, I wanna know how does that work exactly?

Since we don't have a single private key capable of generating more than one comp and one uncomp public keys, we know that there will also be no identical public keys, meaning private/public keys are unique by design, how ever there are combinations of collision happening at the same time, we have different public keys with identical sha-256 hashes, and we have different sha-256 hashes with identical rmd-160 hashes, both cases lead to identical addresses with different prv/pub key pairs, but there will never be a case when we can see different private keys spending a single public key's funds.

Main question still remains the same, how does the code handle receiving transactions to rmd-160 hashes to later realize there are 2 different valid prv/pub key pairs trying to spend from that address? Is there any error correction in bitcoin core dealing with this?

[pooya87]

Main question still remains the same, how does the code handle receiving transactions to rmd-160 hashes to later realize there are 2 different valid prv/pub key pairs trying to spend from that address? Is there any error correction in bitcoin core dealing with this?

The "code" doesn't care. It only handles scripts and in a P2PKH script for example it only cares that the top stack element has a HASH160 that is equal to what is found in the scriptpub and the two top stack items are a valid signature and public key duo in that transaction. If more than one public key can satisfy these conditions, then more than one public key can be used to spend those coins.

[PrimeNumber7]

Main question still remains the same, how does the code handle receiving transactions to rmd-160 hashes to later realize there are 2 different valid prv/pub key pairs trying to spend from that address? Is there any error correction in bitcoin core dealing with this?

Either private key can spend from the address.

For all intents and purposes, the chances of this happening are zero.

[digaran]

If more than one public key can satisfy these conditions, then more than one public key can be used to spend those coins.

Well, you are misunderstanding things here, there are no prv/pub key pairs able to spend funds from a single address, if that was possible it would mean a fatal design flaw in ECDSA, I know the code works with the public key, and the hash 160 as well as hash 256 of public key are irrelevant to ECDSA, nobody spends bitcoins by matching hashes of public keys.

My question is: if I have 2 prv/pub key pairs with colliding hashes resulting in a single address, now imagine me and you have that address but with different prv/pub keys, now I'm awaiting for a payment of 0.4BTC and you are expecting 2BTC, we could see 2.4BTC incoming transactions, but how can we now spend anything from that address while we both have valid keys which are not identical, the code has a flaw here, it can detect incoming txs but has no possible way of proving the ownership of the funds because of 2 faulty hash functions used, though the original concept of using public keys to send the funds is the best solution to resolve the collision problem.

Coming to think about it, having a system where you could use different keys to open a single door is the product of  a poor design and it endangers the integrity of the whole system.

I mean WTH, how do you validate signatures in txs? You'd pass the public key through the 256, 160 hash functions and say it's totally legit, lets confirm it. Not realizing that by doing so you are breaking the core of cryptography.
As they claim that Satoshi's coins are not safe because his public keys are exposed, on the contrary any coin attached to a public key is safe as it gets, on the other hand proving ownership by relying on back-doored hash functions is a deal breaker.

Please correct me if I'm wrong.

[ymgve2]

In your example, you can BOTH spend the 2.4 BTC, but only once (first come first serve), since you both have a valid public key that correspond to the hash. The network doesn't care if the public key is different, it only cares about the public key hashing to the correct address.

This is not the flaw you think it is. Creating any collision in RIPEMD160 or SHA256 is practically impossibly hard. It took Google 110 CPU-years to find a single collision in SHA1 (same bit length as RIPEMD160), and that was with an attack that specifically targeted SHA1.

And even with a collision, that means nothing. For this to be an issue, you need a lot more than a random collision. You need a meaningful collision - where both inputs to RIPEMD160 corresponds to a valid SHA256 hashed public key. That is practically impossibly hard. Not even for old and broken hash functions like MD5 is there any way to create collisions so specific.

It would in theory be less hard to attack SHA256 directly and find two public keys that hash to the same SHA256 value, but you still need to crack SHA256, which is much harder than finding a collision in RIPEMD160.

And this is all to find any arbitrary two keys that match. Public keys, at that*. If you intend to find something that collides with an address already used on the blockchain, the whole thing becomes much harder.


I simply don't think you grasp how impossibly big the computations for finding collisions are. Colliding public keys is a complete non-issue at the current point in time, and we will have ample warning if there are attacks that come close to breaking the security of the double hash construction. In contrast, openly published public keys are significantly weaker to attacks. (But still impossibly far beyond the reach of any current techniques and hardware)


* All these attacks presuppose that you pick basically random values and assume they're valid public keys. If you're instead trying to work with public keys where you know the private key, you also have to calculate the public key for each private key, slowing your attack down by several orders of magnitude on an already impossibly complex attack.

[NotATether]

What would happen if there are 2 identical addresses receiving funds? Since they haven't spent anything, we don't know their public keys which are obviously different, but the nodes/explorers don't know they have different private/ public key pairs, I wanna know how does that work exactly?

The ELI5 answer is that the P2[W]PKH locking script only has the condition for where the hash matches XYZ, and then it allows the funds to be moved (even if they have completely different keypairs).

[sha420hashcollision]

I have a crazy theory, and I hope you can prove I'm wrong.

We have address collusion, that means two different private keys can give us the same address.

all the possible address can be written in Hex Private Key starting from:

Code:

0000000000000000000000000000000000000000000000000000000000000001

With that private key we get the RIPEMD-160 hash

Code:

91b24bf9f5288532960ac687abb035127b1d28a5

Since the address came from that RIPEMD-160 hash then there should be a collision, and the fun fact is that we should be able to calculate how many times each address collide.

We will find the same address 900000000000000000000000 times approx (in Hex) with different private keys if we can see the full list.

Private keys generated in a standard way are not  susceptible to such collisions https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki

[pooya87]

I mean WTH, how do you validate signatures in txs? You'd pass the public key through the 256, 160 hash functions and say it's totally legit, lets confirm it. Not realizing that by doing so you are breaking the core of cryptography.
As they claim that Satoshi's coins are not safe because his public keys are exposed, on the contrary any coin attached to a public key is safe as it gets, on the other hand proving ownership by relying on back-doored hash functions is a deal breaker.

Please correct me if I'm wrong.

When spending bitcoins we aren't only verifying a hash. Each coin that is sent and spent is using a smart contract or in other words a locking and unlocking mechanism that is a series of "operations" that all need to pass for the coins to be spendable. Only a puzzle transaction made for fun would use a OP_HASH OP_EQUALVERIFY alone, all other "contracts" use a mandatory signature verification OP. If you can find a way to produce a signature for that public key, then you'd be able to spend those coins.

This is not a flaw, this is how cryptography is designed. You can't find private key of a randomly generated public key just as you can't find a collision for either SHA256 or RIPEMD160 and we are very far from the day that it becomes feasible.