Status: Draft
Created: 20241210
Motivation
As quantum computing advances, the security of classical cryptographic primitives—especially those relying on discrete logarithms and factoring—may diminish over time. Bitcoin’s current reliance on ECDSA for signatures is expected to remain secure against foreseeable quantum computers, but preparing preemptively for a smooth transition to post-quantum (PQ) algorithms avoids rushed changes later. Introducing quantum-resistant signatures now provides long-term resilience.
Abstract
This BIP proposes a new witness version and script rules enabling quantum-resistant signature schemes, starting with a well-studied, standardized scheme like SPHINCS+. It maintains backward compatibility, allowing legacy addresses and signatures to coexist. Over time, users may voluntarily migrate funds to PQ addresses as quantum threats materialize. The design supports multiple PQ schemes and can adapt if a particular PQ algorithm is compromised, ensuring Bitcoin’s long-term security.
Specification
New Witness Version and Script Structure
- Introduce a new witness version to signal that the output requires a PQ signature.
- For example, use
OP_1QinScriptPubKeyto indicate a PQ public key and the associated verification operation:
0\text{ScriptPubKey} = OP_1Q \; <PK> \; OP_CHECKPQSIGN
Here, <PK> is a public key compatible with the chosen PQ scheme. OP_CHECKPQSIGN is a new opcode that verifies a provided PQ signature against <PK> and the transaction message.
Supported PQ Schemes
- Start with SPHINCS+, a hash-based signature scheme standardized by NIST and backed by well-understood security properties (collision-resistant hash functions).
- The framework allows for future extension:
- Define a
<SchemeID>field to support multiple PQ schemes, e.g.:
- Define a
0\text{ScriptPubKey} = OP_1Q \; <SchemeID> <PK> \; OP_CHECKPQSIGN
- Additional schemes (e.g., CRYSTALS-Dilithium) can be introduced via new
<SchemeID>values.
PQ Signature Verification
The transaction message $M$ (a hash of the input and output data) is verified against a PQ signature $\sigma$ and public key $PK$.
0\text{Verify}_{PQ}(PK, \sigma, M) =
1\begin{cases}
2\text{True}, & \text{if $\sigma$ is a valid PQ signature on $M$ w.r.t. $PK$}\\
3\text{False}, & \text{otherwise}
4\end{cases}
For SPHINCS+, this involves hashing-based verification. If $\text{Verify}_{PQ}(PK, \sigma, M)$ returns True, the input is valid.
Parameter and Size Considerations
- Let the underlying hash function be:
0H: \{0,1\}^* \to \{0,1\}^{256}
- SPHINCS+ typically uses parameters ensuring classical and quantum security at standardized levels.
- Signatures are larger than ECDSA, often tens of kilobytes, which impacts bandwidth and block space. Future PQ schemes may reduce size and improve performance.
Attack Vectors and Mitigations
-
Quantum Attacks:
SPHINCS+ resists known quantum attacks by relying on hard-to-find hash collisions, which remain infeasible even for powerful quantum adversaries. -
Side-Channel Attacks:
Wallets should implement PQ operations using constant-time methods to prevent key leaks. -
Parameter Backdoors and Broken Schemes:
Only deploy schemes vetted by the cryptographic community and standardized by reputable bodies. If a scheme weakens, introduce a new<SchemeID>and encourage migration. -
Multiple PQ Schemes (Chess Moves Against the Future):
By supporting multiple schemes, Bitcoin can pivot quickly if one scheme is compromised. This future-proofing ensures no single point of cryptographic failure.
Backward Compatibility and Deployment
- Legacy addresses and transaction types remain valid. Non-upgraded nodes treat PQ outputs as anyone-can-spend, incentivizing them to upgrade to retain full validation security.
- Introduce the feature as a soft fork (e.g., using methods like BIP9 or BIP8). Miners signal support, and after activation, upgraded nodes begin enforcing PQ signatures on PQ-designated outputs.
- Users can initially create hybrid outputs that accept ECDSA or PQ signatures, allowing a gradual transition.
Testing and Rollout
- Test the PQ changes on Signet/Testnet to gather performance data and confirm compatibility.
- Benchmark verification speeds, block size impacts, and confirm no consensus splits occur among upgraded nodes.
- Provide reference implementations, test vectors, and developer tools.
Example PQ Transaction
- Alice generates a PQ key pair using SPHINCS+ and produces an address
bc1q_pq...referencingOP_1Q <PK> OP_CHECKPQSIGN. - Bob sends BTC to Alice’s PQ address.
- When spending, Alice includes a PQ signature $\sigma$ in the witness:
0\text{Verify}_{PQ}(PK, \sigma, M) = \text{True} \implies \text{Spend allowed.}
Conclusion
This BIP ensures Bitcoin can smoothly adapt to a post-quantum world. By introducing PQ signatures preemptively, the network stays secure against potential future quantum attacks. The flexible design allows multiple PQ schemes, continual cryptanalysis, and incremental user adoption. This future-proofs Bitcoin’s cryptographic foundation, maintaining trust and stability in the decades ahead.
