From ECDSA to Dilithium

Why ECDSA Breaks

Bitcoin’s digital signatures use the Elliptic Curve Digital Signature Algorithm (ECDSA) on the secp256k1 curve. When you create a Bitcoin wallet, your software picks a random 256-bit number (the private key), multiplies it by a fixed generator point on the curve (producing the public key), then hashes the public key to create your address. Security rests on the assumption that reversing the multiplication, computing the private key from the public key, is computationally infeasible.

This assumption holds against classical computers. The best known classical attack (Pollard’s rho) requires approximately 2¹²⁸ operations for secp256k1, a number so large that no classical computer could complete it before the heat death of the universe. But Peter Shor demonstrated in 1994 that a quantum computer can solve the underlying problem, the elliptic curve discrete logarithm, in polynomial time.

The first widely cited resource estimate, Roetteler et al. (2017), put the cost of breaking secp256k1 at roughly 2,330 logical qubits.¹ Accounting for error-correction overhead (then on the order of 1,000 to 10,000 physical qubits per logical qubit), Webber et al. (2022) translated that into the physical-hardware regime: about 317 million physical qubits to break a key in an hour, or 13 million for a day.² Either figure sits far beyond today’s machines, whose largest processors are in the low thousands of qubits.

Those estimates are falling fast. In 2025, Gidney showed RSA-2048 could be factored with fewer than one million noisy physical qubits, a 20x reduction from his own 2019 figure of roughly 20 million.³ In 2026, architectures built on quantum LDPC codes cut error-correction overhead by about 100x, pushing RSA-2048 toward the 100,000 physical-qubit range, with aggressive qubit-for-time tradeoffs reaching the low tens of thousands of qubits at much longer runtimes.⁴ Elliptic-curve attacks against secp256k1 track the same downward curve. The threat is not a fixed date on a roadmap; the bar keeps dropping.

The vulnerability is specific: it applies to any output where the public key has been revealed on-chain. This includes all Pay-to-Public-Key (P2PK) outputs (early Bitcoin, including Satoshi’s coins), any address that has been spent from (the public key appears in the transaction input), and Taproot (P2TR) outputs where the tweaked public key is always visible. Unspent outputs at hashed addresses (P2PKH, P2WPKH) are protected until the moment you spend them, at which point the public key is exposed.

What Replaces It: CRYSTALS-Dilithium

CRYSTALS-Dilithium, standardized by NIST as FIPS 204 (published August 2024), is a lattice-based digital signature scheme.⁵ Its security rests on the Module Learning With Errors (MLWE) problem, a fundamentally different mathematical structure from the elliptic curve problems that Shor’s algorithm exploits.

In simplified terms: MLWE asks you to distinguish between a system of linear equations with small random errors and a truly random system. This problem has no known efficient quantum algorithm. Where Shor’s algorithm provides an exponential speedup against ECDSA, the best known quantum approach to MLWE (Grover-enhanced lattice sieving) provides only a modest improvement that can be compensated by slightly increasing key sizes.

Dilithium provides the same formal security guarantee as ECDSA, Existential Unforgeability under Chosen Message Attack (EUF-CMA), meaning an attacker who can request signatures on messages of their choice still cannot forge a signature on a new message. The key difference is that this guarantee is expected to hold against both classical and quantum adversaries.

The BTQ project chose Dilithium2 (NIST Security Level 2, equivalent to 128-bit quantum security) as its default parameter set. Higher security levels (Dilithium3 at Level 3, Dilithium5 at Level 5) are available in the codebase but produce even larger keys and signatures. Level 2 represents the pragmatic balance: adequate security margin against foreseeable quantum threats while minimizing the size penalty that propagates through every layer of the system.

The Size Comparison

The most consequential difference between ECDSA and Dilithium is not speed. Dilithium verification (~1.5ms) is actually faster than ECDSA verification (~2ms). It is size.⁶

Every one of these size increases propagates through the system: block sizes must grow to maintain throughput, network message limits must increase for block propagation, script size limits must accommodate larger stack elements, and wallet storage expands significantly. The 15x transaction size increase is the single most important number in quantum-resistant Bitcoin design. Every engineering decision downstream flows from it.

New Opcodes for a New Signature

Bitcoin’s script language uses OP_CHECKSIG (opcode 0xac) to verify ECDSA signatures. A quantum-resistant chain needs equivalent opcodes for Dilithium verification. The BTQ implementation adds five new opcodes in the unused opcode space above Bitcoin’s OP_CHECKSIGADD:

A standard Dilithium P2PKH (Pay-to-Public-Key-Hash) script looks almost identical to Bitcoin’s, with only the final opcode changed:

