Will Quantum Computing Break Bitcoin?

By River - @River

PlebUnderground is not affiliated or were not paid to run this article. We wanted to provide and interesting take on this subject. River is a Bitcoin only exchange that has been around for years.

The rise of quantum computing has drawn attention to its potential impact on Bitcoin. As this field develops, many Bitcoiners are wondering if there is a genuine reason for concern.

While quantum computing does not pose an imminent threat to Bitcoin, it’s important to know the timeframe and potential areas of impact. Bitcoin can still function in a world with powerful quantum computers, but bitcoin holders, developers, and the broader Bitcoin community must proactively address existing vulnerabilities ahead of time.

In this article, you’ll learn about the applications of quantum computing to cryptography, the potential vulnerabilities this poses to Bitcoin, and the paths ahead.

Quantum Computing and Cryptography

Quantum computing uses the principles of quantum mechanics to process information in fundamentally different ways from classical computers. While classical computers operate on bits that represent either 0 or 1, quantum computers use quantum bits, or qubits, which can exist in multiple states simultaneously due to superposition. This allows quantum computers to evaluate a vast number of possibilities at once, potentially solving certain complex problems much faster than the computers we use today.

The theoretical foundation of quantum computing was laid in the early 1980s, with physicist Richard Feynman proposing the concept of quantum simulations in 1981. The first functional quantum computer was built in 2001 by researchers at IBM and Stanford University. Since then, the field has progressed with the development of more powerful computers, but remains in a state of infancy, lacking the scale needed for practical applications.

Two Quantum Algorithms That Impact Bitcoin

Shor’s Algorithm and Bitcoin signatures

The first significant algorithm demonstrating the power of quantum computation was Shor’s algorithm, developed by Peter Shor in 1994. This algorithm showed that quantum computers could factor large numbers exponentially faster than classical methods. Bitcoin’s current signature address schemes, ECDSA and Schnorr, rely on the difficulty of factoring large prime numbers and could be impacted by Shor’s algorithm.

Grover’s Algorithm and Bitcoin mining

Grover’s algorithm, developed by Lov Grover in 1996, is another application of quantum computing relevant to cryptography. Specifically, it allows quantum computers to solve certain optimization problems in significantly less time compared to classical algorithms. This principle can also be applied to hashing, a concept integral to bitcoin mining and certain signature types.

A powerful enough quantum computer using Shor’s algorithm or Grover’s algorithm poses potential threats to various aspects of Bitcoin. One primary concern is the security of Bitcoin wallets and their related addresses. However, we will also cover theoretical threats to Bitcoin mining and network consensus.

Quantum’s Impact on Bitcoin Wallets

Wallets are used to create and manage Bitcoin addresses and are the main interface for users to interact with the Bitcoin network. Bitcoin supports various address types, each with varying levels of future vulnerability to quantum computing.

When a wallet generates a public-private key pair, it relies on the mathematical properties of large prime numbers. A private key is typically a randomly generated number, which is then used in combination with functions based on prime numbers and elliptic curves to derive the corresponding public key. The difficulty of reversing these operations without knowing the private key is due to the complexity of factoring large numbers.

Quantum computing could impact Bitcoin wallets in the future by deriving private keys from public keys, and can be divided into two types of attacks: A “long range” attack affects only wallets with exposed public keys, while a “short range” attack would target all current wallet types.

Long-Range Attacks

Any address that has exposed its public key is vulnerable to an attack by a powerful enough quantum computer. This is because a public key could be used to derive the corresponding private key using Shor’s algorithm.

Pay-to-Public-Key (P2PK) addresses are particularly susceptible, as they use the public key directly as the address. Additionally, any address that has been reused after sending a transaction is vulnerable, because the act of transacting reveals the public key. Pay-to-Taproot (P2TR) addresses also expose the public key, but account for a small fraction of total bitcoin.

It is estimated that approximately 1.9 million BTC are held in P2PK addresses, while another 4 million BTC are stored in reused addresses of other types. Together, this represents about 5.9 million BTC potentially at risk in the future from long-range quantum attacks.

Bitcoin wallets today no longer support the P2PK address type, and typically do not reuse addresses. However, if your wallet has reused its address or uses the P2TR address type, you can protect your funds from a potential long-range quantum attack by migrating your bitcoin to a new wallet that does not reuse addresses.

