EIP-8288: Frame Type for PQ Sig and STARK Aggregation

Adds recursive STARK-based aggregation for quantum-resistant signatures and STARKs via an EIP-8141 frame mode

Abstract

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.

Motivation

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:

• Introduces dependency frames that declare (scheme, data_hash, verification_key_hash) 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.
• Supports recursive aggregation at the mempool layer, allowing mempool nodes to combine proofs and reduce bandwidth overhead.
• Is compatible with FOCIL (EIP-7805), ensuring that the aggregation scheme works with fork-choice enforced inclusion lists.

Specification

Constants

New Frame Mode

This EIP introduces a new frame mode for EIP-8141 frame transactions:

Dependency Verification Frame (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:

• The frame’s data must be exactly 96*k bytes, and the first 31 bytes of each set of 96 must be zero.
• For each set of 96 bytes, scheme (byte 31) must be either LEANSPHINCS_SCHEME or LEANSTARK_SCHEME.
• Number of triples must be >= 1 and <= MAX_DEPENDENCIES_PER_FRAME.
• The frame’s target must be None (address 0x00...00).
• The frame’s value must be 0.
• The frame’s flags must be 0.
• The frame’s gas_limit must be sum(LEANSPHINCS_VERIFICATION_GAS if triple.scheme == LEANSPHINCS_SCHEME else LEANSTARK_VERIFICATION_GAS for triple in frame.data_triples).

Transaction Dependencies

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:

frame.data_triples = [
    (data[31], data[32:64], data[64:])
    for data in chunks(frame.data, 96)
]

dependencies(tx) = deduplicate_and_sort([
    triple
    for frame in tx.frames if frame.mode == DEP_VERIFY_FRAME_MODE
    for triple in frame.data_triples
])

dependencies(block) = deduplicate_and_sort([
    triple
    for tx in block.txs
    for triple in dependencies(tx)
])

Where deduplicate_and_sort deduplicates and sorts:

def deduplicate_and_sort(deps):
    o = []
    for dep in sorted(deps):
      if len(o) == 0 or dep != o[-1]:
        o.append(dep)
    return o

Transaction Execution Visibility

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.

Block Validity: Recursive STARK

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.

Recursive STARK Header Entry

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 = [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_hash
      for t in dependencies(block)
  ]))

Recursive STARK Proof Structure

The recursive STARK is generated using Lean Ethereum tooling. It proves the following statement:

public inputs = [deps_hash, AGGREGATED_VK]

private inputs = [deps, witnesses, recursive_proofs, recursive_deps_list, discards]

# Helper: compute deps hash consistently with block_deps_hash
get_deps_hash(deps) = hash(concat([
    int_to_bytes32_big_endian(t.scheme) + t.data_hash + t.verification_key_hash
    for t in deps
]))

# Verify direct dependencies
assert len(deps) == len(witnesses)
for i in range(len(witnesses)):
    scheme, data_hash, verification_key_hash = deps[i]
    if scheme == LEANSPHINCS_SCHEME:
        assert verify_leanSPHINCS(data_hash, verification_key_hash, witnesses[i])
    else if scheme == LEANSTARK_SCHEME:
        assert verify_leanSTARK((data_hash,), verification_key_hash, witnesses[i])
    else:
        assert False

# Verify recursive proofs and collect their deps
all_deps = list(deps)
for i in range(len(recursive_proofs)):
    proof = recursive_proofs[i]
    inner_deps = recursive_deps_list[i]
    # Verify the recursive proof's public input matches its claimed deps hash
    assert verify_leanSTARK((get_deps_hash(inner_deps), AGGREGATED_VK), AGGREGATED_VK, proof)
    # Add the inner deps to the union
    all_deps.extend(inner_deps)

# Remove discards and duplicates
discard_hashes = set(get_deps_hash([d]) for d in discards)
filtered_deps = deduplicate_and_sort([
    dep for dep in all_deps if get_deps_hash([dep]) not in discard_hashes
])

# Verify final deps hash matches public input
assert get_deps_hash(filtered_deps) == deps_hash

The recursive STARK circuit follows a “verify inputs, merge and discard” logic. It verifies:

