PDF Run this chapter's code LaTeX source Comments

Chapter 28Post-Quantum Migration of Blockchains

28.1Why this chapter matters#

Blockchains are one of the hardest post-quantum migration problems in existence, for two reasons the previous chapter only touched. First, the funds are secured by signatures whose public keys are, sooner or later, permanently public on an immutable ledger – so “harvest now, decrypt later” becomes a much sharper “store now, steal later.” Second, there is no administrator: changing the rules of Bitcoin or Ethereum is a governance problem settled by rough consensus and forks, not a software update pushed to servers. This chapter looks at how three ecosystems are actually approaching the transition, as of mid-2026: Bitcoin and Ethereum, the two largest, and Cosmos, which is furthest along in shipped code. Everything here is a moving target: the concrete proposals are drafts, not deployed consensus, and the reader should treat dates and statuses as a snapshot.

Mosca’s inequality \(x + y > z\) (Chapter 1) states the problem in one line, and blockchains are the case where it degenerates. The shelf life \(x\) of an exposed on-chain public key is not measured in years: the ledger is immutable and public, so the key is a target for as long as the chain exists and the coins remain unmoved. With \(x\) unbounded, \(x + y > z\) holds for any migration time \(y\) and any finite \(z\). The inequality therefore cannot be satisfied by better hardware forecasts or by moving faster; it can only be escaped by removing the exposure — which means moving the coins. That is why every roadmap in this chapter, whatever else it disputes, ends up arguing about how to make users act.

28.2Learning goals#

After reading this chapter, you should be able to:

• explain which blockchain primitives a quantum computer breaks (Shor) versus merely weakens (Grover), and the public-key-exposure principle;

• describe Bitcoin’s exposure by output type and the current draft proposals (BIP-360, BIP-361), and distinguish exposure caused by protocol design from exposure caused by user behaviour;

• inventory the cryptographic surfaces of a layer 2 by who can fix each one;

• explain why a hash-based or symmetric layer does not make a system post-quantum, and what to ask instead;

• describe Ethereum’s exposure and its two-front plan: an emergency hard fork and account-abstraction-based migration;

• explain why an EdDSA chain admits a migration route that an ECDSA chain does not, and why generating ECDSA keys from a seed does not close the gap;

• bound a migration by the throughput of the chain itself, and compute that bound;

• weigh the central controversy – whether to freeze quantum-vulnerable coins – and the honest uncertainty in the timeline.

28.3The blockchain threat model#

The immediate migration pressure is on signatures and pairing-based public-key systems. Shor’s algorithm (Chapter 1) threatens Bitcoin’s ECDSA and Schnorr, Ethereum’s account ECDSA and consensus BLS signatures, and the public-key assumptions behind SNARK and KZG systems [1, 2]. Grover gives hashes a square-root rather than exponential weakening, but hashes still require property- and output-length-specific assessment: HASH160, for example, has only a nominal \(2^{80}\) quantum preimage margin.

The subtlety that governs everything is when a public key becomes visible. P2PK and P2TR expose a public key or tweaked public key when a UTXO is created; P2PKH and P2WPKH usually reveal it on first spend, and reuse leaves later outputs exposed. Other scripts must be assessed by their actual path and witness.

28.4Bitcoin#

28.4.1What is exposed#

Bitcoin’s exposure is precisely a function of output type. Coins in pay-to-public-key (P2PK, the earliest, Satoshi-era outputs), raw multisig, and Taproot key-path outputs carry a public key on chain permanently and are long-exposure vulnerable. Coins in the hash-wrapped types (P2PKH, P2SH, P2WPKH) stay protected until the address is reused or spent, at which point the key is revealed [3, 4]. BIP-361 states that, as of 1 March 2026, over 34% of all bitcoin have revealed a public key on chain [5]; an independent Chaincode Labs analysis puts the exposed fraction in the range of roughly one-fifth to one-half of supply [4]. (Older and widely repeated figures attributing a specific amount to Satoshi-era P2PK are best treated as estimates rather than established fact.)

28.4.2Two kinds of exposure#

The aggregate percentage hides the more useful structure. Published on-chain analyses that break the exposed supply down by cause agree on the qualitative shape, even where their totals differ: roughly one quarter to one third of it comes from output types that publish a key by design (P2PK, raw multisig, Taproot key-path), and the clear majority — on the order of seven-tenths — comes from ordinary hash-wrapped addresses that were reused after being spent from. Figure 28.1 draws the mechanism; the split tells us how often each branch is taken.

The distinction matters because the two causes have different remedies and different politics:

• Design exposure is a property of the protocol. No user action can undo it — a P2PK output has its public key in the ledger forever, and the owner cannot retract it. Only a migration to a new output type helps, and for P2PK outputs whose keys are lost, nothing helps at all.

• Behavioural exposure is a property of how wallets were used. It was avoidable in principle, it is still accumulating today with every reused address, and — crucially — it is the part that education, wallet defaults, and fee policy can actually reduce before any consensus change ships.

The practical consequence is that the largest single share of Bitcoin’s quantum exposure does not require a soft fork to start shrinking. It requires wallets to stop reusing addresses, which is a change nobody has to be persuaded to ratify. Any exposure figure quoted without this breakdown makes the problem look more uniformly intractable than it is.

28.4.3The draft proposals#

Two Bitcoin Improvement Proposals anchor the response; both are Draft and not activated as of mid-2026:

• BIP-360, “Pay-to-Merkle-Root” (P2MR) [3] – formerly circulated as “Pay-to-Quantum-Resistant-Hash” (P2QRH) – introduces a new output type, proposed as a backward-compatible soft fork. In its current form it is essentially Taproot with the key-path spend removed, so that no bare public key is ever committed; notably, the current draft defers the choice of the actual post-quantum signature scheme (naming ML-DSA and SLH-DSA only as examples) to a future proposal, rather than mandating one.

• BIP-361, “Post-Quantum Migration and Legacy Signature Sunset” [5] – the migration-and-deadline layer. It proposes a phased sunset of ECDSA/Schnorr: a first phase (on the order of three years after activation) that stops sending funds to legacy address types, and a later flag-day (around five years) that restricts legacy signatures, so that only a holder who can prove ownership by a quantum-safe route can still move the coins.

28.4.4Choice of signature scheme#

For Bitcoin, a signature is an economic object rather than only a cryptographic one. Replacing a tens-of-bytes ECDSA or Schnorr signature with a kilobyte-scale post-quantum signature changes transaction weight, fees, block capacity, storage, relay, and synchronization. Falcon is attractive for compactness but has a more demanding sampler and numerical implementation; ML-DSA is structurally simpler but larger. The relevant comparison must therefore include both wire footprint and implementation risk.

BIP-360 deliberately leaves the scheme unspecified, so the question is open rather than settled; this subsection summarizes what the evidence constrains. A 2026 Blockstream Research review of the lattice candidates [6] works the problem through for Bitcoin specifically. Its central framing: for a chain, the cost metric is not the signature size but the combined public-key and signature size, because a spend writes both to the ledger. Under this metric the ranking of the schemes changes.

Three consequences follow from Table 28.1.

Security level for long-lived outputs.#

A Bitcoin output may remain unspent for decades, so the relevant security horizon is the lifetime of the output rather than of the software that created it. If cryptanalytic progress later pushes a scheme below its intended category, coins locked under the weakened keys remain exposed, and the freeze question of Section 28.4.6 returns. Large deployments already avoid Category 1 lattice parameters on these grounds: Apple’s iMessage PQ3 uses Categories 3 and 5, and Cloudflare pairs X25519 with ML-KEM-768 rather than ML-KEM-512, in both cases citing a margin against cryptanalytic progress over the lifetime of the system. Hash-based schemes are commonly deployed at Category 1, because the underlying assumption is older and better studied than the lattice assumptions.

The cost of a security margin.#

Falcon-1024, at Category 5, has a smaller combined footprint (3073 B) than the best stateless hash-based construction at Category 1 (7888 B) and than ML-DSA-65, the standardized form of Dilithium [7] (Chapter 17), at Category 3 (5261 B). For ML-DSA, raising the category from 2 to 3 adds about 1.5 kB per spend. Falcon is therefore the only candidate whose highest security category remains smaller than every alternative at lower categories.

Absence of an intermediate parameter set.#

The recursive sampler of Chapter 18 halves the ring degree at every step, so the admissible degrees are powers of two, and the parameter sets pass from \(n=512\) (approximately Category 1) directly to \(n=1024\) (above Category 5). There is no intermediate ring and therefore no intermediate parameter set; a deployment must choose one of the two.

Assessment.#

The review [6] recommends a staged transition. For immediate deployment it recommends a hash-based scheme, on two grounds: the hash assumption is the most mature of the alternatives, and FN-DSA is not a finished standard (FIPS 206 was still in development at this book’s snapshot, so there is no fixed specification, no test vectors, and no audited library ecosystem to integrate against). Once Falcon completes standardization, its size advantage over every hash-based alternative changes the comparison. The two families can also be combined: a stateful hash-based scheme with short common-case signatures can use Falcon as its stateless fallback, at a much smaller size than an SLH-DSA fallback for the rare recovery path.

28.4.5The wallet-derivation gap#

There is a second constraint on the choice, and it is not a size problem at all. Bitcoin wallets are hierarchical and deterministic: from one master extended public key, BIP-32 [8] derives an unbounded supply of child public keys using public data only, with the secret key never involved. That is what lets a watch-only hot wallet hand out fresh addresses while the seed stays in cold storage, and it is the backbone of essentially every wallet in use.

None of the standardized post-quantum signature schemes supports it. [6] BIP-32’s unhardened derivation is an addition in the elliptic-curve group — child key \(=\) parent key \(+\) tweak, on both the secret and public sides — and lattice schemes do not offer the same structure for free. The known replacements are research constructions, and expensive ones:

• Dilithium is the furthest along. Rerandomizable-key variants derive a child from a public update value and keep the two keys in step, at a combined footprint of roughly 6.5 to 8.3 kB depending on whether the wallet publishes an uncompressed key or carries a correction in every signature. The obstruction is that ML-DSA’s public-key compression is not additive, so an update cannot simply be added to a compressed parent.

• Falcon has one published construction, which rerandomizes the lattice basis. Doing so inflates the signature-norm bound and pushes an on-chain signature to roughly 23.7 kB, about \(36\times\) a Falcon-512 signature — and its stated parameters do not satisfy the scheme’s own security condition, so a corrected version is larger still. There is currently no workable public-key derivation for Falcon.

The Dilithium variants also carry a deployment assumption that inverts one of ML-DSA’s own design decisions. Unlinkability of derived addresses requires the matrix \(A\) to be shared network-wide. That is formally sound under Module-LWE, but Chapter 17 derives \(A\) from a per-key seed precisely to rule out a backdoored matrix and to stop one precomputation from applying to many targets. The preprocessing in dual-lattice attacks depends only on the matrix, so a single network-wide \(A\) would let one large reduction effort apply to every key on the chain at once. At Dilithium-3 dimensions that attack remains far out of reach — but the convention concentrates the whole network’s security on one instance, which is a different risk profile from the one FIPS 204 chose.

A recurring safety mechanism is commit–reveal: a holder first publishes a binding commitment and only later reveals it. It is designed to mitigate front-running under the stated confirmation-depth, reorganization, fee, timeout, and recovery assumptions; it is not an unconditional guarantee.

28.4.6The freeze controversy#

BIP-361’s sunset implies that coins whose owners never migrate – and coins for which no ownership proof is possible, notably P2PK – become effectively unspendable, i.e. frozen. This is the sharpest open dispute in Bitcoin’s roadmap. Proponents argue a pre-announced sunset is defensive: a quantum attacker would otherwise steal those coins outright, whereas a freeze at least preserves them. Critics call any forced migration confiscatory, contrary to Bitcoin’s property-rights ethos, and warn that freezing long-dormant coins (including Satoshi’s) sets a dangerous precedent. This is a genuine, unresolved political disagreement, not a settled plan, and should be read as such.

28.5Ethereum#

28.5.1What is exposed#

Ethereum has four distinct post-quantum migration surfaces: account authorization based on secp256k1/ECDSA, BLS consensus signatures, KZG commitments for data availability, and pairing- or discrete-log-based proof systems in applications and rollups. A roadmap that replaces only account signatures therefore leaves other quantum-vulnerable assumptions in the protocol stack.

Ethereum addresses reveal an effectively public key once an ECDSA transaction has been sent. BLS validator signatures, pairing curves behind SNARK verifiers, and KZG commitments all rely on public-key assumptions threatened by Shor [1, 2]. A comparison of quantum cost for secp256k1 and BLS12-381 needs group-specific resource estimates; the 381-bit base-field name alone is not such an estimate. KZG migration must distinguish blob retention from commitment binding, proof verification, and consensus dependencies; blob pruning alone does not make the risk mild.

28.5.2The two-front plan#

Ethereum’s response has an emergency track and a structural track; nothing post-quantum has yet shipped to mainnet.

The quantum-emergency hard fork.#

Vitalik Buterin’s proposal “How to hard-fork to save most users’ funds in a quantum emergency” [9] is the contingency plan. On evidence of large-scale theft, the chain would revert to the last pre-theft block, freeze legacy ECDSA accounts, and let users recover funds through a new transaction type carrying a STARK proof that the sender knows the hash preimage secret behind their address – authenticating by knowledge of a hash preimage rather than by an ECDSA signature. Because most users’ recovery secret was never exposed on chain, this protects the majority, at the cost of a wallet-software update. Buterin notes the infrastructure could in principle be built now.

Account abstraction as the migration vehicle.#

The structural plan is to let accounts choose their own signature scheme. EIP-7702 (“Set Code for EOAs,” Final, shipped in the 2025 Pectra upgrade) [10] lets an externally-owned account delegate to contract code, turning it into a smart account with arbitrary verification logic – although 7702 authorizations are themselves secp256k1-signed, so it is a stepping stone, not itself a post-quantum migration. The dedicated vehicle is EIP-8141 (“Frame Transaction,” Draft, 2026, co-authored by Buterin) [11], which explicitly describes native account abstraction as “a native off-ramp … to post-quantum secure systems,” supporting a slot for an arbitrary (custom, post-quantum) signature scheme alongside the classical ones. At the consensus layer, the plan is to replace BLS aggregation with a hash-based signature of the XMSS/Winternitz family (Chapter 19), aggregated inside a purpose-built zero-knowledge virtual machine. Both pieces exist as public prototypes: leanVM, which describes itself as a “minimal hash-based zkVM, for a Post-Quantum Ethereum,” and leanSig, a Rust implementation of the proposed signature scheme whose README states plainly that it is unaudited and not for production [12], and to move KZG commitments to STARK- or lattice-based alternatives; the Ethereum Foundation’s stated assessment targets first-layer post-quantum infrastructure around 2029 [2]. In August 2026 the Foundation announced a revision of this stack’s cryptographic base: the proof system is to be built over binary fields, so that the hash function throughout — in the signatures, in the Merkle commitments, and in the zkVM’s own commitment scheme — can be a standard one (SHA-2 or the BLAKE family) rather than an arithmetization-oriented hash such as Poseidon, on which the earlier prototypes relied. The announced schedule is a production-grade leanVM in 2027 and consensus-layer deployment in 2028 [13].

28.5.3On-chain verification choices#

The structural migration path may introduce post-quantum signature verification on chain; the emergency path instead proposes a STARK proof of seed/preimage knowledge. These are different authentication mechanisms. Their costs are scheme-, parameter-, implementation-, chain-, and gas-schedule-dependent, so a benchmark must state those details, including code commit and measurement date, before comparing gas figures.

Direct verification executes the post-quantum verifier in the contract. A proof-based design instead proves that verification occurred and checks only the proof on-chain. The latter changes both the cost model and the assumptions; the Layer 2 composition issues are developed in Section 28.9, and the post-quantum commitment choices inside such proofs in Section 28.9.5.

28.6Administrative keys: the concentrated case#

Everything so far has treated the threat as distributed: many users, each holding their own coins behind their own key, migrating at their own pace. One class of target inverts that structure completely, and it is under-discussed relative to its size.

A stablecoin is not a native asset but an upgradeable smart contract, and its behaviour is governed by a handful of privileged roles held by ordinary externally-owned accounts — which is to say, by ordinary secp256k1 keys with ordinary on-chain public keys. The roles vary by issuer, but the pattern is consistent:

• a proxy admin, which can replace the contract’s implementation and therefore its entire logic;

• a minter or master-minter role, which can issue tokens without corresponding reserves;

• a blacklister or freezer, which can immobilize balances;

• a pauser, which can halt all transfers.

The security properties here are unlike the rest of this chapter in three ways. The number of keys is tiny, so an attacker needs a handful of Shor executions rather than a campaign. The value controlled is enormous and shared — compromise does not drain one wallet but affects every holder of the token at once, along with every lending protocol, bridge, and exchange that treats it as collateral. And the damage is not bounded by the balance, because a proxy admin can rewrite the accounting rules rather than merely move funds.

Two mitigations that work elsewhere do not help. Multisignature control divides the private keys among several holders, but a quantum adversary derives each one independently from its published public key, so an \(m\)-of-\(n\) scheme raises the attacker’s cost by a factor of \(m\), not exponentially — the same linear degradation noted for user wallets. Hardware custody protects a key against extraction from a device, and Shor does not extract keys from devices; it derives them from the ledger.

The redeeming feature is that this is the one part of the problem with a responsible party. Nobody can compel millions of users to rotate their wallets, but a stablecoin issuer can migrate its own admin roles to post-quantum authorization on its own schedule — provided the chain gives it a post-quantum verification path to migrate to, which returns the problem to the protocol roadmaps above. Concentrated control is the reason this exposure is dangerous, and also the reason it is the most tractable item in the chapter.

28.7Cosmos#

Bitcoin and Ethereum are the chains the quantum discussion usually names, and on both of them the post-quantum work is still a proposal. The ecosystem that has gone furthest in shipped code is neither of them.

28.7.1An opt-in post-quantum consensus key#

Cosmos SDK v0.55 registers ML-DSA-65 (FIPS 204, Chapter 17) as a supported validator consensus key type [14, 15]. This is code in the tree, not a draft: the cosmos.crypto.mldsa65 proto package, the Amino routes, and an x/auth signature-verification cost parameter all ship enabled, and the init and testnet commands accept --consensus-key-algo ml_dsa_65.

What ships enabled is the capability, not the change. genesis.consensus_params.validator.pub_key_types still defaults to ["ed25519"], so an existing chain is unaffected until its own governance adds the new type. Because validator consensus key rotation ships in the same release, an existing chain can adopt post-quantum keys by adding the type and having validators rotate, rather than by starting a new genesis. That is a materially gentler migration path than a flag day.

28.7.2What the size actually costs#

The operational consequences are stated plainly, and they are the same physical fact that shapes every roadmap in this chapter: an ML-DSA-65 public key is 1952 bytes against ed25519’s 32, and a signature is 3309 bytes against 64 – roughly \(60\times\) and \(50\times\). CometBFT’s maximum signature size and per-validator commit-signature budget had to be raised to fit them, and chains enabling the type are told to revisit their block size and gossip framing limits. Every validator signs every block, so this lands squarely on the consensus hot path.

These two numbers are exactly what FIPS 204 prescribes for ML-DSA-65, and the reader can confirm them rather than take them on trust: the implementation of Chapter 17 derives both from the parameter set, \[|pk| = 32 + 32k(\mathrm{bitlen}(q-1) - d) = 1952,\] with the signature length following from \(\lambda\), \(\ell\), \(\gamma_1\), \(\omega\) and \(k\) in the same way.

28.7.3The interoperability hazard#

Cosmos surfaces a migration problem that a single monolithic chain never encounters, and it is the most transferable lesson in this chapter. IBC light clients on a counterparty chain verify your validator set’s commit signatures using the counterparty’s own compiled-in cryptography. If validators holding sufficient voting power start signing with a key type a counterparty cannot verify, headers fail verification there, packet flow with that chain stops, and the light client eventually expires [14]. The counterparty needs only the verification code, not the key type itself – but it does need it, first.

In an interoperable ecosystem, then, post-quantum migration is a coordination problem before it is a cryptographic one, and its failure mode is quiet: nothing breaks at the moment of upgrade, only later, when a connection that used to carry packets stops doing so. Any multi-chain migration plan needs a sequencing story, and no published one yet covers a large IBC graph.

28.8Seeds, preimages, and the EdDSA asymmetry#

Every migration route so far has required the owner to act before the attacker does. There is one family of mechanisms that does not, and it turns on a detail of key generation that most readers will never have had reason to notice.

28.8.1The recovery problem#

Suppose the worst has already happened: a quantum adversary has run Shor’s algorithm against an exposed public key and holds a valid private key. The chain can protect the coins only by refusing legacy signatures — but then the honest owner cannot spend either, because their private key is exactly the one the attacker now has. Recovering the coins requires the owner to demonstrate something the attacker cannot: not possession of the private key, which is no longer secret, but possession of some secret upstream of it.

Ethereum’s emergency plan (Section 28.5.2) is precisely this move: authenticate by proving knowledge of a hash preimage rather than by signing. What makes it work is that the recovery secret was never published, so Shor never touches it. What makes it ad hoc is that Ethereum must arrange for such a secret to exist.

28.8.2RFC 8032 arranges it by construction#

EdDSA does not need the arrangement, because its key generation already has this shape. Under RFC 8032 [16] an Ed25519 key begins as a 32-byte seed \(k\), and the signing scalar is derived by hashing it: \[h = \mathrm{SHA\text{-}512}(k), \qquad s = \mathrm{clamp}\big(h[0..31]\big), \qquad A = s\cdot B ,\] with the upper half \(h[32..63]\) retained as the deterministic nonce prefix. The value stored by the wallet is \(k\); the value that the public key commits to is \(s\).

This one hash is the whole asymmetry. Shor’s algorithm computes discrete logarithms, so from \(A\) an attacker recovers \(s\) — and stops there, because recovering \(k\) from \(s\) is a preimage search on SHA-512, which Grover reduces only quadratically. The honest owner knows \(k\) and the attacker does not, even after the curve is completely broken. The owner can therefore prove, in zero knowledge, \[\exists\, k \;:\; \mathrm{clamp}\big(\mathrm{SHA\text{-}512}(k)[0..31]\big)\cdot B = A ,\] binding the existing address \(A\) to a fresh post-quantum key, with no need to have moved the funds beforehand [17].

The distinction turns on the last clause:

• A pre-commitment scheme — publish a commitment to a future post-quantum key, as BIP-360’s commit–reveal does — requires every owner to act before Q-Day.

• A seed-preimage proof lets an owner recover after Q-Day, having done nothing at all.

Given that SegWit needed over three years to reach 80% of transactions while offering an immediate fee discount, “requires no prior user action” is not a minor convenience. It is the difference between a mechanism that reaches dormant coins and one that does not.

28.8.3Why not simply derive ECDSA keys from a seed?#

The obvious question is why ECDSA chains cannot adopt the same trick: define \(sk = H(\text{seed}) \bmod n\), keep the seed, and prove the preimage later. Cryptographically, nothing prevents it. ECDSA places no constraint on how the scalar is produced, so the construction is sound and the proof statement is the same shape.

More than that, it has already been done. BIP-32 hierarchical deterministic wallets [8] derive every signing key from a master seed through a chain of HMAC-SHA512 steps, and BIP-39 puts a mnemonic and PBKDF2 in front of that. Most Bitcoin and Ethereum keys in existence today do have a hash between the secret their owner wrote down and the scalar their address commits to. The blanket claim that ECDSA chains lack this layer is a statement about the protocol, and it is too strong as a statement about wallets.

The gap is nevertheless real, and it is instructive because it is not a cryptographic gap at all. Three things separate a protocol invariant from a widespread convention:

1. Universality. RFC 8032 makes seed-then-hash the definition of Ed25519 key generation, so every conforming key has the structure. In ECDSA it is a wallet choice, and the exceptions are exactly the high-value historical cases: early Bitcoin keys from dumpprivkey, brainwallets, paper wallets, exchange- and HSM-generated keys, and anything produced before BIP-32 existed in 2012.

2. Detectability. Given an address, nothing on chain reveals whether it has BIP-32 ancestry. A consensus rule cannot offer a recovery path to seed-derived keys and freeze the rest, because it cannot tell them apart in advance; owners of raw-entropy keys would discover the problem only at the moment they tried to recover.

3. A single statement to prove. Ed25519 needs one circuit. ECDSA recovery would have to cover BIP-32 against SLIP-0010 against Electrum’s scheme against raw entropy, hardened against non-hardened derivation, and an arbitrary derivation path — either as a much larger circuit or by revealing the path as a public input, which is probably acceptable but is one more thing to specify and get adopted.

And for keys generated from now on, the idea dissolves entirely. Changing key generation requires a wallet software update; if a wallet is being updated anyway, it should generate an ML-DSA key rather than a cleverly-derived ECDSA one. The seed-preimage route has value only retroactively, for coins already sitting at addresses whose owners cannot or will not act — which is also, not coincidentally, the population every other mechanism in this chapter fails to reach.

28.8.4Caveats that apply to both#

Three conditions are easy to overlook, and each one connects to material elsewhere in this chapter.

It is recovery, not protection.#

A seed proof does nothing while legacy signatures are still valid: the attacker holds a working private key and simply spends with it, faster than the owner will notice. The mechanism only has force on a chain that has already disabled legacy authorization. It therefore does not sidestep the freeze controversy of Section 28.4.6 — it presupposes that the sunset argument has been won.

The proof system must itself be post-quantum.#

Proving a hash preimage inside a Groth16 verifier over a pairing-friendly curve would produce an argument whose soundness Shor breaks, and the resulting system would be no better than the ECDSA it replaced. This is exactly the error catalogued in Section 28.9.1: a hash-based statement carried by an elliptic-curve argument. A STARK or other hash-based proof system is required, and it must be checked all the way down, including its lookup and memory arguments.

The proof must be bound to the destination.#

Recovery proofs are published. If a proof establishes only “someone knows the seed behind \(A\)” without committing to where the funds go, an attacker watching the mempool can replay it in a transaction paying themselves. The proof statement must include the destination, which makes it a signature over the recovery transaction rather than a free-floating attestation — the same front-running hazard, with the same class of fix, as the commit–reveal construction discussed above.

28.9Layer 2s: the composition problem#

The three chains above each migrate one system. A layer 2 does not have that luxury. A rollup or sidechain that settles to Bitcoin is a composition of systems designed separately, migrating on separate timelines, owned by separate parties: it settles to a base layer it cannot change, usually borrows a consensus stack from a third ecosystem, and operates a bridge whose trust root is cryptography of its own choosing [18].

That composition changes the question. For a single chain one may sensibly ask “when will it be post-quantum?” For a layer 2 the only answerable question is which surfaces do we own, and what is the residual risk on the rest? Table 28.4 is the inventory that question needs.

28.9.1The reach of a symmetric layer#

The most useful lesson from auditing such a stack is a negative one, and it generalizes well beyond blockchains: a hash-based or symmetric layer protects only what it carries.

Three instances of the same mistake, all from one real bridge:

• Bitcoin-side bit commitments implemented as Winternitz one-time signatures (Chapter 19) — hash-based, and genuinely post-quantum — were committing the elements of a Groth16 proof over a pairing-friendly curve. The commitment survives Shor; the thing committed does not.

• A garbled-circuit evaluator, built from AES and a hash function and therefore symmetric throughout, was garbling a Groth16 verifier. Garbling changes how the verifier executes, not what it asserts.

• A FRI-based STARK, whose polynomial commitment is hash-based, used an elliptic-curve multiset hash for its offline memory-consistency argument. A quantum adversary never attacks FRI; it forges the memory check [19].

In each case a correct statement — “this layer is hash-based” — supported a false conclusion. The habit to build is to ask what a layer carries, and to keep asking until the answer is a hardness assumption rather than a primitive.

28.9.2The several assumptions inside one proof system#

The third instance deserves emphasis because it is the least obvious. A proof system is not one assumption but several, and the headline commitment scheme is only the most visible. Permutation arguments, lookup arguments and offline memory checks are all places where an elliptic-curve accumulator can sit inside an otherwise hash-based system.

The concrete example is a zkVM whose multiset hash mapped memory values to curve points, so that soundness of the memory argument rested explicitly on discrete log — documented by the project itself, with the fix being a lattice-based multiset hash (LtHash) in the sense of [20], and a working prototype [19]. The encouraging part of that story is that the fix is a primitive swap inside an existing argument, not an architectural change. The cautionary part is that the exposure was visible only in the project’s own issue tracker, not in its dependency list.

28.9.3The exposure that cannot be migrated#

One row of Table 28.4 behaves unlike the others. An account can adopt a new signature scheme because its owner opts in. A precompile cannot: on an EVM chain the elliptic-curve and pairing precompiles (ecrecover, the BN254 group and pairing operations, the BLS12-381 suite, KZG point evaluation) are consensus rules, and the contracts that call them are immutable bytecode. Every on-chain SNARK verifier calls the pairing precompile; that code cannot be upgraded, and generally nobody has the authority to upgrade it.

So this exposure is fixed at deployment time. After a chain is live, the only available action is an inventory — which deployed contracts depend on which precompile, and which of those are consensus- or bridge-critical — and that inventory is worth doing early, because an immutable caller can be identified now but never migrated later.

28.9.4Replacing signature aggregation#

A bridge or consensus layer that aggregates signatures gets a large constant factor from BLS: many signatures verify as one. No standardized post-quantum signature aggregates. ML-DSA and SLH-DSA have no aggregation, so a naive replacement turns one signature into \(N\), each one to two orders of magnitude larger than what it replaced — for a committee of twenty ML-DSA-65 signers, tens of kilobytes where there were tens of bytes.

This is the same wall Ethereum hit at the consensus layer, and the reason its answer is a hash-based signature scheme aggregated inside a zkVM rather than a drop-in replacement (Section 28.5.2). Any system whose design depends on aggregation should expect its post-quantum migration to be an architectural project, not a key-type change.

The word aggregation covers three different requirements, and the post-quantum options differ for each.

Recovering aggregation with a proof system.#

The Ethereum route replaces the aggregate with a proof: each validator signs with a hash-based scheme, and a zkVM proves that \(N\) signatures verified. It recovers a constant-size object for any \(N\) and any set of messages, at the cost of an entire proving pipeline, and it is the only route with a credible path to \(N\) in the hundreds of thousands.

Threshold signing.#

Most bridge and committee designs need less than general aggregation: many signers, one message, accepted once a threshold of them has signed. That is the shape a threshold signature has natively — \(t\) of \(n\) parties run a protocol and jointly emit a single ordinary signature under a joint public key — and unlike aggregation it leaves the verifier untouched: the chain keeps checking one FIPS 204 signature with a stock verifier, whatever the size of the signing set. Two 2026 constructions make this concrete for ML-DSA and differ in the dimension that matters for a committee. Quorus [21] supports any \(t\)-of-\(n\) by evaluating the ML-DSA signing algorithm inside a multi-party computation, at roughly \(100\) kB of communication per party per rejection-sampling round; Celi et al. [22] give a lighter protocol limited to about six parties at up to 1 MB per party. Both produce signatures and keys byte-identical to single-signer ML-DSA. For a signing set in the tens only the first scales.

The price is a change in signing shape rather than in key type. Today each committee member signs independently and offline and a bitmap records who did; threshold signing replaces that with a live multi-round protocol among the selected quorum, so a liveness-tolerant design acquires a signing-time availability requirement. And none of it is standardized: NIST’s first call for multi-party threshold schemes, IR 8214C [23], was finalized only in January 2026. For a peg or bridge trust root, depending on a construction with no FIPS number is a governance decision as much as a technical one, which argues for migrating any key that needs no aggregation first.

Research schemes illustrate why there is no generic “threshold wrapper.” Threshold Raccoon chooses a signing relation designed for collaborative computation and masks participant responses so that the masks cancel only in the aggregate [24]. Flood and Submerse tackles distributed key generation and robust signing by combining projection, Gaussian noise, and verifiable secret sharing to keep hidden shares within the correctness region [25]. In both cases, rounds, communication, robustness, and the noise budget are part of the construction rather than implementation details.

Post-hoc aggregation.#

The option that sounds best — compress \(N\) existing signatures into one small object without changing how anyone signs — works worst. The first aggregate signature for Fiat–Shamir-with-aborts schemes [26] reports “quite small compression rates” in its authors’ words, and aggregates distinct messages where a committee has one. The strong result in this line, aggregating with LaBRADOR (Section 28.9.5), applies to Falcon and not to ML-DSA. If aggregability is a first-order requirement, it is a consideration in which post-quantum scheme to adopt, not a problem to solve afterwards.

28.9.5The commitments inside the proof system#

The question of the preceding subsections — what does each layer carry — applies to the proof system itself. There it becomes a question about the polynomial commitment, because that is where a quantum adversary attacks: the rest of a modern argument is field arithmetic over a transcript.

A signature verifier that is fast in native code may still be expensive inside an arithmetic circuit. Loquat, for example, builds a succinct verification relation around the Legendre PRF and a multivariate polynomial commitment [27]. Evaluating such a route requires constraint count, field compatibility, witness-generation time, proof size, verification cost, and the maturity of its assumptions—not CPU cycles alone.

Two families of commitment are in use, and they differ in what they assume rather than in how fast they run.

• Hash-based commitments — FRI, and its successors STIR and WHIR — open a Merkle tree, so the assumption is a random oracle plus collision resistance, with nothing algebraic underneath. This is what makes a STARK post-quantum, and it is why the memory-check bug of Section 28.9.1 was a bug rather than a design choice: an elliptic-curve accumulator had been placed inside a system whose commitment assumed nothing of the kind.

• Lattice-based commitments — the LaBRADOR line [28] — commit with an Ajtai commitment, which is a matrix–vector product over the module of Chapter 13 and is opened by ring arithmetic rather than by hashing. There is no hash anywhere in the opening.

The Ajtai commitment#

The whole scheme is one line of linear algebra. Fix the ring \(R_q=\mathbb{Z}_q[X]/(X^d+1)\) of Chapter 13 — Greyhound’s implementation takes \(d=64\) — and a norm bound \(\beta\).

The figures in this section follow the convention of the lattice zero-knowledge literature [29] rather than the numbered pseudocode used elsewhere in this book: a header declaring what is public and what is private, then the two parties in columns with the messages between them, and the verifier’s checks gathered into a closing Accept iff. For these protocols the interesting content is who knows what and who sends when, and that convention shows it.

Three properties, each doing real work.

Compression.#

The commitment is \(\kappa\) ring elements no matter how large \(n\) is, so \(\kappa d\lceil\log_2 q\rceil\) bits stand for a witness of any length. A second property accompanies this one: because the hardness of SIS does not depend on the dimension of the solution, lengthening the witness does not weaken the assumption either, so a longer witness costs neither space nor security. \(\mathbf{A}\) is public randomness, with no trusted setup and no structured reference string, exactly as for a Merkle root.

Binding.#

Suppose \(\mathbf{s}\ne\mathbf{s}'\) both open \(\mathbf{t}\). Subtracting the two verification equations gives \[\mathbf{A}(\mathbf{s}-\mathbf{s}') = \mathbf{0} \bmod q, \qquad \mathbf{s}-\mathbf{s}' \ne \mathbf{0}, \qquad \|\mathbf{s}-\mathbf{s}'\| \le 2\beta ,\] which is precisely a solution to Module-SIS at bound \(2\beta\).

Read as a reduction, this is tight and direct. An adversary against binding is handed the M-SIS matrix unmodified (the challenge distribution and the commitment key are the same uniform \(\mathbf{A}\), so nothing has to be simulated), and its output is converted into a solution by a single subtraction. There is no rewinding, no random oracle, and no loss: \(\mathrm{Adv}^{\mathrm{bind}} \le \mathrm{Adv}^{\text{M-SIS}}_{2\beta}\).

The comparison with a Merkle commitment cuts both ways. Binding here rests on the hardness of one specific algebraic problem, Module-SIS in a fixed ring at a fixed bound, where a Merkle commitment asks only that some hash function be collision-resistant; in that sense the lattice assumption is the stronger one, and structure is where the failures earlier in this section came from. Against that, M-SIS is a falsifiable, parameterized assumption used through a tight reduction, whereas a STARK’s soundness argument goes through the random-oracle model, an idealization of the hash rather than an assumption about it, together with the proximity-gap conjectures of its proof of proximity. The lattice commitment assumes more, and states precisely what it assumes; the hash-based one assumes less, through a model that cannot be falsified.

Hiding.#

As drawn, Figure 28.2 is a deterministic function of \(\mathbf{s}\): it binds, but it emphatically does not hide, since testing a guess means recomputing \(\mathbf{A}\mathbf{s}\) and comparing. That stripped form is what a succinct argument uses, for a reason returned to below. Stated in full, the Ajtai scheme carries randomness \(\mathbf{s}_2\) alongside the message \(\mathbf{s}_1\), both short: \[\mathbf{A}_1\mathbf{s}_1 + \mathbf{A}_2\mathbf{s}_2 = \mathbf{t} \bmod q .\] Binding is the same subtraction as before. Hiding now follows because \((\mathbf{A}_2,\mathbf{A}_2\mathbf{s}_2)\) is indistinguishable from uniform, which is decisional Module-LWE (Chapter 13). Binding from SIS, hiding from LWE — the two hard problems of Part II, one each, on the same matrix.

The alternative is the BDLOP commitment, where only the randomness \(\mathbf{s}\) need be short and the message may be arbitrary modulo \(q\): \[\begin{bmatrix}\mathbf{A}\\ \mathbf{B}\end{bmatrix}\mathbf{s} \;+\;\begin{bmatrix}\mathbf{0}\\ \mathbf{m}\end{bmatrix} \;=\;\begin{bmatrix}\mathbf{t}_A\\ \mathbf{t}_B\end{bmatrix} \bmod q .\] The two schemes trade against each other in a way that determines the shape of the protocols built on them. Ajtai demands a short message, but the message’s dimension does not enlarge the commitment at all — and since the hardness of SIS does not really depend on the dimension of the solution, a longer witness costs no security either. BDLOP accepts arbitrary messages and lets further elements be appended for one ring element apiece, but its commitment and its opening grow linearly in the message. So one is for long witnesses with small coefficients and the other for short witnesses with large ones, and protocols need both: Lyubashevsky, Nguyen and Plançon therefore fuse them into a single ABDLOP commitment [29], putting the long witness in the Ajtai part and the low-dimensional auxiliary terms a protocol accumulates in the BDLOP part, which yields the Ajtai commitment for free because one \(\mathbf{t}_A\) serves both.

Both properties are computational, and that is forced rather than chosen: no commitment is simultaneously statistically binding and statistically hiding, since an unbounded adversary breaks whichever was not paid for. Pushing the randomness up to statistical hiding (a regularity argument over \(R_q\)) makes it long, and the opening has to stay short for binding to bite, so the parameters pull against each other.

Which is why the stripped form is the one that appears in this section. A proof system needs the hiding half only if it wants zero knowledge, and these do not by default — LaBRADOR and Greyhound are arguments of knowledge, with zero knowledge available as a costed variant. Worth knowing before assuming that a “commitment” inside a lattice argument conceals anything: usually it is there to bind a prover, not to keep a secret.

Linear homomorphism and norm growth.#

\(\mathbf{A}\mathbf{s}_1+\mathbf{A}\mathbf{s}_2=\mathbf{A}(\mathbf{s}_1+\mathbf{s}_2)\), which is why witnesses can be folded and batched at all. But the bound moves with them: the sum opens to something of norm up to \(2\beta\), a challenge-weighted combination to more, and every round of folding must budget for the growth. In a Merkle tree an opening is exact and composition is free. Here norms are the currency, and the parameters are a norm budget.

The opening problem#

Note what Figure 28.2 does not give: opening it means sending \(\mathbf{s}\), all \(n\) ring elements of it. The commitment is short but its opening is as long as the witness — the exact opposite of a Merkle tree, whose commitment is short and whose openings are logarithmic, at the price of a hash per level.

The central problem of lattice succinct arguments is therefore to convince a verifier that a short opening exists without sending it. LaBRADOR’s answer is recursion — reduce a system of quadratic relations over \(R_q\) to a smaller system of the same shape, commit, and repeat, so the transcript is a sequence of commitments rather than a witness.

The LaBRADOR argument#

LaBRADOR [28] is a proof of knowledge for one fixed shape of statement, the dot-product constraint system: the witness is \(r\) short vectors \(\mathbf{s}_1,\dots,\mathbf{s}_r\in R_q^{n}\) with \(\sum_i\|\mathbf{s}_i\|^2\le\beta^2\), and the constraints are polynomial identities that are quadratic in the inner products, \[\sum_{i,j} a_{ij}\,\langle \mathbf{s}_i,\mathbf{s}_j\rangle \;+\;\sum_i \langle \boldsymbol{\varphi}_i,\mathbf{s}_i\rangle \;+\; b \;=\; 0 \qquad\text{in } R_q ,\] one such equation per constraint. The public data of a constraint are of three kinds. The \(a_{ij}\in R_q\) are scalar coefficients on the quadratic terms, the inner products of two witness vectors. Each \(\boldsymbol{\varphi}_i\in R_q^{n}\) is a public vector of the same length as \(\mathbf{s}_i\), so that \(\langle\boldsymbol{\varphi}_i,\mathbf{s}_i\rangle\) is the linear term in \(\mathbf{s}_i\); the tuple \((\boldsymbol{\varphi}_1,\dots,\boldsymbol{\varphi}_r)\) is the linear coefficient vector of the constraint. And \(b\in R_q\) is the constant. A constraint is therefore a quadratic form in the witness with the inner product as its only nonlinearity, and a purely linear constraint is the case in which every \(a_{ij}\) is zero.

Two examples show how a statement is written in this form. The opening of an Ajtai commitment, \(\mathbf{A}\mathbf{s}=\mathbf{t}\) with \(\mathbf{A}\in R_q^{\kappa\times n}\), is \(\kappa\) linear constraints, the \(k\)-th of them having \(r=1\), \(\boldsymbol{\varphi}_1\) equal to the \(k\)-th row of \(\mathbf{A}\), and \(b=-t_k\); the shortness of \(\mathbf{s}\) is not a constraint but the norm bound \(\beta\) carried alongside the system. A claim about an inner product, such as \(\langle\mathbf{s}_1,\mathbf{s}_2\rangle=v\), is one quadratic constraint with \(a_{12}=1\), no linear part, and \(b=-v\). R1CS, and the verification equations of lattice signatures, translate into collections of such constraints in the same way; that is what makes LaBRADOR a general-purpose argument rather than a proof of one relation.

The split into a quadratic part and a linear part is not cosmetic, because the protocol treats the two differently. The quadratic terms are handled by committing to the inner products \(g_{ij}=\langle\mathbf{s}_i,\mathbf{s}_j\rangle\) themselves. The linear terms cannot be committed the same way, since after amortization the verifier holds a single combination \(\mathbf{z}=\sum_ic_i\mathbf{s}_i\) and the cross terms \(\langle\boldsymbol{\varphi}_i,\mathbf{s}_j\rangle\) mix; the prover commits the mixed values \(h_{ij}\) and the verifier must form the combined coefficient vector \(\sum_ic_i\boldsymbol{\varphi}_i\) itself. Forming it touches every \(\boldsymbol{\varphi}_i\), and the \(\boldsymbol{\varphi}_i\) together are as large as the public statement, which is where the linear verifier of the figure below comes from.

A single round of the protocol turns one such statement into a smaller one of the same shape, and the proof is the transcript of repeating that until the statement is small enough to answer in the clear.

1. Commit. The prover commits to each \(\mathbf{s}_i\) with an Ajtai commitment \(\mathbf{t}_i=\mathbf{A}\mathbf{s}_i\) (Figure 28.2), then commits again to the vector of all the \(\mathbf{t}_i\), split into short digits, so that what is sent is one short outer commitment rather than \(r\) inner ones. The same is done for the inner products \(g_{ij}=\langle\mathbf{s}_i,\mathbf{s}_j\rangle\) that the quadratic constraints will need.

2. Prove the norm by projection. The verifier sends random matrices \(\Pi_i\) with entries in \(\{-1,0,1\}\) and the prover returns the projection \(\mathbf{p}=\sum_i\Pi_i\mathbf{s}_i\), a vector of \(256\) integers regardless of \(r\) and \(n\). By the Johnson–Lindenstrauss lemma, \(\|\mathbf{p}\|\) is, with overwhelming probability, within a constant factor of \(\sqrt{\smash[b]{\textstyle\sum_i\|\mathbf{s}_i\|^2}}\), so a short \(\mathbf{p}\) certifies the norm bound at a cost independent of the witness size. Verifying that \(\mathbf{p}\) really is the projection is itself a linear constraint on the \(\mathbf{s}_i\), and is folded into the next step.

3. Aggregate and amortize. The verifier sends random weights, and all the constraints are combined into a few. It then sends short polynomial challenges \(c_1,\dots,c_r\), and the prover answers with the single vector \(\mathbf{z}=\sum_i c_i\mathbf{s}_i\). The verifier checks \(\mathbf{A}\mathbf{z}=\sum_i c_i\mathbf{t}_i\), which the homomorphism makes possible without seeing any \(\mathbf{s}_i\), and checks the combined constraint against \(\mathbf{z}\) and the committed \(g_{ij}\), using \(\langle\mathbf{z},\mathbf{z}\rangle=\sum_{i,j}c_ic_j\,g_{ij}\).

