How can quantum computers affect bitcoin? Of course, the elliptic curve crytography has been under scrutiny since the quantum computing hype began. Bitcoin was built to replace third party trust with cryptographic proof. But it's not just bitcoin. Two of the most common cryptosystems are Rivest–Shamir–Adleman (RSA) and elliptic curve cryptography (ECC). When you are online, any information that you exchange will be encrypted, usually with RSA or ECC. Both of these are vulnerable to attacks by quantum computers. A large enough quantum computer will become a security problem for anyone interacting online.
What will happen if a quantum computer can undermine the trust of the cryptography that digital currencies are built on? The implementation details of the currencies and how the exchanges handle transactions and wallets can change how seriously quantum computing can potentially impact the currencies.
Encryption Today and Shor's Impact
Encryption works by applying a math formula to a message, and scrambling it so that only a person who you've authorized can see it. The safety of your message relies on the difficulty of “undoing” the mathematical problem without the key.For example, RSA relies on the hard problem of factoring numbers. Multiplying two prime numbers together is easy, but taking a large number and factoring it to get those two prime numbers is difficult. It would take longer than the age of the universe to factor one 4096-bit key with a classical computer.
However, quantum computers solve problems differently than classical computers. Shor's algorithm can find the prime factors of a number and can ”undo” this factoring problem much more easily than a classical computer. This means that someone with a large enough and coherent enough quantum computer, could, in theory, get your private key from the public key (more here). This is a serious problem. A private key should never be shared with anyone, because that private key can be used to authorize transactions that the owner doesn't want to happen. So, as quantum computers become better, the security of RSA will no longer be effective.
RSA has been around since 1977 and is still used today. Later on, ECC was recommended to replace RSA, due to it’s smaller key sizes and speed. However, Shor's discrete logarithm quantum algorithm impacts ECC as well.The research breakthroughs and speed of advances in quantum computing means that the long-term security of these systems is questionable. In 2015, due to concerns about quantum computing attacks, the NSA noted that it plans to replace the recommended “Suite B” ciphers with quantum-resistant algorithms. In January 2019, NIST released a list of 26 potential algorithms that may resist quantum computer attacks. While some of these are viable candidates and we will need to choose new encryption algorithms, cryptocurrencies have unique implementation challenges and uneven standards that will make transitioning harder.
What size of a quantum computer can break bitcoin?
How big does this quantum computer bitcoin killer need to be? Microsoft Research has shown fewer qubits are needed for computing elliptic curve discrete logarithms - as few as about 2500 for a standard 256-bit key than 2048-bit RSA, which needs 4000. However, these are perfect, "logical" qubits. Because of error correction and other necessary processes, we need many more physical qubits. John Preskill noted in his lecture on quantum information that a 10 million physical and 10,000 logical qubit quantum computer would be needed.
Current quantum technology is still very far from this milestone. IBM announced they had achieved a 50-qubit system in late 2017, and Google announced 72-qubits in early 2018. IonQ, which uses ion traps, announced a quantum computer with 160 qubits trapped and performed operations on 79 of them. DWave has released their 2048 qubit system. However, it is a quantum annealer and can't be efficiently used for Shor's algorithm.
However, the goal is eventually build quantum computers large enough for chemistry, optimization, and machine learning. But while quantum computers large enough to do these tasks are far away, the cryptocurrencies currently in circulation can be affected later.
Impact of a Quantum Computer on Cryptocurrencies
While quantum computers large enough to do these tasks are far away, the cryptocurrencies currently in circulation can be affected down the road, so it's important to think ahead. A big concern is that a quantum computer could calculate the private key used to sign transactions from the public keys exposed during transactions, and therefore allow unauthorized spending. How do we mitigate the quantum computing threat on cryptocurrencies? There are a few weak points that allow quantum computers to potentially gain access to coins.
Exposed public key
First, a malicious actor would need to find the public key. While the wallet address is based on the public key, it’s hashed by algorithms that currently are not vulnerable to quantum computing attacks. However, during a transaction, the public key is exposed.For each transaction, the owner authorizes the transfer of a coin to another address by digitally signing a hash of the previous transaction and the public key, and adding these to the end of the chain. The easiest way to see what happens during a transaction is by looking at the code in action. We're using pybitcointools below to show the steps.
The condensed steps:
- Create a private key
- Generate the public key from the private key
- To make a transaction, you sign the transaction with your private key.
- When you read tx2, you see the public key (starting with '0420f34...') exposed in tx2
- Push the transaction
> priv
'57c617d9b4e1f7af6ec97ca2ff57e94a28279a7eedd4d12a99fa11170e94f5a4'
> pub = privtopub(priv)
> pub
'0420f34c2786b4bae593e22596631b025f3ff46e200fc1d4b52ef49bbdc2ed00b26c584b7e32523fb01be2294a
1f8a5eb0cf71a203cc034ced46ea92a8df16c6e9'
> addr = pubtoaddr(pub)
> addr
'1CQLd3bhw4EzaURHbKCwM5YZbUQfA4ReY6'
> h = history(addr)
> h
[{'output': u'97f7c7d8ac85e40c255f8a763b6cd9a68f3a94d2e93e8bfa08f977b92e55465e:0', 'value':
50000, 'address': u'1CQLd3bhw4EzaURHbKCwM5YZbUQfA4ReY6'}, {'output': u'4cc806bb04f730c445c
60b3e0f4f44b54769a1c196ca37d8d4002135e4abd171:1', 'value': 50000, 'address': u'1CQLd3bhw4Ez
aURHbKCwM5YZbUQfA4ReY6'}]
> outs = [{'value': 90000, 'address': '16iw1MQ1sy1DtRPYw3ao1bCamoyBJtRB4t'}]
> tx = mktx(h,outs)
> tx
'01000000025e46552eb977f908fa8b3ee9d2943a8fa6d96c3b768a5f250ce485acd8c7f7970000000000fffff
fff71d1abe4352100d4d837ca96c1a16947b5444f0f3e0bc645c430f704bb06c84c0100000000ffffffff01905
f0100000000001976a9143ec6c3ed8dfc3ceabcc1cbdb0c5aef4e2d02873c88ac00000000'
> tx2 = sign(tx,0,priv)
> tx2
'01000000025e46552eb977f908fa8b3ee9d2943a8fa6d96c3b768a5f250ce485acd8c7f797000000008b48304
5022100dd29d89a28451febb990fb1dafa21245b105140083ced315ebcdea187572b3990220713f2e554f384d2
9d7abfedf39f0eb92afba0ef46f374e49d43a728a0ff6046e01410420f34c2786b4bae593e22596631b025f3ff
46e200fc1d4b52ef49bbdc2ed00b26c584b7e32523fb01be2294a1f8a5eb0cf71a203cc034ced46ea92a8df16c
6e9ffffffff71d1abe4352100d4d837ca96c1a16947b5444f0f3e0bc645c430f704bb06c84c0100000000fffff
fff01905f0100000000001976a9143ec6c3ed8dfc3ceabcc1cbdb0c5aef4e2d02873c88ac00000000'
> pushtx(tx2)
'Transaction Submitted'
Even though the public key is exposed during each transaction, un-doing these steps to get the private key takes longer than the age of the universe for a classical computer, so it's secure.The hierarchical deterministic wallet is now the standard for most mature exchanges. Their wallets allow you to have many wallet addresses. This means that once the private key is used for a transaction, all the coins move, and that key is no longer valid. That means the coins could only be intercepted during the confirmation stage.
Reusing Wallet Addresses
Besides the elliptic curve vulnerability, the security of your coins depends on the exchanges themselves. Not all wallets use the hierarchical deterministic wallet, and so most exchanges right now do not reuse addresses. However, if they do, the private key can be used again to sign a transaction. That means a transaction long in the past could be used to recover the private key, and then that private key could be used again today to move coins.
Fast enough attacks
Even if we do not reuse addresses, there's an argument to be made that there's still time during the transaction to intercept the coins. Someone could, in theory,A transaction would therefore only be vulnerable while the transaction was unconfirmed. However, that could be enough time for a quantum computer to reroute the transaction. Craig Gidney and Martin Ekerå published a paper in May 2019 on how to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.
The average confirmation time for a Bitcoin transaction in June 2019 was 9.47 minutes. However, there have been periods of time when average confirmation times spiked to 11453 minutes - over 7 days!In the world with a large enough quantum computer that would be able to recover the key, all you'd have to do is send the transaction with a higher fee and redirect the transaction to your own wallet.A way to prevent this then would be to set transaction fees very high for the true owner. However, since low fees is a selling point for cryptocurrencies, this would cripple use.
Lost Coins
Ideally, we would need to plan to transition to a new cryptosystem well before a large-scale quantum computer would be available, and have people opt to move their coins before there is a risk of verification ownership. After a certain time, the old, elliptic curve encrypted version will have to become invalid, and the entire value of that chain will fall to zero. This solves the problem of a quantum computer later gaining access and manipulating the cryptocurrency.But we know some bitcoin have been "lost". The owner has somehow lost access to the private key, which is necessary to authorize transactions and spending.
It's possible that some portion of these lost coins are on exchanges that re-used wallets and the old coins could therefore remain vulnerable. If we have access to the public key, Shor's algorithm could recover some of these lost coins.If the person recovering lost coins immediately starts selling, the price would likely crash and undermine confidence in the system. This also raises other questions. Since the amount of bitcoin is capped, would those lost coins be re-issued? Or would the cap be lower?
Moving to a Post-Quantum Algorithm
The above problems exist if we continue using elliptic curve cryptography based systems. However, we can avoid some of these problems as quantum computing power increases if we change the algorithm used to create the public key from the private key. But we'll need to pick an algorithm that has shown evidence that it can stand up to quantum attacks. We call this “post-quantum cryptography.”
The National Institute of Standards and Technology (NIST) has been leading an effort to evaluate and standardize post-quantum cryptography methods, because we need a new recommendation to replace the Suite B ciphers that are vulnerable to a quantum computer.
Cryptocurrencies are currently exploring different cryptosystems. One approach is using symmetric cryptography, which is less vulnerable to quantum computing attacks than asymmetric cryptography. Fawkescoin is trying to solve the problem by demonstrating that a distributed network is possible with symmetric cryptography. Other coins, like the Quantum Resistant Ledger, uses hash-based cryptography. So far, hash-based cryptosystems resist currently known quantum computer attacks.
Looking ahead to a post-quantum future
It's hard to predict future technologies. So, it's likely that quantum computing will not be the only technology that puts cryptocurrencies and security at risk. Sometimes it only takes one technological leap to move us into a place that we didn’t think would be possible. It's likely that the need to update encryption will happen multiple times.
One constant in technology is that there is always progress and new breakthroughs, even if we can't know what they'll be. Zapata Computing released a paper on Variational Quantum Factoring, which may be able to use hybrid (working with classical computers) Noisy Intermediate Scale Quantum (NISQ) devices with just hundreds of qubits to factor numbers. Of course, this new technique is untested and has limitations. However, there is a lot of room for new algorithms and exploration that may shift timelines.
Quantum computers may never be able to scale to 2500 logical qubits. However, a quantum computer of this size can solve many life-changing problems, besides just running Shor's algorithm. Google has been using quantum simulation to explore fertilizer production efficiency problems, which consumes 1-2% of energy in the world. A higher quantity of quantum computer users will almost certainly accelerate the impact on economic, political, and social issues in the world.Some industries, like cryptocurrencies, may consider quantum computers a threat to their long term viability. We can’t stop progress, and technology can and will be used for both good and evil. However, if elliptic curve encryption can truly be compromised, we'll have bigger problems than losing our bitcoin. Understanding and preparing for the security implications of quantum will be crucial. We can't hold back the technology from its positive impacts out of fear.
Are you considering quantum computers as a risk to your cryptocurrency portfolio? Do you think building a big enough quantum computer to launch attacks on bitcoin will be possible? Should cryptocurrencies start worrying about quantum computing threats?