• All leanSPHINCS signatures using the Lean Ethereum leanSPHINCS verifier
• All leanSTARKs using the Lean Ethereum leanSTARK verifier
• Recursive STARKs using the Lean Ethereum leanSTARK verifier.

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.

Block Validity Rules

A block is valid if and only if:

1. The block_deps_hash in the recursive STARK header entry matches the result of hashing dependencies(block)
2. The recursive STARK proof verifies successfully against block_deps_hash and the fixed protocol-level AGGREGATED_VK.
3. All transactions satisfy the normal (EIP-8141 or other) validity rules.

Mempool Wrapper Object

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:

[transactions, mode, content]
transactions = list of EIP-8141 frame transactions (or their hashes if already broadcast)
mode = 0 (direct dependencies) or 1 (recursive STARK)
content = if mode == 0: [deps, proofs]
          if mode == 1: [deps, recursive_stark]

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 wrapper
• proofs = list of individual proofs corresponding to each dependency in deps
• recursive_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:

1. The deps list is the sorted, deduplicated union of all dependencies from each transaction in transactions
2. The total number of leanSPHINCS deps is <= MAX_LEANSIG_DEPS_PER_WRAPPER
3. The total number of leanSTARK deps is <= MAX_LEANSTARK_DEPS_PER_WRAPPER
4. Each dependency has a corresponding proof that can be verified individually

Mode 1 (Recursive STARK): When a mempool node receives a wrapper with mode == 1, they must verify that:

1. The recursive STARK’s public input deps_hash equals hash(deps)
2. The recursive STARK is valid (proves all deps are valid)
3. The total number of leanSPHINCS deps is <= MAX_LEANSIG_DEPS_PER_WRAPPER
4. The total number of leanSTARK deps is <= MAX_LEANSTARK_DEPS_PER_WRAPPER

Each 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.

Recursive Mempool Aggregation

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:

• They passively wait and receive wrapper objects from users. When they see a wrapper, they validate its proof (either direct proofs or a recursive STARK). If valid, they accept it.
• When a transaction becomes unincludable (either because some other transaction from the same sender is included onchain, or because of any other mempool expiry rule), they keep note that its dependencies need to be pruned
• Every 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:

1. Its own aggregate from the previous round
2. Removing anything that needs to be removed
3. Other nodes’ aggregates, in descending order of how many new transactions they will add to the aggregate
4. Users’ transactions, in descending order of priority fee

Nodes may also alternate between adding one object at a time from (3) and (4).

Mempool-Level Limits

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.

FOCIL Compatibility

This EIP is designed to be compatible with EIP-7805 (FOCIL), which implements fork-choice enforced inclusion lists. The compatibility considerations are as follows.

Extended FOCIL Data Structure

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:

[FOCIL]
FOCIL = [transactions, recursive_stark]
recursive_stark = [stark_proof, deps_hash]

• 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.

Attesters Validity Verification

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.

Builder Workflow with FOCIL

The builder’s workflow in a FOCIL-enabled network is:

1. Receive FOCILs from the P2P network. Each FOCIL includes a recursive_stark proving validity of its transactions’ dependencies.
2. Receive mempool wrapper objects from the mempool. Each wrapper may contain either direct proofs or a recursive STARK.
3. Process FOCILs and mempool wrappers in the same way: extract their dependencies and verify their proofs.
4. Decide which transactions to include in the block (ensuring all FOCIL transactions are included).
5. Perform a recursive wrap over all included transactions’ dependencies:
   • Collect all dependencies from all included transactions.
   • Collect all proofs from FOCILs and wrappers that cover included transactions (recursive STARKs from mode 1 wrappers and FOCILs, or direct proofs from mode 0 wrappers).
   • Union all dependencies and remove any from transactions not included.
   • Generate a new recursive STARK proving the final set of dependencies.
6. Set the block header’s recursive_stark field to the aggregated recursive STARK.
7. Build the execution payload including all included transactions.

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.

Censorship Resistance

The recursive aggregation scheme preserves FOCIL’s censorship resistance properties:

