TL;DR
- Cryptocurrencies are digital money systems powered by blockchain technology. While not all the same, all cryptocurrencies share a vulnerability to quantum attacks.
- This post discusses the potential threat quantum computers pose while determining the risk exposure and security of some of today’s cryptocurrencies.
- The post also presents some post-quantum digital signature schemes for building blockchains that can survive the Quantum Era.
Citation
- [1] Vulnerability of Blockchain Technologies to Quantum Attacks by Joseph J. Kearneya, Carlos A. Perez-Delgado. https://arxiv.org/pdf/2105.01815.pdf
- [2] The Future of Cryptocurrency Blockchains in the Quantum Era by Sarah Alghamdi and Sultan Almuhammadi. 2021 IEEE International Conference on Blockchain (Blockchain). IEEE, 2021.
- [3] Assessment of Quantum Threat To Bitcoin and Derived Cryptocurrencies by Stephen Holmes, Liqun Chen. https://eprint.iacr.org/2021/967.pdf
Background
Introduction
In 1994, Peter Shor, creator of Shor’s Algorithm, demonstrated how quantum computers could crack cryptosystems in exponentially faster time than classical computers. The faster computation is because Shor’s algorithm runs on polynomial time. As quantum capabilities advance and blockchains scale to secure billions of dollars of assets, the threat of quantum attacks increases exponentially.
Understanding blockchain’s current level of vulnerability is critical to helping mitigate the risk of losing assets on the blockchain through quantum hacking. It will also help identify what blockchains need to survive the quantum era.
Terminology
Shor’s algorithm:
A quantum computer algorithm for finding the prime factors of an integer. It was developed by American mathematician Peter Shor in 1994 and is the most famous quantum algorithm. Its popularity is due to the fact that it leverages quantum computers’ ability to calculate huge values in exponentially less time.
Discrete Logarithm Problem: Discrete logarithms are mathematical problems defined by multiplicative cyclic groups. They are the basis of public key cryptography security because of the assumption that no efficient method can compute them in general.
ECDSA (Elliptic Curve Digital SIgnature Algorithm): A Digital Signature Algorithm (DSA) which uses public/private keys derived from elliptic curve cryptography (ECC). In the ECDSA algorithm, n is the size of the private signature key and they are based on the algebraic structure of elliptic curves over finite fields.
ECDLP (Elliptic Curve Discrete Logarithm Problems): A unique form of the discrete logarithm problem in which elliptic curves are used for cryptography. ECDLP is the basis of elliptic curve cryptography and rests on the assumption that the problem is hard to compute.
Research Question
When will quantum computing be powerful enough to execute Shor’s algorithm? What can be done to protect blockchains from the Quantum Era?
Summary
Potential Threats and Risk Exposure
Quantum computers drastically reduce the time needed to solve some computational issues. There are two main quantum algorithms relevant to our discussion:
- Shor’s algorithm
- Grover Search algorithm
Shor’s algorithm factors large integers and computes logarithms in polynomial time. The Grover Search algorithm is based on generalizations, searching for the transaction hash codes and solving NP-complete problems. Between the two, Shor’s algorithm is the more significant threat as its computational speed is exponential.
Any blockchain solely relying on integer factorization or discrete log problem (DLP) is completely vulnerable to quantum attacks running on Shor’s algorithm. On the other hand, Grover’s algorithm computes hash functions quadratically, implying that the blockchain can resist attacks by doubling the size of the key.
Blockchains use signature schemes like Elliptic Curve Digital Signature Algorithm (ECDSA) to sign each transaction. This signature is linked to the user’s public/private key pair from which they created their account. ECDSA uses Elliptic Curve Cryptography - a cryptography system based on the algebraic structure of elliptic curves over finite fields. The signature scheme also relies on how difficult it is to solve discrete logarithm problems.
It is worth noting that ECDSA provides the same level of security compared to other schemes, even though it uses smaller keys. For instance, 256 bits when compared to 2048 bits of RSA. These two features make ECDSA ideal for blockchains. Unfortunately, the same features - reliance on discrete logarithm problems and smaller keys - also expose blockchains to quantum attacks.
Quantum computers drastically reduce the time needed to solve some computational issues. There are two main quantum algorithms relevant to our discussion:
The first is Shor’s algorithm that factors large integers and computes logarithms in polynomial time. The second is the Grover Search algorithm based on generalizations, searching for the transaction hash codes and solving NP-complete problems. Between the two, Shor’s algorithm is the more significant threat. As mentioned in the “Terminology” section, the algorithm’s computational speed is exponential.
Any blockchain solely relying on integer factorization or discrete log problem (DLP) is completely vulnerable to quantum attacks running on Shor’s algorithm. On the other hand, Grover’s algorithm computes hash functions quadratically, implying that the blockchain can resist attacks by doubling the size of the key.
Cryptocurrencies Vulnerable to Quantum Attacks
This discourse’s primary purpose is for us to understand the vulnerability level of existing blockchains to quantum attacks. For example, many blockchains like Bitcoin, Ethereum, Litecoin use digital signatures based on Elliptic Curve Discrete Logarithm Problems (ECDLP). Note that a cryptocurrency may use other signature schemes with ECDLP. However, they’ll still be vulnerable to the same quantum attacks due to ECDLP.
Below we look at Bitcoin, Ethereum, and Litecoin and their vulnerability levels. And how long it would take a quantum computer to break the system.
Bitcoin
Bitcoin and all its related cryptocurrencies are at risk of quantum attacks. As mentioned above, Bitcoin uses ECDSA. It has been speculated that a quantum computer of appropriate scale running Shor’s algorithm could break ECDSA in polynomial time. The attack would involve monitoring the public key to find its private key after the transaction is made. With the private key, the attacker can sign new transactions.
Bitcoin uses UTXOs - unspent transaction outputs - for transactions. Once the user initiates the transaction, the network records and deletes each input, and new outputs are created for the next transaction. In the case of quantum attacks, the attacker can “steal” transactions and direct the newly created UTXO to any account they choose.
A quantum computer with a computing power of 485550 qubits, using Shor’s algorithm and running at a clock speed of 10GHz, could complete this attack in 30 minutes. The attack’s success depends on how long the network takes to add new transactions to the block. If each attack falls within 30 minutes (typical for Bitcoin), the attacker could successfully move money before the network notices.
Another thing worthy of note is that early Bitcoin users and miners were paid directly to their public key (P2PK) instead of to the hash of the public key. As a result, these accounts are highly vulnerable to the attacks discussed earlier. The extreme vulnerability is because there is no time limit for the attack. Once a sufficiently large quantum computer is developed, an attacker can easily calculate each account’s private keys, sign new keys (to impersonate the owners) and empty all the funds.
Ethereum
The Ethereum network will soon transition from its current Proof-of-Work consensus mechanism to Proof-of-Stake. PoS’ security relies on users staking Ethereum to gain voting and consensus power. That said, EthHash is currently the PoW mechanism used to secure Ethereum. In Ethereum transactions, there is no “from” field. That makes each public key K associated with the account unknown. You can, however, recover it by reconstructing the key from another user’s transaction signature.
Like Bitcoin, a quantum attacker with a large enough memory can use Grover’s algorithm to attack EthHash. While calculating Ethereum’s risk exposure, the authors discovered the network has a minor advantage with its shorter transaction processing time [1, p.8].
However, Ethereum’s use of account-based transactions eclipses this advantage. For context, every outgoing transaction must be signed using the account’s private key. Once an attacker finds the private key responsible for the transactions, they can access the user’s entire account balance.
That said, even without any advances in ASIC technology, a quantum attacker would need a clock speed of about 5THz before they can attempt a 51% attack on Ethereum (which would still not be successful)[1, p.8].
Litecoin
Litecoin is a fork and lighter version of Bitcoin with some differences. The network has a shorter block time - 2 minutes - and less power consumption for mining due to its different PoW method known as Scrypt. Because Litecoin uses ECDSA, the cryptocurrency is vulnerable to all the quantum attacks mentioned above, especially on unprocessed transactions. But, Litecoin possesses the advantage of a shorter block time and throughput compared to Bitcoin.
This advantage gives Litecoin some resistance against such quantum attacks. But just like Ethereum, the advantage is minor given that with an increase in clock speed, a quantum computer would be capable of attacking Litecoin. It is worth noting that this analysis applies to all altcoins based on the Bitcoin blockchain source code - hard forks and source code forks. In summary, Litecoin has the same quantum vulnerabilities due to its similarities to Bitcoin.
Monero
Monero is a privacy-focused blockchain where transactions are untraceable. The blockchain uses Ring Confidential Transaction (RingCT) to hide the transaction details and the sender’s public key. Monero also uses Edwards Curve Digital Signature Algorithm (EdDSA), based on the discrete logarithm problem. Like ECDSA, EdDSA is vulnerable to quantum attacks. But according to an update (RandomX)[1, p.10], in Monero’s consensus protocol, the blockchain is more resistant to 51% attacks using Grover’s algorithm.
Grin
Grin is another privacy-focused blockchain similar to Monero as it uses Pedersen commitments - a form of discrete logarithm - to hide/obfuscate transaction details. Grin is also in danger of quantum attacks because of its privacy mechanism and use of signature schemes. However, while the attacker can remove the obfuscation, they won’t know if the transactions are important enough for attacks.
Other cryptosystems and blockchains vulnerable to quantum attacks are Beam and Zcash. Both are also privacy-focused blockchains that keep network transaction details private and untraceable. And their vulnerability is also linked to their use of elliptic curves and discrete logarithm problems.
How Long Will It Take?
Now we know why these cryptocurrencies are vulnerable to quantum attacks. How long will it take for a quantum computer to launch a (successful) quantum 51% attack?
Let’s first consider Moore’s Law for an estimate of resources. Bitcoin’s network hash rate is currently about 1.96 x 108 hashes (H/s) per second, while quantum computers start at 40 Mhz. With both increasing over time as dictated by Moore’s law, we have an estimated 27 years until a single quantum computer can successfully launch a 51% attack. This estimate, however, is conservative because quantum computers are still in their infancy, and we can expect them to grow faster in the coming years.
Following the law, running a quantum search algorithm (assuming no error correction) on SHA-256 hashes would require about 512 qubits. Major quantum computer manufacturer IBM predicts such quantum computers will be in the market by 2023. We also consider today’s reported quantum computer clock speeds. With this data, we can expect a quantum attacker using Grover’s algorithm to compute about 1.6 x 1015 H/s.
Earlier, we considered the vulnerability and risk exposure of existing cryptocurrencies like Bitcoin & Ethereum to quantum computer attacks. The two cryptocurrencies represent 59% of the industry, with a current total market cap of 567 billion.
Therefore, the focus is on protecting their vulnerabilities while designing post-quantum digital signatures that will replace ECDSA.
It is worthy to note that we already have cryptosystems that can withstand quantum attacks. Their resistance is due to the digital signatures used in building them, which known quantum algorithms cannot compute. They are in the table below:
| Digital Signature | Blockchain | Market Cap |
|---|---|---|
| CURL-P | IOTA | $799,630,249 |
| WOTS+ | Mochimo | $420,821 |
| XMSS (eXtended Merkle Signature Scheme) | Quantum Resistant Ledger | $13,634,974 |
| Signature Chains | Nexus | $11,247,965 |
| Ring LWE | HyperCash | $6,026,602 |
| Multi-Signature | Cellframe | $7,509,372 |
The third category includes recently designed quantum-safe cryptocurrency blockchains but not implemented yet. They are included in the table below:
| Signature | Cryptocurrencies |
|---|---|
| SPHINCS-256 | Corda |
| XMSS, WOTS+ | Bitcoin PostQuantum |
Estimations
Although quantum computing is in its early stage must overcome many issues, companies are working hard to increase quantum computing capacity.
This nearness to the Quantum Era has made researchers calculate and estimate when a quantum computer could completely break ECDSA. According to Divesh Aggrawal, “Quantum attacks on Bitcoin, and how to protect against them” could be as early as 2027. Michel Mosca, author of “Cybersecurity in an era with quantum computers: Will we be ready?” estimates that a quantum computer capable of breaking RSA with 2048 bits in the year 2031 with a 50% chance. Joseph Kearney, on the other hand, estimates this will be possible by 2035.
Actionables: Avoiding Quantum Attacks
Not all cryptocurrencies are equal to quantum attackers. Different timing attack vulnerabilities and user behavior increase the cost of an attack.
-
Users can migrate to a one-time address, which protects the public key from a quantum computer with low clock speed.
-
A multi-signature address will also raise the bar for attackers. Recall n as the number of signatures required to unlock the address/key, and it takes up to 20 n of signatures to unlock an address in Bitcoin. The user can increase the resources required for the attack as it will take longer to compute in the same unprocessed transaction window.
-
Paying a higher gas fee for a transaction incentivizes miners to process it faster, which reduces the risk of a denial of processing transactions attack.
The industry should also implement a few practices:
- To reduce the ever-present risk of the 51% attack, new blockchains should be built on post-quantum cryptography. These new blockchains should also avoid using PoW for consensus and should instead use PoS or any other consensus that is not based on hash searching.
- There is a need for a quantum-safe blockchain that supports smart contracts. This blockchain will ensure easy startup of other quantum-safe cryptocurrencies in the future.
- IOTA and other post-quantum blockchains using hash-based digital signatures should increase the key sizes to resist attacks running on Grover Search algorithm.
- Classical blockchains should upgrade to post-quantum signature algorithms like NIST’s lattice-based algorithms. This upgrade is possible because the blockchain’s signature scheme is modularized, meaning developers can replace them upon core update.
Further Reading
- P. W. Shor, “Algorithms for quantum computation:
Discrete logarithms and factoring,” in Proceedings 35th annual symposium on foundations of computer science, pp. 124–134, Ieee, 1994. - F. Ma, M. Ren, Y. Fu, M. Wang, H. Li, H. Song, and Y. Jiang, “Security reinforcement for ethereum virtual machine,” Information Processing & Management, vol. 58, no. 4, p. 102565, 2021.
- X. Li, P. Jiang, T. Chen, X. Luo, and Q. Wen, “A survey on the security of blockchain systems,” Future Generation Computer Systems, vol. 107, pp. 841–853, 2020.
- J. Fernando, “Bitcoin vs. litecoin: What’s the difference?.” https://www.investopedia.com/ articles/investing/042015/ bitcoin-vs-litecoin-whats-difference.asp,
- S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,”: https://bitcoin.org/bitcoin.pdf, 2008.
- Coinmarketcap: https://coinmarketcap.com/
- P. Zhang, L. Wang, W. Wang, K. Fu, and J. Wang, “A blockchain system based on quantum-resistant digital signature,” Security and Communication Networks, vol. 2021, 2021.
- Joseph Kearney, Dan Bard, Carlos Perez-Delgado, “Quantum advantage on proof of work”
- Evaluating cryptocurrency security and privacy in a post-quantum world
Adam Corbo, Mitchell “Isthmus” Krawiec-Thayer, Brandon G Goodell
