Bitcoin Forum
July 20, 2019, 12:11:35 AM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Quantum computing and Bitcoin's use of ECDSA  (Read 183 times)
squatter
Hero Member
*****
Offline Offline

Activity: 1162
Merit: 850


STOP SNITCHIN'


View Profile
March 13, 2018, 08:49:30 PM
 #1

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

1563581495
Hero Member
*
Offline Offline

Posts: 1563581495

View Profile Personal Message (Offline)

Ignore
1563581495
Reply with quote  #2

1563581495
Report to moderator
1563581495
Hero Member
*
Offline Offline

Posts: 1563581495

View Profile Personal Message (Offline)

Ignore
1563581495
Reply with quote  #2

1563581495
Report to moderator
1563581495
Hero Member
*
Offline Offline

Posts: 1563581495

View Profile Personal Message (Offline)

Ignore
1563581495
Reply with quote  #2

1563581495
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1563581495
Hero Member
*
Offline Offline

Posts: 1563581495

View Profile Personal Message (Offline)

Ignore
1563581495
Reply with quote  #2

1563581495
Report to moderator
RGBKey
Hero Member
*****
Offline Offline

Activity: 840
Merit: 629


rgbkey.github.io/pgp.txt


View Profile WWW
March 13, 2018, 09:03:00 PM
 #2

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
Moderator
Legendary
*
expert
Offline Offline

Activity: 1820
Merit: 2551


bc1qshxkrpe4arppq89fpzm6c0tpdvx5cfkve2c8kl


View Profile WWW
March 13, 2018, 09:54:18 PM
 #3

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
Full Member
***
Offline Offline

Activity: 334
Merit: 156



View Profile
March 14, 2018, 04:16:37 PM
Last edit: March 14, 2018, 06:11:56 PM by aplistir
 #4

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

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
RGBKey
Hero Member
*****
Offline Offline

Activity: 840
Merit: 629


rgbkey.github.io/pgp.txt


View Profile WWW
March 14, 2018, 08:54:33 PM
 #5

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
Sr. Member
****
Offline Offline

Activity: 476
Merit: 327


Do not trust the government


View Profile WWW
March 14, 2018, 10:06:27 PM
 #6

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 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.
squatter
Hero Member
*****
Offline Offline

Activity: 1162
Merit: 850


STOP SNITCHIN'


View Profile
March 14, 2018, 10:52:46 PM
 #7

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
can into space
Staff
Legendary
*
Online Online

Activity: 2268
Merit: 1105



View Profile
March 15, 2018, 12:52:15 AM
Last edit: March 15, 2018, 02:35:32 AM by malevolent
Merited by squatter (1), _Miracle (1)
 #8

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
Hero Member
*****
Offline Offline

Activity: 1162
Merit: 850


STOP SNITCHIN'


View Profile
March 15, 2018, 07:40:17 PM
 #9

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 into space
Staff
Legendary
*
Online Online

Activity: 2268
Merit: 1105



View Profile
March 15, 2018, 08:07:15 PM
 #10

Can they derive your master public key that way?

No, they can't.

aleksej996
Sr. Member
****
Offline Offline

Activity: 476
Merit: 327


Do not trust the government


View Profile WWW
March 17, 2018, 01:50:07 PM
 #11

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
Legendary
*
Offline Offline

Activity: 1862
Merit: 1002

Reverse engineer from time to time


View Profile
March 17, 2018, 08:54:02 PM
 #12

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.

BTC:1AiCRMxgf1ptVQwx6hDuKMu4f7F27QmJC2
RGBKey
Hero Member
*****
Offline Offline

Activity: 840
Merit: 629


rgbkey.github.io/pgp.txt


View Profile WWW
March 18, 2018, 04:05:08 AM
 #13

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.
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!