• Mempool nodes can recursively aggregate proofs without understanding transaction semantics.
• The scheme does not introduce new centralization pressures beyond those already present in FOCIL.
• The bandwidth overhead of recursive STARKs is constant per peer, regardless of the number of transactions.

Consensus Layer Integration

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.

Lean Ethereum Integration

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:

1. Defining a Lean function that takes a flat list of (scheme, data_hash, verification_key_hash) triples and their corresponding witnesses.
2. Iterating over the list, and for each triple with scheme == LEANSPHINCS_SCHEME, calling leanSPHINCS.verify(data_hash, verification_key_hash, witness).
3. For each triple with scheme == LEANSTARK_SCHEME, calling leanSTARK.verify(data_hash, verification_key_hash, witness).
4. Proving that all verifications return true.
5. Generating a STARK proof of this execution using the Lean Ethereum STARK backend.

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.

Gas Accounting

The gas cost for a dependency verification frame is:

verification_gas(dep_verify_frame) = sum(
    LEANSPHINCS_VERIFICATION_GAS if triple.scheme == LEANSPHINCS_SCHEME else LEANSTARK_VERIFICATION_GAS
    for triple in dep_verify_frame.data_triples
)

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.

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.

Rationale

Why a new frame mode instead of an EVM opcode?

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.

Why recursive STARKs?

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.

Why Lean Ethereum?

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:

1. Hashes vs bitfields as identifiers of what objects are being proven
2. Many-time stateless signatures (leanSPHINCS), instead of the counter-based stateful signatures (leanXMSS) 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.

Gas costs

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:

• Mixed k-time and unlimited-time usage of leanSPHINCS: k-time signatures are significantly smaller than unlimited-time signatures, and SPHINCS could expose a parametrization that supports both. In this case, the former would need to have appropriately lower gas costs.
• Different STARK sizes based on client-side proving time tradeoffs Smaller proofs take longer to generate. We want larger proofs (cheaper to generate) to be possible, while still encouraging smaller proofs that put less load on the mempool nodes. This can be achieved by making gas cost proportional to proof size (or a related metric, like query count, and even polynomial degree).

Backwards Compatibility

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_MODE frames as invalid (unknown frame mode).
• Reject blocks containing a recursive_stark header field as invalid.

This is a consensus-breaking change. Activation requires a network upgrade.

Test Cases

Test Case 1: Simple leanSPHINCS Verification

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.

Test Case 2: Multiple leanSTARK Dependencies

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.

Test Case 3: Block with Mixed Transactions

A block containing:

• A normal EIP-8141 transaction.
• A transaction with dependency verification frames.
• A block header with a recursive_stark field.

Test Case 4: Invalid Recursive STARK

A block with an invalid recursive STARK (e.g., wrong block_deps_hash or invalid proof) in the header should be rejected.

Test Case 5: Mode 0 Mempool Wrapper

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.

Test Case 6: Mode 1 Mempool Wrapper

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).

Test Case 7: Recursive Mempool Aggregation

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.

Test Case 8: Wrapper with Recursive STARK (Mode 1)

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.

Test Case 9: FOCIL with Recursive STARK

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.

Test Case 10: Discard Set

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.

Test Case 11: FOCIL Compatibility

A block containing:

• Transactions from FOCIL inclusion lists.
• Transactions with dependency verification frames.
• A block header with a recursive_stark field that proves all dependencies are valid.
• Verification that the block satisfies FOCIL inclusion constraints.

Reference Implementation

TBD.

Security Considerations

Trust Assumptions

The security of this EIP relies on:

1. Soundness of Lean Ethereum circuits: The STARK circuits must correctly implement the verification logic.
2. Soundness of the hash function used for deps_hash and block_deps_hash: the current leading choice is BLAKE3.
3. Soundness of recursive STARKs: a STARK of a STARK of … 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.

Denial of Service

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.
• 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).

Copyright

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Vitalik Buterin (@vbuterin), Thomas Coratger (@tcoratger), "EIP-8288: Frame Type for PQ Sig and STARK Aggregation [DRAFT]," Ethereum Improvement Proposals, no. 8288, June 2026. Available: https://eips.ethereum.org/EIPS/eip-8288.