Repurposing FOCIL as an L2 forced transaction mechanism

Layer 2
1

Thanks to Péter Garamvölgyi, Thomas Thiery, Francesco Risitano and Jihoon Song for feedback and review.

The following article is based on or related to EIPs at very different inclusion stages, in particular: FOCIL (SFI), Optional Execution Proofs (PFI), Block-level Access Lists (SFI), Validity-Only Partial Statelessness (no EIP), Native rollups (not yet proposed). Details are therefore expected to change over time. While this research is mainly motivated by the need to find a simple forced transaction mechanism for native rollups, the findings can be generally applied to all EVM L2s including existing ones.

Abstract

We present an implementation of a forced transaction mechanism via FOCIL that can be used to bypass the centralized sequencers of EVM L2s without any modification to the state transition function or new transaction types, unlike existing solutions.

Background

FOCIL updates Ethereum’s STF by adding a new list of transactions (the “inclusion list”) that the block has to satisfy for it to get attested. Such transactions are chosen by an “IL committee” on the CL side, which is composed of 16 validators and passed to the EL via the updated Engine API.

def state_transition(​chain: BlockChain, ​​block: Block, ​​inclusion_list_transactions: Tuple[LegacyTransaction | Bytes, ...]​) -> None:

Transactions in the IL can still be validly excluded from a block for three reasons:

  • Intrinsic checks fail: malformed tx, wrong chain id, insufficient gas, invalid signature, params outside of bounds;

  • Stateful checks fail: nonce mismatch, insufficient balance;

  • Block related checks fail: insufficient gas (wrt base fee), insufficient space in block.

Even though a builder can purposely exclude a transaction via “block stuffing”, the protocol provides censorship resistance by inflicting an exponential cost to the attacker by increasing the EIP-1559 base fee and keeping the transaction in the mempool, which will be inserted in the next IL.

All existing EVM L2s currently implement forced transactions by introducing new transaction types and modifying the state transition function. OP stack introduces the “deposited transaction” type, which is derived from L1 event, automatically inserted at the top of the corresponding L2 block, has no signature on L2, pays for gas on L1 and consumes no gas on L2. All the changes of op-geth on top of geth can be found here. Arbitrum stack also introduces a new transaction type (actually several) without signature whose inclusion is enforced by an onchain forced transaction queue, but that pays for gas on L2. All the changes on top of geth can be found here. Most importantly, in both cases, a valid transaction that gets in the list of the transactions to be forced included is never validly excluded because of a full block or base fee: space for them is always reserved and either the base fee is not accounted for or a retry mechanism is implemented.

The mechanism

The core intuition is that the FOCIL’s CL and mempool logic can be fully replaced and replicated by a smart contract on L1: users submit forced transactions to an L1 smart contract instead of a traditional L2 mempool (maybe through L1 FOCIL!), which builds the inclusion list and passes it as an input to the L2 STF verifier, in a similar way the Engine API passes it to the EL. The L2 STF is assumed to be exactly the same as the stateless STF function introduced by EIP-8025. Since 8025 does not build on top of Hegotá yet and therefore does not account for FOCIL, we take the freedom to imagine the stateless IL interface.

Illustration of how “L2 FOCIL” replaces CL and EL components involved in the FOCIL checks for L1.
Illustration of how “L2 FOCIL” replaces CL and EL components involved in the FOCIL checks for L1.2042×1574 240 KB

Illustration of how “L2 FOCIL” replaces CL and EL components involved in the FOCIL checks for L1.

To replicate the mempool behaviour and guarantee censorship resistance, we need to make sure that transactions that end up in the L2 IL are not automatically dropped, given that, unlike existing forced transaction mechanisms, FOCIL does not actually guarantee inclusion in a specific block. Moreover, all transactions that are invalid should not pollute ILs as much as possible, to prevent wasted computation on the prover side and DoS attacks on valid transactions.

We assume that each L2 batch posted by the operator corresponds to an L2 block, otherwise the operator could always produce empty blocks to reduce the base fee and cheaply perform block stuffing attacks. This is not the case today for most rollups, but faster blocks can be simulated with techniques such as flashblocks.

