Shor's Algorithm vs Bitcoin: anatomy of a key-derivation kill chain

TL;DR ¶

Shor's algorithm reduces the elliptic-curve discrete-logarithm problem (ECDLP) to period finding, which a fault-tolerant quantum computer solves in polynomial time. Bitcoin's signatures live on secp256k1, an ECDLP-hard curve. Once a sufficiently large logical quantum computer exists, any address that has ever exposed its public key on-chain is recoverable. Roughly 25% of circulating BTC sits in exactly that state today — primarily P2PK outputs, reused P2PKH addresses, and any UTXO whose spending transaction has been broadcast but not yet mined.

This is not a 2026 problem. It is a 2030-ish problem with a 2026 migration window.

1. The math, compressed ¶

ECDSA over secp256k1 picks a base point G of prime order n ≈ 2^256 and a private scalar d ∈ [1, n-1]. The public key is P = d·G. Signing involves the per-message nonce k, producing (r, s) where:

1
r = (k·G).x  mod n
2
s = k^-1 · (H(m) + r·d)  mod n

A classical attacker would need to invert the scalar multiplication d·G → d, an instance of ECDLP. The best known classical attack is Pollard's rho at ≈ √n ≈ 2^128 operations. Comfortably unbreakable.

Shor's algorithm reformulates ECDLP as a hidden subgroup problem over Z_n × Z_n. Given an oracle for the function:

1
f(a, b) = a·P + b·G

f has period (d, -1) mod n. The quantum Fourier transform extracts that period in O((log n)^3) time. Concretely, a fault-tolerant machine breaks secp256k1 with roughly:

• 2330 logical qubits (Roetteler et al., 2017)
• ~10^9 Toffoli gates
• ~ 8 hours wall-clock at projected ~10^4 Hz logical clock rates

Translate logical to physical with current surface-code overheads (10^3–10^4 physical per logical) and you land at 2 × 10^7 – 2 × 10^8 physical qubits. IBM's Condor (1121 qubits, 2023) and Atom Computing's 1180-qubit neutral-atom (2024) are still noisy intermediate-scale — far below the threshold, but the gap is closing on a Moore-like curve.

2. The exposed BTC inventory ¶

A Bitcoin address only reveals its public key when a UTXO at that address is spent. So the exposure model has tiers:

The first two rows — ~4.2M BTC, roughly USD 280B at current prices — are recoverable by any actor that achieves cryptanalytic relevance first. Satoshi's coins are in this bucket.

The mempool exposure is the active attack surface: an adversary with a fast enough quantum computer can crack the private key from the broadcast signature before the transaction confirms, then race a higher-fee transaction redirecting the funds.

3. The kill chain, concretely ¶

1
[broadcast tx]
2
   |  signature reveals P = d·G
3
   v
4
[harvest now]  -> store (P, tx_hash) tuples
5
   v
6
[decrypt later]  -> Shor on P -> d
7
   v
8
[forge spend]  -> sign new tx with d, RBF higher fee

The "harvest now, decrypt later" model is not theoretical for Bitcoin. State-level adversaries are demonstrably archiving the full chain plus the mempool. Every signature already published is an IOU written against future quantum capacity.

A miner-class adversary with Shor capability does not even need to race — they can hold a UTXO hostage by silently selecting against any tx spending from a vulnerable address and substitute their own.

4. What protocol-level migration looks like ¶

There is no soft-fork path that protects already-exposed keys. Migration has three workable shapes:

4a. New address type with PQ signatures ¶

Add an opcode (e.g. OP_CHECKDILITHIUM) and a new witness version. ML-DSA-44 signatures are 2420 bytes — ~75× larger than 65-byte ECDSA. Blocks get heavier; SegWit-style witness discounts mitigate. The hard part is wallet rotation discipline: users must move every coin from exposed addresses to PQ addresses before Q-day.

4b. Hybrid signatures during transition ¶

Require both an ECDSA and a Dilithium signature in the witness. Belt-and-suspenders. Doubles signature overhead but provides clean rollback if the PQ primitive turns out broken (it has happened: SIKE in 2022, Rainbow in 2022, both NIST finalists).

4c. Hash-based one-time signatures (XMSS / SPHINCS+) ¶

SPHINCS+ is stateless and conservative — security reduces to the hash function only. Signatures are large (~8 KB at NIST L1) but the cryptographic story is the simplest one to verify. Reasonable hedge for a base-layer money protocol where caution dominates.

A coordinated soft-fork freeze of legacy addresses past a flag-day has been proposed and is politically incendiary. The likely outcome: opt-in PQ addresses ship 2027-2028, vulnerable coins owned by active wallets migrate, dormant coins are eventually drained by whoever crosses the quantum threshold first.

5. A toy proof: Shor's structure on a small curve ¶

You cannot run a 256-bit Shor on a laptop. You can run it on a 5-bit curve — instructive, and the structure is identical.

1
# shor-ecdsa-sim.py (excerpt) — see Downloads for full file
2
# Classical period-finding stand-in. Models the quantum oracle f(a,b) = a*P + b*G
3
# over the toy curve E: y^2 = x^3 + 2x + 3 (mod 97). Order n = 5.
4
 
5
def shor_ecdlp_demo(P, G, n):
6
    # In a real run, this period extraction is done by QFT;
7
    # here we brute the structure to expose it.
8
    for a in range(1, n):
9
        for b in range(1, n):
10
            if scalar_mult(a, P) == scalar_mult(b, G):
11
                # a*d ≡ b (mod n), so d = b * a^-1 mod n
12
                return (b * pow(a, -1, n)) % n
13
    return None

The full file in the downloads bundle includes:

• secp256k1 group law for the curious
• A 5-bit demo end-to-end
• An estimator that takes your n and tells you the logical-qubit count Shor would need

6. What to do, this quarter ¶

1. Audit your exposure: for any wallet you control, list addresses that have ever been the sender of a transaction. Those keys are public. Sweep funds into a fresh, never-spent-from address. P2TR (Taproot) is hashed-only until first spend — use it.
2. Stop reusing addresses. This is a hygiene rule that predates Shor and now has teeth.
3. Avoid Lightning channels with large dormant balances on legacy nodes. Channel-open transactions reveal public keys.
4. Watch BIP-360 and BIP-?? (PQ signatures) for protocol-level proposals. Migration discipline is going to be a UX problem, not a math problem.
5. If you run an exchange, start cold-storage rotation now. Custodial responsibility scales linearly with quantum proximity.

7. Reading list ¶

• Roetteler, Naehrig, Svore, Lauter — Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms (2017)
• Aggarwal, Brennen, Lee, Santha, Tomamichel — Quantum Attacks on Bitcoin, and How to Protect Against Them (2018)
• Stewart, Ilie, Zamyatin et al. — Committing to Quantum Resistance (2018)
• NIST IR 8413 — Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process (2022)

The clock starts not when Q-day arrives, but when the first adversary believes Q-day is closer than your migration deadline. That moment may already have passed.