Pages:
Author

Topic: "New address for each payment" is a logic bomb (Read 9169 times)

legendary
Activity: 1176
Merit: 1005
November 17, 2013, 11:37:56 AM
#96
I think the math works out that there's more Bitcoin addresses than there are atoms in the universe.  Basically, it's been talked about many times, and it's nothing to worry about.

True, BUT there is still the possibility of a collision!

That is true for almost all systems.
Air traffic control, PC hardware numbers etc.. As long as the probability is astronomically low it's not a problem.

Actually, when the utility of the system is high, we tolerate fairly high possibilities of collisions.  Air traffic control, for instance.  Mid air collisions can and have occurred in the civilian and military contexts.  It is a problem, but not enough of one to abandon the system.

It would probably make sense, if given a choice between two otherwise equally useful systems, to choose one with no chance whatsoever of a collision.  Not sure we have such a choice, though.
legendary
Activity: 2142
Merit: 1010
Newbie
For those who haven't figured it out yet, Come-from-Beyond is a troll. Everything he says is the opposite of what is good for Bitcoin.

For those who haven't figured it out yet, justusranvier is a fat bald guy who loves to pretend he is a pretty girl when visiting dating services. Care to prove me wrong?

(Heh, I suppose u got the point Cheesy)
legendary
Activity: 1400
Merit: 1013
I think the math works out that there's more Bitcoin addresses than there are atoms in the universe.  Basically, it's been talked about many times, and it's nothing to worry about.

True, BUT there is still the possibility of a collision!
http://www.youtube.com/watch?v=zMRrNY0pxfM
full member
Activity: 182
Merit: 100
I think the math works out that there's more Bitcoin addresses than there are atoms in the universe.  Basically, it's been talked about many times, and it's nothing to worry about.

True, BUT there is still the possibility of a collision!
It's possible for me to win the lotto, it won't happen though
hero member
Activity: 784
Merit: 1000
And if they don't how do they know that the pubkey I am sending them, is the same one as the one I used before, for the same address?
It would be a mistake for them to check. Nobody claims the pubkey is supposed to have any characteristic other than to have a particular hash.

Then suppose my private key is only 160 bits, I can indeed theoretically reuse the same address with a different private key after 2^80 tries.
legendary
Activity: 1596
Merit: 1012
Democracy is vulnerable to a 51% attack.
And if they don't how do they know that the pubkey I am sending them, is the same one as the one I used before, for the same address?
It would be a mistake for them to check. Nobody claims the pubkey is supposed to have any characteristic other than to have a particular hash.
hero member
Activity: 784
Merit: 1000
I wonder how miners do that? If they check all the used pubkeys before they check the hash, that's going to be pretty inefficient, no?

Huh  No idea what you are talking about now?  I am going to give up for the night.

Do the miners check if a pubkey that hashes to a particular address, is also being used sometime in the past, by searching through the whole blockchain?

And if they don't how do they know that the pubkey I am sending them, is the same one as the one I used before, for the same address?
donator
Activity: 1218
Merit: 1079
Gerald Davis
I wonder how miners do that? If they check all the used pubkeys before they check the hash, that's going to be pretty inefficient, no?

Huh  No idea what you are talking about now?  I am going to give up for the night.
hero member
Activity: 784
Merit: 1000
It's a solution because miners are supposed to record hashes for any unspent address that is reused, so they will already know the hashes of the pubkey, and that's why I say not completely spent.

Once again, there is NO SUCH THING AS "not completely spent".  Outputs are spent or unspent.  It is binary, they can't be partially spent.  Until spent the PubKey of an output is UNKNOWN to miners.  The PubKey once spent is ALREADY recorded in the blockchain but there is nothing to protect at this point.  The output has been spent.  It is a non-solution, for a non-problem.



So you are telling me that, if I want to reuse the same address for a second time, miners will only check if my pubkey is the same as the one that is already recorded on the blockchain for this address, right?



You shouldn't be reusing addresses.  So a solution which only protects the most insecure method of doing things only only if the attack happens to occur after the first tx occurs?

If you want that as a "solution" why not just pay to the PubKey?  Nothing to record just eliminate the issue by not having the hash to begin with.  The hash only provides security when the PubKey is unknown.  Your "solution" would be to insecurely make the PubKey known through address reuse to prevent the issue of a the hash being "cracked"?  Why not just not use the hash and pay directly to the PubKey?

I wonder how miners do that? If they check all the used pubkeys before they check the hash, that's going to be pretty inefficient, no?

And if they don't then I can try a different pubkey to reuse the same address.
donator
Activity: 1218
Merit: 1079
Gerald Davis
It's a solution because miners are supposed to record hashes for any unspent address that is reused, so they will already know the hashes of the pubkey, and that's why I say not completely spent.

Once again, there is NO SUCH THING AS "not completely spent".  Outputs are spent or unspent.  It is binary, they can't be partially spent.  Until spent the PubKey of an output is UNKNOWN to miners.  The PubKey once spent is ALREADY recorded in the blockchain but there is nothing to protect at this point.  The output has been spent.  It is a non-solution, for a non-problem.



