Quantum Meets Blockchain — Part I
Scalability is the most commonly discussed blockchain challenge. It’s not the only one. With the rapidly increasing chances that a large quantum computer could happen within 10 years, future blockchains will have to be “Quantum-safe”. This first post asses the threat. Protection against this threat and the opportunities for Quantum Blockchains are considered in a second post.
A blockchain is a decentralized growing list of records called blocks, each containing a list of transactions, whose security is ensured by cryptographic algorithms. A new block is added upon completion and validation of a challenge that reaches consensus between all participants.
In the two most common consensus mechanisms, the challenge either relies on racing to be the first to solve a moderately hard computational problem (Proof-of-Work, PoW) or on being randomly selected as verifier depending on how active one participates in the blockchain, which is usually quantified by the amount of tokens possessed (Proof-of-Stake, PoS). In PoW, the successful miner will be rewarded by newly created tokens while in PoS, the selected minter will receive a fraction of the transaction fees.
There are pros and cons to each mechanism. PoW requires a lot of computational power, correlated with a very high and unsustainable consumption of electricity, but provides a high security. PoS is less resource-intensive, offers faster transactions, but is also (as of today) less secure.
Two mathematical disciplines play a fundamental role in cryptocurrencies, game theory and cryptography. Game theory studies logical decisions made by the participants in a blockchain network whereas cryptography ensures the security and provenance of each transaction.
Many blockchains, notably the Ethereum and Bitcoin blockchains, are built around two categories of cryptographic primitives : a hash function for the consensus mechanism and a digital signature based on Public-Key to securely manipulate blocks and transactions.
A hash function maps an input value of arbitrary size called preimage to a finite-size output called hash. Given the preimage, it is very easy to compute the corresponding hash but finding a correct preimage for a given hash require a computational power greatly exceeding our current capabilities.
In a consensus based on hash functions — notably PoW — the authenticity of all past blocks is verified thanks to the hash contained in the current block. Replace a valid block by a falsified one would require the ability to find a correct preimage that outputs this specific hash value. Solving this search problem is difficult for our computers, and that’s what constitutes the safety net, but less so when considering future advances in computational capabilities, Quantum Computing among others.
A digital signature allows to verify the provenance of a message, check that it has not been altered during transit and ensure that its sender cannot deny having sent it — respectively authentication, integrity and non-repudiation. Not only it is widely used in distributed communications, but it also provides the necessary security to safely manipulate components added to the blockchain.
During block validation, security is also ensured by the use of a Byzantine Agreement Protocol that enables the network of distributed participants, some of them being potentially dishonests, to agree about the updated state of the blockchain in a way that the final decision will reflect the decision of honest participants.
How safe are consensus and signatures for blockchains in a world where Quantum Computing is a reality ? For most of them, not so safe.
Grover’s algorithm designed by Lov Grover in 1996 weakens search-based consensus and Shor’s algorithm designed by Peter Shor in 1994 deals a crippling blow to the security of Public-Key algorithms which lie at the core of digital signatures.
Grover’s algorithm would provide a quadratic speed-up in solving search problems with a Quantum Computer, considerably accelerating the discovery of an adequate preimage for a given hash. It has even been proven optimal in the sense that any future quantum algorithm trying to solve this preimage problem will not be able to solve it more quickly.
Grover’s algorithm — a variant for hash functions. Let consider a hash function f, a target hash y and a suitable preimage x amongst n possible inputs. Grover’s algorithm finds with high probability the value x such that f(x) = y in O(√n) evaluations of f where a classical computer would necessitate O(n) evaluations instead. For a hash of length k bits, Grover’s algorithm would provide a speed-up of factor 2k/2.
The security of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) used in many blockchains — including Bitcoin and Ethereum — relies on the unrealistic time that would be necessary to solve the discrete logarithm problem, today’s computers requiring more time that the age of the Universe to find the result. Shor’s algorithm running on a large Quantum Computer would provide an exponential speed-up compared to best known classical algorithms, shifting the unfeasible to feasible and factoring large numbers in a few years or months, maybe even hours.
Shor’s algorithm for integer factorization. Given an integer N = p.q, the algorithm finds its prime factors p and q in polynomial time. Solving the discrete logarithm problem with this algorithm roughly consists in a variant of solving the integer factorization where we look at pairs of integers instead of a single one.
Breaking the digital signature scheme after a transaction could lead to disastrous consequences in blockchain security, especially when considering cryptocurrencies. First, the overall anonymity would no longer be ensured, allowing for identity theft and forcing transactions without the spender knowing it. Secondly, it would be possible to spend the same cryptocurrency twice — double-spending — without being noticed.
Several precautions have already been suggested to counter these vulnerabilities. For example, a fresh address should imperatively be used for every transaction, which is already recommended by several blockchains included Bitcoin but not often performed in practice. The time available to run a Quantum attack must also be considered ; in the Bitcoin design, the security is weak from the time a transaction is broadcasted until it is validated and followed by new blocks.
Similarly to classical algorithms, a quantum algorithm sequentially applies elementary operations — quantum gates — to modify the states (qubits) before measuring them and retrieving the desired result. In practice, each of these operations slightly deviates from the ideal model, resulting in an erroneous qubit that doesn’t perfectly correspond to the target. The overall amount of errors introduced by applying all the gates to the qubits must be limited and controlled, which is why we need to correct these errors as much as possible.
Classical Error Correction techniques consist of adding extra information — redundancy — that enables recovery of the target information despite errors occurring during the transmission. In Quantum Error Correction (QEC), several « erroneous » physical qubits simultaneously hold the information that should be contained in one « perfect » logical qubit. It is still hard to evaluate the overhead for practical quantum computer and that depends on many factors but, just to give an order of magnitude, Fault-tolerant Quantum Computers using QEC could require as much as 1,000 to 100,000 physical qubits to emulate one single logical qubit.
In “Quantum attacks on Bitcoin, and how to protect against them”, the authors provide a detailed analysis on the feasibility of attacking 1) a Bitcoin PoW based on a double SHA-256 hash function with Grover’s algorithm and 2) a Bitcoin digital signature secured by a 256-bit Elliptic Curve algorithm (ECDSA) with Shor’s.
Both attacks use 2300 to 2400 logical qubits and are limited by their requirements in term of the number of quantum gates that are quite slow to perform with a quantum computer based on superconducting qubits. When finding a preimage associated to a hash with Grover, this low speed negates the quantum speedup and results in a hashing power lower than what is and will be achieved with specialized ASIC hardware. But unlike the Bitcoin PoW that offers an acceptable resistance to quantum attacks, a Bitcoin digital signature can be cracked with Shor’s algorithm in less than 30 minutes with this kind of machine.
The authors estimate that a Quantum Computer powerful enough to break Bitcoin’s signature protocol in less than 10 minutes — Bitcoin’s block time length — may be available as soon as 2027. If so, a quantum attacker could recover the secret key corresponding to a given public key and use it to insert forged transactions in the current block, successfully stealing bitcoins from the owner.
These estimations hold in the context of our current technological capabilities but could change drastically depending on future progress in Quantum hardware and algorithms design, e.g. with more efficient Quantum Error Correction codes, or with new approaches.
Of interest, instead of waiting for a Quantum Computer large enough to implement algorithms that require perfect qubits, the community has been focusing its efforts lately on algorithms that would run on « imperfect » devices, without error correction, and still achieve a benefit, even if modest. These are the Quantum computers that are currently being built, so-called Noisy Intermediate-Scale Quantum (NISQ) computers, with qubit counts expected to be in the 100–500 range within 2023.
For example, a variant of Shor’s algorithm, the Variational Quantum Factoring (VQF) algorithm, combines classical pre-processing with the Quantum Approximate Optimization Algorithm (QAOA) to decompose in prime factors a given integer with a NISQ computer, making the Quantum threat toward blockchains much more real in a near future.
Quantum Computing implementations are still at an early stage and current architectures do not provide a quantum advantage compared to fast ASIC or GPU mining-dedicated hardware, but the emergence of Quantum Processors should not be taken lightly by the Blockchain community.
Blockchain and Quantum Computing are emerging technologies. The current architectures of Bitcoin and Ethereum are not optimal by far for mainstream adoption and now is a good point to start thinking about future “quantum-safe” blockchains and cryptocurrencies, with new signature schemes and consensus mechanisms.
The second post in this series will address classical and quantum protections against the quantum threat. Stay tuned !
