Is Quantum Computing a threat to Bitcoin?
Updated: Apr 15, 2021
Image source - MIT
Ever since Google gained “Quantum Supremacy”, i.e it's Sycamore Quantum Computer solved in 200 seconds what would take conventional supercomputers 10,000 years to solve, the clock has been ticking on when quantum computing will be able to crack the encryption algorithms on which depend modern-day necessities, like instant messaging (WhatsApp), online shopping (Amazon), web browsing (google), online banking and the topic of my interest - Bitcoin.
Is Quantum Computing a threat to cryptocurrencies?
The short answer is “Yes”.
However, that does not mean that all is lost and you should sell your cryptos and accept that your money must be stored in ever-depreciating fiat form. There are ways to protect cryptocurrencies from this threat and the crypto community is hard at work to tackle it before it becomes a real problem.
Before we get into the details, I’d want to make 2 points:
1. A practically useful quantum computer is still many years away.
2. If a practically useful quantum computer was a reality today, we would have bigger things to worry about than bitcoin. Rogue nations would be able to intercept sensitive military secrets like nuclear codes, access controls of critical domestic infrastructure that bring life to a standstill in an enemy country and cause havoc in international finance. Bitcoin security will be the least of our problems.
Now let's get going.
We start with an Idiot’s Guide to Quantum Computing
Conventional Computers use “bits” which can have one of two values, 0 or 1. Quantum Computers use something called “qubits”. Qubits can simultaneously be 0 or 1. Remember Schrödinger’s cat? The cat is locked in a box. You can’t know if it is dead or alive till you open the box. So during the time that it is locked in a box, it is simultaneously dead and alive. (I’m not pretending to understand this. But I like the cat story).
=> So while conventional computers can perform 1 calculation at a time, qubits (which exist in multiple states at a time) enable quantum computers to perform multiple calculations at a time.
What does this have to do with cryptocurrencies?
Among quantum computing’s many use cases is the ability to break encryption. Cryptocurrencies use encryption to sign transactions and this signature is vulnerable to quantum computing.
Let me explain using Anna and George's love story
Let’s say Anna wants to send a message to George. But she knows that the nosy Aunt Sally will intercept the message and read it before passing it on to George. Anna decides to use a key to scramble the message but the problem is that she will need to send the same key to George to unscramble the message and that key too can be intercepted by Aunt Sally. The solution is that instead of using the same key to encode and decode, she can use a public-private key pair that are related to each other.
George has a private key that he keeps to himself and a public key that he broadcasts to everyone. Anna can encrypt her message using George’s public key and the message can be decrypted only by the person who has the private key i.e George. Aunt Sally will have to find someone else to spy on.
Also, when George receives a message, how can he be sure that the message has actually come from Anna and not Aunt Sally impersonating Anna? If Anna signs the message with her own private key that only she knows, George can verify the signature with Anna’s publicly broadcast public key.
Coming to cryptocurrencies, if Anna wants to send 1BTC to George, she will send the BTC to George’s public address and only George who has the corresponding private key can receive the BTC. Also, Anna will need to sign the transaction with her private key which will be used to verify that the BTC was actually sent by Anna and not someone pretending to be her.
What exactly in the Bitcoin network is vulnerable to quantum computing?
The short answer is “Bitcoin’s digital signature system”.
Bitcoin uses Elliptical Curve Digital Signature Algorithm (ECDSA) which creates these public-private key pairs (used by Anna and George above). The relationship between the public-private key pairs is such that if you know the public key, you can verify that the transaction was approved by the holder of the private key, but you cannot derive the private key.
Actually, a more accurate statement would be that it is not feasible to derive the private key from the public key using conventional computers. It would take billions of years. However, in 1994, the mathematician Peter Shor published Shor’s Algorithm using which someone with a sufficiently powerful quantum computer can break the cryptography behind the public-private key pair and derive the private key from the public key much faster.
Who is vulnerable to quantum attacks?
Crypto security experts are constantly reminding us- “Not your keys, Not your coins”. This means that if someone else has your private keys, she has your coins.
The private key however is under threat only if the public key is exposed. If you don’t reveal your public key, then the private key is quantum-safe. The vulnerability happens when the public key is exposed which can happen in the following 3 situations:
1. P2PK addresses - When one transfers BTC to someone, the receiver’s public key is not exposed. What is exposed is the hash of the receiver’s public key (P2PKH- Payment to Public Key Hash). Therefore the receiving address is not under threat. However, in the first year of bitcoin operations, the public key of the receiving address was exposed (P2PK - Payment to Public Key).
=> If those funds have not been moved from the P2PK addresses then they’re vulnerable to a quantum attack. Further, some people have forgotten their private keys and cannot move coins even if they wanted to. The first to develop a usable quantum computer may be able to derive the corresponding private keys and keep those coins for themselves.
2. Reused Addresses - When one transfers BTC from one's wallet, the sender’s public key becomes visible on the blockchain and is vulnerable to a quantum attack. Therefore, one must never reuse an address. Today it is standard practice to create a new public key every time one makes a transfer. Every half-decent crypto wallet does this automatically.
=> As long as users adopt good practices like not reusing public keys, this is not really a problem.
3. Unprocessed Transactions - Once you broadcast your transaction, there is a window when your public key is exposed but the transaction is not confirmed. Your transaction would be sitting in the mempool till it makes it to a block. During that time, if a quantum computer can derive the private key, it can send your coins to the hacker’s address instead of the address you intended to send it to. To ensure that their malicious transaction makes it to the block and not your legitimate transaction, they would pay a higher transaction fee.
=> According to the paper Quantum attacks on Bitcoin, and how to protect against them, quantum computers could break the signature scheme in under 10 minutes (the average time to create a block) as early as 2027. This would make every transaction henceforth vulnerable. This represents the biggest quantum threat to Bitcoin.
If quantum computing already exists then why isn’t anyone using it to steal BTC?
Quantum Computers of roughly 4,000 qubits will be required to break the Bitcoin code. The most powerful Quantum Computers currently existing operate with only about 50 qubits.
Does that mean that once Quantum Computing has advanced to the level where it has 4,000 qubits then that will be the end of cryptocurrencies?
No- The solution is to use quantum-resistant algorithms that cannot be broken even by quantum computing. There are several options available and their pros and cons are being evaluated by the crypto community. Also, while quantum computing is likely to break several of current encryption algorithms, it is also capable of creating hack-proof replacements.
Can someone equipped with a Quantum Computer launch a 51% attack?
To remind the reader, a 51% attack is when someone gains control over 51% of the hashing power and hence controls the blockchain. That someone can control which transactions make it to the blockchain, get all of the block-rewards and transaction fees, approve double-spends, and do other manipulations.
To create the next bitcoin block, one needs to solve a SHA-256 Proof-of-Work hashing problem. There is no algorithm, conventional or quantum, that can reverse engineer SHA-256. So the only way to solve it is “brute force”, which is just a fancy way of saying that you have to keep guessing till to arrive at the right answer. SHA-256 is considered quantum-resistant because the most efficient theoretical implementations of quantum computing are less efficient than ASICS miners (specialized classical computers used to mine bitcoin).
It is possible that with time Quantum Computers will be able to solve SHA-256 hashing problems faster than conventional computers. If that happens more miners will upgrade and adopt quantum computing just like they upgraded from CPUs to GPUs to FGPAs (Field Programmable Gate Arrays) to ASICs (Application-SPecific Integrated Circuits) in the past.
Bitcoin’s proof-of-work consensus mechanism based on SHA-256 algorithm is quantum-resistant but the Elliptical Curve Digital Signature (ECDSA) is not. Cryptocurrencies must migrate to a quantum-resistant signature before quantum computers become a reality. The crypto community is working on alternatives.