To find out what address type you have, you can go to your Bitcoin wallet and find the “receive” button, which is typically displayed on the home page. A Bitcoin address will then be provided, which you can cross-reference with this River Learn article to find out what type it is. To check if your address has been reused, you can paste your address into a block explorer to see if has been used in any transactions in the past.

Short-Range Attacks

When a transaction is sent from an address, the corresponding public key is exposed in the process. This creates a temporary vulnerability lasting until the transaction is confirmed by the Bitcoin blockchain, which typically takes between 10 and 60 minutes.

A quantum computer powerful enough to perform Shor’s algorithm to derive a private key within 10-60 minutes could theoretically steal funds from any address that has sent a pending transaction. This would occur by deriving the victim’s private key and then sending a competing transaction before the victim’s transaction has been confirmed. ** ** This scenario is known as a “short-range” attack, and has potential impact on all Bitcoin wallets in use today.

Key Generation Attacks

Bitcoin addresses depend on high-quality random numbers to generate secure private keys. If the randomness used to create these keys is weak or predictable, an attacker could potentially derive the private key.

Quantum computers using Grover’s algorithm could speed up the process of exploiting weak key generation methods. While the number of addresses potentially vulnerable is unknown and likely quite low, quantum computers could potentially widen the scope of vulnerable addresses.

Quantum’s Impact on Bitcoin Mining

Bitcoin mining relies on brute-force computation using the SHA-256 hashing algorithm to discover new blocks. In theory, quantum computers using Grover’s algorithm could reduce the time required to find a new block by half, assuming equal computational power.

In practice, quantum computing does not currently pose an imminent or long-term threat to Bitcoin mining. For quantum computers to compete with the existing network of mining rigs, they would need to be produced at an enormous scale—something far beyond what is feasible in the foreseeable future. Furthermore, quantum computers require substantial energy for cooling and operation, making them highly cost-inefficient as mining devices.

Quantum’s Impact on Network Consensus

Bitcoin’s functioning relies on achieving consensus among a network of honest nodes. One potential threat to this consensus is a Sybil attack, which occurs when a network is flooded with fake nodes to disrupt transaction propagation, peer-to-peer communication, and consensus.

Quantum computers could theoretically enhance the effectiveness of Sybil attacks due to their ability to optimize complex problems, such as network analysis and evaluating multiple scenarios simultaneously. If successful, a quantum-enabled Sybil attack could block honest nodes from propagating transactions, isolate specific nodes by feeding them false blockchain data, or introduce fraudulent transactions that might be accepted as valid.

In practice, a quantum-enabled Sybil attack is unlikely to be successful even if quantum computers are able to scale rapidly. Bitcoin’s network is highly decentralized, and its consensus mechanisms are designed to discount the influence of a large influx of new, potentially malicious nodes.

When Will Quantum Computing Threaten Bitcoin?

The advancement of quantum computing can be measured by the number of qubits—the basic unit of information in quantum computing—in a single processor. Today, the most advanced quantum computers have between 100 and 1,000 qubits. However, they can only run for a few microseconds before breaking down and displaying high error rates.

In 2022, researchers from the University of Sussex estimated that a quantum computer would need between 13 and 300 million qubits of processing power to crack the ECDSA signature algorithm in a reasonable timeframe of 1-8 hours.

As quantum computing is still in its infancy, it’s difficult to predict when—or if—the field will advance to the point of cracking certain features of Bitcoin. Even under optimistic assumptions about the rate of advancement, it is highly unlikely that quantum computers will pose a significant threat to Bitcoin within the next decade.

Mitigating Quantum Risks to Bitcoin

The most immediate quantum risk to Bitcoin—wallet vulnerability—has viable solutions that may be implemented in the coming years. If Bitcoiners want to protect themselves against the long-term risks of quantum computing, then it is likely that a soft fork will be required to add a quantum-resistant signature algorithm

In the short term, bitcoin held in wallets vulnerable to long-range attacks may be migrated to more secure wallets. Both solutions will require considerable time and blockspace for vulnerable funds to be moved to safe addresses.

Short-Term Solution: Wallet Migration

The roughly 6 million bitcoin held in P2PK addresses and reused addresses may be migrated to address types only vulnerable to short-range attacks. Such migrations significantly delay the hypothetical time until these funds become vulnerable, as long-range quantum attacks require significantly less computational power than short-range attacks.

