Why could the quantum era be Bitcoin's greatest challenge? | Block Height: 874,398
Narcelio. (2024, December 10). "Everyone needs to understand that the cliché 'Bitcoin will be the least of our problems' is completely wrong. At least for Bitcoiners, Bitcoin should be our greatest problem, our biggest concern." [Post on X]. Retrieved from https://x.com/narcelio/status/1866262350480998453.
Introduction
Bitcoin is often regarded as one of the most secure and resilient technologies today due to its use of elliptic curve cryptography (ECDSA) and cryptographic hashing. However, a potential threat looms: quantum computing.
As quantum computing research rapidly progresses, a concern arises: What if the ability to break current cryptography is achieved before Bitcoin evolves to “Quantum Resistant” solutions?
In this article, I do not want to fuel FUD (Fear, Uncertainty, and Doubt), but rather educate on where the risks lie. I will explain:
- How quantum computing could compromise Bitcoin.
- Vulnerable cases (P2PK, P2PKH, SegWit, Taproot).
- Why public key exposure during spending is critical.
- How to prevent or mitigate the risk.
The goal here is clear: to understand the problem before it becomes a reality and, with that, prepare you and minimally introduce you to the post-quantum debate surrounding Bitcoin before it’s too late.
Current Cryptography in Bitcoin
Bitcoin relies on cryptographic algorithms for its security, primarily two pillars:
- Elliptic Curve Cryptography (ECDSA): Derives public keys from private keys.
- Cryptographic Hashing (SHA-256 and RIPEMD-160): Ensures transaction and block integrity and immutability.
However, with advancements in quantum computing, these systems, considered secure with classical technology, may become compromised.
Elliptic Curve Cryptography (ECDSA) and the Quantum Problem
ECDSA is the algorithm used in Bitcoin to derive public keys from a private key. Specifically, Bitcoin utilizes the secp256k1 elliptic curve.
Breaking it down:
- SEC: Standards for Efficient Cryptography Group (SECG).
- P: Indicates an elliptic curve over a prime finite field, where points operate within a prime number-defined field.
- 256: Refers to the key size (256 bits). The finite field restricts valid derivations to values below this prime limit.
- k1: Refers to the Koblitz curve type, known for its efficiency.
How is secp256k1 used in Bitcoin?
The security of ECDSA is based on a problem called the discrete logarithm problem. The public key
𝑃 is generated by multiplying the generator point G by the private key 𝑘:
P = g * K
-
G is the generator point on the elliptic curve;
-
k is the private key;
-
P is the public key.
This operation is unidirectional; it is easy to calculate P from k, but infeasible to calculate 𝑘 from
𝑃. The public key generated is compressed and later hashed (HASH160) to create a Bitcoin address.
There is no efficient algorithm on classical computers to calculate 𝑘 from 𝑃. However, with quantum computing, Shor's Algorithm solves the discrete logarithm problem in polynomial time instead of exponential time, as it happens with classical computing.
When we say that Shor's Algorithm solves the discrete logarithm problem in polynomial time, it means that the time required to break the private key grows polynomially with the size of the problem: the key size.
In other words, if the key size increases, the resolution time grows in a controlled manner and not exponentially, as happens with classical computers.
With Shor's Algorithm on a sufficiently powerful quantum computer, the time required would be reduced. This does not mean it would be instantaneous, but it would be orders of magnitude faster.
This means that a sufficiently powerful quantum computer could:
- Capture the public key (exposed in transactions);
- Calculate the corresponding private key;
- Spend the funds linked to that key.
SHA-256 and RIPEMD-160: Is Hashing Still Secure?
In addition to ECDSA, Bitcoin uses cryptographic hashing—SHA-256 and RIPEMD-160—to secure data like block chaining and public addresses (derived as HASH160 of the public key).
Unlike ECDSA, hash algorithms are not directly vulnerable to Shor’s Algorithm. Instead, they are susceptible to Grover’s Algorithm, which reduces the time needed to find a preimage (hash collision) from 2^𝑛 to
2𝑛/2². For a 256-bit hash (SHA-256), this would require 2^128 operations, which remains extremely difficult even with quantum computing.
Thus, cryptographic hashing remains partially secure but will eventually need to evolve to be fully quantum-resistant.
Bitcoin Address Types: An Overview
Now that we understand the cryptography currently used in Bitcoin, we can move on to understanding public addresses and where they are vulnerable to quantum computing.
Bitcoin addresses represent payment destinations on the network, derived from public keys through cryptographic operations. Over time, different address types have emerged, bringing improvements in security, efficiency, and privacy.
Here is a list of them:
1. P2PK - Pay-to-Public-Key
- Format: The full public key is stored directly in the ScriptPubKey.
-
Usage: One of the first formats used in Bitcoin.
-
Security: Lower, as the public key is visible at the time of transaction creation (not just when spent).
-
Problem: The public key is immediately exposed upon receipt, making these addresses vulnerable to quantum attacks.
2. P2PKH - Pay-to-Public-Key-Hash (Legacy)
-
Format: Uses the HASH160 (RIPEMD-160 + SHA-256) of the public key.
-
Usage: It is the most widely used legacy address format. Addresses begin with the prefix "1".
-
Security: While the funds remain unspent, only the hash of the public key is visible. The full public key is protected and only revealed at the time of spending.
3. P2SH - Pay-to-Script-Hash (SegWit)
-
Format: Stores the hash of a script (redeem script) instead of the public key.
-
Usage: Allows for more complex scripts, like MultiSig. Addresses begin with the prefix "3".
-
Security: The redeem script is revealed only at the time of spending, as part of the ScriptSig. While funds remain unspent, only the hash of the redeem script (HASH160) is visible on the blockchain. The public key is revealed only if the redeem script directly contains it, such as in P2PK or MultiSig scripts.
4. P2WPKH - Pay-to-Witness-Public-Key-Hash (Native SegWit)
-
Format: Introduced by SegWit, it uses the public key hash in the ScriptPubKey.
-
Usage: Reduces transaction costs and prevents malleability. Addresses start with "bc1".
-
Security: Similar to P2PKH, the hash of the public key is stored in the ScriptPubKey. The full public key is revealed in the witness when the funds are spent.
5. P2WSH - Pay-to-Witness-Script-Hash (Native SegWit)
-
Format: Stores the script hash in the ScriptPubKey, the SegWit version of P2SH.
-
Usage: Ideal for complex scripts using SegWit.
-
Security: The script and the public keys involved are revealed only at the time of spending, within the witness script inside the witness.
6. P2TR - Pay-to-Taproot (SegWit v1)
-
Format: Introduced in Taproot, it uses the X-only public key directly in the ScriptPubKey.
-
Usage: More efficient and private, with support for complex spending conditions.
-
Security: The X-only public key is visible in the ScriptPubKey but hides the use of internal scripts. The Schnorr signature is revealed in the witness at the time of spending. The X-only public key is directly exposed, but internal scripts appear only if used.
The Role of Exposed Public Keys
Problem: Once the public key is exposed, it can be captured and processed by a quantum computer in a timely manner.
SegWit and the Post-Quantum Problem: Partial Protection, but Not a Complete Solution
Before SegWit, the public key was exposed at transaction creation (in the output). This meant that an attacker with a quantum computer could attempt to break the public key before it was spent.
With SegWit (P2WPKH), the ScriptPubKey (output) contains only the public key hash (HASH160). The full public key is revealed only in the witness when the transaction is spent.
Why is this important? While the public key remains unexposed, it is protected by a hash, theoretically resistant to quantum attacks under the current model.
The Moment of Vulnerability: The Mempool
Despite partial protection, the problem persists during transaction spending:
-
When sending a SegWit transaction:
- The public key appears in the witness and becomes visible.
- The transaction enters the mempool as unconfirmed.
-
In the mempool, the public key is exposed:
- An attacker with a quantum computer could capture the public key and derive the private key.
- This could allow the attacker to steal funds before the transaction is confirmed in a block.
Future Possible Solutions
To fully address the post-quantum problem, Bitcoin would need to adopt quantum-resistant cryptography, such as lattice-based cryptography or hash-based signatures, which could potentially replace ECDSA.
Note: I don’t fully understand classical computing, let alone quantum.
Conclusion
SegWit marked significant progress by delaying the exposure of public keys until spending, complicating quantum-based attacks. However, it doesn’t fully solve the problem since the public key is exposed in the witness once the transaction is broadcast and becomes visible in the mempool.
In a scenario where a sufficiently powerful quantum computer is operational, the risks are clear:
- Targeted attacks: Public keys exposed in the witness could be broken before transaction confirmation.
- Legacy addresses: Funds in P2PK addresses remain highly vulnerable.
The complete solution involves implementing quantum-resistant algorithms, like lattice-based or hash-based cryptography. Although these technologies are still under study, the post-quantum Bitcoin debate must be prioritized to prepare the network before the threat becomes a reality.
In addition to Bitcoin, various systems that rely on cryptography—such as traditional banks, messaging apps, and online services—would also be affected by quantum computing.
However, most of these systems can adopt quantum-resistant algorithms more quickly and centrally, as they do not rely on majority consensus.
Updates in these systems can be implemented via security patches or software updates. In contrast, Bitcoin, due to its decentralized nature and the need for network-wide consensus, requires a much longer and more careful process of development, testing, and implementation.
In addition to traditional systems, many machine-to-machine communication protocols also rely heavily on cryptography to ensure security and privacy. Examples include TLS/SSL (used in HTTPS), IPsec for VPNs, and SSH for secure remote access.
These protocols use public key algorithms such as RSA, ECDSA, and Diffie-Hellman for encryption and secure key exchange. While fundamental to the security of the internet and private networks, transitioning to quantum-resistant algorithms in these protocols would be faster compared to Bitcoin.
This is because these systems are updated centrally or through standardization bodies like the IETF, enabling a more agile migration to new cryptographic versions.
Developments: What Would Happen to Mining?
What if a Quantum Computer Mined Blocks Too Quickly?
A recurring concern is the idea that a quantum computer could dominate the mining process, breaking the SHA-256 used in Proof-of-Work and validating blocks much faster than traditional miners.
Let’s clarify:
-
Difficulty Adjustment
Bitcoin has a difficulty adjustment mechanism that recalibrates mining difficulty every 2016 blocks (~2 weeks). If blocks are mined too quickly due to a quantum computer's power, the difficulty would increase exponentially, restoring normality. -
Computational Scalability Problem
Even if a quantum computer mines faster initially, nodes still validate blocks under consensus rules. Increased difficulty would exponentially raise energy costs, limiting the quantum computer’s capabilities. -
Hashrate and Quantum Power
A quantum computer with superior hashrate could theoretically launch a 51% attack. However, hashrate alone isn’t sufficient; the network must still accept blocks, with difficulty adjustments acting as a limiting factor.
The Real Risk of Quantum Hashrate
If quantum computing achieves extreme capacity and surpasses the combined hashrate of traditional miners, there could be a temporary risk of mining dominance.
However, as Bitcoin consensus is governed by majority rule and validation by full nodes, the network could adapt preemptively by implementing post-quantum hashes and alternative algorithms.
Translated from: https://morata.substack.com/p/bitcointico-como-o-mundo-pos-quantico