Quantum computing and Bitcoin's use of ECDSA

[squatter]

I came across an interesting article by nopara73 (who works on HiddenWallet and TumbleBit stuff). He discusses when quantum computing will break elliptic curves:

The elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates.

The paper estimates the breakthrough to 2027 with a completely different method. I tend to think 2022–23 are the right numbers...

For Bulletproofs, what matters is the Shor RSA2048 line, which is predicted to be broken in 2022–23.

He concludes that since we don't expose Bitcoin public keys when transacting (only hashes of public keys), that our bitcoins are safe. That is:

Thus, as long as you don’t expose your public key, you don’t need to worry about quantum computers and the only way to expose your public key is to make a Bitcoin transaction. If you don’t reuse addresses you are quantum safe.

So, I have two questions.

1) Aside from the specific case of Pay-to-IP in earlier versions, is the above correct?
2) What is the general plan when ECDSA is broken? Hard fork to a new signature algorithm? Simply never reuse addresses?

[RGBKey]

The problem with quantum computing is you can't ignore it forever. Once it gets fast enough, an attacker could find your private key from your public key in the time between you broadcasting your transaction and it being confirmed, then performing a double-spend with a higher fee. Once it gets to that point, there would be no way to safely transact anymore.

[achow101]

1) Aside from the specific case of Pay-to-IP in earlier versions, is the above correct?

Yes (aside from the estimates; it's hard to predict the future).

2) What is the general plan when ECDSA is broken? Hard fork to a new signature algorithm?

Yes.

[aplistir]

He concludes that since we don't expose Bitcoin public keys when transacting (only hashes of public keys), that our bitcoins are safe.

As the link says, the BIG problem with quantum computers is that there are bitcoins worth more than  $10.000.000.000 in addresses, whose public key has been published. If someone was able to steal all those coins, he could destroy bitcoin by selling all of them at the same time.

We do expose the public key when we make a transaction, but usually the whole address is emptied at the same time, so the public key will be useless after the transaction is completed.

Your coins are safe, if you just keep them in addresses with no spend action, but it seems impossible to protect those old coins. Theymos suggested a solution once, but he did not get support to his idea...

The problem with quantum computing is you can't ignore it forever. Once it gets fast enough, an attacker could find your private key from your public key in the time between you broadcasting your transaction and it being confirmed, then performing a double-spend with a higher fee.

I do not believe quantum computers will ever become THAT fast. That would mean the attacker would have to solve the ECDSA problem in less than 5 minutes!  
And if that would ever become possible, it would be easy to just somehow prevent the network from accepting double spends...
Also. Do you really think the owner of a quantum computer would bother to steal those small everyday transactions, when he could just empty some addresses containing about 100000BTC each, there are several of those, that have published their pulic key....

[RGBKey]

The problem with quantum computing is you can't ignore it forever. Once it gets fast enough, an attacker could find your private key from your public key in the time between you broadcasting your transaction and it being confirmed, then performing a double-spend with a higher fee.

I do not believe quantum computers will ever become THAT fast. That would mean the attacker would have to solve the ECDSA problem in less than 5 minutes!  
And if that would ever become possible, it would be easy to just somehow prevent the network from accepting double spends...
Also. Do you really think the owner of a quantum computer would bother to steal those small everyday transactions, when he could just empty some addresses containing about 100000BTC each, there are several of those, that have published their pulic key....

I do believe that coins would be stolen from the large addresses first. Also, in doing that, Bitcoin would very quickly lose a lot of value. Once people know that their keys can be cracked, Bitcoin has failed. Hopefully we can hard fork to a quantum-proof algorithm before we get to that point.

[aleksej996]

2) What is the general plan when ECDSA is broken? Hard fork to a new signature algorithm?

Yes.

I doubt a hard fork would be needed. I assume this can be done with a soft fork.

As the link says, the BIG problem with quantum computers is that there are bitcoins worth more than  $10.000.000.000 in addresses, whose public key has been published. If someone was able to steal all those coins, he could destroy bitcoin by selling all of them at the same time.

I wouldn't say destroy Bitcoin, as much as give us a really good discount

