What happens to Bitcoin when quantum computers arrive?

Recently announced quantum computing advances have renewed interest in the impact these developments could have on Bitcoin. We provide an overview in a recently published report of the state of quantum computer, its threat to Bitcoin and what steps are being taken. The following post is a brief summary of the key recommendations and findings. You can read the entire report here.

Bitcoin Quantum Computing Preparation Timeline

In response to the possible emergence of quantum computers, we outline a two-track strategy for Bitcoin migration.

• Long-Term PlanThis holistic approach is predicated on the fact that there’s still plenty of time left before quantum computing becomes a real threat. Based on prior protocol upgrade timelines such as SegWit, Taproot and others, we estimate a 7-year transition to a fully quantum-safe system.
• Short-Term Contingency PathThis track is an emergency response for the case of an unexpected quantum breakthrough. The track prioritizes rapid deployments of protective measures for the Bitcoin network, and can be completed in about 2 years.

Both scenarios protect funds from quantum attacks if they are managed carefully, that is, stored with hashed addresses like P2PKH and P2WPKH, without reusing address information. However, to spend those funds post-quantum securely, additional infrastructure would be required. This is anticipated during either the second or third phase.

Quantum Computers – When will they arrive and what can they do?

Quantum computing, if it is implemented at large scales, could provide significant accelerations to specific problems. This would be possible by harnessing quantum mechanics. Cryptographically relevant quantum computer (CRQCs) are machines that can break the mathematical assumptions underpinning modern cryptography. Included in this are algorithms such as Elliptic Curve Cryptography(ECC), which has been fundamental to Bitcoin security. 

CRQCs are a large-scale quantum machine that is still a challenge to construct. To date, quantum computers have not surpassed the performance of classical supercomputers to solve problems that are commercially important, or demonstrated capabilities sufficient to undermine modern cryptography.

Timelines for the CRQC

It is difficult to predict technological progress. The path it takes rarely follows a straight line, and the history of technology offers numerous examples of unexpected breakthroughs. In anticipation of possible shifts in cryptographic landscapes, multiple organizations have suggested timelines for the transition of cryptographic signs.

NIST, the U.S. National Institute of Standards and Technology is a leader in the development of cryptographic standard. They have highlighted two important dates in their published recommendations:

• By 2030Traditional encryption methods like ECDSA and RSA need to be phased out.
• By 2035All cryptographic systems must transition to quantum-free algorithms.

UK National Cyber Security Centre adopts a similar strategy with its three-phase migration plan that will complete the switch to quantum-free cryptography in 2035. The EU and China are working actively on strategies for post-quantum encryption, but they haven’t yet released formal timetables.

 
At the industrial level, many leading companies have adopted post-quantum encryption, such as Cloudflare Signal, Google and others. The hybrid signature scheme combines traditional encryption with post quantum algorithms. This requires an attacker to breach both methods in order to compromise a system. Apple also plans to switch to post-quantum encryption. PQC has become an industry standard and many companies will follow.

What is at Stake

Bitcoin is at risk of serious financial loss. The Fig 2 analysis shows that 32.7% or approximately 6,51,000,000 bitcoins are quantum vulnerable. This is worth more than $700 Billion at the current market value. The funds are held by addresses which have been reusing their address, or funds protected with inherently-quantum-vulnerable types of script. They also include funds vulnerable due to public key disclosure on Bitcoin forks, like Bitcoin Cash. 

Bitcoin: A Threat Model – What should We Worry About?

Bitcoin will be impacted by two areas that quantum computing is predicted to affect: The following are some of the ways to get in touch with each other The following are some examples of how to get started: transaction signatures. The difficulty in combining multiple machines to create a quantum miner gives an unfair advantage to the largest quantum miners. This threatens decentralization. The risk for transaction signatures is direct. A CRQC can derive the private keys of public keys and steal funds. 

These two types of threats have very different timelines. The engineering challenges of building a quantum machine that outperforms modern ASIC miner is far more difficult than building one to break digital signatures. It is largely due to the slow clock speeds of the quantum processors compared with the specialized and highly optimized hardware for Bitcoin mining, and their lack of parallelization.

Signatures

A CRQC would allow attackers to take funds by breaking the belief that it was impossible to obtain a public key using an ECC-based scheme. Signing a transaction using the private key corresponding with a public key is how Bitcoin proves ownership. A CRQC that can deduce the private key using the public key can spend funds and falsely claim to be the owner.

Two different quantum attacks can be performed. Public keys are temporarily revealed when spending funds from hashed-addresses. Attackers have a short window to get private keys, usually minutes or hours. Certain output types, such as P2PK,P2MS and P2TR, expose the public keys on-chain permanently from the time funds are received. This gives attackers an unlimited amount of time to launch quantum attacks. Due to the fact that public keys stay visible on the chain after spending the first amount, the address reuse turns the temporary exposure of hashed addresses permanent. As can be seen in Fig.3, the addresses which hold large amounts of funds, and have exposed public key are most at risk. This includes institutional holdings who practice address reuse.

