Sequencing and Proving

Table of Contents

The following are the key actors in the rollup protocol:

  • Users submit rollup transactions, either through the rollup mempool or via L1-initiated transactions.
  • Sequencers receive transactions from the rollup mempool, build rollup preblocks, commit batches of preblocks to L1, and give users preconfirmations for blocks which have not yet been committed to L1.
  • Nodes run the chain derivation function to generate L2 block inputs from batches of preblocks and perform transaction execution to obtain complete L2 blocks.
  • Provers generate ZK proofs to finalize rollup states on L1.

Our goal is to enable each role to be permissionless, though sequencing and proving will start permissioned.

Rollup Bridge

Interactions between the rollup and L1 are mediated through the bridge contract, which:

  • Accepts batches of L2 preblocks from the sequencer, computes and stores preblock metadata, and provides data availability on L1.
  • Accepts L1-initiated transactions directly from users, which are included into batches after a delay of L1_INITIATION_DELAY L1 blocks.
  • Finalizes batches of L2 blocks by verifying ZK proofs of state transitions.

The bridge maintains the following state which is critical to sequencing and finalizing batches; we omit some additional data here for brevity.

  • bytes32 latestStateRoot -- The state root of the most recent finalized batch.
  • uint256 l1InitiatedNonce -- The nonce of the next L1-initiated transaction.
  • uint256 finalizedBatchesCount -- The number of batches that have been finalized.
  • uint256 pendingL1Batches -- The number of L1 batches that have not yet been included in a finalized batch.
  • uint32[] l1BatchInclusionBlock -- The value of l1BatchInclusionBlock[l1BatchIndex] is the L1 origin of the L1 batch with index l1BatchIndex.
  • mapping(uint256 l1BatchIndex => L1BatchData) l1BatchData -- Metadata for each L1 batch, indexed by l1BatchIndex, which is the count of the L1 batch. The L1BatchData struct contains:
    • bytes32 batchCommitment -- A commitment to the L1-initiated transactions in the batch, detailed below.
    • uint256 preblockCount -- The number of preblocks in the batch.
    • uint256 feeAccumulator -- The total fees collected from L1-initiated transactions until (and including) the batch.
  • uint256 sequencerBatchCount -- The number of sequencer batches committed to L1.
  • mapping(uint256 sequencerBatchIndex => SequencerBatchData) sequencerBatchData -- Metadata for each sequencer batch, indexed by sequencerBatchIndex, which is the count of the sequencer batch. The SequencerBatchData struct contains:
    • bytes32 batchCommitment -- A commitment to the preblocks in the batch, detailed below.
    • uint256 l1Origin -- The L1 origin of the batch.
    • uint256 prevL1BatchIndex -- The index of the most recent L1 batch prior to this batch.
  • uint256 committedBatchesCount -- The total number of batches (sequencer and L1) whose ordering has been committed to L1.
  • mapping(uint256 batchIndex => FinalizedBatchData) finalizedBatchData -- Metadata for each finalized batch.

Sequencing

Sequencers receive user transactions from the mempool and bundle them into preblocks. Preblocks will be submitted to L1 by the sequencer in batches, which are simply arrays of preblocks. The sequencer assigns each batch a non-decreasing L1 origin block, which is the L1 block number to which the batch is associated. The expected honest sequencer behavior is to select the L1 origin block for a batch based on its view of the latest L1 block as of the first preblock in the batch while enforcing the non-decreasing condition. However, the bridge will enforce the weaker condition that

block.number - MAX_L1_ORIGIN_DELAY <= l1Origin <= block.number
prevL1Origin <= l1Origin

to allow for delays in transaction inclusion and the sequencer's view of L1. Once a batch is built, the sequencer commits it to the bridge on L1. This can be done via:

EIP-4844 blobs via the function

function commitBatch4844(
  bytes32 sequencerKeystoreAddress,
  uint256 l1Origin,
  uint256 baseFeeScalar,
  uint256 blobBaseFeeScalar,
  bytes calldata blobDataProof
) external onlySequencer;

where the arguments are:

  • bytes32 sequencerKeystoreAddress -- The keystore address to send fees to.
  • uint256 l1Origin -- The L1 block number to which the batch is associated. This is used for ordering sequencer batches relative to L1-initiated transactions.
  • uint256 baseFeeScalar -- The base fee scalar for the batch.
  • uint256 blobBaseFeeScalar -- The blob base fee scalar for the batch.
  • bytes calldata blobDataProof -- The proof for the point evaluation precompile of the blob. This is used only to verify the BLS_MODULUS parameter to defensively protect against future L1 protocol changes.