So you are telling me that, if I want to reuse the same address for a second time, miners will only check if my pubkey is the same as the one that is already recorded on the blockchain for this address, right?



You shouldn't be reusing addresses.  So a solution which only protects the most insecure method of doing things only only if the attack happens to occur after the first tx occurs?

If you want that as a "solution" why not just pay to the PubKey?  Nothing to record just eliminate the issue by not having the hash to begin with.  The hash only provides security when the PubKey is unknown.  Your "solution" would be to insecurely make the PubKey known through address reuse to prevent the issue of a the hash being "cracked"?  Why not just not use the hash and pay directly to the PubKey?

Still at this point I don't care.  It is a solution to a problem which doesn't exist where the solution is worse than the non-existent problem to begin with.   Go ahead, make a pull of the source code and try to get it implemented.
hero member
Activity: 784
Merit: 1000
It's a solution because miners are supposed to record hashes for any unspent address that is reused, so they will already know the hashes of the pubkey, and that's why I say not completely spent.

Once again, there is NO SUCH THING AS "not completely spent".  Outputs are spent or unspent.  It is binary, they can't be partially spent.  Until spent the PubKey of an output is UNKNOWN to miners.  The PubKey once spent is ALREADY recorded in the blockchain but there is nothing to protect at this point.  The output has been spent.  It is a non-solution, for a non-problem.



So you are telling me that, if I want to reuse the same address for a second time, miners will only check if my pubkey is the same as the one that is already recorded on the blockchain for this address, right? Then they must check all the used pubkeys before they decide if they should check the hash, no?

donator
Activity: 1218
Merit: 1079
Gerald Davis
It's a solution because miners are supposed to record hashes for any unspent address that is reused, so they will already know the hashes of the pubkey, and that's why I say not completely spent.

Once again, there is NO SUCH THING AS "not completely spent".  Outputs are spent or unspent.  It is binary, they can't be partially spent.  Until spent the PubKey of an output is UNKNOWN to miners.  The PubKey once spent is ALREADY recorded in the blockchain but there is nothing to protect at this point.  The output has been spent.  It is a non-solution, for a non-problem.

hero member
Activity: 784
Merit: 1000
No.  The Public Key is unknown for the vast majority of active addresses.

What is the PubKey or SHA-256 hash of the PubKey for this coinbas reward in this block:
https://blockchain.info/block/000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

Hint: only the owner knows.  If this output is spent in the future you would have no method of knowing if it was the "real" owner's spend or a pubkey collision.  

Bitcoin INTENTIONALLY makes the PubKey UNKNOWN until an output is spent.  Once it is spent there is nothing to "protect".   Addresses shouldn't be reused.

So it is not a solution, even for this non-problem.

The supposed problem is someone creating two random private keys that spend the same address, because I am the creator of both, I know both, I think I understand what you want to say, but you don't understand me.

That isn't the (non) issue proposed.  The issue the OP proposed is a hash collision.

Two PubKeys A & B such that the hash of A & B are the same.

Bitcoin standard tx are payments to the PubKeyHash.  So if A & B have the same hash then the private key for A or B can be used to spend outputs sent to that PubKeyHash.


A MINER DOES NOT KNOW THE PUBKEYS AT THE TIME AN OUTPUT IS CREATED.  Payments are only to the PubKeyHash.


The scenario created by the OP is a complete non-issue, however your solution isn't a solution either.  How can miners record the pubkey or first round hash for a value they don't know.  They won't know the PubKey (as opposed to the PubKeyHash) UNTIL the output has already been spent.   It solves nothing.  Once spent the PubKey IS recorded.  It is part of the input in the tx and is part of the blockchain.  Making another recording of it does nothing, it has already been spent.

You don't understand the issue at hand I suppose. OP's scheme will only work(i.e., creating a hash collision) by finding two private keys.

A birthday attack allows you to find two output values f(x1)=f(x2) for some random pairs of inputs of x1 and x2, it doesn't care what you function f is, whether it is some hash(x) or hash(ecc(x)) or hash(wtf(x)), as long as it's single input and single output it will work, so it's all the same 2^(n/2) attempts whether you try to find two privkeys with colliding hashes from their pubkeys, or just two pubkeys with colliding hashes.

However, in our particular case the simplest hash(x) scheme will not work because it requires an infeasible number of equality check and storage space, because the input pubkey length is twice as large as the output length so only the naive method applied, yet for Bitcoin the private key is 256 bits, the same length as the output, cycle detection  http://en.wikipedia.org/wiki/Cycle_detection can be applied to reduce the storage space to constant.

It's a solution because miners are supposed to record hashes for any unspent address that is reused, so they will already know the hashes of the pubkey if a second pubkey tries to spend the same address, and that's why I say not completely spent.
donator
Activity: 1218
Merit: 1079
Gerald Davis
And for RIPEMD-160, with just 2^80 steps he can find such two private keys.