The opcode placement (0xbb to 0xbf) required careful consideration. These values originally fell within the OP_SUCCESSx range defined in BIP-342, which meant any Taproot script containing them would unconditionally succeed without validation. That was a critical vulnerability discovered during development and patched by narrowing the OP_SUCCESSx range to start at 0xc0. View source: src/script/script.cpp L347–356

Auto-Detection: Running Both in One Block

A quantum-resistant Bitcoin cannot require an instant cutover from ECDSA to Dilithium. Wallets must be upgraded, keys migrated, and funds moved, a process that will take years. During the transition, both signature types must coexist in the same blockchain, even in the same block.

The BTQ implementation achieves this through size-based auto-detection in the script interpreter. When the interpreter encounters signature or public key data on the stack:

• Public key > 100 bytes routes to the Dilithium verification path
• Signature > 500 bytes skips DER encoding checks (Dilithium uses raw format)
• Otherwise, standard ECDSA verification

This approach means existing ECDSA transactions work unchanged: no special flags, no version bumps, no opt-in. The interpreter simply recognizes the cryptographic primitive from the data size and routes accordingly. A single block can contain a mix of ECDSA and Dilithium transactions with no coordination between them.

Wallet Integration

Wallet software must store, encrypt, and manage Dilithium keys alongside existing ECDSA keys. The BTQ implementation adds dedicated key types to the wallet database:

• Unencrypted storage: Dilithium private keys (2,560 bytes each) are stored under a DILITHIUM_KEY record type, keyed by the 20-byte key ID (the same RIPEMD160(SHA256(pubkey)) hash used for addresses).
• Encrypted storage: When the wallet is encrypted, keys are wrapped with AES-256-CBC using the wallet’s master key, the same encryption mechanism used for ECDSA keys. The encrypted form is stored as DILITHIUM_CRYPTED_KEY.
• Memory security: Private key objects use secure heap allocation with guard pages and call memory_cleanse() on destruction to prevent key material from lingering in memory.

A practical limitation: BIP-32 hierarchical deterministic (HD) derivation, which allows recovery of all keys from a single seed phrase, does not yet have a standard equivalent for Dilithium. The BTQ codebase includes an HD derivation implementation using HMAC-SHA512, but it is not yet wired into wallet key generation. Until this matures, users must back up the full wallet file rather than relying on a seed phrase alone.

What Bitcoin Itself Is Doing

Bitcoin Core has not yet begun implementing post-quantum signatures, but the research community is active. The most developed proposal is BIP-360, co-authored by Hunter Beast, Ethan Heilman, and Isabel Foster. First drafted in 2024 as Pay-to-Quantum-Resistant-Hash (P2QRH), it has since been renamed Pay-to-Merkle-Root (P2MR), and defines a new output type that commits to post-quantum signature schemes such as FALCON and lattice-based options.⁷

Other proposals explore using OP_CAT (if re-enabled) to verify arbitrary signature schemes in Bitcoin Script without dedicated opcodes, and hash-based emergency signatures (Lamport/Winternitz) as a rapid-deployment fallback.

The consensus challenge is significant: Bitcoin’s conservative governance culture makes sweeping cryptographic changes politically difficult. Every approach involves tradeoffs between signature size, block space, backward compatibility, and activation risk. Projects that implement these changes on separate networks, as BTQ has done with Dilithium and as Ethereum researchers are exploring with their own PQC proposals, provide working reference implementations that the Bitcoin community can evaluate against real-world performance data.

References

1. Roetteler, Naehrig, Svore & Lauter. Quantum resource estimates for computing elliptic curve discrete logarithms. ASIACRYPT 2017. arXiv:1706.06752. Origin of the ~2,330 logical-qubit estimate for secp256k1.
2. Webber, Elfving, Weidt & Hensinger. The impact of hardware specifications on reaching quantum advantage in the fault-tolerant regime. AVS Quantum Science 4, 013801 (2022). doi:10.1116/5.0073075. Physical-qubit estimates (≈317M for a 1-hour attack, ≈13M for a day).
3. Gidney. How to factor 2048-bit RSA integers with less than a million noisy qubits. Google Quantum AI, 2025. arXiv:2505.15917. A 20x reduction from the 2019 estimate of ~20M physical qubits.
4. The Pinnacle Architecture: reducing the cost of breaking RSA-2048 to 100,000 physical qubits using quantum LDPC codes. 2026. arXiv:2602.11457. Error-correction overhead cut ~100x, with aggressive qubit/time tradeoffs.
5. NIST. FIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA). Published 13 August 2024. csrc.nist.gov/pubs/fips/204/final
6. Open Quantum Safe. ML-DSA parameter sets (ML-DSA-44: 1,312 / 2,560 / 2,420 bytes). openquantumsafe.org
7. Beast, Heilman & Foster. BIP-360: Pay-to-Merkle-Root (P2MR), originally drafted as P2QRH. bip360.org