Calldata via the function

function commitBatch(
  bytes32 sequencerKeystoreAddress,
  uint256 l1Origin,
  uint256 baseFeeScalar,
  uint256 blobBaseFeeScalar,
  bytes calldata preblocks
) external onlySequencer;

where the arguments are:

  • bytes32 sequencerKeystoreAddress -- The keystore address to send fees to.
  • uint256 l1Origin -- The L1 block number to which the batch is associated. This is used for ordering sequencer batches relative to L1-initiated transactions.
  • uint256 baseFeeScalar -- The base fee scalar for the batch.
  • uint256 blobBaseFeeScalar -- The blob base fee scalar for the batch.
  • bytes calldata preblocks -- A bytestream encoding the preblocks submitted in this batch according to the format defined in Calldata Format.

Special considerations the sequencer must take into account are:

  • L2 preblock timestamps are enforced by the state transition function to be non-decreasing and satisfy block.timestamp - MAX_SEQUENCER_DELAY <= l2Timestamp <= block.timestamp + MAX_SEQUENCER_DRIFT where block.timestamp is the time of L1 commitment.
  • L1 origin blocks are enforced by the state transition function to be non-decreasing and satisfy block.number - MAX_L1_ORIGIN_DELAY <= l1Origin <= block.number at the time of L1 commitment.
  • L1-initiated transactions submitted in L1 block B are defined by the state transition function to form the initial batch with L1 origin B + L1_INITIATION_DELAY. In particular, the sequencer does not need to resubmit these transactions in a batch.

The considerations above ensure that the relative ordering of sequencer and L1-initiated batches is uniquely determined by their L1 origins.

Upon sequencer batch commitment, the rollup bridge records the following metadata indexed by sequencer batch index, which is later used for verification of the state transition function.

  • bytes32 batchCommitment -- The commitment of the batch.
  • bytes32 l1Origin -- The L1 block origin passed in during commitment.
  • uint256 prevL1BatchIndex -- The L1 batch index of the prior L1-initiated batch in the chain derivation pipeline.

The commitment to the batch is defined by

// daBatchCommitment is defined below
bytes32 batchCommitment = keccak256(
    abi.encodePacked(
        parentSequencerBatchCommitment,
        sequencerBatchIndex,
        sequencerKeystoreAddress,
        l1Origin,
        l1Timestamp,
        baseFeeScalar,
        blobBaseFeeScalar,
        beaconBlockRoot,
        daBatchCommitment
    )
);

// for calldata batches
bytes32 daBatchCommitment = keccak256(abi.encodePacked(CALLDATA_BATCH, keccak256(preblocks)));

// for blob batches
bytes32 daBatchCommitment = keccak256(abi.encodePacked(BLOB_BATCH, blobVersionedHash));

where:

  • CALLDATA_BATCH is the byte 0x01.
  • BLOB_BATCH is the byte 0x02.
  • l1Origin is the L1 block origin passed in during commitment.
  • l1Timestamp is the block.timestamp of the block at which the batch was committed to L1.
  • baseFeeScalar is the base fee scalar for the batch.
  • blobBaseFeeScalar is the blob base fee scalar for the batch.
  • beaconBlockRoot is the most recent beacon block root as of the commitment block.
  • blobVersionedHash is the versioned hash of the blob, as described in the EIP-4844 specification. Blob data is expected to be encoded according to the Blob Data Format, although this is not enforced by the bridge.

We use a different format for daBatchCommitment for calldata batches and blob batches. For the first sequencer batch, as mentioned in Block Format, we define parentSequencerBatchCommitment to be

  • bytes32 INIT_SEQUENCER_BATCH_COMMITMENT = keccak256("AxiomInitSequencerBatchCommitment");

We include parentSequencerBatchCommitment in the hash preimage of batchCommitment so that each batch commitment commits to all previous batch commitments. This batch commitment data is stored in the bridge in the following data structure.

struct SequencerBatchData {
    bytes32 batchCommitment;
    uint256 l1Origin;
    uint256 prevL1BatchIndex;
}

Withdrawal and Deposit Transactions

There are special withdrawal and deposit transactions which connect the L1 and L2 states.

  • Withdrawals can be used by users on L2 to initiate a transaction on L1 and in particular to withdraw funds from the rollup to L1. Withdrawal transactions are ordinary transactions on L2 which update the withdrawal state, after which the bridge will enable a user to prove the existence of a withdrawal on L1, process the withdrawal on L1, and nullify the withdrawal to avoid withdrawal replays.
  • Deposits are used by users on L1 to deposit ETH into the rollup. These must be initiated by users on L1 (see the next section), and the rollup bridge enforces that any necessary asset deposits are made to the bridge prior to their initiation.

