Conor Deegan | [email protected]
Tom McCarthy | [email protected]
2024-11-15
Background
Quantum computing (QC) poses a significant risk to Bitcoin's (BTC) security. The core threat lies in quantum algorithms. For example, Shor’s algorithm, implemented on a quantum computer, can break elliptic curve cryptography, compromising both the Elliptic Curve Digital Signature Algorithm (ECDSA) and Schnorr Signatures used in BTC. Given a sufficiently powerful QC, it is feasible to derive private keys from public keys, enabling malicious actors to steal funds or counterfeit transactions. Via Grover’s algorithm, QCs also pose a threat to BTC’s hash-based consensus mechanism (Proof of Work), though this requires a far more powerful QC. We believe a quantum computer will be able to reverse engineer a BTC private key by 2032.
Quantum Threat Analysis
A sufficiently large QC can break the public-key cryptography used in BTC. A far larger QC can use Grover’s algorithm to compromise BTC’s consensus mechanism. The vulnerable components are:
- Digital signatures: BTC's ECDSA signatures are vulnerable. Each signature requires a user to reveal their public key, from which a quantum attack can derive the associated private key.
- Consensus mechanism: While initially less concerning than reversing a known public key, QC could threaten transaction integrity through an advantage in doing Proof of Work. This would enable unauthorized spending.
Mitigation: Estimates for when quantum computers will be sufficiently powerful to undertake these attacks range from 5 to 15 years. Given Bitcoin's decentralized nature and slow upgrade process, proactive planning is necessary now.
Potential Solutions
We describe 6 possible routes to make BTC robust against QC attacks, listed below. In general, we expect any changes to BTC itself to require substantially larger signature sizes and impact network throughput. If BTC itself is not updated, then a layer 2 or side chain may offer resistance against quantum attacks. In all cases, BTC wallets with exposed public keys are the most vulnerable and difficult to secure.
1. Optional post-quantum validation
2. Quantum-resistant signatures
3. Optional quantum-resistant addresses
4. Hard fork to quantum-resistance
5. Layer 2 quantum-resistance
6. Side chain quantum resistance
1. Optional Post-Quantum Validation (soft fork)
Goal: Enable the use of quantum-resistant signatures for transactions while retaining compatibility with ECDSA. The primary focus is on introducing an optional quantum-safe signature scheme that can be used by existing and new Bitcoin addresses.
Approach: Through a soft fork, Bitcoin would allow a quantum-secure cryptographic scheme alongside ECDSA. Any address—existing or new—can opt to use this alternative signature scheme to sign transactions, offering a dual cryptographic system. Importantly, no new address type is required, as existing addresses can benefit from the new scheme if their public keys haven’t been exposed.
Benefits: Backward compatibility ensures older nodes can continue validating blocks. Users can transition to quantum-safe signatures at their own pace without changing their existing address.
Drawbacks: Larger transaction sizes due to quantum-resistant signatures may impact fees and block capacity. Addresses with previously exposed public keys remain vulnerable to quantum attacks even if they opt to use quantum-safe signatures.
Incentives/Tokenomics: Nodes supporting quantum-resistant addresses may receive incentives (e.g., fee discounts) to encourage migration. Subsidies for reduced transaction fees could be funded through several mechanisms: dynamic fee adjustments that slightly increase fees for non-quantum-resistant transactions, temporary allocations from block rewards, or community-funded grants managed by Bitcoin foundation or P11. These approaches aim to promote early adoption while balancing costs across the network.
Key Difference: This approach does not require new addresses. Quantum-resistant signatures are an optional feature that existing addresses can adopt, provided their public keys haven’t been exposed. This is distinct from other options where new address formats are mandatory for quantum resistance.
Technical Considerations:
- Transaction Size: Introducing quantum-resistant algorithms likely increases transaction size, as quantum-safe signatures and keys are often larger than ECDSA counterparts. For example, a proposed lattice-based scheme’s signature length is ~3kB, compared to 64 bytes for Schnorr signatures, impacting block storage and network throughput.
- Security for Exposed Public Keys: Only addresses whose public keys are not yet exposed gain quantum security. Exposed addresses remain vulnerable even if they switch to quantum-safe signatures for future interactions.
- User Action: Users must explicitly opt to sign transactions using the quantum-safe scheme. Existing addresses that have not exposed their public keys can switch to quantum-safe signatures without needing to change their address.
- Network Impact: Increased transaction size can strain network capacity and raise transaction fees. Nodes and miners may require additional processing power and storage capacity to handle larger signatures.
2. Quantum-Resistant Signatures (soft fork or hard fork)
Goal: Replace or supplement ECDSA with a quantum-resistant signature scheme, see NIST proposals, at the protocol level. Unlike Option 1, this option focuses on a more systemic cryptographic upgrade, potentially replacing ECDSA entirely.
Approach:
- Soft Fork: Add a quantum-resistant signature type alongside ECDSA, allowing users to choose which scheme to use.
- Hard Fork: Fully replace ECDSA with a quantum-resistant signature scheme, requiring all transactions to use the new cryptography.
Benefits: Quantum-safe signatures protect all new transactions, providing a systemic solution. A hard fork ensures all addresses and transactions are quantum-safe, leaving no vulnerable legacy cryptography.
Drawbacks: A soft fork still leaves older transactions and exposed public keys vulnerable. A hard fork can cause community division and risk network splits.
Incentives/Tokenomics: Miners and nodes supporting quantum-resistant signatures could earn higher transaction fees to compensate for larger data processing. Users adopting quantum-resistant signatures might receive slight fee reductions.
Key Difference: This solution targets the signature scheme itself at the protocol level, ensuring systemic quantum resistance. Unlike Option 1, it does not focus on enabling existing addresses to adopt quantum safety but instead upgrades Bitcoin’s entire cryptographic signature layer. A hard fork would enforce quantum resistance for all transactions, whereas a soft fork would still leave legacy cryptography in play.
Technical Considerations:
- Transaction Size: Increases due to quantum-safe signatures (similar to Option 1).
- Security for Exposed Public Keys:
- Soft Fork: Addresses with exposed public keys remain vulnerable unless users migrate funds to quantum-safe addresses and opt for quantum-resistant signatures in new transactions.
- Hard Fork: Eliminates legacy cryptography entirely, retroactively protecting exposed public keys by replacing ECDSA with quantum-resistant algorithms.
- User Action:
- Soft Fork: Users must choose to use quantum-safe signatures.
- Hard Fork: Requires all users to upgrade wallets and re-sign transactions under the new cryptographic standard.
- Network Impact: A hard fork requires broad consensus and risks network splits. A soft fork avoids this but still leaves legacy cryptography in use.
3. Optional Quantum-Resistant Addresses (soft fork)
Goal: Introduce new address types that exclusively use quantum-resistant cryptographic schemes from the start. Unlike Option 1, this approach restricts quantum resistance to specific new address formats, requiring users to explicitly adopt these new addresses for quantum security.
Approach: Bitcoin would allow users to create a new type of address that is quantum-resistant by default. Only these new addresses would use quantum-resistant cryptographic algorithms. Regular ECDSA-based addresses remain unaffected and operate under traditional cryptographic methods.
Benefits: Users can gradually adopt quantum security without requiring a hard fork. Provides a clear, segregated option for users who prioritize quantum resistance.
Drawbacks: Potentially confusing for users who must choose between different address types, especially since existing addresses would not benefit from quantum security. Requires explicit migration of funds to new quantum-resistant addresses for users to achieve quantum security.
Incentives/Tokenomics: Users moving to quantum-resistant addresses may receive transaction fee discounts as an early adoption incentive. Miners validating these addresses could receive enhanced transaction fees temporarily to encourage smooth migration.
Key Difference: This solution requires new address types to enable quantum resistance, unlike Option 1, which allows existing addresses to adopt quantum-safe signatures without changing their format. With this approach, quantum-resistant cryptography is tied exclusively to newly created addresses. Existing ECDSA addresses and their signing methods remain unchanged, making this option narrower and more targeted than Option 1.
Technical Considerations:
- Transaction Size: Transactions from new quantum-resistant addresses would be larger due to the signature scheme. However, because only new addresses are impacted, the overall effect on network transaction sizes might be moderate, especially if adoption is gradual.
- Security for Exposed Public Keys: This approach does not retroactively protect addresses with known public keys. Users with exposed public keys would need to migrate funds to the new address type for quantum security.
- User Action: Users must explicitly create new, quantum-resistant addresses and transfer funds to these addresses for quantum security. Unlike Option 1, where existing addresses can use quantum-safe signatures without changing formats, this solution mandates migration to new address types.
- Network Impact: The introduction of quantum-resistant addresses increases overall transaction size modestly as adoption grows. Nodes will need to support both traditional ECDSA-based addresses and the new quantum-resistant addresses, increasing network complexity and data processing requirements.
4. Quantum-Resistant Hard Fork
Goal: Implement a comprehensive hard fork to replace Bitcoin's cryptographic algorithms with quantum-resistant counterparts across the entire protocol.
Approach: Transition the Bitcoin network to a quantum-resistant cryptographic scheme for all users, requiring consensus across miners, nodes, and wallets. Proof of Work and signature schemes would be the major changes.
Benefits: Full security against quantum threats, without backward compatibility issues.
Drawbacks: Hard forks are contentious and risky, as they can split the community and potentially lead to a competing "legacy" Bitcoin chain.
Incentives/Tokenomics: Miners and nodes on the post-quantum chain could receive higher rewards to promote adoption. Airdrops or fee reductions could be offered to users adopting the new chain early, incentivizing migration from the legacy chain.
Key Difference: Unlike options 1, 2, and 3, this solution involves a complete network-wide replacement of Bitcoin's cryptographic foundation. It fully eliminates ECDSA and replaces it with a quantum-resistant scheme across all addresses, nodes, and miners. This approach does not permit a dual system or gradual transition, as it requires all users to adopt the new cryptographic system simultaneously.
Technical Considerations:
- Transaction Size: A hard fork that mandates quantum-resistant cryptography will generally increase transaction sizes across the network due to the larger quantum-resistant signatures. This would make blocks larger and potentially slow transaction throughput.
- Security for Exposed Public Keys: All addresses and transactions would be quantum-safe post-fork. Exposed public keys would no longer be vulnerable, as the system would replace ECDSA with a fully quantum-resistant scheme.
- User Action: Users would need to upgrade their wallets and possibly re-generate addresses using the new cryptographic scheme. All users would be required to transition to the new system, which could require wallet updates and user action to remain compliant.
- Network Impact: A full network shift would necessitate significant coordination among miners, nodes, and wallets. Larger transaction sizes would require increased bandwidth, storage, and processing power across the network. A hard fork could also split the network if some participants resist the upgrade.
5. Layer 2 Quantum Resistance
Goal: Implement quantum-resistant Layer 2 protocols that operate on top of the Bitcoin protocol.
Approach: Upgrade Layer 2 channels to use quantum-resistant cryptography, allowing secure micro-transactions.
Benefits: Provides quantum resistance without requiring changes to the base layer, maintaining backward compatibility.
Drawbacks: Layer 2 quantum resistance is dependent on Layer 1 security. If the Layer 1 protocol is compromised (e.g., via quantum attacks on exposed public keys), the integrity of Layer 2 channels may also be at risk, as channel anchor transactions are ultimately secured by Layer 1.
Incentives/Tokenomics: Miners and nodes supporting quantum-resistant Layer 2 solutions could receive fee incentives. Users might benefit from lower fees for quantum-secure transactions on Layer 2.
Key Difference: This approach focuses on enhancing Layer 2 solutions with quantum-resistant cryptography, rather than changing the base layer. It provides an additional security layer for micro-transactions and off-chain payments, complementing the existing on-chain security.
Technical Considerations:
- Transaction Size: Because Layer 2 transactions happen off-chain, there is minimal impact on main-chain transaction size. On-chain anchor transactions connecting to Layer 2 channels might see slight size increases if they need quantum-resistant signatures.
- Security for Exposed Public Keys: Layer 2 quantum resistance does not protect addresses on the main chain. Users with exposed public keys would need to move funds to Layer 2 and rely on quantum-resistant Layer 2 solutions for security. If a quantum attack compromises Layer 1 (e.g., an attacker can reverse ECDSA signatures), they could invalidate Layer 2 channel integrity by altering anchor transactions or disrupting settlement guarantees.
- User Action: Users would need to open quantum-secure channels on Layer 2 to benefit from the added security. This requires setting up or moving funds to Layer 2 solutions, which may be complex for some users.
- Network Impact: Minimal impact on the main chain's network capacity or transaction sizes. However, reliance on Layer 2 solutions means increased dependency on these protocols, which can add complexity and potentially centralize parts of the network. The reliance on Layer 1 for ultimate settlement means that the introduction of quantum resistance at Layer 2 is only effective if Layer 1 is quantum-secure or sufficiently robust.
6. Side Chain Quantum Resistance
Goal: Create a side chain with quantum-resistant cryptographic protocols that are compatible with Bitcoin, allowing users to transfer assets for increased security.
Approach: Design a quantum-resistant side chain connected via a two-way peg, enabling users to transfer assets for resistant storage.
Benefits: Allows users to choose between quantum-resistant and traditional chains based on their security needs. Provides a testing ground for quantum-resistant technologies before implementing them on the main chain.
Drawbacks: Side chains may introduce additional complexity and security risks. Users must trust the side chain's security model.
Incentives/Tokenomics: Side chain users might benefit from lower transaction fees or yield-based incentives, making this an attractive option for users prioritizing quantum security.
Key Differences: Unlike other solutions, this approach allows the main chain to remain untouched, while offering a fully quantum-resistant environment on the side chain, providing users with flexibility in choosing their preferred level of security. It provides a testing environment for quantum-resistant technologies before implementing them on the main chain, offering flexibility and security options for users.
Technical Considerations:
- Transaction Size: Main chain transaction sizes remain unaffected, as all quantum-resistant processing occurs on the side chain. Users would only need main-chain transactions to enter and exit the side chain.
- Security for Exposed Public Keys: The side chain provides quantum resistance, so users moving funds there gain protection. However, any remaining main-chain addresses with exposed public keys are still vulnerable unless they move funds to the side chain.
- User Action: Users must transfer assets to the quantum-resistant side chain to gain quantum security. This requires setting up side chain wallets and learning to interact with the side chain, which could be a barrier for some users.
- Network Impact: Minimal effect on main-chain bandwidth and storage. However, side chains introduce additional complexity and require users to trust the security model and consensus mechanism of the side chain. Potential security or interoperability risks between the main chain and side chain could arise.
Open Questions
- Which of the above options are most secure, both near term and long term?
- What are the implications of each option for scaling BTC?
- Which post-quantum cryptographic protocols should be used in each case?