You are now just combining words which don't make any sense when used together.  Hashes don't have private keys.
No the issue is a hash collision.   With 2^80 attempts one can find TWO PubKeys which hash to the same PubKeyHash.
donator
Activity: 1218
Merit: 1079
Gerald Davis
No.  The Public Key is unknown for the vast majority of active addresses.

What is the PubKey or SHA-256 hash of the PubKey for this coinbas reward in this block:
https://blockchain.info/block/000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

Hint: only the owner knows.  If this output is spent in the future you would have no method of knowing if it was the "real" owner's spend or a pubkey collision.   

Bitcoin INTENTIONALLY makes the PubKey UNKNOWN until an output is spent.  Once it is spent there is nothing to "protect".   Addresses shouldn't be reused.

So it is not a solution, even for this non-problem.

The supposed problem is someone creating two random private keys that spend the same address, because I am the creator of both, I know both, I think I understand what you want to say, but you don't understand me.

That isn't the (non) issue proposed.  The issue the OP proposed is a hash collision.

Two PubKeys A & B such that the hash of A & B are the same.

Bitcoin standard tx are payments to the PubKeyHash.  So if A & B have the same hash then the private key for A or B can be used to spend outputs sent to that PubKeyHash.


A MINER DOES NOT KNOW THE PUBKEYS AT THE TIME AN OUTPUT IS CREATED.  Payments are only to the PubKeyHash.


The scenario created by the OP is a complete non-issue, however your solution isn't a solution either.  How can miners record the pubkey or first round hash for a value they don't know.  They won't know the PubKey (as opposed to the PubKeyHash) UNTIL the output has already been spent.   It solves nothing.  Once spent the PubKey IS recorded.  It is part of the input in the tx and is part of the blockchain.  Making another recording of it does nothing, it has already been spent.
hero member
Activity: 784
Merit: 1000
No.  The Public Key is unknown for the vast majority of active addresses.

What is the PubKey or SHA-256 hash of the PubKey for this coinbas reward in this block:
https://blockchain.info/block/000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

Hint: only the owner knows.  If this output is spent in the future you would have no method of knowing if it was the "real" owner's spend or a pubkey collision.  

Bitcoin INTENTIONALLY makes the PubKey UNKNOWN until an output is spent.  Once it is spent there is nothing to "protect".   Addresses shouldn't be reused.

So it is not a solution, even for this non-problem.

The supposed problem is someone creating two random private keys that spend the same address, because he is the creator of both so he knows both, not someone trying to spend other's address.

And for RIPEMD-160, with just 2^80 steps he can find such two private keys.
donator
Activity: 1218
Merit: 1079
Gerald Davis
No.  The Public Key is unknown for funded addresses that have not been spent yet.

What is the PubKey or SHA-256 hash of the PubKey for the coinbase reward in this block?
https://blockchain.info/block/000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

Hint: only the owner knows.  If this output is spent in the future you would have no method of knowing if it was the "original" owners pubkey or a collision pubkey.

Bitcoin INTENTIONALLY makes the PubKey UNKNOWN until an output is spent.  Once it is spent there is nothing to "protect".   Addresses shouldn't be reused.

So it is not a solution, even for this non-problem.
hero member
Activity: 784
Merit: 1000
A practical and perhaps trivial fix is for miners to record both SHA-256 and RIPEMD-160 hashed addresses for the pubkey of each address that is not completely spent, and reject any further pubkey that hashes to one but not another, while normal users will only need to remember RIPEMD-160 addresses.

There is no such thing as "not completely spent".  Outputs are either spent or unspent.   Miners won't know the PubKey until an output is spent.  The standard tx for Bitcoin is "pay to PubKeyHash".   In the output of a tx only the receiving pubkeyhash is known, not the pubkey.  Still it is not a credible attack, no fix is needed.  Miners shouldn't do anything that encourages address reuse.

I am not sure what you are trying to state other than a terminology problem, I would not have written the quoted post without knowing what you wrote here, do you think the "fix" I proposed will work(by checking two different hashes to make sure there will not be a RIPEMD-160 collision through birthday attack, so that no two privkeys can spend the same address) for the supposed problem or not? I have other reasons for such a fix but I want to wait for your clarification first.
donator
Activity: 1218
Merit: 1079
Gerald Davis
A practical and perhaps trivial fix is for miners to record both SHA-256 and RIPEMD-160 hashed addresses for the pubkey of each address that is not completely spent, and reject any further pubkey that hashes to one but not another, while normal users will only need to remember RIPEMD-160 addresses.

There is no such thing as "not completely spent".  Outputs are either spent or unspent.   Miners won't know the PubKey until an output is spent.  The standard tx for Bitcoin is "pay to PubKeyHash".   In the output of a tx only the receiving pubkeyhash is known, not the pubkey.  Still it is not a credible attack, no fix is needed.  Miners shouldn't do anything that encourages address reuse.
hero member
Activity: 784
Merit: 1000
A practical and perhaps trivial fix is for miners to record both SHA-256 and RIPEMD-160 hashed addresses for the pubkey of each address that is not completely spent, and reject any further pubkey that hashes to one but not another, while normal users will only need to remember RIPEMD-160 addresses.
Pages:
Jump to: