Quantum Resistance

Definition 39.1 (Qubit)

Classical computers use bits (0 or 1). Quantum computers use qubits. A qubit's state is a superposition

α|0⟩ + β|1⟩,   with   |α|² + |β|² = 1

that yields 0 or 1 on measurement with probabilities |α|² and |β|²; the constraint expresses that these probabilities sum to one.

Classical Bit:
├── State: 0 OR 1
├── Operations: AND, OR, NOT, XOR
└── Parallelism: Multiple physical bits

Quantum Qubit:
├── State: α|0⟩ + β|1⟩ (superposition)
├── |α|² + |β|² = 1 (probability constraint)
├── Operations: Quantum gates (Hadamard, CNOT, etc.)
├── Entanglement: Correlated qubits
└── State space: dimension 2ⁿ for n qubits
    (amplitudes, not independently readable values)

Definition 39.2 (Quantum Gates)

Quantum algorithms are built from specialized operations on qubits:

Common Quantum Gates:
├── Hadamard (H): Creates superposition
│   H|0⟩ = (|0⟩ + |1⟩)/√2
│
├── Pauli-X: Quantum NOT gate
│   X|0⟩ = |1⟩, X|1⟩ = |0⟩
│
├── CNOT: Controlled NOT (entanglement)
│   |00⟩ → |00⟩, |01⟩ → |01⟩
│   |10⟩ → |11⟩, |11⟩ → |10⟩
│
└── Phase Gates: Rotate quantum state
    Rz(θ): |0⟩ → e^(−iθ/2)|0⟩,  |1⟩ → e^(+iθ/2)|1⟩

