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), and 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.

A 2021 study by Webber et al. estimated that breaking secp256k1 would require approximately 2,330 logical qubits. With current error correction overhead (roughly 1,000–10,000 physical qubits per logical qubit), this translates to millions of physical qubits — beyond today’s machines, but within the range that multiple hardware roadmaps target for the 2030s and 2040s.

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–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 — a critical vulnerability discovered during development and patched by narrowing the OP_SUCCESSx range to start at 0xc0.

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 → route to Dilithium verification path
• Signature > 500 bytes → skip 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 by Hunter Beast, which defines a Pay-to-Quantum-Resistant-Hash (P2QRH) output type supporting multiple PQC signature schemes including FALCON, SPHINCS+, 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.