4. Recurse. What the verifier now holds is a claim that \(\mathbf{z}\), together with the openings of the outer commitments, is short and satisfies a dot-product constraint system — the same shape as the input, with the \(r\) witness vectors replaced by one (plus the digit vectors of the commitments), and with the norm bound grown by the size of the challenges. Instead of sending \(\mathbf{z}\), the prover treats this new statement as the input to another round.

Figure 28.3 writes one round in the convention of the rest of this section.

Each round shrinks the witness by roughly the factor \(r\) that amortization buys, and the total transcript is a handful of commitments and one \(256\)-entry projection per round, plus the final small witness sent in the clear. That is where the size comes from: about \(58\) kB for an R1CS instance of \(2^{20}\) constraints at the 128-bit level, essentially independent of the statement size beyond a few rounds. And it is where the verifier’s cost comes from: to check the combined constraint the verifier must form \(\sum_i c_i\boldsymbol{\varphi}_i\) over the original public statement, so its work is linear in the statement even though the proof is not. Greyhound (below) is the construction that supplies a sublinear verifier, and it uses LaBRADOR only to compress its transcript.

The outline above compresses two papers into a page. A lecture-length treatment of the same path — Ajtai commitments and Lyubashevsky-style proofs, then LaBRADOR, then Greyhound, then the LaBRADOR and Greyhound proof-of-concept implementations — with slides, recordings and participants’ notes, is the lattice course of the ZKP Academy [30], and it is the recommended companion to this section for a reader who wants the protocols in full rather than in outline.

Extraction from such a proof carries a cost. It does not hand back the witness that was committed. What it yields is a \(\bar{\mathbf{s}}\) and a short polynomial \(c\) with \[\mathbf{A}\bar{\mathbf{s}} = c\,\mathbf{t} \bmod q, \qquad \|\bar{\mathbf{s}}\| \ \text{larger than}\ \|\mathbf{s}\| ,\] which is a different equation: the norm has grown, and an unknown multiplicand has appeared. That gap is called slack, and it is not a proof artefact to be tidied away later.

Two consequences show why. Practically, a scheme downstream of such a proof inherits the \(c\). In lattice verifiable encryption this was for years the reason the decryptor had to guess \(c\) in order to decrypt, making expected decryption time track the adversary’s running time — so the scheme could only be deployed where an attacker’s time could be bounded [29]. And in parameters, slack compounds: a larger extracted solution demands a larger modulus for SIS security, which demands a larger dimension for LWE security, which enlarges everything again. It is the same wall that aggregating Falcon signatures hit, where LaBRADOR’s norm check proved “both approximate and with respect to the entire witness,” with the slack growing in the number of signatures, forcing the first iteration to be replaced with an exact proof of smallness [31]. Much of the work in this area over the past decade concerns reducing or removing slack.

From a commitment to a polynomial commitment#

Figure 28.2 commits to a vector. A proof system needs to commit to a polynomial \(f\) and later convince a verifier that \(f(x)=y\) at a point \(x\) chosen after the commitment — a polynomial commitment scheme, or PCS. Two requirements: it is binding, so no prover can answer two different values at the same point; and it is succinct, so the commitment and the evaluation proof are far smaller than \(f\) itself.

The polynomial commitment as the unit of migration.#

Most modern argument systems — STARKs, PLONK and their descendants — factor into two independent pieces:

1. a polynomial interactive oracle proof, in which the prover hands the verifier idealized oracles for some polynomials and the verifier queries them. This half is information-theoretic: it assumes nothing, and a quantum adversary gains nothing against it.

2. a compiler that replaces each oracle with a polynomial commitment, and each interaction with Fiat–Shamir.

Every computational assumption in the system enters through the second step. That is why “is this proof system post-quantum?” is nearly always a question about its PCS, and why the Ziren repair earlier in this section is a primitive swap rather than a redesign: the protocol above the commitment does not know or care what the commitment is made of.

The square-root decomposition.#

For the lattice row, the bridge from Figure 28.2 to a PCS is a reshaping. Write \(f(X)=\sum_{i<N} f_i X^{i}\) with \(N=n\cdot m\), arrange the coefficients into an \(n\times m\) matrix \(M\) with \(M_{i,j}=f_{i+jn}\), and the evaluation factors: \[f(x)\;=\;\sum_{j<m} x^{jn} \sum_{i<n} f_{i+jn}\,x^{i} \;=\;\mathbf{a}(x)^{\!\top} M\, \mathbf{b}(x), \qquad \begin{aligned} \mathbf{a}(x)&=(1,x,\dots,x^{n-1}),\\ \mathbf{b}(x)&=(1,x^{n},\dots,x^{(m-1)n}). \end{aligned}\] A quadratic form, and a commitment that is linearly homomorphic can be pushed through one side of it.

Both the transcript and the verifier are \(O(\sqrt{N})\): the prover sends one column’s worth of data instead of the whole matrix, and the verifier does \(O(\sqrt{N})\) ring operations instead of reading \(f\).

Why the real protocol has three rounds.#

The figure is the idea, and one step short of a protocol. The entries of \(\mathbf{b}(x)\) are powers of \(x\) and are not small, so \(\mathbf{w}=M\mathbf{b}(x)\) is not short either and check 1 cannot be satisfied at any useful bound. A real instantiation therefore inserts a round: the verifier sends a short random challenge, the prover answers with a combination weighted by it, and the response stays inside the norm budget. That extra round is the difference between the picture and Greyhound; the difficulty lies in the norm bounds rather than in the algebra. Figure 28.5 gives the protocol as Greyhound runs it. It differs from the sketch in two further respects: what is public, and which side of the quadratic form the challenge lands on.

Inner and outer commitments.#

Figure 28.4 lists the column commitments \(\mathbf{t}_j\) as public. In Greyhound they are not; only a commitment to them is. The reason is size. Each \(\mathbf{t}_j=\mathbf{A}\mathbf{f}_j\) is a binding Ajtai commitment to a short column, but there are \(m=O(\sqrt{N})\) of them, so a commitment to \(f\) consisting of all the \(\mathbf{t}_j\) would be \(O(\sqrt{N})\) long. Greyhound therefore commits twice: the inner commitments \(\mathbf{t}_j=\mathbf{A}\mathbf{f}_j\), and an outer commitment \[\mathbf{u}\;=\;\mathbf{B}\,G^{-1}(\mathbf{t}_1\|\cdots\|\mathbf{t}_m)\] to the concatenation of all of them. The gadget inverse \(G^{-1}\) is not optional: the \(\mathbf{t}_j\) are uniform modulo \(q\), and an Ajtai commitment binds only short inputs, so they are first split into short digits and the digit vector is what \(\mathbf{B}\) commits. The polynomial commitment is \(\mathbf{u}\), a handful of ring elements whatever \(N\) is; the \(\mathbf{t}_j\) are revealed inside the evaluation proof and checked against it. This is the same two-level pattern as step 1 of the LaBRADOR outline in Section 28.9.5.

Where the challenge lands.#

The response that must be short is a combination of columns weighted by a short challenge, \(\mathbf{z}=F\mathbf{c}\); the partial evaluations \(w_j=\langle\mathbf{a}(x),\mathbf{f}_j\rangle\) are sent in the clear and need not be short at all, because \(\mathbf{z}\) pins them.

SageMath experiment: the commitment and the evaluation protocol#

The two figures are short enough to run. The first listing is Figure 28.2 in a toy ring, \(R_q=\mathbb{Z}_{12289}[x]/(x^{16}+1)\) with \(\kappa=2\) and \(n=8\): a uniformly random \(\mathbf{A}\), a ternary witness, the commitment \(\mathbf{t}=\mathbf{A}\mathbf{s}\), and the verifier’s two checks. The parameters are far too small for security; they are chosen so that every object can be printed.

# The Ajtai commitment in a toy ring: t = A s with s short.
q, d, kappa, n = 12289, 16, 2, 8
R.<x> = PolynomialRing(GF(q)); Rq.<X> = R.quotient(x^d + 1)

