Pages:
Author

Topic: "New address for each payment" is a logic bomb - page 4. (Read 9193 times)

legendary
Activity: 2142
Merit: 1010
Newbie
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.
legendary
Activity: 1372
Merit: 1002
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 also possible for me to win the lottery without even playing. But, do you think it will happen?
donator
Activity: 1218
Merit: 1079
Gerald Davis
My thoughts on this are that a collision will occur in about 10 years. The question that lies is will that collision be one of the biggest bitcoin wallets or a wallet with very little bitcoins.

You base this on what magic?

Do you understand how large even 2^80 is?

If a billion people produces a thousand addresses per second for the next 1000 years the odds of a collision are 1 in 260,000.

Of course even that understates the chance because regardless of how many new addresses are used only a finite number of addresses can be funded.  The absolute max number of funded addresses is 2.1 quadrillion and that would be all addresses contain a single satoshi each.  The actual number of addresses is likely to be much much much lower but that provides an absolute upper bound.




donator
Activity: 1218
Merit: 1079
Gerald Davis
I have to say my response to the subject line is "No it isn't."

The person putting the affirmative statement on the table has the obligation actually to prove it.  My guess is you can't.

Math related to birthday paradox was provided in the OP. The rest is just a plain common sense. U guessed right coz it's very hard to prove obvious things.

Birthday paradox my ass.  I had already noted and ignored that.  It will probably be a meaningless dust transaction if you've looked at the blockchain lately. Even if it does happen.

It is far more likely (as in thousands of quadrillions to one) that any match would be unused addresses.   The used active addresses space is ~11M addresses.  2^80 is 109,902,347,237,693,561x larger.

So after an utterly asinine amount of time, energy, and cost if/when a pair of pubkeys which produce the samepubkeyhash were found it is 99.99999999999999999% likely the two pubkeys would be ones created by the attacker and be empty.
legendary
Activity: 1176
Merit: 1005
I have to say my response to the subject line is "No it isn't."

The person putting the affirmative statement on the table has the obligation actually to prove it.  My guess is you can't.

Math related to birthday paradox was provided in the OP. The rest is just a plain common sense. U guessed right coz it's very hard to prove obvious things.

Birthday paradox my ass.  I had already noted and ignored that.  It will probably be a meaningless dust transaction if you've looked at the blockchain lately. Even if it does happen.
donator
Activity: 1218
Merit: 1079
Gerald Davis
The original discussion was about being able to find 2 keypairs which form the same bitcoin address in 2^80 attempts on average.  Assuming someone has the resources to do this, what is the advantage for them?  I can't think of anything they could do to take advantage of this?

Also to perform the attack, I'm thinking you'd need to store at least 52 bytes per address (32-byte private key and 20-byte pubkey hash).  This is 52 Yottabytes of data!

Nothing.  The OP claim is they could do this at massive expense to spend coins from an address using two different pubkeys and that would be a negative PR for Bitcoin.

I am doubtful how much of an effect it would have and if anything people would be a repeat (or thousands of repeats) which wouldn't occur and it would be chalked up to incredibly bad luck.  Still anyone with the resources to do this could 51% the network which is an "easier", cheaper and far more direct attack.

He can't spend coins from them, all he could find are two hash-collision pubkeys.

Well that is the point the "attacker" (and yes this would be most expensive and stupidest possible attack on Bitcoin) could find a pair of pubkeys which hash to the same pubkeyhash, then send coins to that address, and then spend those coins with both pubkeys. 

Generally speaking this is something that shouldn't be possible and it may be a small loss of confidence as it would be publicly visible to anyone on the blockchain.  It would be good for a FUD campaign "see Bitcoin is broken" and that is the OP contention.   However the MASSSIVE expenditure required to perform this "attack" combined with the limited effect makes it dubious.   A single instance would quickly be dismissed as incredibly unlikely random chance.  To replicate the attack and make it appear that Bitcoin was compromised would require finding hundreds or thousands of pairs of pubkeys which share a pubkeyhash so the entire attack cost would have to be increased by a factor of 100x or 1000x.  At this point you are taking more computing power and energy than what is required to 99.9% attack the Bitcoin network.

So no there is no utility in this "attack" but it is technically incorrect to say coins couldn't be spent.  They would be the attackers own coins but they could be spent by either (or more like both) pubkeys which hash to the same pubkeyhash.
newbie
Activity: 46
Merit: 0
My thoughts on this are that a collision will occur in about 10 years. The question that lies is will that collision be one of the biggest bitcoin wallets or a wallet with very little bitcoins.
hero member
Activity: 784
Merit: 1000
The original discussion was about being able to find 2 keypairs which form the same bitcoin address in 2^80 attempts on average.  Assuming someone has the resources to do this, what is the advantage for them?  I can't think of anything they could do to take advantage of this?

Also to perform the attack, I'm thinking you'd need to store at least 52 bytes per address (32-byte private key and 20-byte pubkey hash).  This is 52 Yottabytes of data!

Nothing.  The OP claim is they could do this at massive expense to spend coins from an address using two different pubkeys and that would be a negative PR for Bitcoin.

I am doubtful how much of an effect it would have and if anything people would be a repeat (or thousands of repeats) which wouldn't occur and it would be chalked up to incredibly bad luck.  Still anyone with the resources to do this could 51% the network which is an "easier", cheaper and far more direct attack.

He can't spend coins from them, all he could find are two hash-collision pubkeys.
donator
Activity: 1218
Merit: 1079
Gerald Davis
The original discussion was about being able to find 2 keypairs which form the same bitcoin address in 2^80 attempts on average.  Assuming someone has the resources to do this, what is the advantage for them?  I can't think of anything they could do to take advantage of this?

