How Quantum-Secure is Ethereum?
Ethereum is one of the most popular blockchains in the world today. With the advances being made in quantum computing, and with Praxxis founder David Chaum speaking this week at Ethereum’s Devcon5 conference, the Praxxis team evaluates how secure Ethereum’s cryptography is against a quantum attack.
By The Praxxis Team, October 7, 2019.
This post is part of a series on quantum computing. To make sure you don’t miss a post from Praxxis, download the xx collective app to receive updates on your smartphone.
Ethereum is one of the most popular blockchains in the world today. Having described how quantum computers work, and how quantum computing threatens blockchain cryptography, we can make these ideas more concrete by examining how vulnerable Ethereum is to a quantum-capable adversary. This topic is especially relevant this week as the Ethereum Foundation hosts Devcon5 in Osaka, Japan, where Praxxis founder David Chaum will be speaking on Thursday.
What is Quantum Computing?
Unlike standard binary computers, which are built on bits, the building blocks of quantum computers are qubits. Qubits are made with materials subject to quantum mechanics, such as electrons, which means that a qubit can represent 0, 1, or any superposition of these two states. Qubits also interact with each other through quantum entanglement, so that a quantum computer with X qubits can be in a superposition of up to 2X states simultaneously.
Most cryptographic systems are built on a difficult mathematical problem (their cryptographic primitive) that would take a binary supercomputer a massive amount of time to solve. The superposition feature of quantum computers opens a potential shortcut to solving the mathematical problem, and therefore breaking the cryptographic system. Shor’s algorithm and Grover’s algorithm are two pathways to radically weakening much of today’s cryptography.
These pathways are no longer theoretical; both Shor’s and Grover’s algorithms have been demonstrated on tiny quantum computers. In addition, reports indicate that Google has recently achieved quantum supremacy, meaning that they used a 53-qubit computer to complete in 3.5 minutes a task that would have taken a binary supercomputer 10,000 years to complete.
Quantum Attacks on Ethereum’s Proof of Work
Like many blockchains, Ethereum has two significant limitations against an adversary equipped with a quantum computer: Ethereum’s proof of work (PoW) hash function, and the algorithm used to produce Ethereum signatures.
Ethereum is currently a PoW blockchain, although there are plans to transition to a proof of stake (PoS) system in the future. PoW systems require nodes or miners to solve a mathematical problem to produce each block in the chain and confirm transactions. The difficulty of the problem gives many different miners a decent probability of producing any given block, creating a system of checks and balances to protect against a miner trying to forge the record of transactions.
Ethereum’s PoW algorithm is known as Ethash and built on the Keccak hash function, which became SHA3, published as a NIST hash standard in 2015. The security of Ethash, like many hash functions, is weakened by a quantum computer using Grover’s algorithm to reduce the computational power necessary to break the algorithm. If the time needed for a traditional brute force attack is 2d, a quantum computer could reduce this to 2d/2 or 2d/3. While this approach could allow a quantum-capable adversary to out-perform other Ethereum miners, pursuing a 51% attack, the advantage provided by quantum computers is limited. Instead, an adversary would be more likely to focus on Ethereum’s signatures.
Quantum Attacks on Ethereum Signatures
The second attack pathway is the algorithm used to produce Ethereum signatures. Ethereum uses the Elliptic Curve Digital Signature Algorithm (ECDSA) to produce signatures, which validate the origin and integrity of messages and payments on the blockchain. This setup is very similar to the Bitcoin blockchain, and uses the same ECDSA algorithm, the secp256k1 curve.
ECDSA is a form of Elliptic Curve Cryptography (ECC), which uses an elliptic curve algorithm as its cryptographic primitive. This algorithm is computationally difficult because it is built on the time-consuming Discrete Logarithm Problem . However, this cryptography is vulnerable to Shor’s algorithm, which introduces a bigger speedup than Grover’s algorithm, thus representing a more likely angle of attack for an adversary.
If a quantum-capable adversary used Shor’s algorithm to successfully attack ECDSA, they would fundamentally undermine the signature and wallet system of most blockchains, including Ethereum. Doubts about the integrity of signatures and wallets would be very dangerous to the stability of the blockchain. The speed with which the adversary could crack signatures would depend on the size of the quantum computer, but even a relatively slow attack would be of concern. Fortunately, the Ethereum community has foreseen this threat and has identified some solutions.
What Steps Should Ethereum Take?
Ethereum is not defenseless against quantum computing adversaries. Ethereum is pursuing a multi-year roadmap known as Ethereum 2.0 (Serenity), which aims to shift Ethereum from PoW to a PoS system known as Casper. While Casper is currently based on ECC and thus vulnerable to Shor’s algorithm, a core researcher at Ethereum has stated that Casper may be upgraded to a quantum-resistant algorithm “in the three-to-five-year time horizon.” And Ethereum’s signatures could also be upgraded; Ethereum co-founder Vitalik Buterin has suggested that if quantum computing becomes a greater threat, the Ethereum blockchain can move to Lamport signatures.
The Praxxis team believes that these important efforts should be prioritized by the Ethereum community. We should not assume that all advances in quantum computing will be made public. In fact, much of the value that an adversary would gain from breaking a cryptographic system relies on secrecy. Given the importance and value of the work that the Ethereum community has accomplished over the years, there are strong incentives for funding the development of quantum computers for cryptanalysis.