There are about 2**160 pigeons sitting in approximately 2**256-32 cages,
You have mixed the stuff.
In my analogy pigeons correspond to keys , while cages - to addresses.
Topic: One more question regarding collisions (Read 347 times)
You have mixed the stuff.
In my analogy pigeons correspond to keys , while cages - to addresses.
There are about 2**160 pigeons sitting in approximately 2**256-32 cages, theoretically for every original pigeon there are 2**96 clones. The question is, how many images of pigeons can you hold in your hand while searching, and how many cages per second can you search?
And when you are doing the search, you will have to compare each cage's content with all of your images(address or RMD-160 hash), which takes us back to the old problem of computationally difficult to do.
If LBC pool has anything to say, they can say it by solving puzzle 66.
And when you are doing the search, you will have to compare each cage's content with all of your images(address or RMD-160 hash), which takes us back to the old problem of computationally difficult to do.
If LBC pool has anything to say, they can say it by solving puzzle 66.
If it's about address collision, they wouldn't only search within a limited private key range that's quite possible to bruteforce.
If one has, let's say, 10 pigeons sitting in 9 cages he may search withing a limited number of pigeons (let's say at least 2) sitting in one cage.
The same is true with the search within a limited private key range.
They still have a chance to find the key collision when searching "within a limited private key range".
Yeah, I know what collision means 
Looks like they are now focused on private keys bruteforcing but, as they stated, finding collision is among LBC priorities
That's what they're doing even now, as you can see in the image, it's about "private key collision" and not an address collision which is the topic is all about.Looks like they are now focused on private keys bruteforcing but, as they stated, finding collision is among LBC priorities
Quote from: https://lbc.cryptoguru.org/about
OP is asking about address collision which is about two different private keys that produce the same pubKey hash.
LBC on the other hand, is specifically looking for private keys in 2^160 range that's already used by others, same address but same private key.
If it's about address collision, they wouldn't only search within a limited private key range that's quite possible to bruteforce.
Assuming you trust them, especially with their closed-source software which have remote-execution capability.
Definitely yes.
I think those who involved into LBC activity are wise enough to connect, solely, designated machines rather than those ones which have sensitive soft (like wallets) and/or information.
Disclaimer. I'm not involved as I don't have the spare machine with powerful CPU.
That LBC statistic must be incorrect because a single 4xxx level card should be able to do 90mkeys/sec entirely on its own, and 50-100 times that if it does a linear scan of the private key space.
Looking at https://lbc.cryptoguru.org/about, it looks like they only perform 3 performance optimization and they use software called "GPUAuth4All" for GPU brute-force. I expect it's combination of optimized GPU usage and lack of interest towards LBC.
The aim of my previous post was to show that there are some fantastical ppl who put their efforts on finding collision.
Assuming you trust them, especially with their closed-source software which have remote-execution capability.
There is project called Large Bitcoin Collider which uses the hashing power of involved folks for finding collision. Currently LBC is capable to generate on average up to 90Mkeys/sec. Please, have a look on their trophies so far:
-snip-
The probability to find collision with LBC is vanishingly small, but...there is always a but.
Those "trophies" are specifically created from private keys with a very small search-space.-snip-
The probability to find collision with LBC is vanishingly small, but...there is always a but.
e.g.: starting from 0x01, 0x03, 0x07.... 0x236fb6d5ad1f43 (#54) and higher ranges.
They were merely bruteforcing private keys starting from 0x01 to their target range of the puzzle transaction (link) to match the same private key used by the creator of the puzzle.
It has nothing to do with collision.
Yeah, I know what collision means
Looks like they are now focused on private keys bruteforcing but, as they stated, finding collision is among LBC priorities
retrospectively, the probability of your coming-into-being is equal to almost zero, but despite of this, you are typing on this forum.
There is project called Large Bitcoin Collider which uses the hashing power of involved folks for finding collision. Currently LBC is capable to generate on average up to 90Mkeys/sec. Please, have a look on their trophies so far:
-snip-
The probability to find collision with LBC is vanishingly small, but...there is always a but.
Those "trophies" are specifically created from private keys with a very small search-space.-snip-
The probability to find collision with LBC is vanishingly small, but...there is always a but.
e.g.: starting from 0x01, 0x03, 0x07.... 0x236fb6d5ad1f43 (#54) and higher ranges.
They were merely bruteforcing private keys starting from 0x01 to their target range of the puzzle transaction (link) to match the same private key used by the creator of the puzzle.
It has nothing to do with collision.
The probability to find collision with LBC is vanishingly small, but...there is always a but.
This is misleading IMO, LBC is nothing but a brute force pool and has nothing to do with actual hash collisions. There is no evidence suggesting they have found 2 different private keys opening a single address. Also note that we have different types of collisions, one would be 2 different public keys having the same SHA-256 hash output, or having 2 different SHA-256 hashing to one RMD-160 output.
That LBC statistic must be incorrect because a single 4xxx level card should be able to do 90mkeys/sec entirely on its own, and 50-100 times that if it does a linear scan of the private key space.
The following is from the Bitcoin wiki:
Or, in other words: Is there any way to find out if a collision already happened in the past?
Quote
Since Bitcoin addresses are basically random numbers, it is possible, although extremely unlikely, for two people to independently generate the same address. This is called a collision. If this happens, then both the original owner of the address and the colliding owner could spend money sent to that address. It would not be possible for the colliding person to spend the original owner's entire wallet (or vice versa).
So the question is: Could it be possible that a collision already happened in the past, we just don't know it? And even the "victims" of a collision do not know?Or, in other words: Is there any way to find out if a collision already happened in the past?
There is project called Large Bitcoin Collider which uses the hashing power of involved folks for finding collision. Currently LBC is capable to generate on average up to 90Mkeys/sec. Please, have a look on their trophies so far:
Quote from: https://lbc.cryptoguru.org/trophies
The probability to find collision with LBC is vanishingly small, but...there is always a but.
For instance, retrospectively, the probability of your coming-into-being is equal to almost zero, but despite of this, you are typing on this forum.
We can, of course, assume that it is the old owner. But we just don't know.
We know.
We know because we understand the probabilities.
But you're welcome to pretend that we don't know if that somehow satisfies your curiosity.
Well, it is possible to write a Script, which will do exactly that.
Input Script:
Output Script:
See also: https://bitcointalksearch.org/topic/reward-offered-for-hash-collisions-for-sha1-sha256-ripemd160-and-other-293382
And then, it is all about incentives: if enough coins will be there, on such address, then people will have a reason, to reveal such collision.
Input Script:
Output Script:
Code:
OP_2DUP OP_EQUAL OP_NOT OP_VERIFY //checking if public keys are different
OP_2DUP OP_HASH160 OP_SWAP OP_HASH160 OP_EQUALVERIFY //checking if their hashes are identical
OP_TOALTSTACK OP_CHECKSIGVERIFY OP_FROMALTSTACK OP_CHECKSIG //making sure that the signatures are correct, so public keys are valid
Which means, that you can just create a TapScript branch, with this challenge, and then you can spend coins by using your key, but also someone else will be able to do that, by providing that kind of collision.OP_2DUP OP_HASH160 OP_SWAP OP_HASH160 OP_EQUALVERIFY //checking if their hashes are identical
OP_TOALTSTACK OP_CHECKSIGVERIFY OP_FROMALTSTACK OP_CHECKSIG //making sure that the signatures are correct, so public keys are valid
See also: https://bitcointalksearch.org/topic/reward-offered-for-hash-collisions-for-sha1-sha256-ripemd160-and-other-293382
And then, it is all about incentives: if enough coins will be there, on such address, then people will have a reason, to reveal such collision.
That's an interesting read.
So at the end of the day, we do not know if a collision ever happened or not. It is a bit of a rabulism here. And as long as the involved two parties wouldn't reveal it, we would not know.
For example. If coins from an old wallet which was dormant for years suddenly move - we don't know if someone is "the lucky winner" of a collision or if the old owner all the sudden moved the coins.
We can, of course, assume that it is the old owner. But we just don't know.
Well, it is possible to write a Script, which will do exactly that.
Input Script:
Output Script:
See also: https://bitcointalksearch.org/topic/reward-offered-for-hash-collisions-for-sha1-sha256-ripemd160-and-other-293382
And then, it is all about incentives: if enough coins will be there, on such address, then people will have a reason, to reveal such collision.
Input Script:
Output Script:
Code:
OP_2DUP OP_EQUAL OP_NOT OP_VERIFY //checking if public keys are different
OP_2DUP OP_HASH160 OP_SWAP OP_HASH160 OP_EQUALVERIFY //checking if their hashes are identical
OP_TOALTSTACK OP_CHECKSIGVERIFY OP_FROMALTSTACK OP_CHECKSIG //making sure that the signatures are correct, so public keys are valid
Which means, that you can just create a TapScript branch, with this challenge, and then you can spend coins by using your key, but also someone else will be able to do that, by providing that kind of collision.OP_2DUP OP_HASH160 OP_SWAP OP_HASH160 OP_EQUALVERIFY //checking if their hashes are identical
OP_TOALTSTACK OP_CHECKSIGVERIFY OP_FROMALTSTACK OP_CHECKSIG //making sure that the signatures are correct, so public keys are valid
See also: https://bitcointalksearch.org/topic/reward-offered-for-hash-collisions-for-sha1-sha256-ripemd160-and-other-293382
And then, it is all about incentives: if enough coins will be there, on such address, then people will have a reason, to reveal such collision.
Seems to me it should be pretty straightforward to catch this happening. Basically, if there's transaction activity on a wallet you just created - one that should have no history - something is wrong.
From my understanding of the question, RealMalatesta is not asking if the creator of the wallet can catch it. He wants to know if YOU (or me, or himself, etc) can catch the fact that it has happened to someone else.
It's easy to identify if you're the one that creates the collision and then you look for it in your own addresses.
It's also easy if someone else creates a collision with an address that you already own and then they spends from it, as long as you regularly check up on every address you've ever owned.
But for a third party, such as yourself, to identify that a collision happened between two other people requires that they both reveal their public keys.
Odds are astronomically low it's a legit collision in the key space. More likely explanations are a faulty rng when originally generating the key, or
This is a good point. There has absolutely been cases identified where more than one person ended up with the exact same private key. This can happen with a bug in software, or if someone tries to create a wallet from a predetermined seed rather than generating it randomly.
What isn't going to happen is two different private keys that result in a hash collision on the pubKeyHash (and therefore on the address).
<...> seems that there is no way in such a scenario to detect the collision, right?
Seems to me it should be pretty straightforward to catch this happening. Basically, if there's transaction activity on a wallet you just created - one that should have no history - something is wrong. Odds are astronomically low it's a legit collision in the key space. More likely explanations are a faulty rng when originally generating the key, or someone getting unauthorized access to it through nefarious means.
I'm not talking about the chance of a collision, I'm well aware of the more than slim likelihood.
And yet your questions seem to imply that you don't understand just how slim that likelihood is.
I'm talking about ways how a possible collision could be detected.
What collision? A collision isn't going to happen.
If I understand DannyHamilton correctly, there is almost no way to detect a collision
No way? I described a way. You mean no additional ways? That would depend on the specifics of the situation, but in most cases would be difficult to detect without the cooperation of at least one of the two parties involved.
Someone used a wallet and produced tons of addresses long time ago, and then sent the Bitcoin to a new wallet, deleting or losing the old wallet.dat
At another point in time, a company creates a wallet for cold storage and (again: I know that this is close to impossible, it is a pure theoretical scenario) and creates a couple of addresses which never go online. In theory, it would be possible that there occurs a collision.
At another point in time, a company creates a wallet for cold storage and (again: I know that this is close to impossible, it is a pure theoretical scenario) and creates a couple of addresses which never go online. In theory, it would be possible that there occurs a collision.
Depends on what you mean by "in theory" and "would be possible". It is in no way realistically possible. But to play along with your mental game:
Under this scenario, the company could (if they wanted to) check the blockchain to see if any of their addresses had a collision. However, companies generally don't bother doing this because it's a waste of time and effort that could be better used to protect against realistic threats. For the rest of us, there's no way to know until the company eventually spends those bitcoins (at which time they'll reveal their public keys) OR I suppose the company could supply to you (or publish to the public) their public keys if you could convince them to do so. In that case anyone with those public keys could check.
I'm not talking about the chance of a collision, I'm well aware of the more than slim likelihood. I'm talking about ways how a possible collision could be detected. If I understand DannyHamilton correctly, there is almost no way to detect a collision unless:
So a pure theoretical scenario:
Someone used a wallet and produced tons of addresses long time ago, and then sent the Bitcoin to a new wallet, deleting or losing the old wallet.dat
At another point in time, a company creates a wallet for cold storage and (again: I know that this is close to impossible, it is a pure theoretical scenario) and creates a couple of addresses which never go online. In theory, it would be possible that there occurs a collision.
Not a theory seems that there is no way in such a scenario to detect the collision, right?
Quote
...the only way we'd be able to know for certain would be if BOTH individuals each spent separate outputs that had the same pubKey hash, but provided two different public keys for their transaction
So a pure theoretical scenario:
Someone used a wallet and produced tons of addresses long time ago, and then sent the Bitcoin to a new wallet, deleting or losing the old wallet.dat
At another point in time, a company creates a wallet for cold storage and (again: I know that this is close to impossible, it is a pure theoretical scenario) and creates a couple of addresses which never go online. In theory, it would be possible that there occurs a collision.
Not a theory seems that there is no way in such a scenario to detect the collision, right?
The following is from the Bitcoin wiki:
Sorry but if you've included the next sentence in that same bitcoin-wiki article, your question would sound silly.Quote
Since Bitcoin addresses are basically random numbers, it is possible, although extremely unlikely, for two people to independently generate the same address. This is called a collision. If this happens, then both the original owner of the address and the colliding owner could spend money sent to that address. It would not be possible for the colliding person to spend the original owner's entire wallet (or vice versa).
Since it already provided a good representation of its chance:
Quote from: en.bitcoin.it
But because the space of possible addresses is so astronomically large it is more likely that the Earth is destroyed in the next 5 seconds, than that a collision occur in the next millenium.
And it's not even an overstatement when it comes with collision. 
It is proven, as mentioned above, that it is mathetically possible, but the chance is astronomically low.
Adding to that, what is even funnier is that using 12 words as a seed phrase and examining every possible wallet account, you will be able to generate every possible address. Great, isn't it? Starting from the same wallet, changing derivation paths, you will come across every possible address.
Adding to that, what is even funnier is that using 12 words as a seed phrase and examining every possible wallet account, you will be able to generate every possible address. Great, isn't it? Starting from the same wallet, changing derivation paths, you will come across every possible address.
Could it be possible that a collision already happened in the past, we just don't know it?
That depends on what you mean when you use the word "possible". There are many things in the universe that have a mathematical non-zero probability, but which have such a small probability of ever happening that no reasonable person would ever use the word "possible" to describe them.
Or, in other words: Is there any way to find out if a collision already happened in the past?
If it happened (it hasn't), then the only way we'd be able to know for certain would be if BOTH individuals each spent separate outputs that had the same pubKey hash, but provided two different public keys for their transaction. This would be a pretty straight-forward search for someone to write software to perform on the blockchain, but I'm not going to waste my time writing it.
If only one of the individuals spent the outputs, then there'd only be one public key, and no way for us to know.
@Peter Green has a good answer to this question which you can find here https://crypto.stackexchange.com/questions/33821/how-to-deal-with-collisions-in-bitcoin-addresses
The numbers may change slightly, but the probability is very small (1/2^37) and can be considered negligible, or you have a better chance of mining Bitcoin legally instead of stealing it through hash collisions.
The numbers may change slightly, but the probability is very small (1/2^37) and can be considered negligible, or you have a better chance of mining Bitcoin legally instead of stealing it through hash collisions.
The following is from the Bitcoin wiki:
Or, in other words: Is there any way to find out if a collision already happened in the past?
Quote
Since Bitcoin addresses are basically random numbers, it is possible, although extremely unlikely, for two people to independently generate the same address. This is called a collision. If this happens, then both the original owner of the address and the colliding owner could spend money sent to that address. It would not be possible for the colliding person to spend the original owner's entire wallet (or vice versa).
So the question is: Could it be possible that a collision already happened in the past, we just don't know it? And even the "victims" of a collision do not know?Or, in other words: Is there any way to find out if a collision already happened in the past?
Jump to: