1.7 million legacy Bitcoins, 9-minute attack window: Quantum computing is spurring a wave of "lock replacement"

What if one day, others could infer your payment password just by knowing your bank card number? What would happen?

The quantum computing risk that Bitcoin faces follows roughly this exact logic.

Today, Bitcoin can operate securely because each wallet has a pair of "keys": one is called the public key, which can be made public; the other is called the private key, which must be kept only by yourself. Under normal circumstances, even if others know your public key, it is almost impossible for them to calculate the corresponding private key. Therefore, as long as the private key is not leaked, it is extremely difficult for others to transfer your money away.

However, quantum computing brings a major problem. In the future, if quantum computers are powerful enough, they can use a method called Shor's algorithm to derive the private key from the public public key. In other words, a wallet that previously required "stealing the key" to open may in the future only need a glance at the "lock" to recalculate a usable key.

This is exactly where quantum computing truly threatens Bitcoin. If others can also calculate your private key, how can you prove that this Bitcoin belongs to you?

In the past, this problem was always considered far from reality. Theoretically, quantum computing can indeed break the cryptographic system used by Bitcoin, but it was widely believed that building such a machine would require an astonishingly large scale.

In March this year, a paper from researchers at Google Quantum AI, Stanford, UC Berkeley and the Ethereum Foundation changed this judgment. This 57-page paper recalculated exactly how large a quantum computer would be needed to attack Bitcoin in the future?

The result given by the authors is that breaking the secp256k1 cryptographic system used by Bitcoin may only require about 1200 to 1450 logical qubits. Under one of their assumed superconducting quantum computing architectures, the number of physical qubits required could even drop to less than 500,000.

What is even more notable is a figure: 9 minutes. According to the model in the paper, a sufficiently powerful and fast quantum computer in the future may be able to derive the private key from the public public key in approximately 9 minutes.

Worse still, some coins do not have any way to actively "change the lock". For example, a large amount of Bitcoin left over from the Satoshi era has not been moved for more than ten years, and the private key may even have been lost long ago. If quantum computers can recalculate these private keys in the future, these Bitcoins that have been dormant for many years can suddenly be accessed again.

Therefore, what is truly worth discussing about this paper is not only focused on "Will quantum computing crack Bitcoin?", but also raises a series of deeper questions:

• Why can quantum computing threaten cryptocurrencies?
• How powerful a machine is needed to carry out a real quantum attack?
• How exactly will Bitcoin be attacked?
• Why does Ethereum face more complex risks than Bitcoin?
• All the problems stem from ECDLP, so why not just switch to PQC directly?
• If millions of dormant BTC cannot be migrated, what should we do in the end?

With these questions, let's see how this paper answers them.

01

Why can quantum computing threaten cryptocurrencies?

This paper does not focus on where quantum computers outperform classical computers in computing power, but discusses a more specific cryptographic problem.

The security of a large number of modern blockchains relies on the Elliptic Curve Discrete Logarithm Problem, namely ECDLP, which is very difficult to solve on classical computers.

The Cryptographically Relevant Quantum Computer (CRQC) will threaten the existing public key cryptographic system. The problem faced by RSA comes from Shor's algorithm's efficient quantum solution to integer factorization, while the problem faced by Elliptic Curve Cryptography (ECC) comes from Shor's algorithm being able to solve ECDLP efficiently.

This has a very direct relationship with cryptocurrencies. Blockchains such as Bitcoin and Ethereum make extensive use of digital signatures built on top of ECDLP.

The core of most cryptocurrencies' security is built on a basic assumption, that ECDLP is extremely difficult to solve. Specific blockchain functions that rely on this hardness assumption include transaction verification for Bitcoin and Ethereum, as well as the Proof-of-Stake (PoS) consensus mechanism of Ethereum.

Based on these estimates, the paper discusses two possible CRQC evolution scenarios, which will serve as the basis for the subsequent discussion of potential mitigation strategies. In particular, how fast early CRQCs can complete attacks will directly determine which blockchain vulnerabilities can be realistically exploited, and thus determine which intermediate mitigation measures should be prioritized before fully migrating to PQC.

According to the required execution speed of the attack, and whether each attack needs to access the CRQC, or only needs to use the CRQC once to prepare a universally reusable attack tool, quantum attacks are divided into three categories:

1. On-Spend Attacks: Target transactions that are being transmitted and have not yet been finally recorded on the blockchain. After a blockchain user broadcasts a transaction, the attacker must derive the private key within the allowed time window before the transaction is recorded by the blockchain. This requires the quantum computer to be able to solve ECDLP within the transaction settlement time of the target blockchain. The settlement time of different blockchains ranges from hundreds of milliseconds to several minutes, for example, Solana is about 400 milliseconds, Ethereum is about 12 seconds, and Bitcoin averages about 10 minutes. On-spend attacks are also known as "short-range attacks" or "just-in-time attacks".

2. At-Rest Attacks: Target public keys that have been exposed on-chain or off-chain for a long time, such as dormant wallets that reuse keys. In this scenario, the attacker has several days or even longer to derive the private key. At-rest attacks are also known as "long-range attacks" or "long-exposure attacks".

3. On-Setup Attacks: Target fixed public protocol parameters, with the goal of creating a universally reusable backdoor in a cryptographic protocol. The attacker only needs to use the CRQC to perform one offline quantum calculation to construct the backdoor, and then use a classical computer to carry out attacks with this backdoor later. For example, an attacker could use Shor's algorithm to recover the so-called "toxic waste" that should have been destroyed in the Powers-of-Tau trusted setup ceremony. The Bitcoin blockchain itself is immune to on-setup attacks, but some scaling solutions, such as Ethereum's Data Availability Sampling mechanism, and some privacy protocols, such as Tornado Cash, will be affected by this particularly hidden and dangerous attack pattern.

It should be pointed out that quantum attacks on cryptocurrencies can also be classified in other ways. For example, they can be further subdivided according to the damaged security attribute:

• Asset ownership attacks, such as forging transactions in Bitcoin;

• Consensus attacks, such as performing deep blockchain reorganization after compromising more than half of Ethereum validators;

• Confidentiality attacks, such as breaking the unlinkability between diversified addresses of Zcash;

• Currency integrity attacks, such as illegally creating new coins in Mimblewimble or vulnerable Ethereum zk-rollups;

• Solvency attacks, such as causing anchor collapse through illegal Rootstock redemptions or stablecoin redemptions, or silently draining the Tornado Cash anonymity pool;

• Data availability attacks, such as forging Ethereum's data availability sampling proofs;

• Governance attacks, such as forging votes for Cardano or Ethereum Decentralized Autonomous Organizations (DAOs), or taking over cross-chain bridge assets controlled by multi-signatures.

Bitcoin and Ethereum transaction verification, Ethereum's PoS consensus, etc., all rely on this assumption to varying degrees.

Taking Bitcoin as an example, its basic asset unit is UTXO. Whether a UTXO can be spent requires the spender to submit a valid digital signature that matches the corresponding public key; generating a valid signature requires mastering the corresponding private key. Therefore, the paper summarizes Bitcoin's cryptographic ownership relationship very directly. In the cryptographic sense, owning bitcoin means mastering the private key corresponding to the public key that locks these bitcoins.

And the fundamental change brought by CRQC lies right here. Once the public key is already public, CRQC can use Shor's algorithm to derive the corresponding private key by solving ECDLP.

The paper therefore believes that this will fundamentally shake Bitcoin's current ownership model built on cryptographic hard problems.

Why are cryptocurrencies particularly worthy of attention?

First, many blockchains rely heavily on ECDLP-based cryptographic systems for efficiency and scalability. At the same security level, this type of cryptographic system requires a key length nearly an order of magnitude smaller than RSA, so the size of CRQC required to crack them is also smaller.

Second, traditional finance usually has multi-layer security protection and transaction traceability mechanisms, while blockchains often lack the ability to trace fraudulent transactions. The paper clearly points out: A successful digital signature forgery can lead to irrecoverable asset theft.

Therefore, strictly following the logic of the paper, the threat of quantum computing to cryptocurrencies can be summarized as:

ECDLP is the underlying hard problem for digital signature security. Shor's algorithm can solve ECDLP efficiently on CRQC, the exposed public key may be used to recover the private key, and attackers can generate legal digital signatures, threatening the existing mechanism of proving ownership with private keys.

However, the paper also specially emphasizes that it cannot be deduced that "quantum computing can easily break all parts of the blockchain". Different protocols and functions have different quantum resilience. For example, the paper believes that Bitcoin's PoW consensus itself is not a realistic quantum attack target at this stage.

02

How powerful a machine is needed to carry out a real quantum attack?

This paper expounds a very important view: To measure a quantum computer that can attack secp256k1, you cannot only look at "how many qubits it has".

The reason is that for the n-bit ECDLP problem, the comparison of the existing most advanced Shor's algorithm compilation schemes is not simple, because there is a key space-time tradeoff. On the one hand, it is the number of logical qubits, which determines how large the CRQC required to launch a quantum attack must be, and on the other hand, it is the number of Toffoli gates.