As far as I understand, it gets exponentially difficult to create a quantum computer that can work with bigger keys, so it is still probably an open question on the possibility of reasonably building such a strong quantum computer.
I assume we will switch to some new quantum secure algorithm with a soft fork as we slowly get closer to that big quantum computer, just like the rest of the tech industry does as well. It isn't just Bitcoin that would have to be upgraded, Internet and tech industry as a whole will need to go through this together.

[squatter]

1) Aside from the specific case of Pay-to-IP in earlier versions, is the above correct?

Yes (aside from the estimates; it's hard to predict the future).

2) What is the general plan when ECDSA is broken? Hard fork to a new signature algorithm?

Yes.

Thanks. I guess since this threat is sort of existential to the protocol that the fork would be non-contentious. Is there any consensus about what algorithm might be chosen?

I doubt a hard fork would be needed. I assume this can be done with a soft fork.

I assume we can add new rules requiring signatures to conform to a new signature algorithm. But without a hard fork, wouldn't we also still need to enforce use of ECDSA?

[malevolent]

He concludes that since we don't expose Bitcoin public keys when transacting (only hashes of public keys), that our bitcoins are safe.

The problem is that a non-insignificant number of people shares/exposes their extended public keys / master public keys to various wallets, apps and services, and many more could be socially engineered to reveal them.

Public keys can also be derived from messages signed by ECDSA private keys.

Another way someone may expose their public key is if they participate in creating a multisignature P2SH address and when making a P2SH transaction; in case of the former the public keys are revealed only to those who participated in creating the multisig P2SH address.

[squatter]

He concludes that since we don't expose Bitcoin public keys when transacting (only hashes of public keys), that our bitcoins are safe.

The problem is that a non-insignificant number of people shares/exposes their extended public keys / master public keys to various wallets, apps and services, and many more could be socially engineered to reveal them.

Any idea how this might affect an Electrum watching-only wallet setup w/ offline signing? I don't think the master public key is transmitted to Electrum servers, but that may not matter. Because of the way Electrum verifies, grouping HD wallet addresses together is trivial for the Electrum server you connect to. Can they derive your master public key that way?

[malevolent]

Can they derive your master public key that way?

No, they can't.

[aleksej996]

I guess since this threat is sort of existential to the protocol that the fork would be non-contentious. Is there any consensus about what algorithm might be chosen?

Don't underestimate the Bitcoin community and their ability of creating passionate debates from nothing.
Even if they all agree that a fork needs to happen, they will still fiercely debate on what kind of fork it should be.

I assume we can add new rules requiring signatures to conform to a new signature algorithm. But without a hard fork, wouldn't we also still need to enforce use of ECDSA?

Miners can simply agree (as a soft fork is) to not mine nor accept as valid ECDSA signed transactions.
However they might still want to keep those valid, which might make sense, depending on how easy these attacks might be in practice.
We will have to wait and see.

New signing algorithm might simply use anyone-can-spend transactions, like segwit does, with miners agreeing that they won't mine them unless they are also sent this new type of signature with the transaction that is trying to spend the coins from this anyone-can-spend transaction.
This is how segwit doesn't break old nodes that see valid anyone-can-spend transactions, but can't seem to get their transactions confirmed if they try to spend them themselves.

[Remember remember the 5th of November]

The problem with quantum computing is you can't ignore it forever. Once it gets fast enough, an attacker could find your private key from your public key in the time between you broadcasting your transaction and it being confirmed, then performing a double-spend with a higher fee. Once it gets to that point, there would be no way to safely transact anymore.

Although then it would be a fight between the other person who also has a QC and they will be rebroadcasting with an ever higher fee, thus negating the whole thing.

[RGBKey]

The problem with quantum computing is you can't ignore it forever. Once it gets fast enough, an attacker could find your private key from your public key in the time between you broadcasting your transaction and it being confirmed, then performing a double-spend with a higher fee. Once it gets to that point, there would be no way to safely transact anymore.

Although then it would be a fight between the other person who also has a QC and they will be rebroadcasting with an ever higher fee, thus negating the whole thing.

I wouldn't say it would be "negated", by this point, Bitcoin would be very dead. Nothing could bring it back at this point, a hard fork to another algorithm wouldn't even be able to save it if this happened first.