State Transition Function

Table of Contents

The state transition function maps rollup states and new L1 blocks to new rollup states. This is done via the following stages:

  • Chain Derivation: Parse rollup data in L1 blocks into batches of L2 block inputs by:
    • Batch Derivation: Parse L1 blocks into serialized batches.
    • Preblock Derivation and Batch Validation: Deserialize batches and preblocks, perform state-independent validation, and discard invalid batches.
    • Block Input Derivation: Transform batches of valid preblocks into L2 block inputs.
  • Batch Execution:
    • Batch State-Dependent Validation: Validate (state-dependent) batches of L2 block inputs on successive L2 states and discard invalid batches.
    • Execution: Execute batches of L2 block inputs on successive L2 states to construct L2 blocks.

We describe each of these stages in detail below.

Chain Derivation

Once batches are posted to DA, they determine L2 block inputs via the chain derivation function, which is applied in the following stages.

Batch Derivation

Batch derivation first parses the L1 chain data into serialized batches of preblocks, which can come from two sources:

  • Sequencer batches, with DA on L1 either via calldata (commitBatch) or blobs (commitBatch4844).
  • L1-initiated batches, formed from L1-initiated transactions after a delay of L1_INITIATION_DELAY L1 blocks.

Batches are derived in order of L1 origin block. For L1 origin l1Origin:

  • If there are L1-initiated transactions in L1 block l1Origin - L1_INITIATION_DELAY, they form the first derived batch with L1 origin l1Origin. This batch consists of:
    • One preblock for each L1-initiated transaction in L1 block l1Origin - L1_INITIATION_DELAY, with each preblock containing a single L1-initiated transaction in order of appearance on L1.
    • sequencerKeystoreAddress set to L1_INITIATED_SEQUENCER_ADDRESS.
  • Further batches with L1 origin l1Origin are sequencer batches in the order they were committed to L1.

Note: When implementing the batch derivation, nodes should track uint256 nextL1Origin, the smallest possible value of the next L1 origin, which is incremented in the following two cases:

  • If a new sequencer batch is committed with a higher L1 origin, nextL1Origin should be set to the L1 origin of the new sequencer batch. In this case, the node should process L1 batches with L1 origin between the previous and new values of nextL1Origin.
  • If the L1 block number is block.number, nextL1Origin should be set to max(block.number - MAX_L1_ORIGIN_DELAY, nextL1Origin).

Example: If L1_INITIATION_DELAY = 10 and there are L1-initiated transactions T1 and T2 in blocks 10 and 15, respectively, and sequencer batches B1 and B2 with L1 origin 20 and 24, respectively, then the derived batches, in order, will be:

  • B(T1) with L1 origin 20
  • B1 with L1 origin 20
  • B2 with L1 origin 24
  • B(T2) with L1 origin 25

where B(T1) and B(T2) are batches with a single preblock derived from T1 and T2, respectively. Note that B(T1) occurs before B1 because L1-initiated transactions come before sequencer batches with the same L1 origin.

Preblock Derivation and Batch Validation

Preblock derivation transforms serialized batches into deserialized preblocks while performing state-independent batch validation checks, which are checks which do not depend on the rollup state. The metadata for preblocks derived from L1-initiated batches will have:

  • timestamp for each preblock set to max(lastTimestamp, block.timestamp + L1_INITIATION_DELAY * L1_SLOT_TIME), where lastTimestamp is the final timestamp of the last valid committed batch and block.timestamp is the timestamp of the L1 block in which the L1-initiated transaction was submitted on L1. The motivation for the shift is to estimate the timestamp of the L1 origin block corresponding to the L1-initiated transaction.

This ensures that timestamp satisfies the state-independent preblock validity checks on timestamp below.

We define validity for preblocks and batches as follows, paralleling the batch queue checks in the OP Stack derivation pipeline. We say that a preblock is state-independent valid if:

  • The preblock and all transactions in the preblock are validly serialized.
  • The timestamp for preblocks in sequencer batches satisfy l1Timestamp - MAX_SEQUENCER_DELAY <= timestamp <= l1Timestamp + MAX_SEQUENCER_DRIFT, where l1Timestamp is the L1 block timestamp at which the preblock was committed. This check is skipped for preblocks in L1-initiated batches.
  • All transactions in the preblock are state-independent valid.
  • There are at most MAX_TRANSACTIONS_PER_BLOCK transactions in the preblock.

We say that a batch is state-independent valid if:

  • If it is a sequencer batch, it is validly serialized according to the calldata or blob format. If it is an L1-initiated batch, this check is omitted.
  • The l1Origin of the batch satisfies prevL1Origin <= l1Origin, where prevL1Origin is the l1Origin of the previous valid batch.
  • There are at most MAX_PREBLOCKS_PER_BATCH preblocks in the batch.

Note that a batch can be state-independent valid even if some or all of its preblocks are state-independent invalid, so long as the serialization of the batch is valid. In particular, any L1 batch is always state-independent valid.

Block Input Derivation

Block input derivation transforms state-independent valid preblocks into L2 block inputs, which are all portions of the L2 block which do not depend on transaction execution. The L2BlockInput is not explicitly materialized in the rollup bridge, but it contains the following fields, which are all fields in L2Block excluding blockNumber, parentHash, stateRoot, and withdrawalsRoot:

struct L2BlockInput {
    uint256 timestamp;
    bytes32 transactionsRoot;
    bytes32 sequencerKeystoreAddress;
    Transaction[] transactions;
}

The L2BlockInput is derived from a batch of L2Preblocks by computing:

  • the transactionsRoot as the indexed Merkle tree root of all transactions in the preblock, and
  • the sequencerKeystoreAddress as the sequencer address committed in the batch for sequencer batches, and L1_INITIATED_SEQUENCER_ADDRESS for L1-initiated batches.

Applying the block input derivation function to a state-independent valid batch produces a set of L2 block inputs corresponding to the state-independent valid preblocks in the batch.

Batch Execution

Batch execution performs state-dependent validation and execution of batches. We say that a block input is state-dependent valid if:

  • All transactions in the block input are state-dependent valid.
  • The timestamp satisfies prevTimestamp <= timestamp, where prevTimestamp is the timestamp of the previous block input in the batch. If the block input is the first in the batch, prevTimestamp is the timestamp of the last valid L2 block.

and any state-independent valid batch is also state-dependent valid. State-dependent validation and execution of batches are tightly coupled. To be more precise, we use the following pseudocode to describe the batch execution in the form of a function named ExecuteBatch. Given a batch of block inputs batch, and rollup state state, ExecuteBatch(state, batch) is defined as:

ExecuteBatch(state, batch):
  newState = state
  for blockInput in batch:
    isValid, postState = ExecuteBlock(newState, blockInput)
    if isValid is true:
      newState = postState
  return newState

ExecuteBlockInput(state, blockInput):
  newState = state
  for tx in blockInput:
    isValid, newState = ExecuteTransaction(newState, tx)
    if isValid is false:
      // Block input is state dependent invalid.
      return (false, None)
  return (true, newState)

ExecuteTransaction(state, tx):
  if tx is not state dependent valid against state:
    return (false, None)
  newState = apply tx to state
  return (true, newState)

After execution, the L2 block is constructed with:

  • blockNumber set to be sequentially increasing from the previous block.
  • parentHash set to the hash of the previous block.
  • stateRoot set from the final state of newState.
  • withdrawalsRoot set from the final state of newState.