L1-Initiated Transactions

Users have the option to initiate a transaction from L1, which will place the transaction into a batch after a delay of L1_INITIATION_DELAY L1 blocks. All L1-initiated transactions are placed in their own preblocks.

Initiating Transactions on L1

Users can initiate a transaction on L1 by submitting it to the rollup bridge using initiateL1Transaction. For a deposit transaction, an additional check is performed to ensure that users have deposited the necessary funds. The bridge must constrain that at most MAX_PREBLOCKS_PER_BATCH L1-initiated transactions may be submitted in a single L1 block. These L1-initiated transactions are tracked in the bridge by their L1 transaction commitment, which is indexed by L1 batch index and defined by

bytes32 l1TxCommitment = keccak256(abi.encodePacked(prevL1TxCommitment, l1BatchIndex, l1InitiatedBatchOrigin, l1Timestamp, txHash));

where:

  • bytes32 prevL1TxCommitment is the previous L1 transaction commitment.
  • uint256 l1BatchIndex is the index of the L1 batch in which the transaction was initiated.
  • uint64 l1InitiatedBatchOrigin is the L1 origin of the corresponding L1 batch, given by block.number + L1_INITIATION_DELAY.
  • uint256 l1Timestamp is the L1 timestamp of the block in which the transaction was initiated.
  • bytes32 txHash is the hash of the transaction.

In the construction of the L2 transaction and computation of txHash, the bridge must track a sequentially increasing uint256 l1InitiatedNonce over all L1-initiated transactions. In addition, the transaction serialization must be defined so that the transaction hash can be computed by the bridge using msg.value, the value of l1InitiatedNonce, and a user-provided RLP-encoded portion of the transaction. As mentioned in Block Format, the first L1 batch commitment is set to INIT_L1_BATCH_COMMITMENT = keccak256("AxiomInitL1BatchCommitment");.

In addition to the transaction commitment, a global accumulator of the fees collected over all L1-initiated transactions is maintained. The data is stored in the bridge in the following data structure.

struct L1BatchData {
  bytes32 batchCommitment;
  uint256 preblockCount;
  uint256 feeAccumulator;
}

Benefits and Consequences of L1 Initiation

L1 initiation allows users to pay L1 fees to achieve some level of censorship resistance. The guarantee it provides is as follows:

  • After a delay of L1_INITIATION_DELAY L1 blocks, the sequencer can only censor a specific L1-initiated transaction if it stops committing new batches to L1.
  • After a delay of L1_INITIATION_DELAY + MAX_L1_ORIGIN_DELAY L1 blocks, a user's L1-initiated transaction is guaranteed to be included in a batch regardless of sequencer behavior. This results from the fact that an L1-initiated transaction in L1 block B forms the first batch with L1 origin B + L1_INITIATION_DELAY, and after block number B + L1_INITIATION_DELAY + MAX_L1_ORIGIN_DELAY, the smallest valid L1 origin for a sequencer committed batch is B + L1_INITIATION_DELAY + MAX_L1_ORIGIN_DELAY + 1.

The delay preserves the ability of sequencers to provide preconfirmations to users while ensuring that users have recourse in the event of sequencer censorship or downtime.

Proving

Provers verify the execution of the state transition function by generating a ZK proof and sending it onchain. The rollup bridge records a set of finalized batches and finalized rollup state roots. If the corresponding batch is the last batch to be finalized in a verification, the state root is stored in the bridge in the following data structure with non-zero stateRoot and withdrawalsRoot.

struct FinalizedBatchData {
    bytes32 stateRoot;
    bytes32 withdrawalsRoot;
    uint256 sequencerBatchIndex;
    uint256 l1BatchIndex;
}

Here the variables uint256 sequencerBatchIndex and uint256 l1BatchIndex are the sequencer and L1 batch indices associated with the most recently finalized batch as described in Batch Format.

The prover can finalize state roots from any finalized batch via the following function:

struct FinalizationArgs {
  uint256 parentFinalizedBatchIndex;
  uint256 targetSequencerBatchIndex;
  uint256 targetL1BatchIndex;
  bytes32 newStateRoot;
  bytes32 newWithdrawalsRoot;
  address rewardAddress;
  bytes proof;
}

function finalizeBatch(FinalizationArgs calldata args) external onlyProver;

