Quantum computing and Bitcoin's use of ECDSA

RGBKey

hero member

Activity: 854

Merit: 658

rgbkey.github.io/pgp.txt

Quote from: Remember remember the 5th of November on March 17, 2018, 03:54:02 PM

Quote from: RGBKey on March 13, 2018, 04:03:00 PM

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.

Remember remember the 5th of November

legendary

Activity: 1862

Merit: 1011

Reverse engineer from time to time

Quote from: RGBKey on March 13, 2018, 04:03:00 PM

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.

aleksej996

sr. member

Activity: 490

Merit: 389

Do not trust the government

Quote from: squatter on March 14, 2018, 05:52:46 PM

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.

Quote from: squatter on March 14, 2018, 05:52:46 PM

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.

malevolent

legendary

Activity: 3472

Merit: 1724

Quote from: squatter on March 15, 2018, 02:40:17 PM

Can they derive your master public key that way?

No, they can't.

squatter

legendary

Activity: 1666

Merit: 1196

STOP SNITCHIN'

Quote from: malevolent on March 14, 2018, 07:52:15 PM

Quote from: squatter on March 13, 2018, 03:49:30 PM

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

legendary

Activity: 3472

Merit: 1724

Quote from: squatter on March 13, 2018, 03:49:30 PM

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

legendary

Activity: 1666

Merit: 1196

STOP SNITCHIN'

Quote from: achow101 on March 13, 2018, 04:54:18 PM

Quote from: squatter on March 13, 2018, 03:49:30 PM

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

Quote from: squatter on March 13, 2018, 03:49:30 PM

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?

Quote from: aleksej996 on March 14, 2018, 05:06:27 PM

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?

aleksej996

sr. member

Activity: 490

Merit: 389

Do not trust the government

Quote from: achow101 on March 13, 2018, 04:54:18 PM

Quote from: squatter on March 13, 2018, 03:49:30 PM

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.

Quote from: aplistir on March 14, 2018, 11:16:37 AM

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 Wink

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.

RGBKey

hero member

Activity: 854

Merit: 658

rgbkey.github.io/pgp.txt

Quote from: aplistir on March 14, 2018, 11:16:37 AM

Quote from: RGBKey on March 13, 2018, 04:03:00 PM

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.

aplistir

full member

Activity: 378

Merit: 197

Quote from: squatter on March 13, 2018, 03:49:30 PM

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

Quote from: RGBKey on March 13, 2018, 04:03:00 PM

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

achow101

staff

Activity: 3458

Merit: 6793

Just writing some code

Quote from: squatter on March 13, 2018, 03:49:30 PM

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

Quote from: squatter on March 13, 2018, 03:49:30 PM

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

Yes.

RGBKey

hero member

Activity: 854

Merit: 658

rgbkey.github.io/pgp.txt

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.

squatter

legendary

Activity: 1666

Merit: 1196

STOP SNITCHIN'

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

Quote

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

Quote

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:

Quote

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?

Topic: Quantum computing and Bitcoin's use of ECDSA (Read 235 times)