Bitcoin Forum

As u know, each time u make a payment Satoshi's client generates a new address to send change to. He (or someone else) also advised to create a new address each time someone needs to receive a payment (for anonymity reason). Entropy of an address is 160 bits (due to RIPEMD-160 "compression"). Applying (http://burtleburtle.net/bob/hash/birthday.html#birthday) Birthday Paradox we get that when 2^80 addresses are created we will, likely, get a collision. This is not critical, coz "older" address will be empty, probably. But this can be used in black PR against Bitcoin. An adversary (who is generating addresses non-stop) will be able to show 2 different public keys with the same address. Media will be happy to publish articles with "Bitcoin completely broken" title...

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.

U r talking about a case when u need to create a collision for one special address. Read http://en.wikipedia.org/wiki/Birthday_problem plz.

But still, even if someone is generating billions of addresses a second for millions of years, the statistical odds are extremely low they would find a collision even under those circumstances.  I'm not a math whiz or I'd show you the proof, but I know the calculations have been done many times before, and always check out.

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

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.

If you don't know the private key, then there's no attack. But even so ..

Okay, it's 7 years with the full hashing power of all Bitcoin mining. And all such an attacker would have is an account that he himself had compromised. He'd be a long way from compromising anyone else's account.

It's a PR attack. An attacker can even invest freshly printed millions dollars.

You can launch a 51% attack just by expending more effort than all miners expend. Worrying about a PR attack that requires you to expend hundreds of times that effort is senseless.

Maybe. As time passes probability of 51% attack goes to zero, while probability of collision attack goes to 100%.

We all know that Bitcoin will have to evolve or face technical obsolescence. We have no way to know *today* what changes will be correct in the future though. Bitcoin still uses a near optimum set of tradeoffs for today's technology because those decisions were made just a few years ago.

Bring this up again in about eight years.

They wouldn't be the first completely moronic, uninformed media attention Bitcoin has survived. 

I'm not sure we should make technical decisions based on the moronic, uninformed opinions of, well, morons.  Seems the current system is inevitably going to lead to some measurable problems, while the alternative leads to a nearly unmeasurable chance of a problem.  Also, if that completely breaks Bitcoin, then the mere existence of brain wallets using bad passphrases is much more of a worry.

I agree that public address should be a 256bit hash, too.
Why do we care about the size of the public base58 address, anyways?

It's either copied/pasted or QR-code-scanned, I'm pretty sure nobody ever typed-in an address char by char using a keyboard.
So why take the risk of restraining the 256 bit key pairs to fit in a collision-more-likely 160 bit public address?

For security reason. If NSA knows how to reverse SHA-256, it may not know how to do the same with RIPEMD-160.

I can understand and agree with that, but there are other hash functions, it seems...
I'm not an expert at all, but after a quick search BLAKE2s came up, for example?

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 ?

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?

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

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.

Probably because I don't have a clue, and am just on the verge of trying to understand? ;D
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!

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

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.

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.  

You're not worried about someone compromising their own key or someone else's key. You're worried about someone compromising *your* key.

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.

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.

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.

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.

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.

It's also possible for me to win the lottery without even playing. But, do you think it will happen?

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.

It's also without consideration that mining hardware cannot be used for finding duplicates.

So, you made your point, maybe somewhere sometime someone will get an account that belongs to someone else, probably getting 0.01 BTC free
All right.

No system is perfect. Abstractions do leak. Everyday people make mistakes and loose bitcoin accounts, or send money to the wrong account or have their computer hacked and get robbed from their btc accounts.

So What ?  1 error over tens of millions transactions should make the complete system unusable ? nope. It's a fairly good reliability. Far more reliable than any other banks.

That was an assessment.

U could read the OP at least before replying...

Not worth answering.

The latest numbers show around 10^80 atoms so there are "a bit" more atoms.

I think it's also possible that a black hole will suddenly erupt above the New York Stock Exchange and suck in everything there, then suddenly disappear back to whence it emerged.

It COULD happen.  Prove it couldn't. 

So we should probably get rid of stock exchanges.  Especially the Nikkei.  It's just as likely to suffer such an event.

Heh, why do ppl post in this thread if they have no clue what birthday paradox is...

Because:
1) people are lazy to check wtf is the birthday paradox
2) math is not quite as easy as watching baseball
3) your thread assumes a vulnerability of the bitcoin protocol , so i'm not sure why haven't you already been burned as an "infidel" already :D

So true

I understand that the eventual collision of two keys will be blown way out of proportion and used as an attack by the media and conflicting interests. However what can we do? The current advice to not reuse keys is very sound and the benefits outweigh the risk by far.

What could a solution be? So that the media never gets this opportunity... CFB, if the key space is now 2^161 how much does this offset the probabilities in the birthday paradox? What keyspace would make any collision unlikely given every human producing a trillion addresses every nano second for thousands of years? 2^1000000?

As I see your claim, that a collision is going happen sooner than the conventional thought allows, the solution would be to make the key space so much larger that any collision is unlikely forever.

Keep reusing addresses. Sending change to a new address doesn't increase anonymity.

The way I imagine change addresses working, I always thought that they are increasing anonymity somewhat. Why do you disagree?

If money never returns to base, so to speak, it always looks like it is moving forward somewhere and working out what forward is the merchant and what forward is you can become difficult.

If that was as u said then we wouldn't need http://zerocoin.org/

Oh true, we certainly need zerocoin or coinjoin very soon. I would imagine if either one of those systems became commonplace and in the reference client you could make a very good argument that the creation of a new address for every transaction is not required for anonymity.

However once an address spends coins it reveals something? I forget what that something is. I remember reading an address that has not spent coins is somewhat safer. Is this something that could be overcome too?

That is a public key.

Does that revealed information make the address less secure?

I think what you are referring to is the fact that when you spend coins, you have to sign the tx with your private key, thus giving a "hint" about it.

Ah ok that makes sense, so is that a theoretical/academic risk or a real practical risk?

If someone owns a quantum computer he will be able to recover the private key almost as fast as u sign a message with it. So until the public key is unknown the private key can't be picked.

It has been a real risk not long ago, on android, because its rng was broken.
From what I understood, as soon as you had 2tx signed, your private key could be deduced.

Coz when most of bitcoiners were licking ass of Bitcoin foundation founders I was on the opposite side.



Do u mean quantum tunneling? Aye, I know about this phenomenon.


At least one (http://www.youtube.com/watch?v=1_qOs26Op1Q).

---

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.

R u sur it iznt coz u talk like thiz ?

Ye, coz ignore counter jumped +20 after I took part in debates regarding Bitcoin Foundation. Why?

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.

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.

That's valid point.

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?


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.


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

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.

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. 

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

DeathAndTaxes, you already read it  :-*

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.

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

I guess I should stop doing Vanity Generation  :P

:D

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.

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.

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

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.

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.

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.

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.

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 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.

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.

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?

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.

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.

???  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?

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.

It's possible for me to win the lotto, it won't happen though

http://www.youtube.com/watch?v=zMRrNY0pxfM

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 :D)

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.