Definition 39.3 (Shor's Algorithm)

Shor's algorithm (Peter Shor, 1994) efficiently solves the discrete logarithm problem—the foundation of ECDSA security:

Given public key P = d × G, find private key d

Classically this requires about 2¹²⁸ operations for a 256-bit curve. Shor's algorithm reduces it to roughly 10¹² quantum gate operations, given a sufficiently large quantum computer. The algorithm proceeds in three stages:

Shor's Algorithm for Discrete Log:

1. Quantum Phase Estimation
   ├── Create superposition over pairs (a, b)
   ├── Apply controlled group operations
   └── Measure to learn the period

2. Period Finding
   ├── Find the period of f(a, b) = aG + bP
   ├── Uses Quantum Fourier Transform
   └── Polynomial time vs exponential classical

3. Extract Private Key
   ├── The period of f encodes d (since P = dG)
   ├── Compute d from the measured phase
   └── Verify: d × G = P ✓

Resource Requirements (256-bit ECDSA):
├── Qubits needed: ~2,330 logical qubits
├── With error correction: ~13,000,000+ physical qubits
├── Gate operations: ~10¹²
└── Current state: ~1,000 noisy physical qubits

Definition 39.4 (Public-Key Exposure by Address Type)

Not all Bitcoin addresses are equally vulnerable to Shor's algorithm. An output is exposed exactly when its public key (rather than a hash of it) is visible on-chain:

Address Type	Public Key Exposed?	Quantum Vulnerable?
P2PK (early)	Always (in scriptPubKey)	Yes - immediately
P2PKH (legacy)	After first spend	Yes - after spending
P2WPKH (SegWit)	After first spend	Yes - after spending
P2TR (Taproot)	Always (tweaked key in output)	Yes - immediately
Fresh addresses	Never (hash only)	Protected until spent

Definition 39.5 (Transaction Race Attack)

Even "protected" addresses face risk during spending. In a transaction race attack, a quantum adversary extracts the public key from a broadcast transaction and races to compute the private key before the transaction confirms:

Transaction Race Attack:

1. Victim broadcasts transaction
   └── Public key now visible in mempool

2. Quantum attacker observes transaction
   └── Extracts public key from signature

3. Attacker computes private key
   └── Using Shor's algorithm (if fast enough)

4. Attacker signs competing transaction
   └── Sends coins to attacker's address

5. Race condition
   └── If quantum computation < block time, attacker wins

Critical timing:
├── Average block time: 10 minutes
├── Required quantum speed: < 10 minutes
└── Current Shor implementations: many hours on simulators

Definition 39.6 (Grover's Algorithm)

Grover's algorithm (Lov Grover, 1996) provides quadratic speedup for unstructured search via amplitude amplification:

Classical search: O(N)   →   Quantum search: O(√N)

For SHA-256 preimage search:

Classical: 2²⁵⁶ operations   →   Quantum: 2¹²⁸ operations

Mining with Grover's Algorithm:

Classical Mining:
├── Goal: Find nonce where SHA256(block) < target
├── Expected operations: 2^difficulty
└── Parallelizable: More ASICs = more hashes

Quantum Mining:
├── Apply Grover to search for valid nonce
├── Expected operations: √(2^difficulty) = 2^(difficulty/2)
├── NOT parallelizable: √N × √N = N (no advantage)
└── Coherence requirements: Extreme

Practical Reality:
├── Grover requires coherent computation
├── Cannot simply add more qubits for speedup
├── One quantum computer = √N speedup
├── M quantum computers: only √M collective speedup (vs M× classically)
└── ASICs likely remain competitive for mining

Definition 39.7 (Logical Qubit)

Current quantum computers are "noisy"—qubits decohere and operations have errors. A logical qubit is an error-corrected qubit built from many physical qubits, allowing arbitrarily long computations. Useful cryptographic attacks require fault-tolerant quantum computers built from logical qubits.

Logical Qubit Construction:

Physical qubits available: ~1,000
├── Error rate: ~0.1-1% per operation
├── Coherence time: ~100 microseconds
└── Operations possible: ~1,000 before decoherence

Error Correction Overhead:
├── Requires 1,000-10,000 physical qubits per logical qubit
├── Surface code: Most promising approach
├── Need ~0.1% physical error rate minimum
└── Better error rates = lower overhead

For Breaking 256-bit ECDSA (Roetteler et al., 2017):
├── Logical qubits needed: ~2,330
├── Physical qubits (optimistic): ~2,330,000
├── Physical qubits (pessimistic): ~23,000,000
└── Current maximum: ~1,000 (noisy)

Definition 39.8 (Mosca's Inequality)

Let X = time to migrate cryptography, Y = time data must remain secure, and Z = time until the quantum threat arrives. Migration must begin now whenever

X + Y > Z

Definition 39.9 (NIST Post-Quantum Standards)

In 2024, NIST finalized the first post-quantum cryptographic standards:

Algorithm	Type	Use Case	Key Size	Signature Size
ML-KEM (Kyber)	Lattice	Key encapsulation	~1.5 KB	N/A
ML-DSA (Dilithium)	Lattice	Signatures	~2.5 KB	~4.6 KB
SLH-DSA (SPHINCS+)	Hash-based	Signatures	~64 bytes	~8-50 KB
ECDSA (current)	Elliptic curve	Signatures	33 bytes	~72 bytes

Definition 39.10 (Lattice-Based Signatures)

Lattice-based cryptography rests on the hardness of lattice problems, for which no efficient quantum algorithm is known. It is the family most often proposed for Bitcoin, on signature-size and verification-speed grounds:

Lattice Problem (simplified):

Given: Basis vectors of a high-dimensional lattice
Find: Shortest vector in the lattice

Classical: Exponential in dimension
Quantum: Still exponential (no known efficient algorithm)

ML-DSA (Dilithium) for Bitcoin:
├── Security: 128-256 bit post-quantum
├── Public key: 2,592 bytes (vs 33 bytes ECDSA)
├── Signature: 4,627 bytes (vs 72 bytes ECDSA)   [ML-DSA-87]
└── Verification: Fast, similar to ECDSA

Definition 39.11 (Hash-Based Signatures)

Hash-based signatures are the most conservative option—their security relies only on the security of the underlying hash function:

SPHINCS+ (SLH-DSA):
├── Based on: Merkle trees + hash chains
├── Security assumption: Hash function (SHA-256, SHAKE)
├── Advantages:
│   ├── Minimal assumptions
│   ├── Well-understood security
│   └── No new mathematical assumptions
├── Disadvantages:
│   ├── Large signatures (8-50 KB)
│   └── Slower signing
└── Bitcoin impact: ~100x larger transactions

Lamport Signatures (simpler):
├── One-time use only
├── Signature: 8 KB for 256-bit security
├── Verification: Fast
└── Can be committed in P2SH today

Definition 39.12 (Post-Quantum SegWit, P2QRH)

The first migration strategy adds post-quantum signature schemes as new SegWit versions via a soft fork:

Post-Quantum SegWit:

Version 0: P2WPKH, P2WSH (current)
Version 1: P2TR (Taproot)
Version 2-16: Available for future use

Proposed P2QRH (Quantum Resistant Hash):
├── SegWit version 2 or higher
├── Commit to post-quantum public key hash
├── Reveal PQ signature in witness
└── Backwards compatible soft fork

Implementation:
witness_v2 = OP_2 <32-byte PQ key hash>
spending = <PQ signature> <PQ public key>

Definition 39.13 (Commit-Delay-Reveal)

The second strategy protects against transaction race attacks by separating the commitment to spend from the reveal of the (quantum-vulnerable) public key:

Commit-Delay-Reveal Protocol:

1. Commit Phase
   ├── User commits to spending intention
   ├── Hash of (destination, amount, nonce)
   └── No signature required (quantum-safe)

2. Delay Phase
   ├── Wait N blocks (e.g., 100)
   ├── Prevents race condition
   └── Attacker cannot predict destination

3. Reveal Phase
   ├── Provide pre-image of commitment
   ├── Include signature (may be broken)
   └── Commitment proves ownership

Benefits:
├── Works with existing ECDSA
├── Quantum attacker cannot steal
├── Time lock provides protection
└── Soft fork implementation possible

Definition 39.14 (Hybrid Signatures)

The third strategy combines classical and post-quantum signatures, so the construction is secure as long as either scheme remains secure:

Hybrid Signature Scheme:

signature = {
    classical: ECDSA_sign(sk_ecdsa, message),
    quantum: ML_DSA_sign(sk_mldsa, message)
}

verify(pk_ecdsa, pk_mldsa, message, signature):
    return ECDSA_verify(pk_ecdsa, message, sig.classical)
           AND ML_DSA_verify(pk_mldsa, message, sig.quantum)

Security:
├── Secure if EITHER scheme is secure
├── Protects against PQ scheme weaknesses
├── Larger signatures (acceptable trade-off)
└── Migration path to pure PQ later

Definition 39.15 (Committed Lamport Fallback)

A holder can be protected today by committing to a hash-based signature inside a P2SH script—a "commit now, reveal later" defense:

Committed Lamport Fallback:

1. A Lamport keypair is generated offline
   └── One-time use hash-based signature

2. A P2SH address commits to the script
   ├── Script: IF <lamport verify> ELSE <ECDSA> ENDIF
   └── Hidden until spending

3. If a quantum threat materializes
   ├── The holder spends via the Lamport path
   └── Quantum computers cannot break the hash commitment

One Plausible Sequencing (illustrative):

2026-2028: Research Phase
├── Finalize PQ signature choice
├── Design soft fork proposal
├── Implement in Bitcoin Core (experimental)
└── Community discussion and review

2028-2030: Testing Phase
├── Signet deployment
├── Wallet integration
├── Security audits
└── BIP finalization

2030-2032: Activation
├── Soft fork activation
├── New PQ address types available
├── Migration begins
└── Wallet support widespread

2032-2042: Migration Window
├── Users migrate to PQ addresses
├── Layer 2 upgrades
├── Exchange support
└── Legacy addresses deprecated (social)

2042+: Post-Quantum Era
├── All active coins quantum-resistant
├── Legacy coins (Satoshi's etc.) at risk
├── Protocol decisions on unmoved coins
└── Full PQ security achieved