Summary

Post-quantum (PQ) cryptography for Ethereum is a long-horizon but increasingly concrete challenge. The PQ track in Ethereum’s Strawmap roadmap targets a PQ L1 by 2029. The main obstacles are (1) BLS signature aggregation has no PQ equivalent at practical sizes, and (2) Falcon/Dilithium PQ signatures are large (~666–2800 bytes vs. 64 bytes for ECDSA). The decoupled consensus architecture (Goldfish heartbeat with ~256 validators per slot) creates a path: a PQ heartbeat can deploy before the full PQ migration by using naive signature concatenation.

Threat Model

Quantum computers running Shor’s algorithm can break:

  • ECDSA/secp256k1: recovers private keys from public keys (used in EOA transaction signing)
  • BLS signatures: recovers private keys (used in validator attestations)
  • DH key exchange: compromises SSL/TLS session keys in transit

They cannot break:

  • Hash functions (SHA-256, keccak) at meaningful depths
  • Symmetric encryption (AES) with sufficient key lengths

Timeline: “cryptographically relevant quantum computer” (CRQC) — one capable of breaking 256-bit ECDSA — is estimated at 10–20 years out, but preparation must begin now because:

  1. “Harvest now, decrypt later”: adversaries can record encrypted data today and decrypt it when QC arrives
  2. Key migration is slow: getting millions of validators and users to migrate takes years

PQ Signature Schemes

Falcon (NIST Finalist / Standard)

  • Based on lattice problems (NTRU lattice)
  • Signature size: 666 bytes (Falcon-512) or 1280 bytes (Falcon-1024)
  • Key size: 897 / 1793 bytes (public key)
  • Very fast signing and verification
  • NIST PQC standard as of 2024
  • Problem for Ethereum: 666 bytes per validator × 1M validators = 666 GB per slot — completely impractical for aggregation

Dilithium (NIST Standard / CRYSTALS-Dilithium)

  • Based on lattice problems (module lattice)
  • Signature size: 2420–4595 bytes depending on security level
  • Simpler to implement than Falcon; preferred for many applications
  • Even larger than Falcon; worse for Ethereum’s aggregation problem

XMSS / LMS (Hash-Based)

  • Based on hash functions only (minimal trust assumptions)
  • Signature size: large (varies; few KB to tens of KB)
  • Key state: stateful — keys must be updated after each use; one-time property
  • Very conservative security assumptions
  • leanMultisig: a zkVM targeting XMSS aggregation for Ethereum (early benchmarks: 300–500KB for 1000+ signatures, approaching naive concatenation cost)

BLS (Current, NOT Post-Quantum)

  • Small signatures (96 bytes)
  • Efficiently aggregatable (N signatures → 96 bytes)
  • Based on elliptic curve pairings (broken by quantum)
  • Will need complete replacement for PQ Ethereum

The Aggregation Problem

Ethereum’s current BLS aggregation:

  • 1M validators × 96 bytes (BLS sig) → aggregated to 96 bytes (a single aggregate signature)
  • This is the only practical scheme enabling 1M validators per epoch

With PQ signatures:

  • No known PQ scheme aggregates efficiently at this scale
  • Falcon: 1M × 666B = 666 GB per slot (impossible)
  • Active research areas: lattice-based aggregation, STARK-based signature compression, recursive SNARKs

leanMultisig approach (early benchmarks 2026):

  • Proves aggregation of 1000+ XMSS signatures in a zkVM
  • Proof size: 300–500 KB
  • Conjectured security assumption (not yet formally proven)
  • If confirmed, enables near-BLS-like overhead for PQ finality

The Two-Layer Architecture Solution

The Goldfish/Majorum decoupled consensus creates a path:

PQ Heartbeat (Goldfish, ~256 validators):

  • 256 validators per slot → concatenated signatures
  • 256 × 3KB (Falcon or XMSS) = ~768 KB per slot
  • Fits in a block; no aggregation needed
  • Can be deployed today (or soon after standardization)
  • Provides dynamic availability with PQ security

PQ Finality (Majorum, full validator set):

  • Requires PQ aggregation for 1M+ validators
  • Blocked on leanMultisig or other PQ aggregation maturing
  • Can be upgraded independently of the heartbeat
  • Timeline: 2027–2029 (per Strawmap)

This converts PQ migration from “solve aggregation first, then everything” → two independent problems.

Frame Transactions and Per-Transaction Key Rotation

EIP-8141 enables ephemeral key rotation that provides near-PQ mitigation for user transactions:

  • A singleton registry contract stores: (master_key, [ephemeral_key_1, ephemeral_key_2, ...])
  • Each transaction is signed with the next unused ephemeral key
  • Even if secp256k1 is broken by a CRQC, each key is used only once → exposed key does not compromise past or future transactions
  • Compatible with BIP44 HD key derivation
  • Not true PQ: a CRQC could derive the next ephemeral key from the previous one if the derivation is secp256k1-based. Requires switching the derivation to a PQ primitive for full protection.

FOCIL and PQ Signatures

The FOCIL + Native AA proposal (Mar 2026) explicitly addresses PQ signatures:

  • Falcon/Dilithium signatures exceed MAX_VERIFY_GAS_PER_FRAMETX (~100,000 gas) at current gas costs
  • PQ FrameTxs would be FOCIL-ineligible at launch
  • They propagate via alternative private channels (ERC-4337-style bundlers)
  • Their omission from blocks is always excused
  • Future: raise MAX_VERIFY_GAS_PER_FRAMETX in a later fork to enable PQ FOCIL inclusion

Strawmap PQ Roadmap

ForkTimelinePQ milestone
HegotáH2 2026PQ readiness groundwork (EIP-8141 ephemeral keys; FOCIL-awareness for PQ)
~2027H1 2027PQ heartbeat (Goldfish with concatenated Falcon sigs)
~2028H1 2028leanMultisig-based PQ finality (if proof secure)
~2029H1 2029Full PQ L1 (all validator operations PQ)

Open Questions

  • Will leanMultisig’s conjectured security assumption be formalized before 2028?
  • Can any lattice-based scheme provide BLS-equivalent aggregation at 1M scale?
  • Should Ethereum migrate user ECDSA (account keys) before consensus BLS, or simultaneously?
  • How do hardware wallets support PQ key management? (Most current hardware wallets don’t support Falcon/Dilithium)

Key Sources

  • Native Ephemeral Key Rotation via Frame Transactions (2026) — per-tx key rotation; quantum mitigation
  • Why Ethereum Needs a Dynamically Available Protocol (Zanolini, Mar 2026) — PQ heartbeat benefit; 768 KB concatenation math; leanMultisig
  • FOCIL + Native AA (Thomas Thiery, Mar 2026) — PQ sig gas > MAX_VERIFY_GAS; FOCIL-ineligibility