def centered(v):        # coefficients of a ring element in (-q/2, q/2]
    return [c - q if c > q // 2 else c for c in map(Integer, v.lift().list() + [0]*d)][:d]
def norm2(vec):         # squared Euclidean norm of a vector of ring elements
    return sum(c^2 for v in vec for c in centered(v))
def short(k, bound=1):  # k ring elements with coefficients in [-bound, bound]
    return vector(Rq, [Rq([randint(-bound, bound) for _ in range(d)]) for _ in range(k)])

A = random_matrix(Rq, kappa, n)      # public randomness, no trapdoor
s = short(n)                          # the witness
t = A * s                             # the commitment: kappa ring elements
beta2 = n * d                         # every coefficient at most 1 in size

def open_ok(t, s):                    # the verifier of Figure 28.2
    return A * s == t and norm2(s) <= beta2

print("opens:", open_ok(t, s))
s_long = short(n, bound=q // 4)       # long vectors fail the norm check, whatever A s is
print("long vector passes the norm check:", norm2(s_long) <= beta2)

The second listing continues from the first and runs Figure 28.5: an \(n\times m\) matrix \(F\) of short ring elements, the \(m\) inner commitments, the gadget decomposition into base-16 digits and the outer commitment \(\mathbf{u}\), then the three rounds and the five checks. digits is \(G^{-1}\) and undigits is \(G\); the verifier never sees \(F\) or the \(\mathbf{t}_j\) except through \(\mathbf{u}\) and the digits it is handed. Tampering with one partial evaluation makes check 5 fail, which is the consistency that \(\mathbf{z}\) enforces.

# The square-root PCS: inner and outer commitments, then the
# three-round evaluation protocol.  Continues from the Ajtai listing.
m = 4                                  # F is n x m: N = n*m short ring elements
ell, base = 4, 16                      # 16^4 > q: four digits per coefficient

def digits(vec):                       # G^{-1}: split each coefficient in base 16
    out = []
    for v in vec:
        cs = [Integer(c) for c in v.lift().list() + [0]*d][:d]
        for j in range(ell):
            out.append(Rq([(c >> (4*j)) & 15 for c in cs]))
    return vector(Rq, out)
def undigits(dv):                      # G: the inverse map
    return vector(Rq, [sum(dv[i*ell + j] * base^j for j in range(ell))
                       for i in range(len(dv) // ell)])

B = random_matrix(Rq, kappa, kappa * m * ell)   # for the outer commitment
F = matrix(Rq, n, m, lambda i, j: short(1)[0])  # the committed coefficients
T = [A * F.column(j) for j in range(m)]         # inner commitments t_j
tvec = vector(Rq, sum((list(t) for t in T), []))
u = B * digits(tvec)                             # outer commitment: the PCS commitment

xpt = Rq.random_element()                        # evaluation point
a = vector(Rq, [xpt^i for i in range(n)]); b = vector(Rq, [xpt^(n*j) for j in range(m)])
y = a * F * b                                    # the claimed value f(x)

# Round 1: prover sends the digits and the partial evaluations.
dvec = digits(tvec); w = vector(Rq, [a * F.column(j) for j in range(m)])
# Round 2: verifier sends a short challenge.  Round 3: prover answers with z.
c = short(m); z = F * c

def verify(dvec, w, c, z):                       # the five checks of the evaluation figure
    digit_ok = all(0 <= Integer(v) < base for dd in dvec for v in dd.lift().list())
    tv = undigits(dvec); tj = [tv[i*kappa:(i+1)*kappa] for i in range(m)]
    return (digit_ok and norm2(z) <= n * d * (m * d)^2   # 1. digits and shortness
            and B * dvec == u                    # 2. outer commitment opens
            and w * b == y                       # 3. the evaluation
            and A * z == sum(c[j] * tj[j] for j in range(m))   # 4. inner homomorphism
            and a * z == sum(c[j] * w[j] for j in range(m)))   # 5. w is consistent with z

print("honest transcript verifies:", verify(dvec, w, c, z))
w_bad = vector(Rq, list(w)); w_bad[0] += 1
print("with a tampered partial evaluation:", verify(dvec, w_bad, c, z))

What the experiment does not do is compress: the prover sends \(\mathbf{d}\), \(\mathbf{w}\) and \(\mathbf{z}\) in the clear, \(O(\sqrt{N})\) ring elements, and the verifier does \(O(\sqrt{N})\) ring multiplications. Greyhound’s remaining step is to hand the five checks, as a dot-product constraint system in \(\mathbf{d}\) and \(\mathbf{z}\), to LaBRADOR (Section 28.9.5), which is what shrinks the transcript to tens of kilobytes.

The role of the norm check.#

Without the norm check there is no commitment at all. The map \(\mathbf{s}\mapsto\mathbf{A}\mathbf{s}\) from \(R_q^{n}\) to \(R_q^{\kappa}\) with \(n\gg\kappa\) is wildly non-injective — every \(\mathbf{t}\) has on the order of \(q^{d(n-\kappa)}\) preimages, and Gaussian elimination finds one in polynomial time. Anyone can open an Ajtai commitment to anything they like, provided they are allowed to answer with a large vector.

What is hard is finding a short preimage, and finding two short preimages of the same \(\mathbf{t}\) is exactly the Module-SIS problem of the binding argument above. So the norm bound is not a side condition on the scheme; it is the scheme. Every message in every round carries one, every operation that combines messages has to account for the growth, and a protocol that loses track of a bound anywhere has lost binding everywhere. This is why lattice arguments read like an exercise in bookkeeping, and why the extraction slack of the previous subsection is the natural failure mode rather than a surprise.

Comparison with FRI.#

The mechanism differs from FRI’s more than their shared post-quantum label suggests. FRI never proves an algebraic identity: it establishes that a committed word is close to a low-degree codeword, by folding the word and opening a few positions, and its cost is therefore counted in queries and Merkle paths — which is precisely why a verifier written in Bitcoin Script spends nearly all of its budget on hashing. The lattice PCS proves the identity directly, and its cost is counted in ring multiplications and in norm growth. The two are different mechanisms with different cost centres; replacing one with the other changes the system’s cost profile, not a parameter.

Composition.#

Greyhound’s contribution is the three-round protocol of Figure 28.5 with the norm control that lattices require, and then a composition: checks 1–5 of that figure are linear and quadratic relations in the short vectors \(\mathbf{d}\) and \(\mathbf{z}\), which is a dot-product constraint system in the sense of Section 28.9.5, so LaBRADOR can prove that a satisfying transcript exists and compress the \(O(\sqrt{N})\) transcript to polylogarithmic size [32].

The composition affects only the proof size. The sublinear verifier is already present in the base protocol; LaBRADOR shrinks the proof and leaves the verifier’s cost unchanged, at \(O(\sqrt{N})\).

What the verifier actually computes#

Verification is often summarized as ring multiplication by way of the NTT; the implementation is less direct. A proof modulus is chosen to make the security argument work, not to be NTT-friendly, and Greyhound’s is not: its implementation states plainly that NTT-based multiplication cannot be used directly for \(R_q\), and instead multiplies modulo several small primes of 12 to 14 bits that do split fully in \(\mathbb{Z}[X]/(X^{64}+1)\), recombining by explicit CRT [32].

The transform of Chapter 6 still runs, but several times per multiplication, followed by a CRT reconstruction. For a verifier that pays per operation, this constant factor is part of the design.

Proof size against verification cost.#

Lattice arguments produce the smallest post-quantum proofs by a wide margin: LaBRADOR proves an R1CS with \(2^{20}\) constraints in 58 kB at the 128-bit level, against megabytes for the hash-based family. The cost has moved rather than disappeared, and it has moved to the verifier — LaBRADOR’s is linear in the witness, and Greyhound measures 2.80 s to verify a degree-\(2^{30}\) evaluation, which its own authors put at roughly twice Ligero’s [32]. A verifier living inside a contract or a script is buying bytes with time, and should confirm it wants that trade.

Published figures in this line also need reading carefully, because no two of them measure the same object: Greyhound’s headline 53 kB is an evaluation proof rather than a proof of a computation, and the much-quoted 73 kB from SALSAA is one folding step over linear relations, against 979 kB for the same system’s general-purpose argument [33].

Signature aggregation.#

No standardized post-quantum signature aggregates (Section 28.9.1); one research result exists. Falcon signatures can be aggregated by proving their verification inside LaBRADOR: 500 signatures in about 73 kB, against roughly 3.6 MB for the best lattice aggregate-signature scheme otherwise [31]. Two qualifications apply. The parameters are at 121-bit security rather than 128, and every size is an analytic estimate — there is no prover or verifier implementation to measure.

The mechanism also shows why aggregation is not free even when it works. Beyond the exact-smallness repair above, the proof cannot run over Falcon’s own modulus at all: the projection the argument uses needs room that \(q=12289\) does not have, so the statement is lifted to a proof modulus of 61 bits for FN-DSA-512 and 63 for FN-DSA-1024 [31]. Aggregating signatures means proving statements about them in a different arithmetic from the one they were signed in.

A third qualification concerns generality. The result does not transfer to ML-DSA, for a structural reason: its soundness proof handles a signing oracle only for hash-then-sign schemes, the GPV structure of Chapter 18, and ML-DSA’s Fiat–Shamir-with-aborts structure (Chapter 17) is exactly what the proof cannot accommodate. The one existing aggregation result therefore applies to FN-DSA and not to ML-DSA, which adds a consideration beyond size to the comparison of Section 28.4.4.

Assumptions within the lattice family.#

The family label determines as little here as it did in Section 28.9.1. In 2024 a quantum polynomial-time algorithm was shown to sample well-distributed LWE instances while provably not knowing the secret, assuming only that LWE is hard [34]. It invalidated the security analyses of six published lattice SNARKs at a stroke.

The scope of the result is instructive. The six affected schemes are standard-model, designated-verifier constructions resting on a knowledge-of-encoding assumption — an assumption that the sampler refutes. The LaBRADOR line is untouched, because it assumes Module-SIS in the random oracle model and never assumes that an adversary producing an encoding must know what it encoded. The two lines share a primitive family but rest on different assumptions, with different outcomes; the paper states that it invalidated security analyses rather than broke the constructions. At every level of the stack, the assumption rather than the family label is what determines the security.

28.10Timelines and honest uncertainty#

No quantum computer capable of breaking secp256k1 or BLS12-381 exists as of mid-2026. A 2026 arXiv preprint, not a consensus survey, gives one set of model-dependent estimates for cryptographically relevant quantum computing [1]. A 2025 Google analysis of RSA-2048 illustrates a downward resource-estimation trend, but is RSA-specific and not a direct estimate for Bitcoin or Ethereum curves [35]. Expert elicitation [36] and national guidance [37–39] place the migration deadline for conventional systems in the early-to-mid 2030s. NIST deprecates every quantum-vulnerable public-key algorithm after 2030 and disallows it after 2035, whatever the key size [37], and the most sensitive US federal systems must adopt post-quantum key establishment by the end of 2030 and post-quantum signatures by the end of 2031 [40, 41]. But those targets were set for enterprise IT, where an administrator can deploy a change; they were not calibrated for a system whose users must each act individually.

The honest position is that \(z\) in Mosca’s inequality is unknown and contested. The useful response is to stop arguing about \(z\) and measure \(y\) instead — the migration time is a property of the system, not of the adversary, and unlike \(z\) it can be computed.

28.10.1Migration is bounded by blockspace#

Here is the constraint that the roadmap debates tend to skip. Migrating a coin is not a database update; it is a transaction, and transactions compete for a fixed and quite small amount of blockspace. So there is a floor on how fast any migration can possibly proceed, and it depends only on arithmetic — the number of outputs to move, the size of a post-quantum spend, and the throughput of the chain.

Write \(N\) for the number of unspent outputs to migrate, \(w\) for the weight a single migration transaction consumes, \(W\) for the weight available per block, and \(T\) for the block interval. If migration were given every unit of every block, it would still take \[T_{\min} \;=\; T \cdot \left\lceil \frac{N\,w}{W} \right\rceil ,\] and at a share \(\sigma\) of blockspace the figure scales by \(1/\sigma\).

Two features of this bound deserve emphasis. It is a lower bound assuming all of the chain’s capacity goes to migration and nothing else — no payments, no ordinary economic activity — which no live chain would tolerate. And it is driven by \(w\), which for a post-quantum spend is dominated by the signature and public key, exactly the quantities that are one to two orders of magnitude larger than what they replace. The sizes tabulated throughout this book are not merely a bandwidth annoyance: they set the clock on the migration itself.

A published analysis of this question for Bitcoin reports a required downtime on the order of a few months of exclusive blockspace, under its own assumptions about which outputs must move and what a migration spend costs [42]. The exercise below builds a cruder model and gets a larger answer; the discrepancy is the instructive part, and reconciling the two is the point.

Exercise: compute the bound#

The sensitivity of the formula to \(w\) is best seen by evaluating it. Using the tools of Chapter 2:

# Lower bound on migration time: every weight unit of every block, nothing else.
BLOCK_WEIGHT   = 4_000_000   # weight units available per Bitcoin block
BLOCKS_PER_DAY = 144         # one block per ten minutes

def migration_days(n_outputs, witness_bytes, base_bytes=80, share=1.0):
    # SegWit discount: witness bytes cost 1 weight unit, the rest cost 4.
    weight_per_tx = witness_bytes + 4 * base_bytes
    per_block = BLOCK_WEIGHT // weight_per_tx
    blocks = -(-n_outputs // per_block)          # ceiling division
    return blocks / (BLOCKS_PER_DAY * share)

SCHEMES = [("ed25519 (baseline)",  64 + 32),      # signature + public key
           ("FN-DSA-512",         666 +  897),
           ("FN-DSA-1024",       1280 + 1793),
           ("ML-DSA-65",         3309 + 1952),
           ("SLH-DSA-128s",      7856 + 32)]

for label, n in [("every UTXO (~190M)", 190_000_000),
                 ("exposed third (~63M)", 63_000_000)]:
    print(label)
    for name, size in SCHEMES:
        print(f"  {name:20s} {migration_days(n, size):8.0f} days exclusive"
              f"   {migration_days(n, size, share=0.10):8.0f} days at 10%")

The model gives roughly 1800 days to move every output at ML-DSA-65 sizes with the whole chain to itself, and about 600 days for the exposed third — against 137 and 46 days respectively for the classical baseline. At a tenth of blockspace, which is already generous for a chain that must keep processing payments, the exposed third alone runs to some sixteen years.

Four things to take from that. The baseline rows show that migration is slow even with classical signatures, so post-quantum sizes are an aggravating factor rather than the sole cause. The SLH-DSA rows price the most conservative assumption in schedule rather than in bytes — a trade-off the size tables of Chapter 27 state but do not cost out. The FN-DSA rows are the reason Section 28.4.4 cares about the combined footprint: at Falcon-512 sizes the schedule is roughly a third of the ML-DSA-65 figure and a fifth of the SLH-DSA one, so the scheme choice moves the migration clock by years, not percentages. And the gap between these figures and the published estimate is itself the lesson: this model migrates one output per transaction, at full witness size, for the entire exposed set. Every one of those is pessimistic, and the published analysis relaxes them.

So relax them, and see which matters. Vary the migrating set; batch many outputs into one transaction; apply an aggregation or a proof-based authorization in place of a per-output signature. Batching is the interesting lever, because \(N\) and \(W\) are given to the designer while \(w\) per migrated output is the one term a protocol can actually negotiate — which is precisely what the output-type and recovery-path proposals in this chapter are trying to buy.

28.11Pitfalls#

Pitfall 1: assuming “my address is a hash, so I am safe.”#

True only until the first spend. Any account that has transacted has exposed its public key; on Ethereum that is essentially every active account, and on Bitcoin it includes every reused address.

Pitfall 2: treating draft proposals as decided.#

BIP-360, BIP-361, and EIP-8141 are drafts; the freeze question in particular is contested. Reporting them as Bitcoin’s or Ethereum’s “plan” overstates consensus.

Pitfall 3: quoting a single gas figure.#

On-chain verification costs move between implementations, versions, and precompile assumptions. A number without a source and date is not meaningful.

Pitfall 4: assuming hybrid signatures are the safe default.#

They are the conservative choice in TLS, where the redundant work is ephemeral, negotiated, and invisible (Section 27.3.2). On chain the extra signature is stored forever by everyone, cannot be negotiated away, and obliges users to migrate twice. Importing the internet’s default here doubles the dominant cost.

Pitfall 5: quoting an exposure percentage without its cause.#

“One third of supply is exposed” conflates outputs that publish a key by design with addresses that were reused, and only the second is still growing and reducible without a consensus change (Section 28.4.2).

Pitfall 6: treating migration as a scheduling problem.#

It is a throughput problem. Blockspace bounds it from below regardless of how well the ecosystem coordinates (Section 28.10.1), so a plan that begins when Q-Day is announced cannot finish, however motivated everyone is by then.

28.12Summary#

Blockchains sharpen the quantum threat and complicate the response:

• the danger is to signatures (Shor), not hashing (Grover); an exposed public key on an immutable ledger is a permanent, “store now, steal later” liability — which makes the shelf-life term in Mosca’s inequality unbounded, so \(x+y>z\) holds for any finite Q-Day and the only escape is to remove the exposure;

• exposure has two causes with different remedies: output types that publish a key by design, and address reuse — the larger share, still accumulating, and reducible by wallet behaviour alone;

• administrative keys (stablecoin proxy admin, minter, pauser) are the concentrated case: few keys, shared blast radius, immune to multisig and hardware custody, but owned by someone who can actually act;

• Bitcoin proposes a new quantum-hardened output type (BIP-360) and a contested legacy-signature sunset (BIP-361), both draft soft forks;

• Ethereum pairs an emergency hard fork with STARK-based hash-preimage recovery and an account-abstraction migration path (EIP-7702 shipped, EIP-8141 draft), targeting first-layer post-quantum infrastructure in the 2028–2029 window;

• Cosmos has gone furthest in shipped code, registering ML-DSA-65 as an opt-in validator consensus key type, at \(60\times\) the key size and \(50\times\) the signature size of ed25519;

• a layer 2 inherits all of these at once and can fix only some of them, so its plan must be organized by ownership of each surface rather than by scheme;

• a symmetric or hash-based layer protects only what it carries: Winternitz commitments, garbled circuits and FRI commitments have all been found wrapping elliptic-curve assertions, and a proof system can hide a discrete-log dependency in an argument that is not its headline commitment scheme;

• some exposures cannot be migrated at all — an EVM pairing precompile has immutable callers, so it can be inventoried but never upgraded — and aggregation has no post-quantum drop-in, which is why replacing BLS is an architectural project;

• EdDSA chains inherit a recovery route from RFC 8032’s seed-then-hash key generation, letting an owner prove seed knowledge after Q-Day with no prior action; ECDSA chains can imitate it per-wallet (BIP-32 already does) but cannot make it a consensus rule, because the structure is neither universal nor detectable on chain;

• migration is bounded from below by blockspace, not by willingness: at post-quantum witness sizes the floor is months to years of exclusive blockspace, and years to decades at any share that leaves the chain usable — a bound that follows from arithmetic rather than from any contested claim about quantum hardware;

• the timeline is uncertain but the required lead time is long, which is why these communities are debating the transition years before any quantum computer can execute the attack.

This is where cryptographic theory meets the messiest realities of deployment – immutable history, decentralized governance, and irreversible loss – and it is a fitting place to close: the mathematics is ready, and the harder work of migrating the systems that depend on it has only begun.

References