When executing Shor's algorithm fault-tolerantly, Toffoli gates usually dominate the overall resource cost and determine the total running time of the algorithm, so they also directly determine whether on-spend attacks are feasible. The lowest number of logical qubits in the current public literature comes from a recent preprint by Chevignard et al.: for n=256, they estimate that only about 1100 logical qubits are needed (asymptotically 3.12n+o(n)).

However, such a small logical quantum storage space comes at the cost of more than 100 billion Toffoli gates. Such a huge number of gates means extremely high running time and also requires a large number of physical qubits. Because the actual number of physical qubits required depends on both the number of logical qubits and the number of circuit gates.

At the other extreme, the result with the lowest number of Toffoli gates in the previous public literature is roughly from Litinski, which is about 200 million Toffoli gates. It should be noted that the title of that paper says 50 million instead of 200 million, because it includes some optimizations that can reduce the amortization cost of multi-instance solving, and what this paper focuses on is single-instance attack. The price Litinski's scheme pays for reducing the number of Toffoli gates is that the number of logical qubits is more than twice that of Chevignard et al.'s scheme. After further accounting for quantum error correction overhead, Litinski's scheme is expected to require about 9 million physical qubits on the photonic quantum computing architecture.

This paper reports that the team has developed a logical quantum circuit for cracking elliptic curve ECDLP over finite fields: for the case where the prime modulus length and group order are both n bits, its space overhead is about 4.5n. The paper gives the resource requirements of the two schemes under different n values: one optimizes the number of qubits, and the other optimizes the number of gates.

When n=256, the two circuits respectively require:

• 1200 logical qubits + 90 million Toffoli gates; or

• 1450 logical qubits + 70 million Toffoli gates.

If measured by spacetime volume, which is a key resource indicator that particularly affects quantum error correction overhead, then when solving a single ECDLP instance, our estimation is about an order of magnitude improved compared with the previous most efficient scheme. This is exactly the resource estimation verified by the ZK proof mentioned earlier. The conclusion can be directly applied to ECDLP on secp256k1; this elliptic curve is widely used by mainstream blockchains such as Bitcoin and Ethereum for digital signatures.

Figure 1.

Under the standard assumptions for superconducting qubit hardware, such as planar degree-four connectivity, a physical error rate of 10⁻³, and running a variant of the surface code architecture similar to the assumption, it is calculated that the above quantum circuit can be executed on less than 500,000 physical qubits.

The reason why this estimate has dropped significantly is, on the one hand, that the optimized logical circuit size is smaller, which reduces the quantum error correction overhead; on the other hand, it uses a high-density surface code configuration protected by "yokes" to store logical qubits in a more efficient way.

To estimate the actual wall-clock running time of the circuit, the authors assume that the quantum computation is performed in a reaction-limited manner, that is, the execution speed is mainly limited by the reaction time of the control system. If we assume that the control system reaction time is 10 microseconds, which is a standard value commonly used for superconducting qubits [100], and assume that each Toffoli gate has an additional overhead of 50%, then executing 70 million or 90 million Toffoli gates on a superconducting CRQC will take about 18 minutes or 23 minutes respectively. This time is already close to Bitcoin's average block generation time of 10 minutes.

If we consider that the quantum computer can pre-calculate the first half of the algorithm in advance, on-spend attacks will be even faster. The first half of the algorithm only depends on the protocol parameters shared by all addresses, so the quantum computer can pre-calculate and remain in a "primed" state, waiting for the target public key to appear. In this way, the time from when the public key is exposed to when the corresponding private key is derived can be cut in half.

Therefore, calculated from the time the attacker obtains the public key and starts calculating from the primed state, the on-spend attack is expected to only take about 9 minutes or 12 minutes. This means that a superconducting CRQC capable of performing at-rest attacks on static assets on the chain is very likely to also be able to perform on-spend attacks on active transactions.

As will be further discussed later, it is not believed that scaling from 1200 logical qubits to 1450 logical qubits will create significant additional scaling obstacles. To simplify subsequent discussions, this paper therefore assumes that the first-generation fast-clock CRQC can solve ECDLP on secp256k1 and similar elliptic curves on average in about 9 minutes.

If the attacker has multiple machines that are already in the primed state, this time can be further shortened. If 11 primed machines are used to launch attacks in parallel, each machine only needs to perform 32 elliptic curve point additions, instead of the 208 times required by a single primed machine, and an acceleration of about 6.5 times can be obtained.