The mining industry

Bitcoin mining relies on the idea that the likelihood of finding a block is linearly proportional to the computational effort. Grover’s algorithm is a quantum-search technique that offers a quadratic increase in speed for bruteforce search. Grover’s method isn’t easily parallelizable, which makes it different from classical mining. The limitation may give an unfair advantage to those with large, centralized quantum computers. This could lead to a greater concentration of mining rather than a wider participation.

Quantum mining, in addition to centralization concerns, could change miners’ best strategies. For example, it may degrade chain quality by increasing stale block rates. Higher stale-block rates can reduce the cost and feasibility of certain attacks, such as selfish mining.

The development of CRQCs is much further away than building a quantum computing system that can outperform modern ASIC mining machines. Quantum mining, therefore, isn’t a pressing concern. It is also unlikely to pose a real threat within the next few decades. It is worthwhile, however, to continue exploring Proof-of Work in the future quantum context. The ecosystem would be better prepared for the world of quantum mining if it had a greater understanding of potential risks.

What are the major challenges in migration to Quantum Security?

Quantum Secure Signatures

Quantum secure cryptographic signatures were studied by researchers for many decades. But interest in the field and its progress has accelerated over recent years. The development of protocols such as SPHINCS+ or FALCON has been a result. Despite its relative youth, the field has already seen several proposals that initially appeared to be very secure, but which were then broken. The SIKE scheme has been broken by classic computers as well. The field is still active, and the candidates are constantly evolving.

In Table 1, it is shown that post-quantum schemes are significantly more complex in terms of key sizes and signatures, as well as verification times. This compares to the classical algorithms, such ECDSA or Schnorr, which Bitcoin currently uses. In order to address this issue, some suggestions suggest using SegWit’s Witness Discount mechanism in order to reduce footprint on the chain. There is no consensus on the optimal approach to integrating quantum secure signatures with the protocol. Quantum-secure schemes are not fully compatible with classical signatures. These include those used in Lightning Network, and many other applications. The cryptography community continues to focus on this area and expects further improvement in the future.

The Migration Pathways

If Bitcoin chooses to migrate funds that are vulnerable to quantum resistant formats, a significant number of UTXOs would need to be moved. There are several approaches being considered, with each involving different trade-offs. Others focus on the secure use of outputs with hashed addresses without disclosing public keys too early. Some propose methods to regulate or limit the use of UTXOs which are vulnerable to quantum stealing. The strategies require most often changes in consensus rules such as soft-forks. They must also take into account the difficulty of moving a high volume of UTXOs. This can potentially take 4-18 months, even with a sustained allocation of blocks. 

Philosophical Dilemma – Do we let money be stolen?

Bitcoin is facing a basic philosophical issue: should funds that are quantum vulnerable be rendered permanently non-spendable?”burned”Quantum computers can be accessed by anyone (“stolen”)? This decision affects Bitcoin’s key principles such as immutability and censorship-resistance. This approach views quantum vulnerability as a bug in the protocol that requires a conservative solution, preventing wealth from being redistributed to those who are successful at the CRQC race. According to the steal approach, burning money violates property rights and confiscates assets of those who are unaware or cannot migrate quickly.

Market dynamics is more than just a philosophical issue. The coordinated burning of millions of bitcoins would remove them permanently from the market, increasing their value and providing certainty to markets. The ability to steal quantum data allows for massive wealth transfer from entities who possess quantum technology, creating market volatility and uncertainty as the funds are slowly drained. This decision is crucial for the governance of Bitcoin, as it requires that community members balance security concerns with fundamental principles such as user sovereignty and nonintervention.

So, what’s next?

CRQCs will bring a significant shift to the digital world, putting at risk much of our current digital infrastructure, including secure communications, authentication and other digital services. Quantum computing may not be a reality yet, but preparations are being made to ensure Bitcoin is resilient against any future changes. Researchers in the Bitcoin and cryptographic communities continue to explore and assess possible risks. In our report, we highlight two key areas which may require immediate attention. These are: preventing address reuse and evaluating tradeoffs between Burning vs. Discussions about exposed funds.

It is possible that the window of opportunity for taking proactive measures will not last indefinitely. As important as staying informed about quantum computing and encryption is, it is also essential to study mitigation strategies. Starting now, it is important to be thoughtful and deliberate in order to ensure Bitcoin’s future security, especially as we move into a post quantum world.

Clara Shikhelman, Anthony Milton and others have contributed a guest article. The opinions expressed by Clara Shikhelman and Anthony Milton are theirs alone, and not those of BTC Inc. or Bitcoin Magazine.