There are roughly 45,800 UTXOs using P2PK addresses, holding almost 2 million bitcoin. A full migration of P2PK addresses to safer address types, such as P2WSH, would require between 5 and 6 Bitcoin blocks filled with such migration transactions, taking about 1 hour to complete. The number of UTXOs using reused addresses is undoubtedly larger, and would require significantly more time to migrate.

Long-Term Solution: Consensus Change to Update Signature Algorithm

There are at least 11 existing signature algorithms that are claimed to be quantum resistant. The reliability of these post-quantum signature schemes varies widely. Notably, 8 of them were introduced after 2015 and lack the extensive testing needed to gain the trust of the developer community. Post-quantum signature schemes also vary widely in their size, an important factor given the limited blockspace available in Bitcoin blocks. Larger signature sizes could impact Bitcoin’s transaction throughput network efficiency.

The US National Institute of Standards and Technology has approved 3 of these signature schemes for use in quantum-secure encryption, meaning they have undergone sufficient testing to be seen as reliable. Compared with Bitcoin’s ECDSA signature algorithm, these post-quantum schemes are at least 10 times larger in size.

To address Bitcoin’s long-term quantum vulnerability, the QuBit soft fork has been proposed by developer Hunter Beast. QuBit includes BIP-360, which was created in December 2024. The BIP introduces a Pay to Quantum Resistant Hash (P2QRH) output type that relies on post-quantum signature algorithms.

The P2QRH address type combines the security of Schnorr signatures, as used in Pay-to-Taproot, with post-quantum signature schemes. By layering these two signature algorithms, P2QRH addresses would be no less reliable than Taproot addresses, with the added security of a post-quantum signature.

All P2QRH addresses begin with the prefix “bc1r”, making them easily identifiable as quantum-resistant. This prefix distinguishes P2QRH addresses from SegWit addresses, which start with “bc1q”, and Taproot addresses, which begin with “bc1p”.

Initially, FALCON will serve as the post-quantum signature algorithm. In the future, lighter signature algorithms may be used after undergoing ample testing. For example, the SQIsign signature algorithm, initially introduced in 2023, has a signature size 4 times smaller than FALCON.

Due to the potential size of a P2QRH attestation, BIP-360 introduces a separate witness called the attestation to maintain Bitcoin’s present transaction throughput. Only valid signatures can be committed to an attestation, meaning arbitrary data cannot be added by miners, as that would affect the consensus of their block.

After introducing a post-quantum signature algorithm, all bitcoin held by ECDSA-based addresses and Taproot addresses must be migrated to P2QRH address types to be resistant to a short-range attack. This entails a full migration of the entire existing UTXO set.

An October 2024 paper by researchers at the University of Kent estimates that a full migration of vulnerable addresses would take 76 days, assuming that all Bitcoin transactions would be for migration transactions and nothing else. A more reasonable assumption, in which 25% of blockspace is used for migration transactions, suggests that a full migration would take roughly 2 years to complete.

What Will Happen to Lost Bitcoin During a Quantum Attack?

River estimates that roughly 1.6 million bitcoin are lost, in addition to Satoshi’s estimated holdings of 968,000 BTC. These coins may never be migrated to safe addresses, raising questions about what steps could be taken to potentially prevent them from being stolen through a quantum attack.

An extreme solution would involve “disabling” or otherwise moving Satoshi’s and all lost coins to prevent them from being taken by a quantum attacker. Such an action would require a soft fork of the Bitcoin protocol.

It is unlikely that consensus will be reached around this path. Disabling lost coins always runs the risk of being confiscatory, as it is impossible to prove such coins are truly “lost”. Additionally, controlling someone’s coins runs against the ideals of the Bitcoin protocol, which follows the “not your keys, not your coins” philosophy.

It is more likely that Satoshi’s coins and all lost coins will remain in their current wallets until their private keys have been forged by a quantum computer, which may never end up occurring. If this happens, it is unclear how these coins will be treated from a legal and regulatory perspective.

Key Takeaways

• A powerful enough quantum computer using Shor’s algorithm or Grover’s algorithm poses potential threats to various aspects of Bitcoin.

• Even under optimistic assumptions about the rate of advancement, it is highly unlikely that quantum computers will pose a significant threat to Bitcoin within the next decade.

• There are viable pathways to make Bitcoin resistant to quantum threats, including the QuBit soft fork.

»»»»»» Twitter | Youtube | Citadel21 | PlebUnderground Swag Shop »»»»»»