What Moving a Live Network to Post-Quantum Signatures Costs

By Nika, NodeTimes newsroom.

A post-quantum signature is between one and three orders of magnitude larger than the elliptic-curve signature it replaces, and the bill for that arrives as block space, fees and verification work rather than as cryptography. A network therefore faces a choice between three resources it cannot spend at once: block size, block frequency and aggregation. This is the cost side of the migration rather than the question of what breaks, and the numbers are modelled for a network in general, not measured on one.

Signatures got bigger by design

Post-quantum signatures are large because the schemes rest on different hard problems, and the size follows from the construction rather than from a flaw in an implementation.

ML-DSA (module-lattice signatures): the scheme family standardised in FIPS 204, whose signatures are vectors over a polynomial ring, so their size grows with the dimension and the modulus rather than with a curve point. SLH-DSA (stateless hash-based signatures): the family standardised in FIPS 205, where a signature carries the authentication path of a hash tree and therefore consists of many small hash values instead of one algebraic object. FN-DSA: the Falcon-based scheme, whose signatures are the most compact of the three NIST signature families because its construction exploits a structure that the module-lattice scheme does not use in the same way.

The reason none of them shrinks is structural:

• A lattice signature is a vector, and the vector has to fit in the signature; shrinking it means weakening the parameters, not compressing the encoding.
• A hash-based signature contains the path that proves a one-time key belongs to a published root, and the path has as many elements as the tree has layers.
• Hash-based schemes give up size to gain a security argument that assumes nothing beyond the hash function, which is exactly why the size does not fall.

What that means for a chain is not only bytes. In a proof-of-stake network the signature is what makes the block producer accountable, so its size per transaction multiplies across every verification the network performs, and the shape of that multiplication is what the rest of this article is about. The wider picture of which chains face this and how they differ is in the guide to post-quantum blockchains.

Sizes, scheme by scheme

The differences between post-quantum schemes are larger than the difference between any of them and a classical signature, so the choice of scheme matters more than the choice to migrate.

Every number in that table is a specification size, not a measurement taken on a live chain. Two things make the ranges wide. First, each family has parameter sets that trade size against security level, and the spread inside ML-DSA alone runs from 2420 bytes for ML-DSA-44 to 4627 for ML-DSA-87. Second, the public key is a separate line item from the signature, and whether it travels with every transaction depends on the account model, not on the scheme.

The most compact choice is the Falcon-based one, and its size is the reason several networks look at it first; the trade is a more delicate implementation and a signing routine that is harder to get right than the module-lattice scheme. Where that construction comes from is set out in the material on Falcon, and the algebra behind the larger family is in the explainer on lattice-based schemes.

What a signature costs inside a block

Inside a block a signature is not a fixed cost, it is a share of every transaction, and that share decides how many transactions fit.

The arithmetic is worth doing once, in the open. A secp256k1 signature, the ECDSA scheme whose break and replacement the explainer on how quantum computers break ECDSA sets out, occupies about 64 bytes of a transaction, and in several designs the public key can be recovered from it, so nothing else needs to travel. No standardised post-quantum scheme offers that recovery, so the public key has to travel with the transaction or be looked up in the state, and that is the lever behind the whole bill. Replacing that with an ML-DSA-65 signature puts 3309 bytes into the same transaction, and if the public key is carried along, its 1952 bytes come with it: about 5261 bytes in place of 64.

Whether the key travels is the single biggest lever available, and it is a question about the account model:

• Account-based chain with the key in state: the public key is stored once per account and the transaction carries only the signature, so the per-transaction cost is roughly fifty times the classical one, not eighty.
• Signature carried in the transaction with no state lookup: the key travels every time, and the same payment pays for both objects.
• Aggregated batch: many signatures are replaced by one object, which breaks the linear relationship between size and transaction count, at the price of the aggregation machinery.

Then comes the protocol's own price for bytes. Where calldata costs a fixed amount of gas per non-zero byte, the signature is charged like any other data: at 16 gas per non-zero byte, an ML-DSA-65 signature alone accounts for about 53,000 gas before the transaction executes anything. Set against the protocol's floor of 21,000 gas for a plain transfer, the signature alone is worth about two and a half ordinary transfers, and a fixed block gas limit is what turns that ratio into a capacity figure.

Aggregation, and why the standards do not give it

Aggregation replaces many signatures with one object, and none of the standardised post-quantum signature schemes provides it natively.

Classical BLS signatures aggregate because the scheme lives in a group where two signatures can be multiplied into one: signatures on the same message collapse into a single object that takes one pairing to check, while signatures on different messages keep a pairing each, so the saving across a real batch is a factor rather than a constant.

The post-quantum families lack that handle: a lattice signature is a vector and a hash-based signature is a set of hash values, and there is no operation under which a hundred of them collapse into one. Aggregation therefore has to be built on top of the signatures rather than inside them, usually as a recursive STARK: a proof system verifies a batch of signatures, and the verification of that proof is itself provable, so the proofs of many batches fold into one short object.

• What the proof buys: one short object on chain instead of one signature per transaction, and verification cost that grows far more slowly than the batch.
• What it costs: a prover that must be run and trusted for liveness, proving time that grows with the batch, and a new failure mode if the prover stops publishing.
• What it cannot fix: the signature still has to exist off-chain to be proven, so aggregation moves cost rather than deleting it.

The consequence for a network is a schedule question rather than a technical one: aggregation is the right answer for throughput, but it requires a proof system that is itself a subject of active research, so the practical order is to make the primitives replaceable first and to add aggregation where the batch structure already exists.

Verification cost

Verification is the second bottleneck: a bigger signature is more data to parse and more work per validator, and the two do not grow at the same rate.

Parsing is the part that is easy to underestimate. A signature that is fifty times larger is also a signature that must be propagated, decoded and hashed, and every validator does that for every transaction. A lattice signature verifies quickly once it is parsed, because the operation is short-vector arithmetic over a small ring; a hash-based signature verifies by recomputing a tree path, which is cheap per hash but adds up when the path is long. The design notes of the standards present the size as the price of a construction that assumes very little about the adversary's mathematics.

Three budgets move together, and a network that only watches one of them will be surprised by another:

• Bandwidth: block propagation and peer traffic, which grow with the signature, not with the number of transactions.
• CPU: signature parsing and verification on every node, which grows with both.
• State: stored public keys, if the account model keeps them, which turns a per-transaction cost into a permanent one.

What a network can actually choose

A network has four levers, and each one spends a different resource: parameters, aggregation, a separate output type, and a delayed migration.

1. Parameter sets: pick the smallest set that meets the security target, which reduces the signature without changing the architecture. Reversible, cheap to start, and limited to the spread inside one scheme family.
2. Aggregation: replace many signatures with one proof, which is the only lever that breaks the linear relation between size and transaction count. Expensive in complexity, and dependent on a prover that has to keep working.
3. A separate output type: give post-quantum signatures their own way to be spent, so existing outputs keep their size and only new ones pay. Reversible in the sense that a chain can stop creating them, difficult to reverse in the sense that they stay in the state.
4. Delayed migration: keep the classical scheme for as long as the assumption holds, and spend the time on the interfaces that make the next step possible. Free today, expensive in the sense that the assumption is not under the network's control.

The order between these levers is the actual decision, and it depends on what the network runs out of first. A chain whose blocks are small runs out of space and needs aggregation or a new output type; a chain whose validators are already busy with execution notices the verification bill first. Choosing between them is where the migration stops being a cryptography project and becomes a capacity plan, and the history of how the standards arrived at these sizes is in the account of the NIST process.

Frequently asked questions

How much bigger is a post-quantum signature?

In the common lattice-based schemes a signature is tens of times larger than a classical one: ML-DSA starts at 2420 bytes against about 64 for a secp256k1 signature.

The size, not the security level, is what creates the network problem, because every transaction carries it.

Can signatures be aggregated?

Yes, but not by the standardised schemes themselves: aggregation has to be built on top, typically as a proof that verifies a batch of signatures.

Classical BLS aggregation is a property of the scheme, which is exactly what the post-quantum families do not offer.

Does a bigger signature raise every transaction's fee?

Yes, where fees are charged by the space a transaction occupies, because the signature's share of that space grows sharply.

Whether the increase is proportional to the signature depends on the account model: a key stored in state is paid for once, not per transaction.

Is verification more expensive too?

Not for the check itself: the extra cost is parsing, propagating and hashing a larger object on every validator. A lattice signature verifies quickly once it is parsed, and only the hash-based family pays for a long authentication path.

The bill arrives as bandwidth and CPU for handling more data on every validator, rather than as a slower check or a storage cost.

What should a network do first?

Decide which resource it intends to spend: parameters, aggregation, a separate output type, or time.

That decision sets everything after it, because the four levers are not additive: aggregation changes the capacity model, while parameters only move within it.