"New address for each payment" is a logic bomb

[dree12]

A lot of talk about the birthday paradox here.

From my understanding, the birthday paradox is theoretical in nature. An attacker can claim, and mathematically prove, to have an arbitrarily high probability of having generated a collision, but cannot show the colliding public keys.

This is due to the outrageous memory requirement. Storing 2⁸⁰ public keys in memory is impossible, as it would require ~39 yottabytes of memory. In comparison, the NSA is predicted to have less than 5 zettabytes (0.005 yottabytes) of storage capacity, despite having what is likely the largest cold storage complex in the world. Even assuming hard disk size doubling every year, it would take 13 years for someone to amass that kind of capacity.

As has been predicted, generating 2⁸⁰ addresses is likely to be feasible in the next decade; however, proving with 100% certainty that a collision has occurred is not.

[DeathAndTaxes]

Do you understand how large even 2^80 is?

Bitcoin network hashrate is 5*10^15 ~ 2^52. So in 2^28 seconds (8 years) we'll reach this number. Doesn't look too large. And this is without the Moore's law.

Even if we assume that the hardware COULD be used for this purpose basically you are saying:

Someone could spend 800%* of the cost to 51% the Bitcoin network to potentially produce an unused pair of pubkeys which hash to the same pubkeyhash rather than:
a) collect ~50% of annual Bitcoin mining revenue.
b) attack the network with a sustained 51% attack.

Yeah I think we are safe.  So once again do you realize how large 2^80th is.  Do you realize the asinine cost it would require to produce a collision?  Do you realize the far easier attacks that can be done with that amount of cost, and energy?  Do you realize the utter stupidity of using this as an attack?

* In reality it is probably closer to 8,000% as generating PubKeys is far more computationally expensive than generating SHA-2 hashes.

[Come-from-Beyond]

From my understanding, the birthday paradox is theoretical in nature. An attacker can claim, and mathematically prove, to have an arbitrarily high probability of having generated a collision, but cannot show the colliding public keys.

This is due to the outrageous memory requirement. Storing 2⁸⁰ public keys in memory is impossible, as it would require ~39 yottabytes of memory.

That's valid point.

[DeathAndTaxes]

An attacker can claim, and mathematically prove, to have an arbitrarily high probability of having generated a collision, but cannot show the colliding public keys.

The attack is successful it is very easy to prove.  Find a PubKey A & B such that RIPEMD-160(SHA2(SHA2(PubKeyA)) == RIPEMD-160(SHA2(SHA2(PubKeyB)).  Publish A & B or simply send coins to the address they share and spend from that address using both PubKeys.  Showing a collision is very black and white so I think maybe you mean something else?

This is due to the outrageous memory requirement. Storing 2⁸⁰ public keys in memory is impossible, as it would require ~39 yottabytes of memory. In comparison, the NSA is predicted to have less than 5 zettabytes (0.005 yottabytes) of storage capacity, despite having what is likely the largest cold storage complex in the world. Even assuming hard disk size doubling every year, it would take 13 years for someone to amass that kind of capacity.

There is also the benefit vs cost.  Even if/when storing that amount of data is possible we are talking about a cost which is magnitudes higher than simply 51% attacking the network.  So this "attack" has magnitudes higher cost for magnitudes less impact.  It will never happen.  Even if someone had that kind of resources and wanted to destroy Bitcoins there are simply easier simpler ways to do so.

As has been predicted, generating 2⁸⁰ addresses is likely to be feasible in the next decade; however, proving with 100% certainty that a collision has occurred is not.

Maybe you mean "will occur" because after a collision has occurred it is trivial to prove that it has occurred?

[Come-from-Beyond]

So once again do you realize how large 2^80th is.

I don't, each day I work with 256-bit numbers, 2^80 looks so small.

dree12 convinced me that we r safe coz it's hard to store 2^80 numbers.

[DeathAndTaxes]

So once again do you realize how large 2^80th is.

I don't, each day I work with 256-bit numbers, 2^80 looks so small.

dree12 convinced me that we r safe coz it's hard to store 2^80 numbers.

Even if it is trivial to store 2^80 the cost for this "attack" would be magnitudes more than a 51% attack and would do magnitudes less.  We can only hope in the future attackers are willing to skip the obvious cheaper attack and waste magnitudes more resources on a trivial pointless "attack".

A single collision isn't going to even cause a blip in the long term utility of Bitcoin.  It would take thousands of such collisions to make people question if the address system is flawed.  Even a single collision would cost far more than simply 51% attacking the network and refusing all transactions.  Hundreds or thousands of collisions would be a cost on an order not seen.

[DeathAndTaxes]

When 2^80 addresses are created u will find at least 1 identical pair with probability very close to 100%. I'm not talking about finding a collision to one particular address.

And assuming 11M active funded addresses there is a 99.99999999999999999% (should be 18 9s ) chance the address is unfunded.

Of course for it to be any use one would need to store both the private keys AND public key and generate the public key from a private key using ECDSA operations so we are talking a rather slow operation and roughly double the storage requirements of storing just pubkeys. 

[Wardan_reloadeD]

Look at this: https://bitcointalk.org/index.php?topic=316773.msg3397505#msg3397505

DeathAndTaxes, you already read it  

[darkmule]

First off, the birthday "paradox" isn't even a paradox.  It's just a common way human minds fail to understand an address space.  In this case, birthdays are less than 9 bits of data.  So collisions will be very common.

Does anyone even use this shit except as a bar bet to con a sucker?  As in "I bet two people in here have the same birthday!"

The address space of Bitcoin makes the collision possibility a pure speculation.  The sucker would be the one betting on a meaningful collision here.

[Come-from-Beyond]

Does anyone even use this shit except as a bar bet to con a sucker?  As in "I bet two people in here have the same birthday!"

Yes, it's used in cryptography. For key agreement, for example.

[devthedev]

I guess I should stop doing Vanity Generation 

[Come-from-Beyond]

I guess I should stop doing Vanity Generation 

[mateo]

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.

[phzi]

A single collision wouldn't be very relevant... discovering a way to calculate collisions would be, but discovering 1 collision is extremely unlikely to even assist in that.  And the OP topic makes no sense... there are many reasons it's more secure to use a new address for each transaction, but there is basically no reason to fear more addresses.  The "logic" this thread talks about is not even slightly logical or mathematically sound.

[Come-from-Beyond]

there are many reasons it's more secure to use a new address for each transaction, but there is basically no reason to fear more addresses.

Care to tell at least one reason for new address for each transaction?

[justusranvier]

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.

[oakpacific]

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.

[DeathAndTaxes]

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.

[oakpacific]

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.

[DeathAndTaxes]

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.