We therefore design a forced tx contract as follows: users submit signed txs to an onchain list that is ordered by `maxFeePerGas`, descending. On submission, all intrinsic (i.e. stateless) checks are performed. As explained in the Validity-Only Partial Statelessness (VOPS) research post and here, performing the stateful checks are fundamental to maintain a healthy mempool: even though in L2 FOCIL a submitted transaction pays for gas on L1, it is cheap to stuff the head of the list with transactions that have a very high `maxFeePerGas` but have invalid nonce or insufficient balance, causing ILs to only contain invalid transactions. VOPS therefore suggests that stateless nodes should still maintain each account balance and nonce via BALs. While EVM L2s will also be able to produce and publish BALs, it is unfeasible to maintain balances and nonces in a smart contract: for L1, the estimated storage already adds up to ~8.4GB, and for L2s it is likely to be significantly higher. We therefore require users to submit an account proof, obtained via eth_getProof against a recent L2 state to be admitted in the list. Since FOCIL doesn’t tell us whether a transaction in an inclusion list has been included or not and why, transactions that end up in a IL, even after these checks, cannot be automatically dropped. Two mechanisms can be used:

  1. A permissionless `prune` function is added that, given an account proof against a newer block, proves that either the nonce has changed or that the balance has become insufficient. It is important to remember that the nonce check alone is not sufficient as EIP-7702 broke the invariant that an account balance can decrease only if the nonce increases. To achieve incentive compatibility, forced tx submitters can be asked to submit a small bond to refund pruners when the transaction gets invalidated.

  2. The operator provides a merkle proof against the tx root during settlement. Given the IL is validated by the STF (e.g. via a ZK proof), we can check that if a transaction has not been included and there was space left in the block, then the transaction must have been invalid and can be dropped. Estimated costs: ~275k gas per tx in IL, 32 txs is within 10M gas, possibly lower with multiproofs. If a transaction in the IL is invalid but there was no space left in the block, the transaction would not be dropped as we cannot discern the full block case from the invalid case. The 1559 base fee mechanism guarantees that a block with sufficient space will be eventually produced, assuming enough elasticity.

The L2 operator, when calling the settlement function with an L2 block, pulls the current IL from the transactions at the top of the list up to a predefined gas budget or until transactions do not pay enough for the current base fee. Such IL is enforced as an input to the onchain verifier, and its satisfaction is considered a validity rule. To prevent race conditions and griefing attacks, the IL can be built with only transactions that are at least older than a threshold, so that the prover can know in advance the exact transactions it will be forced to include. If the L2 centralized sequencer refuses to produce blocks completely, a timeout can be triggered onchain to remove the whitelist and restore censorship resistance.

A concrete implementation can be found here. A submission is estimated to cost ~1.3M gas, while a prune ~1.1M gas, both corresponding to roughly 0.001 ETH at 1 gwei per gas.

While out of scope of this research post, the forced transaction contract can be naturally customized to perform additional checks before being accepted based on the specific L2 needs.

Accounts-only nodes

Today, obtaining an account proof requires connecting to a full node, which is prohibitive for most users, especially for L2s. The VOPS proposal, when combined with a zkEVM, aims to reduce the storage load on attesters and includers from ~233GiB to ~8.4 GiB by only validating the state using proofs and maintaining an healthy mempool by only storing balances and nonces obtained via BALs. Since L2s also post proofs and will be able to post BALs, a similar type of node can be imagined for L2 users to allow them to more easily submit forced transactions in case of censorship without having to maintain the full state. Unfortunately, since BALs only post storage diffs, it is necessary to track the full state to be able to reconstruct the storage root needed to provide an account proof. For quick reference, a BAL is defined as:

BlockAccessList = List[AccountChanges]

AccountChanges = [
    Address,                    # address
    List[SlotChanges],          # storage_changes (slot -> [block_access_index -> new_value])
    List[StorageKey],           # storage_reads (read-only storage keys)
    List[BalanceChange],        # balance_changes ([block_access_index -> post_balance])
    List[NonceChange],          # nonce_changes ([block_access_index -> new_nonce])
    List[CodeChange]            # code_changes ([block_access_index -> new_code])
]

while an Account is serialized in the trie as:

def encode_account(​raw_account_data: Account, ​​storage_root: Bytes​) -> Bytes:
   """
   Encode `Account` dataclass.

   Storage is not stored in the `Account` dataclass, so `Accounts` cannot be

   encoded without providing a storage root.
   """

   return rlp.encode(
       (
           raw_account_data.nonce,
           raw_account_data.balance,
           storage_root,
           raw_account_data.code_hash,
       )
   )

If BALs were to be modified to also provide the storage root changes, of which just the last at the end of the block is needed, nodes would be able to construct account proofs without having to maintain a full state. EIP-8268 (thanks Toni for the ref!) proposes exactly this change.

3 Likes