More Confusion Regarding Public Keys - Statistical Questions

[The00Dustin]

I was reading the oclvanitygen thread for kicks and came across this:

In addition, while you can possibly get a collision on the address, you still can't spend from that address unless you have the correct private key.  So even if you do happen to get a full match on the address, you might still not have the correct private key to go with it. (addresses are hashes of the public key, which have a smaller space than the public key, so at least there's a greater potential for a collision on the address)

Reading it caused me to ponder a security question...  Unless I am behind the times, current general knowledge seems to be that one should not re-use addresses because the availability of the public key might make it easier to break the private key.  Given this, I assume TheRealSteve's statement is at least partially incorrect.

Specifically, if the public key is not available, then this part of the statement is wrong:

"In addition, while you can possibly get a collision on the address, you still can't spend from that address unless you have the correct private key.  So even if you do happen to get a full match on the address, you might still not have the correct private key to go with it."

IIRC, and even if I hadn't actually previously read something to this effect, logically speaking, the first key combination successfully used to spend bitcoin has its public key tied to the address, and no other public key can be used in the future (which also prevents any other private key from being used except in an m of n scenario), so when the public key has not been tied to an address yet, a different key combination could be used in the event of a collision (however unlikely) because there is nothing to say the alternate public key is not the original.

Now, assuming my analysis is correct, this begs the question of which is riskier today (granted that which is riskier could change in the future if any specific piece of cryptography in use is broken in the future), and statistically speaking, what are the odds that define each scenarios risk:

1) Re-using an address or otherwise publishing your public key for said address in the blockchain.
Risk: Public key is used to make it easier to break private key

2) Keeping the public key private to avoid the risk in (1), as is currently recommended.
Risk: Collision allows someone else to assume control of your address

I understand the odds for (2) are astronomical and posted all over the place, but I don't know if there are calculable odds for (1).  Assuming there are, it would be neat to know how much safer (2) is, and it would be somewhat validating/fulfilling (albeit certainly unlikely) if it turns out (1) is safer when we assume no other cryptography breakage will occur.

So, can the odds for (1) be calculated?  Also, does any cryptography breakage already exist which would change the odds for (1)?  Finally, is it possible to calculate the odds of any future cryptography breakage that Would affect (1)?

[DannyHamilton]

I was reading the oclvanitygen thread for kicks and came across this:

In addition, while you can possibly get a collision on the address, you still can't spend from that address unless you have the correct private key.  So even if you do happen to get a full match on the address, you might still not have the correct private key to go with it. (addresses are hashes of the public key, which have a smaller space than the public key, so at least there's a greater potential for a collision on the address)

TheRealSteve is mistaken.  Any private key that creates a public key that hashes to the exact same address can be used to sign any transaction that spends an output that was received at that address.  This means that there are approximately 7.9 X 10²⁸ valid private keys for every version 1 bitcoin address.

Unless I am behind the times, current general knowledge seems to be that one should not re-use addresses because the availability of the public key might make it easier to break the private key.

While it is technically true that re-using a bitcoin address risks exposing the public key and as such slightly reduces the cryptographic protection of the bitcoins received at the address, this is not currently a significant risk. The real reason to use a new address for every transaction is to increase privacy and maintain the funngibility of bitcoin.

Given this, I assume TheRealSteve's statement is at least partially incorrect.

TheRealSteve's statement is based on a mistaken assumption that the original private key must be used to sign the transaction with the current protocol.

IIRC, and even if I hadn't actually previously read something to this effect, logically speaking, the first key combination successfully used to spend bitcoin has its public key tied to the address, and no other public key can be used in the future (which also prevents any other private key from being used except in an m of n scenario),

This is not how the protocol is currently designed.  There is nothing in the protocol currently tying an address to any particular public key that has been used in the past.

so when the public key has not been tied to an address yet, a different key combination could be used in the event of a collision (however unlikely) because there is nothing to say the alternate public key is not the original.

Correct.  For that matter, even if a public key has already been exposed, a different public key that hashes to the same address could still be used.

Now, assuming my analysis is correct, this begs the question of which is riskier today (granted that which is riskier could change in the future if any specific piece of cryptography in use is broken in the future), and statistically speaking, what are the odds that define each scenarios risk:

1) Re-using an address or otherwise publishing your public key for said address in the blockchain.
Risk: Public key is used to make it easier to break private key

2) Keeping the public key private to avoid the risk in (1), as is currently recommended.
Risk: Collision allows someone else to assume control of your address

The occurence of option 1 does not prevent the occurence of option 2.  Therefore, option 1 carries BOTH the risk you have indicated AS WELL AS the risk you have listed for option 2.  Therefore, it clearly carries marginally greater risk.

[The00Dustin]

Thanks for the response.  This is the second time my memory has clearly served me incorrectly and you have come in with some clarification.  You may recall the other, it was about the public key being included in the blockchain on change addresses or something like that.  I wish I knew what I read, because I'm sure both mistakes came from the same piece of reading material.  As it stands, I can't really determine whether the material was at fault or I misread something.

[Bitcoinpro]

You could just check the block chain to see if someone has used the public key first before using it yourself

the only reason to change your address is to keep making it harder for someone to steal your private keys

since you could be, security wise, possibly revealing them when you make a transaction at the address, but

would not have to potentially reveal them to receive funds. When you generate the keys obviously you can

have your computer disconnected from the web.

[DannyHamilton]

the only reason to change your address is to keep making it harder for someone to steal your private keys

This is not true.

The reason to change your address on every transaction is to increase privacy and maintain the fungibility of bitcoin.

since you could be, security wise, possibly revealing them when you make a transaction at the address

A properly operating wallet should not reveal private keys.

[Bitcoinpro]

the only reason to change your address is to keep making it harder for someone to steal your private keys

This is not true.

The reason to change your address on every transaction is to increase privacy and maintain the fungibility of bitcoin.

since you could be, security wise, possibly revealing them when you make a transaction at the address

A properly operating wallet should not reveal private keys.

maybe explaining the fungability a bit better would help, id have to look at transactions costs storage structure again,

you dont absolutely have to rely on a properly operating wallet if you have generated the private key's offline, keep

them safe and dont use your deposits until making a new address, though you would still be wanting to make sure

you have the best most reliable wallet to suit your needs as you said,

[andytoshi]

the only reason to change your address is to keep making it harder for someone to steal your private keys

This is false. Key management is the job of wallet authors, and ordinary users do not need to be aware of them at all. The mapping between ECDSA keys and addresses is an implementation detail of the Bitcoin scripts used to support pay-to-address transactions, and should not affect decisions on the level of user behaviour. At the UI level, addresses are simply opaque payment identifiers. You use a new one for each payment you receive so that you can distinguish between them -- they are more akin to an invoice number than any sort of key. Reusing addresses is at best shoddy accounting, but likely indicates a deeper confusion about their semantic meaning.

And as others have said, address reuse is bad for the privacy of all users of the Bitcoin network, because it shrinks the set of ownership classes visible to an outside observer.

you dont absolutely have to rely on a properly operating wallet if you have generated the private key's offline, keep

You absolutely need to rely on a wallet to manage your keys. Even if you are a professional cryptographer, Bitcoin requires the active use of dozens or hundreds of keys, which cannot be revealed or lost. Manually managing these is a recipe for disaster.

[minerpumpkin]

maybe explaining the fungability a bit better would help

I guess he points out that it should be as hard as possible to trace coins across the blockchain. If i reuse an address, it becomes an obvious central point of my spendings. I use change-addresses, it's not really obvious if the coins have changed hands.