This EIP extends EIP-8141 with a new frame mode that enables EVM-level aggregation of cryptographic signatures and STARK (Scalable Transparent ARguments of Knowledge) proofs. The scheme allows transactions to carry lightweight dependencies — (scheme, data_hash, verification_key_hash) triples — which are aggregated off-chain into a single recursive STARK. Block validity requires this recursive STARK, enabling efficient post-quantum (PQ) and scalable signature aggregation using Lean Ethereum tooling.
Quantum-resistant signatures and zero-knowledge proofs both have a very high calldata requirement and gas cost. Current proposals for hash-based signatures are in the range of ~2-3 kB and ~150,000 to 200,000 gas to verify. Lattice-based signatures have a similar cost. Meanwhile, hash-based zero-knowledge proofs (STARKs) all take over 128 kB, or as much as 512 kB if fast generation is a goal (which it is client-side), which implies a STARK will take many millions of gas to verify. This on its own would mean that privacy protocols will have an impractically high cost, and be completely incompatible with FOCIL (EIP-7805) and Frame Transactions (EIP-8141).
This EIP solves this problem by adding STARK-based aggregation. Instead of a block directly containing these user-submitted signatures and STARKs, the block contains one single recursive STARK that proves their existence. More specifically, it:
(scheme, data_hash, verification_key_hash) triples as transaction-level dependencies.| Name | Value |
|---|---|
DEP_VERIFY_FRAME_MODE | 3 |
MAX_DEPENDENCIES_PER_FRAME | 256 |
LEANSPHINCS_SCHEME | 0x10 |
LEANSTARK_SCHEME | 0x11 |
LEANSPHINCS_VERIFICATION_GAS | 3000 |
LEANSTARK_VERIFICATION_GAS | 30000 |
AGGREGATED_VK | TBD |
AGGREGATION_INTERVAL | 1000 (milliseconds) |
MAX_SIGS_PER_TX | 16 |
MAX_STARKS_PER_TX | 1 |
MAX_LEANSIG_DEPS_PER_WRAPPER | 16 |
MAX_LEANSTARK_DEPS_PER_WRAPPER | 1 |
This EIP introduces a new frame mode for EIP-8141 frame transactions:
DEP_VERIFY_FRAME_MODE)We modify EIP-8141 to also allow frames with mode DEP_VERIFY_FRAME_MODE, in addition to all previously allowed modes. A frame with mode DEP_VERIFY_FRAME_MODE is a dependency verification frame. It declares a set of dependencies as (scheme, data_hash, verification_key_hash) triples. These triples are not executed as EVM code; instead, they are recorded as dependencies that must be proven valid by the recursive STARK in the block.
The payload encoding is a simple 96*k byte concatenation of k triples, each consisting of:
scheme: 31 zero bytes padding, then 1 byte identifying the verification scheme (LEANSPHINCS_SCHEME or LEANSTARK_SCHEME).data_hash: 32 bytes. For LEANSPHINCS_SCHEME, this is the message hash (msghash). For LEANSTARK_SCHEME, this is the public inputs hash (pub_input_hash).verification_key_hash: 32 bytes. For LEANSPHINCS_SCHEME, this is the public key hash (pubkey_hash). For LEANSTARK_SCHEME, this is a hash of the STARK verification key (vk_hash).This data is stored in the frame's data field.
Validity constraints:
data must be exactly 96*k bytes, and the first 31 bytes of each set of 96 must be zero.scheme (byte 31) must be either LEANSPHINCS_SCHEME or LEANSTARK_SCHEME.>= 1 and <= MAX_DEPENDENCIES_PER_FRAME.target must be None (address 0x00...00).value must be 0.flags must be 0.gas_limit must be sum(LEANSPHINCS_VERIFICATION_GAS if triple.scheme == LEANSPHINCS_SCHEME else LEANSTARK_VERIFICATION_GAS for triple in frame.data_triples).A frame transaction may contain frames with mode DEP_VERIFY_FRAME_MODE. These frames declare dependencies that must be satisfied by the block's recursive STARK.
The complete list of dependencies for a transaction is the concatenation of all dependency triples from all dependency verification frames. The data_triples property of a frame is the list of (scheme, data_hash, verification_key_hash) triples parsed from the frame's data field:
Where deduplicate_and_sort deduplicates and sorts:
During EVM execution, the transaction's dependencies are made available through the existing EIP-8141 FRAMEPARAM, FRAMEDATASIZE, and FRAMEDATACOPY instructions.
Contracts can iterate over all frames in the transaction using FRAMEPARAM to identify DEP_VERIFY_FRAME_MODE frames, then use FRAMEDATASIZE and FRAMEDATACOPY to read the dependency data from each frame's data field.
Specifically:
FRAMEPARAM(0x02, i) returns the mode of frame i. Frames with mode DEP_VERIFY_FRAME_MODE are dependency frames.FRAMEPARAM(0x04, i) returns len(data) for frame i.FRAMEDATACOPY(memOffset, dataOffset, length, i) copies the dependency data from frame i into memory.The data format for each dependency frame is a concatenation of 96-byte triples: scheme || data_hash || verification_key_hash.
This allows smart contracts to introspect the declared dependencies during execution using the existing EIP-8141 frame introspection mechanism.
A block is valid only if it contains a recursive STARK in the block header that proves the validity of all dependencies in all transactions. This is formalized as follows.
A new top-level field, recursive_stark, is added to the block header. This field contains the aggregated STARK proof for the block.
Header encoding:
stark_proof: The serialized recursive STARK proof.block_deps_hash: The 32-byte hash of all dependencies in the block, computed from the concatenation of all 96-byte dependency triples across all transactions:The recursive STARK is generated using Lean Ethereum tooling. It proves the following statement:
The recursive STARK circuit follows a "verify inputs, merge and discard" logic. It verifies:
We assume that the leanSPHINCS and leanSTARK verifiers are structured in such a way that they take as input a 32-byte pubkey hash or verification key hash, and the relevant parts of the full public key or verification key are included as part of the signature or proof as a witness. This is a generic transformation that can be made to any signature scheme or STARK scheme: verify_sig(msg, pub, sig) becomes verify(msg, hash(pub), (pub, sig)) and verify_stark(data_hash, vk, proof) becomes verify_stark(data_hash, hash(vk), (vk, proof)).
The recursive STARK circuit does not understand the structure of transactions or blocks beyond iterating over a flat list of (scheme, data_hash, verification_key_hash) triples, their corresponding witnesses, and nested recursive STARKs.
The recursive STARK is verified using a fixed protocol-level AGGREGATED_VK.
To enable unlimited-depth recursion, we need to pass the AGGREGATED_VK in as an input to the proof itself.
A block is valid if and only if:
block_deps_hash in the recursive STARK header entry matches the result of hashing dependencies(block)block_deps_hash and the fixed protocol-level AGGREGATED_VK.At the mempool level, transactions with dependency verification frames are wrapped in wrapper objects that are broadcast once per AGGREGATION_INTERVAL. Each wrapper contains a list of transactions and either their direct dependencies or a single recursive STARK proving all dependencies.
Wrapper encoding:
Where:
transactions = list of transactions in the wrapper. For transactions that were already broadcast in a previous wrapper, their hash is used instead of the full transaction to save space.deps = sorted, deduplicated union of all (scheme, data_hash, verification_key_hash) triples from all transactions in the wrapperproofs = list of individual proofs corresponding to each dependency in depsrecursive_stark = a single recursive STARK proving validity of all deps, with public input hash(deps)Mode 0 (Direct dependencies): When a mempool node receives a wrapper with mode == 0, they must verify that:
deps list is the sorted, deduplicated union of all dependencies from each transaction in transactions<= MAX_LEANSIG_DEPS_PER_WRAPPER<= MAX_LEANSTARK_DEPS_PER_WRAPPERMode 1 (Recursive STARK): When a mempool node receives a wrapper with mode == 1, they must verify that:
deps_hash equals hash(deps)<= MAX_LEANSIG_DEPS_PER_WRAPPER<= MAX_LEANSTARK_DEPS_PER_WRAPPEREach wrapper contains exactly one STARK in mode 1, and one STARK per leanSTARK dependency in mode 0. Per AGGREGATION_INTERVAL, a mempool node broadcasts exactly one wrapper containing all currently active transactions, with exactly one STARK covering all their dependencies.
Mode 0 is intended to be used primarily by clients broadcasting their transactions. If desired, mempool nodes whose local transaction pool contains ONLY leanSPHINCS signatures and no STARKs may choose to rebroadcast a mode 0 aggregation that naively concatenates the leanSPHINCS instead of proving them, as doing so may be more space-efficient up to about a hundred leanSPHINCS signatures.
The wrapper object is not a valid transaction on its own. Mempool nodes, FOCIL creators and builders use the same recursive STARK format to aggregate proofs. The only difference is the scope: mempool nodes aggregate over their current view of valid and includable transactions, while builders aggregate over the transactions they decide to include in the block.
This EIP introduces recursive aggregation at the mempool layer. This allows mempool nodes to combine proofs and reduce bandwidth overhead to builders.
Mempool nodes follow the following algorithm:
AGGREGATION_INTERVAL milliseconds, they generate a new mode 1 wrapper object containing all still-valid transactions, and a recursive STARK proving their validity. They forward this wrapper object to their peers, replacing any transaction that they already sent previously with its hash to save data.If a node anticipates that it will not have enough proving time to aggregate in all aggregates that it saw, it should prioritize in the following order:
Nodes may also alternate between adding one object at a time from (3) and (4).
To prevent DoS attacks, two mempool-level limits apply to recursive STARK aggregation: MAX_LEANSIG_DEPS_PER_WRAPPER and MAX_LEANSTARK_DEPS_PER_WRAPPER, defined in Constants.
Additionally, two mempool-level limits apply to each transaction: a transaction can have <= MAX_SIGS_PER_TX leanSPHINCS dependencies and <= MAX_STARKS_PER_TX leanSTARK dependencies, added up across all frames.
These limits ensure that the worst-case mempool DoS vector of this scheme is equivalent to the situation if the same data were sent in the clear. That is, a sender could alternatively submit a transaction containing the raw signatures and STARKs as calldata, and the mempool would have to store and propagate that data anyway.
These limits in all cases apply to the length of the sorted, deduplicated dependency list. The list in a wrapper is required to be deduplicated in any case. For transactions, however, it does mean that it is legal to have a transaction with eg. > MAX_SIGS_PER_TX leanSPHINCS dependency declarations, if some of them are pointing to the same object so the deduplicated list is within limits. This behavior is wasteful but harmless; it is charged for and limited through the gas mechanism.
This EIP is designed to be compatible with EIP-7805 (FOCIL), which implements fork-choice enforced inclusion lists. The compatibility considerations are as follows.
The FOCIL data structure is extended to include a recursive_stark field, similar to a block. This allows FOCILs to carry pre-aggregated proofs of their transactions' dependencies:
transactions: The list of transactions in the inclusion list.recursive_stark: A recursive STARK proving validity of all dependencies in all transactions.deps_hash: The hash of all dependencies in the FOCIL's transactions.This extension allows FOCILs to be self-contained: they carry not just the transactions but also a proof that all their dependencies are valid. This is analogous to how a block carries both transactions and a recursive STARK.
To determine which transactions are mandatory to include for FOCIL purposes, attesters must validate all transactions in each FOCIL, and verify their dependencies by verifying the recursive proof in that FOCIL.
The builder's workflow in a FOCIL-enabled network is:
recursive_stark proving validity of its transactions' dependencies.recursive_stark field to the aggregated recursive STARK.Note that the job of a mempool actor aggregating to reforward, a FOCIL creator aggregating to generate a FOCIL, and a builder aggregating to include, are exactly the same task. Both take a set of wrapper objects (from mempool or FOCILs), extract their dependencies and proofs, and produce a recursive STARK covering the union of all valid dependencies.
The recursive aggregation scheme preserves FOCIL's censorship resistance properties:
The recursive STARK scheme is compatible with the consensus layer's use of Lean Ethereum tooling. The same STARK backend and verification infrastructure can be used for both consensus layer signature aggregation and execution layer dependency verification. Inclusion lists (ILs) are just a different kind of package of transactions (like blocks) and use the same signature schemes as other components; no new signature scheme is required specifically for ILs.
This EIP assumes the use of Lean Ethereum tooling for generating and verifying the recursive STARKs. This tooling can be found at the leanEthereum GitHub organization.
The recursive STARK is generated by:
(scheme, data_hash, verification_key_hash) triples and their corresponding witnesses.scheme == LEANSPHINCS_SCHEME, calling leanSPHINCS.verify(data_hash, verification_key_hash, witness).scheme == LEANSTARK_SCHEME, calling leanSTARK.verify(data_hash, verification_key_hash, witness).true.The circuit is a relatively simple recursive "union and remove" construction, very similar to that which is planned to be used for consensus-layer signatures. It does not understand transactions or blocks; it only sees a flat list of dependencies and witnesses.
The verification key AGGREGATED_VK used to verify the recursive STARK is a fixed protocol-level value derived from the Lean Ethereum STARK circuit definition.
The gas cost for a dependency verification frame is:
The actual STARK verification is performed off-chain by the builder, so the gas cost represents the expected cost of verifying the recursive STARK, not the actual cost. It is much cheaper than the onchain costs for similar operations because the cost is only paid by the builder and the mempool, not by all validating nodes.
The recursive_stark header field has its own gas cost, charged as part of the block's base fee:
where total_deps_in_block is the total number of dependency triples across all transactions in the block.
Because these dependencies are at the transaction body level and are not created inside the EVM, they are not affected by transaction execution reverting, and the gas is still fully charged even if the transaction reverts. This is similar to eg. intrinsic gas for calldata.
As a special case, notice that if a frame or a transaction has the same dependency multiple times, gas is charged for each declaration. So duplicate dependencies in a transaction are legal, but are wasteful.
If an EVM opcode were chosen instead, the core question is how to handle missing or invalid proofs. From a mempool node's point of view, if it sees a dependency appear during transaction execution, and it has no valid proof for it, then it must be able to reject that transaction. And if a mempool accepts a transaction, it must be confident that EVM execution in later frames will not create other dependencies that are unfulfilled.
The most realistic alternative would be for an opcode that creates a (scheme, data_hash, verification_key_hash) dependency to only be callable during an EIP-8141 validation frame. This would be viable. However, it would still make the mempool and builder's job relatively harder, because the EVM execution and dependency validation would have to be done sequentially rather than in parallel. It would also add more need to reason about special cases where EVM execution might add a dependency but then revert.
Recursive STARKs allow the aggregation of many individual proofs into a single proof. This is essential to avoid the size blowup of one STARK per transaction (that uses a STARK).
Introducing a recursive STARK into each block header does increase the block header size greatly. However, this is ultimately a cost that will have to be paid regardless, if we want light clients to be able to verify the correctness of blocks.
This EIP proposes recursive aggregation at the mempool layer. Mempool nodes generate recursive STARKs every tick, combining all valid wrapper objects they know about. This reduces bandwidth to the builder, as the builder receives pre-aggregated proofs from mempool nodes. In particular, the STARK-related overhead for the builder is a fixed ~256 kB per AGGREGATION_INTERVAL milliseconds.
The builder uses the exact same recursive STARK format to aggregate all included transactions' dependencies into the block-level recursive STARK.
The Lean Ethereum tooling has already been extensively developed, has full formal verification in progress, and is the expected signature and recursive proof type for the future Ethereum consensus chain.
This EIP's use case — processing many thousands of signatures and STARKs per slot without extreme data overhead — is almost identical to the consensus layer's use case. The main differences are:
Because the underlying use cases are similar, from a total spec simplification perspective, it is best to reuse the exact same tooling, rather than create a totally different set of tools for the execution layer.
Users who want to use quantum-resistant signature schemes other than leanSPHINCS signatures will have to either use them in the clear, and accept the onchain gas costs of doing so, or wrap them client-side in a STARK, and then reuse the leanSTARK route.
As written, the EIP enforces fixed gas costs for both signatures and STARKs. This is assuming one parametrization of leanSPHINCS is used, and one parametrization of STARKs (or at least a small ratio between the average case and the upper bound).
An upper bound does need to be enforced. We make sure to add appropriate trace width limits and execution cycle count limits to STARK verification. In the current design (KoalaBear field, fixed trace width), this is enforced by the 2**24 trace length limit inherent to KoalaBear, and the trace width is fixed. If leanVM is redesigned, limits need to be kept in mind, so that the maximum possible proof size is a small multiple of the average case.
There may be two valid reasons to adjust the current fixed-cost approach and switch to variable cost:
This EIP introduces new transaction types and frame modes. It does not modify the behavior of existing transactions. Transactions without signature or STARK verification frames are unaffected.
Nodes that do not implement this EIP will:
DEP_VERIFY_FRAME_MODE frames as invalid (unknown frame mode).recursive_stark header field as invalid.This is a consensus-breaking change. Activation requires a network upgrade.
A transaction with a single DEP_VERIFY_FRAME_MODE frame containing one (LEANSPHINCS_SCHEME, msghash, pubkey_hash) triple, followed by a VERIFY frame that checks the existence of a dependency with a pubkey_hash pulled from its storage, and the msghash pulled by using TXPARAM to extract the transaction signature.
A transaction with a single DEP_VERIFY_FRAME_MODE frame containing multiple (LEANSTARK_SCHEME, pub_input_hash, vk_hash) triples, followed by a VERIFY frame that checks the existence of the dependencies with APPROVE_EXECUTION_AND_PAYMENT flags set.
A block containing:
recursive_stark field.A block with an invalid recursive STARK (e.g., wrong block_deps_hash or invalid proof) in the header should be rejected.
A mode 0 mempool wrapper containing multiple transactions (including the transaction from Test Case 1). Verify that the wrapper's deps and proofs match the transactions' dependencies, and that each proof can be verified individually.
A mode 1 mempool wrapper containing multiple transactions (including the transaction from Test Case 2). Verify that the wrapper's recursive STARK proves all dependencies are valid, and that the deps_hash matches hash(deps).
A scenario where a mempool node receives multiple transactions and generates a mode 1 wrapper with a recursive STARK. Verify that the recursive STARK covers all dependencies of all transactions in the wrapper, and that the wrapper can be verified by other mempool nodes and builders.
A mempool wrapper containing a transaction with dependencies, where the wrapper uses mode == 1 and contains a pre-computed recursive STARK. Verify that the recursive STARK's public input deps_hash matches hash(deps) and that the proof is valid.
A FOCIL containing transactions with dependencies, where the FOCIL includes a recursive_stark field. Verify that the recursive STARK proves validity of all dependencies in the FOCIL's transactions, and that a builder can incorporate this FOCIL into a block-level recursive STARK.
A scenario where a mempool node generates a recursive STARK that includes a discard set, excluding expired or invalid objects from the validity claim. Verify that the resulting deps_hash reflects only the non-discarded dependencies.
A block containing:
recursive_stark field that proves all dependencies are valid.TBD.
The security of this EIP relies on:
deps_hash and block_deps_hash: the current leading choice is BLAKE3.A malicious sender could create transactions with many dependency frames, forcing builders to generate large recursive STARKs. The primary defense is the mempool-level limits:
MAX_SIGS_PER_TX limits the number of leanSPHINCS dependencies per transaction to 16.MAX_STARKS_PER_TX limits the number of leanSTARK dependencies per transaction to 1.MAX_DEPENDENCIES_PER_FRAME limits the number of dependencies per frame.MAX_FRAMES (from EIP-8141) limits the number of frames per transaction.MAX_LEANSIG_DEPS_PER_WRAPPER and MAX_LEANSTARK_DEPS_PER_WRAPPER limit the number of dependencies per mempool wrapper.These limits are chosen such that the theoretical worst-case mempool DoS vector of this scheme is equivalent to the situation if the same data were sent in the clear. That is, a sender could alternatively submit a transaction containing the raw signatures and STARKs as calldata, and the mempool would have to store and propagate that data anyway. The limits ensure that the data stored in the dependency frames is bounded by the same order of magnitude as the data that would be stored in a traditional transaction, limiting the increase in mempool DoS exposure. However, an increase in mempool DoS exposure still exists, because quantum-resistant signatures and proofs are much larger and more costly to verify than the present-day elliptic-curve-based versions of these primitives.
These limits are inspired by the mempool policy framework of ERC-7562 (as used in EIP-8141).
Copyright and related rights waived via CC0.