Post-Quantum Ethereum at the Execution Layer

Transcript

Hello. I'm Yoonhyung Lee from Yonsei University's CNL, studying in Professor Jeong Kyung-moon's lab. Today I'll talk about post-quantum Ethereum at the execution layer, starting from EIP-7885, which I co-authored, up to how hash-based signatures can be made easier with proofs. Once a sufficiently powerful quantum computer arrives, signatures like the ECDSA Ethereum uses today become unsafe, so Ethereum has been preparing a transition to PQC.

So can we just pick a safe quantum-resistant signature and swap it in? In practice, no. For the signer, what matters is how quickly new keys can be generated, how quickly they can sign, and how keys can be backed up and managed. For the network, we need to look at how large public keys and signatures get, and how that affects gossip propagation and bandwidth. For the verifier, the computation of verification itself and how much gas it costs can become the issue.

So the PQ transition isn't simply a matter of which cryptographic algorithm to choose. It's a system design problem that weighs signature size, key management, verification cost and security together. Looking at NIST's current post-quantum signature standards, the current standards are ML-DSA and SLH-DSA, and Falcon is under review. The main way to split them into two: ML-DSA and Falcon are lattice-based, while SLH-DSA is a hash-based signature.

Lattice-based signatures rest on the assumption that lattice problems are hard for computers to solve. ML-DSA is based on Module-LWE and SIS-type problems, and Falcon, being NTRU-based, relies on problems such as NTRU lattices. In implementations, you see a lot of modular arithmetic for polynomial multiplication and NTT. Hash-based schemes, on the other hand, rely on properties like preimage resistance of hash functions, long used in conventional cryptography, and use repeated hash computations and Merkle trees.

Typical examples are schemes like SLH-DSA, XMSS and LMS. Comparing signature sizes, a Falcon signature is 666 bytes, while SLH-DSA is about 7.8 KB, so lattice-based ones are considerably smaller. So lattice versus hash is a difference in the underlying cryptographic structure. Next, there are the concepts of stateful and stateless: whether the signer has to store some usage state

or not. Let's see how hash-based signatures handle the state problem and how they're constructed. First, let me explain hash-based signatures. A hash-based signature has 4 main components. First, WOTS is a one-time signature: it builds several hash chains and, depending on the message, reveals a specific position in each chain to produce the signature.

FORS is a few-time signature: based on the message digest, it selects secret leaves from several small trees and reveals them along with their authentication paths. Merkle authentication is the process of confirming that a key or node is included under a given Merkle root. And stacking multiple XMSS trees in layers gives you a hypertree. Looking at the structure on the right, XMSS combines WOTS with Merkle authentication and continuously stores the index of the next leaf to use.

This is called a stateful signature. In contrast, the SLH-DSA or SPHINCS+ family first uses FORS and then links multiple XMSS trees on top. Because the tree and leaf to use are derived from the message, the signer can use it without storing a persistent counter like a next-unused-leaf index. That's why it's called a stateless signature. Then, in stateful signatures, taking XMSS as an example, why is it dangerous if the state rolls back?

Say you've used XMSS signatures up to number 41, and the next one to use is number 42. Normally, since 42 has been used, you record 42, safely save the next state, and then share the signature externally. But after signing message A with key 42, if, as in the cases shown here, you restore an old backup, sign on several devices at the same time, or something fails before the state is saved, the same key 42 could be used for message B as well.

Then this isn't simply a matter of sending a transaction twice. The same one-time key gets used on different messages, which breaks WOTS's one-time security, and that leaf can then be used to forge signatures. So these stateful signatures are hard to use in user wallets and on the execution layer. Instead, in cases like the consensus layer, where a single device uses them continuously, they can be used cheaply.

So on Ethereum, XMSS is used on the consensus layer, and the execution layer is taking a different approach. Now let's look at stateless signatures. First, let me introduce SLH-DSA, the most representative NIST standard signature. SLH-DSA first hashes the message together with a randomizer and the public key to create a message digest. This digest determines not only what FORS signs, but also which XMSS tree and leaf to use.

Next, the verifier uses the FORS signature to recover the FORS public key. This value is the entry point into the hypertree above. Going from the bottom up, the first XMSS layer verifies a WOTS signature over this value and follows the Merkle authentication path to recover that layer's root.

The next layer verifies that root again with WOTS, computes the root along the authentication path again, and this repeats across multiple layers. So if the final computed root matches the PK root in the public key, the signature is considered valid. But because it includes many FORS and XMSS paths and signatures, as you saw earlier, the signature gets very large, and, as the figure shows, the number of hash computations grows a lot too.

So using it as-is is expensive, which is why the aggregation I'll discuss later becomes important. In the strawmap, the roadmap describing Ethereum's direction, this hasn't been fixed but has kept changing. In the strawmap's early version, NTT precompiles were chosen as the solution for the execution layer.

Next came Ephemeral Keys: instead of keeping a single signing key, the direction proposed was to rotate signing keys. And the current direction, following Instincts, has evolved toward linking hash-based signatures with STARK proving and aggregation. Let me start with the earliest approach, which I worked on: the NTT precompile. Before explaining the NTT precompile, let me explain what NTT is.

NTT stands for Number Theoretic Transform. If you've studied signal processing, it's easy to understand if you think of the Fast Fourier Transform. In FFT, instead of computing a convolution or polynomial multiplication directly, you move to the frequency domain via the Fourier transform and turn a complex multiplication into point-wise multiplication. NTT follows almost the same idea, but instead of using complex numbers, it performs a similar transform over finite fields.

Multiplying polynomials directly means computing many coefficient combinations, but after the NTT, you multiply component-wise, apply the inverse NTT, and then return to the original representation. This polynomial multiplication is one of the core operations of lattice-based schemes such as ML-DSA and Falcon, a core building block. This EIP provides these NTT operations as a precompile. It's an EIP I co-authored.

A precompile takes operations too expensive to implement in EVM bytecode, implements them as native code in the Ethereum client, and smart contracts use them by calling a fixed address. Rather than turning one specific signature scheme into a precompile, the NTT precompile offers operations common to many lattice-based schemes: forward NTT, inverse NTT, modular vector multiplication, and addition.

I tested this precompile and applied it to existing Solidity smart-contract Falcon and ML-DSA verifiers. In our tests, Falcon went from 1.81M gas to 475K gas, about a 73% gas reduction. ML-DSA went from 7.8M to 5.7M, and we got results saving over 2M gas.

Next, let me explain Ephemeral Keys. Ephemeral Keys uses the term "Quantum Structure." The smart account's address stays the same, while the signing key that authorizes the account is rotated with every user operation. The initial idea was to sign the current user operation with the current ECDSA-based key, passing along the next signer, and once validation completes, rotating to the next key. That way, you don't have to keep one signing key for long.

But because ECDSA itself isn't quantum-resistant, the public key is exposed while the transaction waits in the mempool, so a sufficiently powerful quantum attacker could attack during that mempool wait. So the design was switched to hash-based FORS. The account stores only the current signer's commitment, verifies the signature via a FORS signature, and if validation succeeds, rotates to the next signer

commitment. FORS is used here because WOTS, if reused even once, loses its security completely, whereas FORS, as a few-time signature, degrades gradually instead of collapsing entirely when a key is reused by mistake, so it can mitigate the risk of accidental reuse. But this approach must keep rotating the signer commitment, so there's the problem of managing state,

and since FORS itself isn't a standardized signature scheme, there are issues on the infrastructure maintenance side too. Lastly, before explaining Instincts, let me first explain Frame Transactions, which it builds on. A Frame Transaction splits a single transaction into multiple contract call frames. The key is separating a transaction's authorization from its actual execution.

Then, in the sender frame, the approved sender becomes the caller and the actual transaction is executed. The verify step is basically a static call, so apart from what's temporarily allowed, like APPROVE, it can't change state. What matters is that an account can define directly in code how it wants its transactions to be authorized. So how can these authorization conditions be checked with a single aggregated proof?

What links the authorization conditions to actual mempool aggregation is EIP-8288, In-Mempool Signature Aggregation. The key here is that the verification frame declares, as dependencies, which crypto verifications it needs in order to be valid. A dependency consists of three main pieces of information. First, the scheme specifies which verification method is used.

Next, the data specifies which message or public input is being verified. Finally, the verification key specifies which public key or verification key must be used. The wallet submits its signature or an individual proof with the transaction. In the mempool, dependencies from many transactions can be aggregated, and the builder produces an aggregate proof covering all dependencies of the transactions it will actually include in the block.

Finally, nodes check this proof and perform balance and state precondition checks, and regular transaction validation and execution, as before. Account code determines which message or key is a valid authorization condition for the account, and the aggregated proof proves that the condition and the signatures or proofs are actually valid.

Looking at this aggregation in the figure, the left shows the basic structure of STARK aggregation. Results of verifying multiple signatures are turned into proofs, recursively combined, and merged into a higher-level proof. The right shows how this aggregation goes through the mempool and is finally included in a block.

When new transactions and signatures arrive, they can be re-aggregated with the existing proof, and finally the builder creates an aggregate proof bundling every verification dependency for the block it will build. So instead of verifying every signature in the block one by one, nodes only need to verify this proof to confirm that they're all valid. Then, given that lattice-based signatures are small and, unlike hash-based ones, lend themselves to MPC, why is Ethereum leaning so strongly toward hash-based?

This is Vitalik's answer in the EIP-888 Ethereum Magicians discussion: minimize the cryptographic primitives the base layer depends on, and reduce the infrastructure that has to be maintained. So if signatures, proofs and commitments use, as far as possible, the same family of cryptographic primitives, with this system we can reduce the number of cryptographic components and implementations the base layer has to manage.

Another issue I consider important here is how closely we stick to the standard. If you build a new custom scheme, you naturally get better performance than existing schemes in a specific environment. But that comes at a cost. The biggest issue is security review. Standards have gone through public review over a very long period, but changed parameters or new primitives need that part reviewed again.

Also, with a standard, existing verifiers and libraries are widely available, but a custom scheme needs its own verifier and separate tooling reviewed. And these aren't built once and done; they have to be maintained separately afterward. Recently there was a similar episode around Ethereum's hash choice. Until now in ZK, proving standard hashes like SHA was costly, so these systems actively explored ZK-friendly hashes like Poseidon that are easy to prove

in proof systems. But recently, as Justin Drake raised issues with Poseidon, instead of using Poseidon, Ethereum is moving back to existing hashes like SHA or Blake. Behind this is the rise of binary fields. Binary fields can naturally express operations like bits and XOR, so the cost of proving standard hashes has dropped sharply. So while designing new primitives suited to proofs used to matter, now that costs are lower, the choice is shifting toward keeping well-reviewed

standard primitives and improving the proving systems instead, or so it's expected. So hash-based signatures now face a choice. On one side, research optimizing the signature scheme itself for the environment; on the other, research keeping the standard and optimizing the proving. First, let's look at work that optimizes the signature scheme itself.

SPHINCS- on the left is a SPHINCS variant aimed at making direct EVM verification cheap on Ethereum. In its representative parameter set, C13, instead of hashes like SHA or Blake, it uses Ethereum-friendly Keccak, and combines FORS, a 2D hypertree and WOTS.

The resulting signature is about 3.7 KB. Even verifying directly on the EVM, the cost can be brought down to around 105K gas. Rather than taking the standard structure as-is, it's an approach that tunes parameters and building blocks to Ethereum's EVM to cut direct verification cost. SHRINCS on the right is a direction being discussed in the Bitcoin community.

It tries a somewhat different approach to verification. Normally it uses a stateful path based on unbalanced XMSS and WOTS. If the used-leaf state is managed properly, the signature can be made much smaller, and with unbalanced XMSS in particular, when few signatures have been used, signatures get even smaller. So in normal operation, it uses signatures of between 0.5 and 4.6 KB.

But if the state can no longer be trusted, instead of continuing on the stateful path, it falls back to a SPHINCS-style stateless path. The signature then grows to about 5.8 KB, but it can be used indefinitely without persistent signing state. In short, SPHINCS- targets EVM verification cost, while SHRINCS optimizes signature size and state differently depending on the use case.

Recently, the speed of proving standard hashes has been improving very fast. First, one of the most important changes is the discovery of binary-field proving. Earlier SNARKs relied on large prime fields. Standard hashes like SHA or BLAKE3 use a lot of bit-level operations like XOR and AND, so representing them in those fields was costly. By switching to binary fields, they can be expressed far more naturally as Boolean computation.

Flock uses this property: it's a proof system specialized for batch proving of the same Boolean circuit run in bulk. It builds a Spartan-like protocol over binary fields and optimizes sumcheck and zerocheck for the batch structure, achieving figures about 9 times faster than Binius64 on paper. Then came work using binary STARKs. Rather than a new structure heavily specialized for batch hashing like Flock, it uses binary fields inside an existing STARK,

and showed that this still delivers quite high performance. And beyond papers, circuit-golfing platforms are advancing rapidly too. zk.golf is writing optimizations for SHA and BLAKE3 in Lean, a formal verification language, so they fully match the spec while cutting costs in half.

And on a platform called j4n, they ran a challenge on proving and achieved performance 3 to 4 times better than before. These advances in proving systems aren't happening only on the hash-based side. Lattice-based work is advancing in many ways too.

On the Falcon side, there was also an approach to prove Falcon signatures themselves quickly. And work like Lattice Jolt and Lattice genus is emerging that links lattice-based commitments with general-purpose proving. So because both hash-based and lattice-based proving are advancing quickly, the old assumption that standard hashes make proving too slow is gradually changing.

Given this trend, the question I'm looking at is this: without redesigning SLH-DSA for Ethereum, keeping the standard as-is, can we make just the proving and aggregation efficient? The current target is the SLH-DSA set with the smallest signatures among the standards. We take the verification procedure defined in FIPS and express it, and the proof system must confirm that each hash's inputs are connected correctly according to SLH-DSA's actual

verification flow. Next, we're considering putting multiple signatures through proving and turning them into a single proof. Beyond proving time, we plan to focus on how much memory is used, what the verification time is, what the size is, and so on. So my question is how far, without modifying the standard for Ethereum, we can lower verification cost by leveraging recent advances in proof systems. That's the research in progress.

Today we covered everything from the NTT precompile to Ephemeral Keys, HBS signatures and mempool aggregation. That concludes my talk. Thank you. Please give a big round of applause to researcher Yoonhyung Lee.