Also to perform the attack, I'm thinking you'd need to store at least 52 bytes per address (32-byte private key and 20-byte pubkey hash).  This is 52 Yottabytes of data!

Nothing.  The OP claim is they could do this at massive expense to spend coins from an address using two different pubkeys and that would be a negative PR for Bitcoin.

I am doubtful how much of an effect it would have and if anything people would be a repeat (or thousands of repeats) which wouldn't occur and it would be chalked up to incredibly bad luck.  Still anyone with the resources to do this could 51% the network which is an "easier", cheaper and far more direct attack.
member
Activity: 118
Merit: 10
The original discussion was about being able to find 2 keypairs which form the same bitcoin address in 2^80 attempts on average.  Assuming someone has the resources to do this, what is the advantage for them?  I can't think of anything they could do to take advantage of this?

Also to perform the attack, I'm thinking you'd need to store at least 52 bytes per address (32-byte private key and 20-byte pubkey hash).  This is 52 Yottabytes of data!
legendary
Activity: 1596
Merit: 1012
Democracy is vulnerable to a 51% attack.
R u sure? I was thinking that 160-bit hash provides 80-bit security.
You're not worried about someone compromising their own key or someone else's key. You're worried about someone compromising *your* key.
donator
Activity: 1218
Merit: 1079
Gerald Davis
Probably because I don't have a clue, and am just on the verge of trying to understand? Grin

Nothing wrong with learning.   Asymtric encryption never has a strength equal to its key size.  The public and private keys are related mathematically and the mathematical properties which make asymmetric encryption possible also allow more intelligent attacks then simply trying private keys until you find a collision.  ECDSA is actually pretty efficient where key strength of 2^(n/2) is possible for key length of 2^n.  Other methods like RSA require much larger key sizes for the same key strength, 128 bit security using RSA for example requires 2048 bit keys.

A 256 bit ECDSA key despite having 256 bits only provides 128 bits of security.  In other words to send the coins for a known address/pubkey and unknown private key requires either:
a) find another private key which produces the same PubKey.   On average this will require 2^128 attempts.
OR
b) find another PubKey which produces the same PubKeyHash.  On average this will require 2^160 attempts.

If the PubKey is unknown then only B is possible and security improves to 160 bit security.  This is why is is recommended you not reuse addresses.  It provides a secondary line of defense in the event method "a" ever becomes viable.

Security of a system comes from the weakest link and for Bitcoin that means 128 bit security.  Making the other links stronger won't improve security.  
legendary
Activity: 2142
Merit: 1010
Newbie
I have to say my response to the subject line is "No it isn't."

The person putting the affirmative statement on the table has the obligation actually to prove it.  My guess is you can't.

Math related to birthday paradox was provided in the OP. The rest is just a plain common sense. U guessed right coz it's very hard to prove obvious things.
legendary
Activity: 1176
Merit: 1005
I have to say my response to the subject line is "No it isn't."

The person putting the affirmative statement on the table has the obligation actually to prove it.  My guess is you can't.
donator
Activity: 1218
Merit: 1079
Gerald Davis
160 bit pubkey hash provides 160 bit security.

R u sure? I was thinking that 160-bit hash provides 80-bit security.

Only against a collision between two random (and essentially 100% chance unused) keys.  Against an preimage attack the security of any unbroken hash of length n is always 2^n.

https://en.wikipedia.org/wiki/Preimage_attack
sr. member
Activity: 336
Merit: 250
Cuddling, censored, unicorn-shaped troll.
I agree that public address should be a 256bit hash, too.
Why?
256 bit ECDSA only provides 128 bit security
160 bit pubkey hash provides 160 bit security.
What would making the pubkeyhash larger accomplish other than bloating the blockchain?
Probably because I don't have a clue, and am just on the verge of trying to understand? Grin
I don't see why a 256bit private key being transformed into a 160bit hash would not lose entropy, but I'll lurk more and quit bothering you with my newbie statements!
sr. member
Activity: 251
Merit: 250
U can generate addresses much faster coz u don't need to know the private key. Pick any set of bytes and say it's a public key. 2^80 is not a big number.

Edit:
2^80 == (2^10)^8 ~ 1000^8 == 10^24.
And now look at the hash rate of Bitcoin network.

Of course, when a normal miner checks a hash, it starts by checking the top 32 bits are zero, which is a trivial operation. Checking for a collision with a growing database of up to 2^80 previous hashes is a lot more effort.
legendary
Activity: 2142
Merit: 1010
Newbie
160 bit pubkey hash provides 160 bit security.

R u sure? I was thinking that 160-bit hash provides 80-bit security.
donator
Activity: 1218
Merit: 1079
Gerald Davis
I agree that public address should be a 256bit hash, too.

Why?

256 bit ECDSA only provides 128 bit security

160 bit pubkey hash provides 160 bit security.

What would making the pubkeyhash larger accomplish other than bloating the blockchain?
sr. member
Activity: 336
Merit: 250
Cuddling, censored, unicorn-shaped troll.
Did BLAKE2 exist when Satoshi was coding Bitcoin? Also RIPEMD-160 wasn't "sponsored" by the US govt, was it?

Maybe not, but the base58 RIPEMD-160 hash was mainly used to reduce public address size, as far as I'm aware, which looks like a bad choice to me.
From what I read, progressively replacing the RIPE hash with a stronger non-sponsored one while maintaining backward compatibility would not be impossible.
So why not change now ?
Pages:
Jump to: