| eip | 9999 | |
|---|---|---|
| title | Frame type for quantum-resistant Signature and STARK Aggregation | |
| description | Add recursive STARK-based aggregation for signatures and STARKs via EIP-8141 frame types | |
| author | Vitalik Buterin (@vbuterin) | |
| discussions-to |
|
|
| status | Draft | |
| type | Standards Track | |
| category | Core | |
| created | 2026-06-03 | |
| requires | 2718, 2929, 2930, 7702, 8141 |
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) triples — which are aggregated off-chain into a single recursive STARK. Block validity requires this recursive STARK, enabling efficient post-quantum 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 and Frame Transactions.
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:
- Introduces dependency frames that declare
(scheme, data_hash, verification_key)triples as transaction-level dependencies. - Requires a recursive STARK at the block level that proves the validity of all dependencies in all transactions.
- Reuses lean Ethereum tooling (for signatures and STARKs), to maximize shared codebase.
- Provides a mempool wrapper format that bundles transactions with their dependencies and proofs.
| Name | Value |
|---|---|
FRAME_TX_TYPE |
0x06 |
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 |
MAX_SIGS_PER_TX |
16 |
MAX_STARKS_PER_TX |
1 |
This EIP introduces two new frame modes for EIP-8141 frame transactions:
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) 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_SCHEMEorLEANSTARK_SCHEME).data_hash: 32 bytes. ForLEANSPHINCS_SCHEME, this is the message hash (msghash). ForLEANSTARK_SCHEME, this is the public inputs hash (pub_input_hash).verification_key: 32 bytes. ForLEANSPHINCS_SCHEME, this is the public key (pubkey). ForLEANSTARK_SCHEME, this is the STARK verification key (vk).
This data is stored in the frame's data field.
Validity constraints:
- The frame's
datamust be exactly96*kbytes, and the first 31 bytes of each set of 96 must be zero. - For each set of 96 bytes,
scheme(byte 31) must be eitherLEANSPHINCS_SCHEMEorLEANSTARK_SCHEME. - Number of triples must be
>= 1and<= MAX_DEPENDENCIES_PER_FRAME. - The frame's
targetmust beNone(address0x00...00). - The frame's
valuemust be0. - The frame's
flagsmust be0. - The frame's
gas_limitmust besum(LEANSPHINCS_VERIFICATION_GAS if triple.scheme == LEANSPHINCS_SCHEME else LEANSTARK_VERIFICATION_GAS for triple in frame.data_triples).
A frame transaction may contain DEP_VERIFY_FRAME_MODE frames. 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) triples parsed from the frame's data field:
frame.data_triples = [
(data[31], data[32:64], data[64:])
for data in chunks(frame.data, 96)
]
dependencies(tx) = [
triple
for triple in frame.data_triples
for frame in tx.frames if frame.mode == DEP_VERIFY_FRAME_MODE
]
dependencies(block) = [
triple
for triple in dependencies(tx)
for tx in block.txs
]
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 themodeof framei. Frames with modeDEP_VERIFY_FRAME_MODEare dependency frames.FRAMEPARAM(0x04, i)returnslen(data)for framei.FRAMEDATACOPY(memOffset, dataOffset, length, i)copies the dependency data from frameiinto memory.
The data format for each dependency frame is a concatenation of 96-byte triples: scheme || data_hash || verification_key.
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:
[recursive_stark]
recursive_stark = [stark_proof, block_deps_hash]
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:block_deps_hash = hash(concat([ int_to_bytes32_big_endian(t.scheme) + t.data_hash + t.verification_key for t in get_dependencies(block) ]))
The recursive STARK is generated using Lean Ethereum tooling. It proves the following statement:
public inputs = [block_deps_hash]
private inputs = [block_dependencies, witnesses]
assert len(block_dependencies) == len(witnesses)
for i in range(len(witnesses)):
block_dependencies[i] = (scheme, data_hash, verification_key)
if scheme == LEANSPHINCS_SCHEME:
assert verify_leanSPHINCS(data_hash, verification_key, witnesses[i])
else if scheme == LEANSTARK_SCHEME:
assert verify_leanSTARK(data_hash, verification_key, witnesses[i])
else:
assert False
assert hash(block_dependencies) == block_deps_hash
The recursive STARK circuit is a simple list walker. It verifies all leanSPHINCS signatures using the Lean Ethereum leanSPHINCS verifier, and all leanSTARKs using the Lean Ethereum leanSTARK verifier. It does not understand the structure of transactions or blocks beyond iterating over a flat list of (scheme, data_hash, verification_key) triples and their corresponding witnesses.
The recursive STARK is verified using the AGGREGATED_VK, which is the hash of the verification key used for the aggregated proofs.
A block is valid if and only if:
- The
block_deps_hashin the recursive STARK header entry matches the result of hashingget_dependencies(block) - The recursive STARK proof verifies successfully against
AGGREGATED_VK. - The recursive STARK's public output is
true(all dependencies verified). - All transactions satisfy the normal EIP-8141 validity rules.
The block header's recursive_stark field is a single struct field, so any block that includes it necessarily has exactly one value. No separate cardinality rule is required.
At the mempool level, transactions with dependency verification frames are wrapped in a wrapper object that includes the transaction, its dependencies, and the individual proofs.
Wrapper encoding:
[wrapper_tx, deps, proofs]
wrapper_tx = the EIP-8141 frame transaction
deps = list of all (scheme, data_hash, verification_key) triples
proofs = list of individual leanSPHINCS signatures or leanSTARK proofs corresponding to deps
When a mempool node receives such an object, they must verify that:
- The list of deps and the list of proofs have the same length
- The total number of leanSPHINCS deps is
<= MAX_SIGS_PER_TX - The total number of leanSTARK deps is
<= MAX_STARKS_PER_TX - The i'th proof is a valid proof for the i'th dependency with the corresponding scheme
The wrapper object is not a valid transaction on its own. It is the builder's responsibility to:
- Receive the wrapper from the mempool.
- Aggregate all individual proofs in all
proofsof all transactions that they see into a single recursive STARK using Lean Ethereum tooling. - Include the original transactions in the block, and set the block header's
recursive_starkfield to the aggregated recursive STARK.
This EIP assumes the use of Lean Ethereum tooling for generating and verifying the recursive STARKs.
The recursive STARK is generated by:
- Defining a Lean function that takes a flat list of
(scheme, data_hash, verification_key)triples and their corresponding witnesses. - Iterating over the list, and for each triple with
scheme == LEANSPHINCS_SCHEME, callingleanSPHINCS.verify(data_hash, verification_key, witness). - For each triple with
scheme == LEANSTARK_SCHEME, callingleanSTARK.verify(data_hash, verification_key, witness). - Proving that all verifications return
true. - Generating a STARK proof of this execution using the Lean Ethereum STARK backend.
The circuit is a simple list walker. 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 derived from the Lean Ethereum STARK circuit definition.
The gas cost for a dependency verification frame is:
verification_gas(dep_verify_frame) = (
LEANSPHINCS_VERIFICATION_GAS if triple.scheme == LEANSPHINCS_SCHEME else LEANSTARK_VERIFICATION_GAS
)
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:
recursive_stark_gas = LEANSTARK_VERIFICATION_GAS * total_deps_in_block
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.
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:
- Reject transactions containing
DEP_VERIFY_FRAME_MODEframes as invalid (unknown frame mode). - Reject blocks containing a
recursive_starkheader field as invalid.
This is a consensus-breaking change. Activation requires a network upgrade.
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) 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 side 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 does not propose recursive aggregation at the mempool layer. Mempool nodes only verify individual proofs against their corresponding dependencies. The recursive STARK is constructed once by the builder at block-production time. A future optimization could allow mempool nodes to recursively aggregate proofs themselves, reducing bandwidth to the builder, but this EIP deliberately avoids that complexity.
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:
- Hashes vs bitfields as identifiers of what objects are being proven
- Many-time signatures (leanSPHINCS), instead of the one-time signatures that the consensus layer can use because it needs to enforce one-signature-per-slot anyway.
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.
A transaction with a single DEP_VERIFY_FRAME_MODE frame containing one (LEANSPHINCS_SCHEME, msghash, pubkey) triple, followed by a VERIFY frame that checks the existence of a dependency with a pubkey 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, vkhash, vk) triples, followed by a VERIFY frame that checks the existence of the dependencies with APPROVE_EXECUTION_AND_PAYMENT flags set.
A block containing:
- A normal EIP-8141 transaction.
- A transaction with dependency verification frames.
- A block header with a
recursive_starkfield.
A block with an invalid recursive STARK (e.g., wrong block_deps_hash or invalid proof) in the header should be rejected.
A mempool wrapper of the transaction from Test Case 1. Test its unwrapping, and that the result equals the block provided in Test Case 1.
A mempool wrapper of the transaction from Test Case 2. Test its unwrapping, and that the result equals the block provided in Test Case 2.
The security of this EIP relies on:
- Soundness of Lean Ethereum circuits: The STARK circuits must correctly implement the verification logic.
- Soundness of the hash function used: the realistic choices are Poseidon and BLAKE3. Poseidon is far more efficient to prove, but its security still remains to be fully verified.
- Soundness of recursive STARKs, up to at least depth 2: a STARK of a STARK must be sound. This is widely believed to be true and many constructions running live onchain already depend on this. However, this adds difficulty to end-to-end formally proving the scheme and its applications. Note also that the STARK verification keys that users put in to this system are up to users, and may potentially have unlimited recursion depth.
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_TXlimits the number of leanSPHINCS dependencies per transaction to 16.MAX_STARKS_PER_TXlimits the number of leanSTARK dependencies per transaction to 1.MAX_DEPENDENCIES_PER_FRAMElimits the number of dependencies per frame.MAX_FRAMES(from EIP-8141) limits the number of frames per transaction.- The gas cost for verification frames scales with the number of dependencies, making large dependency sets expensive.
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).
[TBD]
Copyright and related rights waived via CC0.