A Discussion on Quantum-Resistant Upgrade Paths for Bitcoin

Presently, SHA-256, the hash function used by Bitcoin, holds up well against quantum attacks due to Grover's algorithm only providing a quadratic speedup, effectively halving its bit security but still remaining within acceptable limits. However, the elliptic curve digital signature algorithm (ECDSA) employed for transaction verification is vulnerable to Shor's algorithm, which could theoretically break it in polynomial time if a sufficiently powerful quantum computer were developed. This vulnerability exposes public keys and unconfirmed transactions to potential theft, underlining the necessity for a preemptive quantum-resistant upgrade.

The paper proposes several strategies for integrating post-quantum cryptographic schemes into Bitcoin Core, each designed to address the unique challenges posed by such an upgrade. These challenges include maintaining network determinism, ensuring economic continuity, and preserving decentralized governance without causing significant instability or resource strain on the network.

One suggested approach is a hybrid signature validation model, where transactions would contain both a classical ECDSA signature and a post-quantum signature, specifically CRYSTALS-Dilithium, requiring modifications to the signature verification process. Although this method would significantly increase the input size of transactions, it offers a backward-compatible solution that could coexist with existing infrastructure.

Another strategy involves introducing a new opcode for quantum-resistant addresses, OP_CHECKSIG_PQ, through a soft fork. This approach would allow for a clean separation between old and new addresses, facilitating voluntary migration without immediately invalidating legacy transactions.

The third option considered is a complete replacement of ECDSA via a hard fork, a more drastic measure that carries high coordination costs and the risk of splitting the blockchain.

The economic and game-theoretic dimensions of these strategies are also analyzed, highlighting miners' optimization for fee revenue and propagation speed, the impact of larger signatures on block weight and orphan probability, and the need for a coordinated equilibrium among network participants.

A phased migration framework is suggested to gradually introduce post-quantum support, starting with optional upgrades and moving towards mandatory adoption over time, allowing for assessment and adjustment at each stage.

Finally, the document outlines open research questions related to the aggregation of post-quantum signatures, the potential for block compression techniques to mitigate the growth in signature size, and strategies for protecting dormant unspent transaction outputs (UTXOs).

This analysis represents a comprehensive examination of the technical, cryptographic, and economic considerations involved in upgrading Bitcoin to resist future quantum threats, underscoring the importance of early and careful planning in the face of evolving computational capabilities.