where parameters are as follows:

  • uint256 parentFinalizedBatchIndex -- Batch index of a previously finalized batch that has a state root persisted to it. We allow any finalized batch instead of just the most recent to ensure that all proofs generated against a finalized batch remain valid even if more recent batches are finalized in the interim.
  • uint256 targetSequencerBatchIndex and uint256 targetL1BatchIndex -- Indices identifying the batch to finalize to, which may either be a sequencer batch or an L1-initiated batch. This batch must be more recent than the previously finalized batch with index parentFinalizedBatchIndex.
  • bytes32 newStateRoot -- The state root after applying the state transition function up to the batch identified by indices targetSequencerBatchIndex and targetL1BatchIndex.
  • bytes32 newWithdrawalsRoot -- The withdrawals root after applying the state transition function up to the batch identified by indices targetSequencerBatchIndex and targetL1BatchIndex.
  • address rewardAddress -- The address to which the prover reward is given. This is used as a public input into the proof, preventing front-runners from claiming the reward despite not generating a proof.
  • bytes proof -- Data comprising a ZK proof verifying the state transition function.

The bridge verifies that:

  • The batch with index parentFinalizedBatchIndex is finalized with state root oldStateRoot and withdrawals root oldWithdrawalsRoot.
  • The sequencer batch index targetSequencerBatchIndex and L1-initiated batch index targetL1BatchIndex correspond to a valid batch. This can happen in one of two ways:
    • Sequencer batch: This happens if targetL1BatchIndex is equal to the prevL1BatchIndex field corresponding to the sequencer batch at index targetSequencerBatchIndex.
    • L1-initiated batch: This happens if either:
      • The sequencer batch with index targetSequencerBatchIndex + 1 exists and has l1Origin at least l1InitiatedBatchOrigin, where l1InitiatedBatchOrigin is the L1 origin of the L1 batch with index targetL1BatchIndex.
      • There is no sequencer batch with index targetSequencerBatchIndex + 1 and block.number > l1InitiatedBatchOrigin + MAX_L1_ORIGIN_DELAY, which ensures that no future sequencer batches can have L1 origin less than l1InitiatedBatchOrigin.
  • Let (oldStateRoot, oldWithdrawalsRoot, parentL1BatchIndex, parentSequencerBatchIndex) be the FinalizedBatchData associated to the batch with index parentFinalizedBatchIndex. The data in proof is a valid ZK proof constraining that applying the state transition function yields (newStateRoot, newWithdrawalsRoot) from (oldStateRoot, oldWithdrawalsRoot) from:
    • Sequencer batches with index in (parentSequencerBatchIndex, targetSequencerBatchIndex]
    • L1-initiated batches with index in (parentL1BatchIndex, targetL1BatchIndex].

The verification must access the SequencerBatchData for the sequencer batch at index targetSequencerBatchIndex and the l1TxCommitment for the L1 batch at index targetL1BatchIndex. Note that it does not require accessing SequencerBatchData for prior batches because the batch commitments are accumulators and commit to prior batches.

Prover Fees

All L1 batches collect fees from users that are directed the prover. The fees are attributed to the prover in the bridge after an L1 batch is finalized. If a prover finalizes the L1 batches with index (parentL1BatchIndex, targetL1BatchIndex] and the most recently finalized L1 batch is latestFinalizedL1BatchIndex, the fees the prover earns are given by:

max(
    0,
    l1BatchData[targetL1BatchIndex].feeAccumulator - l1BatchData[latestFinalizedL1BatchIndex].feeAccumulator
);

Notably, while batches can be finalized multiple times, only the first prover to finalize a batch earns the fees for that batch.

Provers can claim their allocated fees at any time by calling claimProverFees().

Calldata Data Format

Encoding batches in calldata

We serialize a batch into calldata by embedding the following bytestream into calldata:

bytes batchEncoding = abi.encode(preblocks);

for a batch given by L2Preblock[] preblocks.

Blob Data Format

Embedding bytes into a blob

A blob consists of 4096 field elements in the scalar field of the BLS12-381 elliptic curve, which has modulus between 2^254 and 2^255. We embed up to 1024 * 127 bytes of data in the blob as follows:

  • Each field element must be at most 254-bit.
  • Each group of 4 field elements is interpreted as a 127 byte chunk via a decomposition into 4 groups of 254 bits in each field element.
  • The blob is interpreted as a sequence of 1024 chunks, each of which is 127 bytes.

To encode a bytestream into a blob, the first chunk is interpreted as the length of the bytestream, and the remaining chunks are interpreted as the bytestream itself.

Encoding batches in blobs

We serialize a batch into a blob by embedding the following bytestream into the blob:

bytes batchEncoding = abi.encode(preblocks);

for a batch given by L2Preblock[] preblocks.