In this article we discuss how to verify a digital signature produced with Module-Lattice-Based Digital Signature Algorithm (ML-DSA) on Ethereum Virtual Machine (EVM). ML-DSA has been standardized by the National Institute of Standards and Technology (NIST) in FIPS 204 as a post-quantum cryptographic (PQC) scheme. It is expected to eventually replace existing elliptic-curve-based digital signature schemes such as ECDSA and EdDSA as cryptographically-relevant quantum computers (CRQCs) are on track to become practical. For our discussion, in the context of EVM, it is important to understand why we need to verify ML-DSA signatures inside an EVM program. When a smart contract on the Ethereum blockchain needs to verify signature over any arbitrary message, it uses the ecrecover precompile. It allows recovering the signer's 20-byte Ethereum address, which lets one compare if the signature came from an expected party. It costs roughly 3000 gas to verify an ECDSA signature on EVM. It is cheap because the precompile exists. Otherwise it could have been prohibitively expensive — approximately couple hundred thousands of gas. Any computation on the EVM when deemed expensive is because of the metered gas cost being high. In recent times, there have been serious efforts undertaken to make the Internet post-quantum secure. Accordingly there is a need to make Ethereum post-quantum secure. In a fairly complex protocol stack like Ethereum, there are many places where cryptography needs to switch to its PQ counterparts. Our focus is on a small portion of that stack. Mainly for signatures on custom messages that a smart contract verifies inside EVM execution environment before it executes further business logic. It can also be extended to account abstraction (AA) model which lets one put custom transaction authentication logic for externally-owned accounts (EOAs). Today when one sends a transaction to Ethereum blockchain it must be signed using ECDSA over secp256k1 curve. The hardware or software wallet does much of the heavy lifting on key generation and signing front. Signing algorithm and choice of the curve is hardcoded in the Ethereum protocol itself. Imagine if one could change the transaction authentication logic for only their account without the protocol forcing everyone to migrate their accounts — that's the promise of the smart accounts. EOAs made "smart" using smart contracts. It allows gradual rollout of PQ secure authentication. For more on this line of development, I refer the reader to EIP 4337 and EIP 7702. AA paves the path for using ML-DSA for authenticating transactions in purely opt-in basis. For the rest of the article we will focus on optimizing the cost of verifying ML-DSA signatures inside smart contracts running on the EVM.
FIPS 204 specifies three instances of ML-DSA — ML-DSA-44, ML-DSA-65 and ML-DSA-87. We choose to work with ML-DSA-65, which provides cryptographic security equivalent to "NIST Category 3". ML-DSA verification function takes public key, signature, message and an optional context string as input. ML-DSA-65 public key is 1952 bytes. ML-DSA-65 signature is 3309 bytes. Message can be arbitrary long. Optional context string is capped at 255 bytes. I won't explain the ML-DSA signature verification algorithm itself. Rather we will focus on its components, so that we know which parts are contributing how much to the overall verification cost. I will split ML-DSA verify into roughly following three steps.
Given a signature the ML-DSA verify function unpacks it, rejecting when hint bits encoding is invalid or infinity norm of the signature crosses parameterized bound.
Decoding signature involves placing bits into coefficients of polynomials or vectors of polynomials.
Those coefficients are members of a 23-bit prime field that ML-DSA is parameterized with.
Regenerating the commitment inputs is dominated by hashing, with XOFs defined in FIPS 202, aka SHA3 standard.
It includes generating a public matrix A, by expanding a seed included in the public key, by means of "rejection sampling" the ouput of SHAKE128 XOF.
Hashing with SHAKE256 XOF is used in a couple of places — for recomputing the challenge vector from the commitment hash which is embedded in the signature, computing 64-byte message representative, and computing the final commitment hash which is compared against the signature for acceptance or rejection decision.
Reconstructing the commitment hash requires performing arithmetic over polynomials, in the number theoretic transform (NTT) domain.
NTT evaluates a polynomial, replacing its coefficients with point values.
This allows easy arithmetic over polynomials, i.e., a x b can be as easy as element-wise multiplication, s.t., a and b are two polynomials of degree N.
Before recomputing the commitment hash the result polynomial is interpolated back to coefficient domain using inverse number theoretic transform (iNTT).
Simply put, it involves linear algebra and NTT.
Now that we have a fairly good high-level mental map of the operations involved in verifying a ML-DSA signature, I want to focus on a specific part of it. The hashing. It is more than 50% of the signature verification cost. Any hashing ML-DSA does is dominated by applying 24 rounds of Keccak-f[1600] permutation. The specific choice of XOF dictates sponge rate/ capacity and domain separator in use. ML-DSA uses two XOFs, SHAKE128 and SHAKE256. Roughly speaking SHAKE128 offers 128-bit collision resistance security and SHAKE256 offers 256-bit collision resistance security. For more precise explanation I refer the reader to Table 4, titled "Security strengths of the SHA-1, SHA-2, and SHA-3 functions", in section A.1 on page 23 of FIPS 202.
I won't bore you with code. You can find all of it in the itzmeanjan/veripq repository. It implements ML-DSA-65 signature verification algorithm as a Solidity library. Solidity is the most used programming language for writing smart contracts targeting EVM. The library is tested against the ACVP known answer test (KAT) vectors for ML-DSA-65 verify, to ensure functional correctness and conformance. NIST maintains ACVP test vectors in the usnistgov/ACVP repository. I maintain a C++ library for the full suite of ML-DSA in itzmeanjan/ml-dsa, which is used to generate new KATs for optimized instances of ML-DSA, I will propose in the rest of the article. To clarify expectations, we will optimize only the hashing part of ML-DSA. We won't touch anything else in ML-DSA signature verification. Any change in the hash functions obviously changes the output of ML-DSA key generation and signing functions, given same input, i.e., seed, message or context string. All new test vectors are generated in reproducible manner by applying git patches. All ML-DSA-65 flavours are tested to be correct using KAT vectors. Simply put, any claim I make in the rest of the article on performance of ML-DSA-65 verify, can be reproduced using material in the accompanying repository.
Verifying a ML-DSA-65 signature over a 2793-byte message and 183-byte context string costs 15,432,417 gas on EVM.
The message size is weirdly long because it is one of the NIST ACVP KAT vectors.
Out of 15.4 million gas, 8,674,229 is spent just on hashing — that is a whopping 56%.
A combination of 24-round Keccak-f[1600] permutation calls and sponge absorptions/ squeezings are behind it.
The ML-DSA-65.verify() implementation we gas metered, employs a fairly well-known optimization for efficient hashing.
For example, when rejection sampling the public matrix A6 x 5, s.t. each cell is a polynomial of degree N (= 256), we use Single Instruction Multiple Data (SIMD) parallel SHAKE128 — better referred to as SHAKE128x4.
A mild digression.
You may note, ML-DSA-65 is named so because of the dimension of the public matrix A.
Following this you can figure out the dimension of the public matrix A, in other NIST-standardized instances of ML-DSA, such as ML-DSA-44 and ML-DSA-87.
A natural next question to ask is how does one get to exploit SIMD parallelism on EVM?.
EVM is a computer architecture featuring 256-bit native words.
Like x86_64 or arm64 architecture features native word size of 64-bit.
On x86_64, there are instruction extensions, named AVX2, which features 256-bit vector units.
AVX2 extension lets one interpret a 256-bit vector unit as N many packed words, where each word is of bit width ∈ {8, 16, 32, 64, 128, 256} and operate over those N many words in parallel.
That is SIMD parallelism crash-course in a handful of sentences.
I used x86_64's AVX2 just as an example, there are other SIMD instruction extensions like x86_64's AVX512, arm64's NEON or SVE.
Coming back to EVM.
We can imagine EVM as a computer architecture featuring 256-bit wide SIMD vector units.
The mighty Keccak-f[1600] permutation state is a matrix of dimension 5x5 with each cell being 64-bit wide — 25 lanes, each of 64-bit.
If we implement SHAKE128 or SHAKE256 on EVM, each lane will anyway occupy a 256-bit native word.
But only 64 bits will be of significance, resulting in waste of 192 bits, per lane.
That is a massive under utilization of scarce resource — compute capability.
In ML-DSA-65, four cells of the public matrix A can be sampled in parallel.
By putting four 64-bit lanes from four different instances of SHAKE128 XOF onto single 256-bit EVM word, we can rejection sample four polynomials of matrix A, in parallel.
How would that look like?
Imagine, we are rejection sampling first four cells of the matrix A6 x 5, i.e., matrix cells indexed as (0, 0), (0, 1), (0, 2) and (0, 3), in row-major order.
In a naive way, each cell can instantiate a SHAKE128 XOF, seeded with a 32-byte seed string, followed by two bytes, encoding matrix cell index (i, j), s.t., 0 ≤ i < 6 and 0 ≤ j < 5.
In a smarter way, lane0 of Keccak-f[1600] permutation from four instances of SHAKE128 will occupy a full 256-bit word of EVM.
We replicate it 24 more times to cover all 25 lanes of four SHAKE128 instances.
Notice, in the naive way, on EVM, keeping the state of four SHAKE128 instances would have costed us 4 x 5 x 5 = 100 EVM words.
The SIMD-packed representation lets us achieve the same at 1/4 of the cost.
Obviously there are some limitations — both absorption and squeezing needs to be executed in lock-step, i.e., exactly N bytes needs to be absorbed by all four parallel SHAKE128 instances.
Same applies for squeezing.
In this specific context, absorption is fairly straightforward.
Each of the 6 x 5 = 30 SHAKE128 instances will absorb exactly 32 + 2 = 34 bytes.
The rate of the SHAKE128 sponge is 168-byte.
Meaning absorption costs only a single Keccak-f[1600] permutation call.
On the squeezing front, it employs rejection sampling.
Because each SHAKE128 instance absorbs diversified input seed, their output stream will be completely different.
Thanks to the avalanche property of a cryptographic hash function.
Meaning four SHAKE128 instances running in parallel might squeeze inequal length of output.
This inconvenience is solved at the cost squeezing exactly 168-byte rate-sized blocks from all four SHAKE128 instances, even though some of them may not need it anymore because all 256 coefficients of the polynomial has already been sampled.
It is not that bad.
Couple of observations based on what we know so far.
To reduce the cost of hashing in ML-DSA-65, we can halve the number of Keccak-f[1600] permutation rounds. 24 becomes 12. But we loose compatibility with ML-DSA-65, as specified in FIPS 204. Replace use of SHAKE128 and SHAKE256 in ML-DSA-65 with their Turbo equivalents, i.e., TurboSHAKE128 and TurboSHAKE256, respectively. TurboSHAKE is specified in RFC 9861. It is such a simple solution to halve the cost of Keccak-f[1600] permutation without loosing any cryptanalytic advantage of it. We refer to this instance of ML-DSA-65 as TurboML-DSA-65. Verifying a TurboML-DSA-65 signature for the same message and context string costs 12,366,017 gas on the EVM. At the cost of loosing compatibility with FIPS 204 ML-DSA-65, we save ~19.8% in gas cost of verifying a post-quantum ML-DSA signature on EVM. That does not say much. Only part of ML-DSA we have touched to build TurboML-DSA is hashing. TurboML-DSA-65 spends 5,602,105 gas just on hashing — that is still a whopping 45.3% of the total 12.3 million gas spending. Compared to FIPS 204 ML-DSA-65, the hashing cost has reduced by roughly 35.4%, while the overall signature verification cost has reduced by roughly 20%. A natural next question to ask, why did not the cost of hashing just drop by half when we halved number of rounds in Keccak-f[1600] permutation?. It is important to note, hashing with SHAKE or its Turbo variants is not just applying Keccak-f[1600] permutation. Obviously that is a dominating cost. There are sponge operations which exists regardless of the number of rounds halving in permutation. That's why verifying TurboML-DSA-65 signature still costs ~12.3 million gas. At the time of writing, when Fusaka upgrade is in place on Ethereum, the block gas limit is capped at 60 million. For more details on past and future Ethereum upgrades, I refer you to their roadmap. Today we can verify only three ML-DSA-65 signatures and four TurboML-DSA-65 signatures on Ethereum per block. Not practical.
Let's go one step further. Reduce the cost of hashing in ML-DSA even further. EVM offers a precompile for keccak256. It has an one-shot hashing interface which allows absorption of arbitrary long message and produces a 32-byte digest. If I could have used Keccak256 for all hashing needs in ML-DSA, I would have. That is not possible because ML-DSA often needs more than 32 bytes of digest. That's why it uses a flexible hash function aka XOF to squeeze arbitrary long digest. But I can always build a keccak256 precompile-accelerated XOF. An eXtendable Output Function built on top of Keccak256 hash function. What would that look like?
Keccak256XofCtr: A Keccak256-based eXtendable Output Function in counter mode
absorb(msg):
- Append msg to an internal buffer
finalize():
- Apply keccak256() on the internal buffer holding concatenated absorbed messages
- Set state <- keccak256(buffer)
- Set counter <- 0
squeeze(out):
- Produce a 32-byte block and increment counter for squeezing next block
- Produce as many blocks required to fill output buffer
- Buffer rest, if any, in an internal buffer
- Set buffer <- keccak256(state || counter)
- Set counter <- counter + 1
Simply put, to expose a sponge-like XOF interface, keep concatenating input message bytes in a buffer until the sponge is ready to be finalized, i.e., ready to produce output stream. Absorption is nothing but applying keccak256 precompile on concatenated stream of message bytes. It produces a 32-byte digest, which becomes the "state" of the sponge, for the rest of its life cycle. To support squeezing arbitrary long output stream, counter mode comes to rescue. A zero-initialized "counter" is kept as part of the Keccak256XofCtr state. A squeezed block is keccak256 digest of concatenation of "state" and "counter". After squeezing a 32-byte block, the counter is incremented by 1. The counter is 256-bit wide. The native word size on EVM. Keccak256XofCtr, allows squeezing at max 32 * 2256 bytes, i.e., 2261 bytes. Such an unimaginably high bound.
Keccak256XofCtrML-DSA-65, a flavour of ML-DSA-65, featuring Keccak256XofCtr XOF, replacing both SHAKE128 and SHAKE256, scores 8,792,483, in signature verification gas cost. A 28.9% reduction in signature verification gas cost, compared to last optimization attempt — Turbo instance of ML-DSA-65. Compared to FIPS 204 ML-DSA-65, it is a 43% reduction in gas cost. Speaking of only hashing, the cost comes down to 2,118,015 gas — down to 24.1% of total verification cost. A gradual improvement from spending 56% of verification gas cost on hashing to 45% and finally down to 24%. Choosing a custom XOF, built over Keccak256 hash function, at the cost of loosing compatibility with the standard, enables us in verifying up to six signatures per block of Ethereum. That doubles the capacity compared to FIPS 204 ML-DSA-65. Is it ready to adopt at scale? No.
Observation, the decision of replacing both SHAKE128 and SHAKE256 in ML-DSA with Keccak256XofCtr can be concerning. Keccak256 is a sponge, with a capacity of 512 bits, i.e., it can offer up to 128-bit collision resistance security. For this specific parameter of ML-DSA, i.e., ML-DSA-65, which offers "Category 3" security, which is at least as secure as AES-192 block cipher, the choice of hash function does not provide sufficient level of security. Replacing the use of SHAKE128 with Keccak256XofCtr is fine from cryptographic security point of view. Though it does not hold in case of SHAKE256.
What else can we do to make ML-DSA practical on EVM? We need precompiles for accelerating ML-DSA verification on EVM. For example, number theoretic transform can be heavily optimized, bringing down the signature verification cost. Exposing a Keccak-f[1600] permutation precompile, with paremeterizable number of rounds, will be immensely helpful. It could open the door for supporting other gas-optimized Keccak-f[1600] based hash functions and XOFs. Accelerated prime field arithmetic, using Montgomery representation and lazy modulo reduction can obviously help. Though it won't be general purpose, because the specific 23-bit prime field ML-DSA uses may not be useful for other PQ digital signature schemes. Good news is there is already a draft proposal, EIP 8051, for adding ML-DSA precompile to EVM.