Native post-quantum signature verification on the EVM: feasibility

Design document, published from the repository at docs/contracts/PQC_FEASIBILITY.md.

Question. Can QuantLayerAuthorizationManager verify ML-DSA (FIPS 204) signatures natively in Solidity, the way it verifies ECDSA with ecrecover?

Answer. Not practically. A lower bound for ML-DSA-65 is about 22.5 million gas per verification. That is about 7,500 times ecrecover (3,000 gas) and 70% of Arbitrum's 32M per-transaction gas limit, and it leaves out decoding and norm checks. QuantLayer therefore verifies post-quantum signatures off-chain and brings them on-chain through an explicit, non-trustless attestation (see ONCHAIN_PROTOCOL.md §5).

Method

We implemented and tested ML-DSA's two dominant kernels in Solidity, measured their gas cost, and extrapolated with an explicit operation count. The code is in contracts/test/bench/. It is benchmark-only and is not deployed.

KernelImplementationCorrectness check
Keccak-f[1600] (SHAKE128/256)KeccakF1600.permuteReference (plain Solidity) and KeccakF1600.permute (unrolled inline assembly)Keccak-256 built on the permutation is fuzzed against the KECCAK256 opcode, including block boundaries. SHAKE128/256 match FIPS 202 known answers, including multi-block squeeze. The assembly version is fuzzed against the reference.
NTT over Z_q[X]/(X²⁵⁶+1), q = 8380417MlDsaNtt.ntt / invNtt (reference) and MlDsaNtt.nttAsm (assembly loops)invNtt(ntt(a)) = a. invNtt(ntt(a) ∘ ntt(b)) equals the schoolbook negacyclic product (fuzzed). The assembly NTT is fuzzed against the reference.

The EVM's KECCAK256 opcode only exposes Keccak-256 with fixed padding. ML-DSA needs SHAKE128/SHAKE256 with arbitrary-length output, so a native verifier has to run the permutation in EVM code.

Reproduce:

cd contracts && pnpm exec forge test --match-contract PqcFeasibility -vv

Measurements (Foundry 1.7.1, solc 0.8.28, optimizer 200 runs, Cancun)

OperationGas
Keccak-f[1600], reference Solidity739,164
Keccak-f[1600], unrolled assembly98,294
NTT (256 coefficients), reference381,134
NTT, assembly184,121
Inverse NTT, reference426,267
Pointwise mulmod product, per coefficient210
ecrecover (precompile), for comparison3,000

ML-DSA-65 verification estimate (k = 6, l = 5)

StepCountGas
SHAKE permutations: ExpandA (30 polynomials × ~5 SHAKE128 blocks), tr = H(pk) (1,952 B), μ, SampleInBall, H(μ ‖ w1)~17517,201,450
NTTs: NTT(z) ×5, NTT(c), NTT(t1·2ᵈ) ×6, inverse ×6183,314,178
Pointwise products: A·z (6×5×256) + c·t1 (6×256)9,2161,935,360
Calldata: signature 3,309 B + public key 1,952 B (16 gas/byte upper bound)5,261 B84,176
Lower-bound total≈ 22.5M

The estimate is a lower bound. It omits:

  • bit-unpacking of z, h and t1;
  • rejection sampling in ExpandA and SampleInBall;
  • the infinity-norm check;
  • hint application (UseHint);
  • w1 encoding;
  • memory expansion across 30 polynomials.

Expert-optimized implementations might cut the measured kernels by a further 2–3×, which would still put verification in the multi-million-gas range. ML-DSA-87 and SLH-DSA are larger still: SLH-DSA verification needs thousands of hash calls.

Conclusion and consequences

  1. Not on the EVM today. At ≥ 22.5M gas, one verification consumes most of an Arbitrum transaction. It can't be composed with application logic, and cost grows with the parameter set. We don't ship a Solidity ML-DSA verifier.

  2. Off-chain verification plus attestation. QuantLayer Quantum (libcrux, FEAT-07) or the TypeScript engine verifies the signature. A k-of-n quorum of registered attestors signs an EIP-712 PqcAttestation that the chain checks. This is a trust assumption, and every on-chain result says so (Assurance.Attested).

  3. Hybrid keeps a trustless classical half. In hybrid mode, the ECDSA half of the request is verified on-chain. A failure of the attestors alone can't authorize a request without the subject's classical key.

  4. Ways to remove the trust assumption later.

    • Arbitrum Stylus: verify ML-DSA in WASM (Rust, libcrux), which is far cheaper per operation than EVM bytecode. This is the most promising path.
    • A future precompile for ML-DSA or SHAKE.
    • A ZK proof of ML-DSA verification: prove "this ML-DSA signature verifies" in a SNARK. Recursion is costly to prove, but cheap to verify on-chain.

    The algorithm field and proof-system versioning leave room for any of these without changing the manager's interface.