Axiom Keystore Specifications

Table of Contents

About the Axiom Keystore

The Axiom Keystore is a special-purpose ZK rollup which manages signing data for smart accounts across all other rollups. This gives users a single place to manage their keys and enables operations like key recovery and rotation to be done once and automatically applied for a user's smart accounts across all rollups. The design features:

  • Censorship resistance via L1 force inclusion
  • Fast finality via zkVM verification
  • Ability to specify key rotation policies in Rust
  • Adapters for L2s like OP Stack and ERC-6900/7579 modular smart accounts to integrate with the keystore

Guide to the Specifications

The specifications are divided into the following sections:

  • Rollup Protocol: Discusses the core rollup protocol, including sequencing and data availability, the state transition function, and finalization.
  • Keystore: Defines the transactions and state changes for the keystore.
  • AA Wallet Integration: Describes how the keystore integrates with smart account wallets on L2s.
  • Appendix: Describes data structures used in the keystore.

Rollup Protocol Overview

Table of Contents

This section of the specs describes the rollup protocol and bridge design, which facilitates communications and settles state between Ethereum Mainnet (L1) and the rollup. It does not discuss the particulars of keystore application logic, which are specified in Keystore.

Design Objectives

The rollup protocol design optimizes for the following objectives:

  1. Finality via ZK verification: To achieve objective finality, the rollup verifies the state transition function using ZK validity proofs.
  2. Censorship resistance via force inclusion: Users who are censored by a sequencer can pay more to force include their transactions on L1, with the guarantee that they will be included on L2 within a fixed timeframe.
  3. Minimize dependence on L1 implementation details: The protocol minimizes reliance on L1 implementation details such as the Merkle-Patricia-Trie (MPT) structure of the transaction and receipt tries.
  4. Minimize latency in the typical case: The protocol minimizes time-to-finality in the typical case of honest / live protocol participants, while maintaining soundness in the adversarial case. In particular, the L2 node and sequencer are designed to be resilient to L1 reorgs without waiting for L1 finality for L1-related operations.
  5. No single sequencer or prover assumption for soundness: The protocol is initially designed with a single sequencer and prover. However, in preparation for decentralizing these roles, no part of protocol soundness can rely on the assumption of a single sequencer or prover.

Architecture Overview

The rollup protocol specifies the following components, detailed in the sections below:

  • State, transactions, and blocks: These define the rollup state and its modification via blocks comprised of transactions. We also specify preblocks and batches, which are intermediate data structures used to construct inputs to the state transition function.
  • Rollup bridge, node, sequencer, and prover: The rollup node, sequencer, and prover interact with L1 via the rollup bridge, where the sequencer posts transaction batches, the node reads rollup data and applies the state transition function, and the prover verifies rollup execution in ZK.
  • State transition function: This derives the state of the rollup from L1 data alone. As new L1 data is available, the state transition function maps a rollup state and new L1 blocks to a new rollup state.
  • ZK verifier: This verifies ZK proofs that the state transition function is correctly applied to create new rollup states from previous states.

Rollup Data Structures

Table of Contents

Rollup State

We divide the rollup state into two components:

  • An ordinary read-write state, committed to via the state root, which is a bytes32 stateRoot representing the Merkle root of the underlying indexed Merkle tree.
  • A write-only withdrawals state, committed to via the withdrawals root, which is a bytes32 withdrawalsRoot representing the Merkle root of the underlying indexed Merkle tree.

These two Merkle roots will be separately updated on L1 upon L2 block finalization, and the rollup logic must guarantee that withdrawals are only ever appended to.

Initially, the state and withdrawals indexed merkle tree are empty with their height set to zero.

Transaction Serialization and Validity

We require that transactions are serialized in two different ways:

  • As raw bytes put in calldata or blobs for data availability.
  • In a Solidity struct for L1-initiated transactions.

Each transaction must also be associated with a transaction hash, which is required to commit to each of its fields.

We say that a serialized transaction is valid relative to a rollup state if it passes two types of validity checks:

  • State-independent validity: These checks enforce that the transaction is validly serialized and has the correct authentication. These checks should depend only on the transaction data and not on the rollup state. They are parallel to Geth's transaction validation pipeline.
  • State-dependent validity: These are checks on the transaction which depend on the rollup state prior to the transaction. They typically include nonce checks or authentication against key data in the rollup state.

These two pieces of the validity check will be run in different parts of the protocol.

Preblock Format

Transactions are sequenced and committed to L1 in preblocks, which contain transactions and the following sequencer-determined metadata fields:

  • uint256 timestamp - The sequencer-assigned timestamp of the preblock.

The sequencer will post preblocks in the following format. In particular, preblocks do not reference previous states.

struct L2Preblock {
    uint256 timestamp;
    Transaction[] transactions;
}

There may be at most MAX_TRANSACTIONS_PER_BLOCK transactions in a preblock.

Batch Format

Preblocks enter the chain derivation pipeline in batches, which are arrays of preblocks combined with metadata fields. Batches can be created in two ways:

  • Sequencer batches, which are created by the sequencer and posted to L1 via the bridge.
  • L1-initiated transactions, which are created by users on L1 and included into batches after a delay of L1_INITIATION_DELAY L1 blocks.

The two types of batches are indexed by the sequentially increasing indices uint256 sequencerBatchIndex and uint256 l1BatchIndex, respectively, which are tracked in the rollup bridge. Each batch B is associated with a sequencer batch and an L1-initiated batch as follows:

  • uint256 sequencerBatchIndex -- The sequencer batch index of the most recent sequencer batch up to B, possibly including B itself. If no such sequencer batch exists, this is 0.
  • uint256 l1BatchIndex -- The L1-initiated batch index of the most recent L1-initiated batch up to B, possibly including B itself. If no such L1-initiated batch exists, this is 0.

The global position of a batch in the set of all batches is given by uint256 batchIndex and is determined by batchIndex = sequencerBatchIndex + l1BatchIndex. The specifics of the batch format are detailed in Sequencing and L1-Initiated Transactions.

Block Format

A rollup block consists of an ordered list of rollup transactions together with the following block metadata fields:

  • uint256 blockNumber - The rollup block number, constrained to be sequentially increasing.
  • uint256 timestamp - The rollup timestamp, constrained to be non-decreasing and between block.timestamp - MAX_SEQUENCER_DELAY and block.timestamp + MAX_SEQUENCER_DRIFT by the state transition function.
  • bytes32 parentHash - The hash of the previous block.
  • bytes32 sequencerKeystoreAddress - The keystore address of the sequencer.
  • bytes32 stateRoot - The state root after execution of the block.
  • bytes32 withdrawalsRoot - The withdrawals root after execution of the block.
  • bytes32 transactionsRoot - The Merkle root of all transactions in the block, formatted to be the indexed Merkle tree root (with the Keccak hash) of the mapping with key-value pairs (idx, txHash[idx]) for idx = 0, ..., #transactions - 1. If the block contains no transactions, this is the root of an empty indexed Merkle tree (with height zero).

It is represented by the following Solidity struct.

struct L2Block {
    uint256 blockNumber;
    uint256 timestamp;
    bytes32 parentHash;
    bytes32 sequencerKeystoreAddress;
    bytes32 stateRoot;
    bytes32 withdrawalsRoot;
    bytes32 transactionsRoot;
    Transaction[] transactions;
}

Each block has a blockhash, defined by

bytes32 blockhash = keccak256(abi.encodePacked(blockNumber, timestamp, parentHash, sequencerKeystoreAddress, state
Root, withdrawalsRoot, transactionsRoot));

At genesis, we adopt special values for the state root, withdrawals root, blockhash, block number, and timestamp, given by:

  • bytes32 GENESIS_STATE = keccak256("AxiomGenesisStateRoot");
  • bytes32 GENESIS_WITHDRAWALS = keccak256("AxiomGenesisWithdrawalsRoot");
  • bytes32 GENESIS_BLOCKHASH = keccak256("AxiomGenesisBlockhash");
  • uint256 GENESIS_BLOCK_NUMBER = 0;
  • uint256 GENESIS_BLOCK_TIMESTAMP = 0;

We also use the following special values for the first l1 and sequencer batch commitments:

  • bytes32 INIT_L1_BATCH_COMMITMENT = keccak256("AxiomInitL1BatchCommitment");
  • bytes32 INIT_SEQUENCER_BATCH_COMMITMENT = keccak256("AxiomInitSequencerBatchCommitment");

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.

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 satisfies l1Timestamp - MAX_SEQUENCER_DELAY <= timestamp <= l1Timestamp + MAX_SEQUENCER_DRIFT, where l1Timestamp is the L1 block timestamp at which the preblock was committed.
  • 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.

ZK Verification of the State Transition Function

Table of Contents

ZK Verification Design

We verify the state transition function using a zkVM built using OpenVM. OpenVM enables on-chain verification of an implementation of the keystore state transition function written in Rust using additional intrinsics implemented as VM extensions in OpenVM.

The ZK verification proof has the following public inputs and outputs:

  • bytes32 oldStateRoot: The old state root before the state transition function is applied.
  • bytes32 oldWithdrawalsRoot: The old withdrawal root before the state transition function is applied.
  • uint256 oldSequencerBatchIndex: The index of the most recent sequencer batch included in oldStateRoot and oldWithdrawalsRoot.
  • uint256 oldL1BatchIndex: The index of the most recent L1 batch included in oldStateRoot and oldWithdrawalsRoot.
  • bytes32 targetSequencerBatchCommitment: The final sequencer batch commitment included in the updated L1 data being processed in the state transition function.
  • bytes32 targetL1BatchCommitment: The final L1 batch commitment included in the updated L1 data being processed in the state transition function.
  • bytes32 newStateRoot: The new state root after the state transition function is applied.
  • bytes32 newWithdrawalsRoot: The new withdrawal root after the state transition function is applied.
  • address rewardAddress: The address to which the prover reward is given.

The ZK verification proof verifies the following version of the state transition function:

Applying the state transition function to rollup data committed to in targetSequencerBatchCommitment and targetL1BatchCommitment and the rollup state committed to in oldStateRoot and oldWithdrawalRoot based on sequencer batches up to index oldSequencerBatchIndex and L1 batches up to index oldL1BatchIndex results in the rollup state committed to in newStateRoot and newWithdrawalRoot.

Reading L1 state

For certain operations within the state transition function, it is necessary to read variables from the L1 state, such as gas and blob fee data. While a sequencer can directly query an L1 node for this data for preconfirmations, verifying the STF in ZK requires a root of trust for the L1 state which commits to the desired data. We use the beacon block root as this root of trust, as it commits to all L1 state back to the Capella hard fork.

Open-Source Dependencies

The ZK verification of the state transition function is done using OpenVM, a performant and modular zkVM framework built for customization and extensibility. OpenVM is open-source and developed by contributors including Axiom, Scroll, and other individuals. It uses the following open-source dependencies:

  • Plonky3: A modular toolkit for building ZK proof systems. It was developed by Polygon Zero and has been audited.
  • halo2: A widely used elliptic curve based ZK proof system, which is deployed in production by teams including Axiom, Scroll, and Taiko. This also uses the following open-source libraries built on top of halo2:
    • halo2-lib: A core library for halo2 circuits developed by Axiom. This library is audited and used across the ZK ecosystem, including in production by Axiom and Scroll.
    • snark-verifier: A core library for proof aggregation in halo2 developed by Privacy & Scaling Explorations (PSE) and modified by Axiom. This library is audited and used across the ZK ecosystem, including in production by Axiom, Scroll, and Taiko.

Protocol Configuration Constants

Table of Contents

We use the following global constants about Ethereum:

  • uint256 L1_SLOT_TIME = 12 -- The number of seconds between L1 slots.

The protocol design depends on the following configuration constants.

  • uint256 MAX_SEQUENCER_DRIFT = 60 -- The maximum number of seconds the L2 timestamp may be ahead of the L1 timestamp upon sequencing.
  • uint256 MAX_SEQUENCER_DELAY = 86400 -- The maximum number of seconds the L2 timestamp may be behind the L1 timestamp upon committing a preblock to L1.
  • uint256 MAX_L1_ORIGIN_DELAY = 7200 -- The maximum number of L1 blocks the L1 origin may be behind the L1 block number upon sequencing.
  • uint256 L1_INITIATION_DELAY = 10 -- The number of L1 blocks after which L1-initiated transactions are force included in L2 blocks.
  • uint256 MAX_PREBLOCKS_PER_BATCH = 100 -- The maximum number of preblocks in a batch.
  • uint256 MAX_TRANSACTIONS_PER_BLOCK = 5 -- The maximum number of transactions in a rollup block.
  • bytes32 L1_INITIATED_SEQUENCER_ADDRESS -- The keystore address of the sequencer to send fees to for L1-initiated transactions.

Keystore Overview

Table of Contents

This section describes the state and transaction types of the keystore rollup.

Design Objectives

The keystore rollup is designed to manage the public signing data for users of smart accounts across different rollups. The design goals are the following.

  1. End users must be able to transact with a keystore account alone: Keystore account holders must be able to perform key recovery and update operations without any other type of Ethereum account, including an L1 EOA. This enables end users to have a complete experience using a keystore account alone.
  2. End users must be able to onboard without transacting on the keystore: We expect end users to onboard onto general-purpose rollups, and the keystore must allow them to do so without requiring a separate transaction on the keystore. This is achieved using counterfactual address derivation.
  3. No dependence on smart account implementations: The keystore must support different smart account implementations without any changes to the keystore protocol itself. This enables different wallet providers to innovate on smart account design without requiring frequent changes to the keystore itself.
  4. Minimized functionality: To minimize security surface area, the keystore should support the minimum possible functionality necessary to enable key rotation and update operations.

Keystore State and Addresses

Table of Contents

The keystore supports a read-write state, indexed by a new keystore address, and a write-only withdrawals state, indexed by withdrawal hash. We explain the address format and each state in this section.

Keystore Address Format

Addresses on the keystore are bytes32 values. They may be generated offchain using counterfactual initialization using the following parameters:

  • bytes32 salt - a salt to enable address uniqueness.
  • bytes initialData - the initial signing data associated with the address.
  • bytes initialVkey - the initial verification key for updates for the address.

The keystore address is then given by keystoreAddress = keccak256(salt, keccak256(initialData), keccak256(initialVkey)).

Keystore State

Keystore Read-Write State

The read-write state consists of the following mappings, which are indexed by keystore address. They are committed to using a siloed Indexed Merkle tree.

state: mapping(keystoreAddress: bytes32 => (dataHash: bytes32, vkeyHash: bytes32));
balances: mapping(keystoreAddress: bytes32 => balance: uint256);
nonces: mapping(keystoreAddress: bytes32 => nonce: uint256);

These mappings store the following data:

  • state[keystoreAddress] is defined to support counterfactual initialization, meaning:
    • If state[keystoreAddress] == (bytes32(0), bytes32(0)), then keystoreAddress has been counterfactually initialized, and if keystoreAddress == keccak256(salt, keccak256(initialData), keccak256(initialVkey)) for some salt, initialData, and initialVkey, then initialData and initialVkey are interpreted as the signing data and update verification key associated with keystoreAddress.
    • Otherwise, if state[keystoreAddress] = (dataHash, vkeyHash) for dataHash = keccak256(data) and vkeyHash = keccak256(vkey), then data and vkey are the signing data and update verification key associated with keystoreAddress.
  • balances[keystoreAddress] is the ETH balance in wei associated with keystoreAddress.
  • nonces[keystoreAddress] is the nonce associated with keystoreAddress, defined to be the number of transactions previously initiated from keystoreAddress.

To authenticate a (dataHash, vkeyHash) pair for a keystore account, we use the following data structure:

struct KeystoreAccount {
    bytes32 keystoreAddress;
    bytes32 salt;
    bytes32 dataHash;
    bytes vkey;
}

The authentication of KeystoreAccount against a keystore state is given by the following function:

function authenticateKeystoreAccount(KeystoreAccount acct) {
    if (state[acct.keystoreAddress] != (bytes32(0), bytes32(0))) {
        require(state[acct.keystoreAddress] == (acct.dataHash, keccak256(acct.vkey)));
        require(acct.salt == bytes32(0));
    } else {
        require(acct.keystoreAddress == keccak256(acct.salt, acct.dataHash, keccak256(acct.vkey)));
    }
}

Note: Although the keystore state contains dataHash and vkeyHash instead of data and vkey, the preimages of dataHash and vkeyHash will have appeared in rollup DA for accounts which have transacted on the keystore. Keystore nodes are expected to store these preimages and enable users to retrieve them via a JSON-RPC API.

Keystore Withdrawals State

The write-only withdrawals state is given by the following mapping, which is also committed to using a siloed Indexed Merkle tree:

withdrawals: mapping(withdrawalHash: bytes32 => withdrawal: Withdrawal);

for a Withdrawal represented by

struct Withdrawal {
    address to;
    uint256 amt;
}

and withdrawalHash = keccak256(abi.encodePacked(keystoreAddress, nonce)), where keystoreAddress is the keystore address of the user initiating the withdrawal and nonce is the nonce of the withdrawal transaction.

ZK Account Authentication

Table of Contents

We authenticate transactions using zero-knowledge proofs instead of the usual ECDSA signature scheme. This allows the keystore to support arbitrary smart account types without additional protocol changes.

ZK Proof Format

We specify the authentication of a message hash msgHash against data committed to by dataHash using a verification key vkey for a halo2 circuit. A proof validating against vkey will establish the following statement:

Assuming the authentication is against data committed to by dataHash, there is valid authentication data to approve the message in msgHash.

To implement this, we require the public inputs PI(pf) to be a vector of length 4 forming a byte subarray of pf, with each element being 32 bytes and representing a value in the 254-bit scalar field of the BN254 curve. This vector should encode the following values:

PI(pf)[0:2] – hi-lo representation of bytes32 dataHash
PI(pf)[2:4] – hi-lo representation of bytes32 msgHash

To be explicit, we relate PI(pf) to pf by PI(pf)[i] = pf[384 + 32 * i : 384 + 32 * i + 32], and we say that bytes32 values (a, b) form a hi-lo representation of a bytes32 value c if a and b are 16 bytes and c = (a << 128) || b, i.e. a contains the top 16 bytes of c, and b contains the lower 16 bytes of c.

Account Authentication

To verify a ZK account authentication for msgHash, we perform the following check:

function authenticateMsg(bytes32 dataHash, bytes32 msgHash, bytes proof, bytes vkey) {
    require(PI(proof)[0:2] == dataHash);
    require(PI(proof)[2:4] == msgHash);
    require(proof is valid against vkey);
}

Example: 1-of-1 ECDSA Multisig

As an example, each L1 EOA can be associated with a 1-of-1 ECDSA multisig on the keystore as follows.

1-of-1 ECDSA multisig
=====================
Key:
* keccak256(salt, keccak256(eoa_addr), keccak256(vk))

Public IO:
* PI[0:2] -- dataHash
* PI[2:4] -- msgHash

Circuit statement:
* `keccak256(eoa_addr) == dataHash`
* there is an ECDSA signature for `msgHash` which verifies against `pub_key`
* `eoa_addr` corresponds to `pub_key`

Keystore Transactions

Table of Contents

Transaction Type Overview

There are three transaction types for deposits, withdrawals, and user key data updates. They are represented by the following enum:

enum KeystoreTxType {
    DEPOSIT,
    WITHDRAW,
    UPDATE,
}

See Fee Schedule for details on how the transactions are priced.

EIP-712 and EIP-7730 Compatibility

To maximize compatibility with the existing Ethereum wallet ecosystem, we use EIP-712 for signing transaction message hashes, which will enable the most compatible wallet-level information display for vkeys using EOA signers. The relevant global constants are defined below.

bytes EIP712_REVISION = bytes('1');
bytes32 EIP712_DOMAIN =
    keccak256('EIP712Domain(string name,string version,uint256 chainId');
uint256 CHAIN_ID = 999999999;
bytes32 DOMAIN_SEPARATOR = keccak256(abi.encode(EIP712_DOMAIN, keccak256("AxiomKeystore"), keccak256(EIP712_REVISION), CHAIN_ID));

We also provide an EIP-7730 compliant descriptor for improved transparency into signing data (if supported by the wallet).

{
  "context": {
    "eip712": {
      "domain": {
        "name": "AxiomKeystore",
        "version": "1",
        "chainId": 999999999
      },
      "schemas": [
        {
          "primaryType": "Withdraw",
          "types": {
            "EIP712Domain": [
              { "name": "name", "type": "string" },
              { "name": "version", "type": "string" },
              { "name": "chainId", "type": "uint256" }
            ],
            "Withdraw": [
              { "name": "userKeystoreAddress", "type": "bytes32" },
              { "name": "nonce", "type": "uint256" },
              { "name": "feePerGas", "type": "bytes" },
              { "name": "to", "type": "address" },
              { "name": "amt", "type": "uint256" }
            ]
          }
        },
        {
          "primaryType": "Update",
          "types": {
            "EIP712Domain": [
              { "name": "name", "type": "string" },
              { "name": "version", "type": "string" },
              { "name": "chainId", "type": "uint256" }
            ],
            "Update": [
              { "name": "userKeystoreAddress", "type": "bytes32" },
              { "name": "nonce", "type": "uint256" },
              { "name": "feePerGas", "type": "bytes" },
              { "name": "newUserData", "type": "bytes" },
              { "name": "newUserVkey", "type": "bytes" }
            ]
          }
        },
        {
          "primaryType": "Sponsor",
          "types": {
            "EIP712Domain": [
              { "name": "name", "type": "string" },
              { "name": "version", "type": "string" },
              { "name": "chainId", "type": "uint256" }
            ],
            "Sponsor": [
              { "name": "sponsorKeystoreAddress", "type": "bytes32" },
              { "name": "userMsgHash", "type": "bytes32" },
              { "name": "userKeystoreAddress", "type": "bytes32" }
            ]
          }
        }
      ]
    }
  },
  "metadata": { "owner": "keystore.axiom.xyz" },
  "display": {
    "formats": {
      "Withdraw": {
        "intent": "Withdraw from Axiom Keystore",
        "fields": [
          {
            "path": "userKeystoreAddress",
            "label": "User Keystore Address",
            "format": "raw"
          },
          { "path": "nonce", "label": "Nonce", "format": "raw" },
          { "path": "feePerGas", "label": "Fee Per Gas", "format": "raw" },
          { "path": "to", "label": "To", "format": "raw" },
          { "path": "amt", "label": "Amount", "format": "raw" }
        ]
      },
      "Update": {
        "intent": "Update data or vkey at keystore address",
        "fields": [
          {
            "path": "userKeystoreAddress",
            "label": "User Keystore Address",
            "format": "raw"
          },
          { "path": "nonce", "label": "Nonce", "format": "raw" },
          { "path": "feePerGas", "label": "Fee Per Gas", "format": "raw" },
          { "path": "newUserData", "label": "New User Data", "format": "raw" },
          { "path": "newUserVkey", "label": "New User Vkey", "format": "raw" }
        ]
      },
      "Sponsor": {
        "intent": "Sponsor a transaction",
        "fields": [
          {
            "path": "sponsorKeystoreAddress",
            "label": "Sponsor Keystore Address",
            "format": "raw"
          },
          {
            "path": "userMsgHash",
            "label": "User Message Hash",
            "format": "raw"
          },
          {
            "path": "userKeystoreAddress",
            "label": "User Keystore Address",
            "format": "raw"
          }
        ]
      }
    }
  }
}

Deposits

Deposit transactions are always L1-initiated and take the following form:

struct DepositTransaction {
    uint256 l1InitiatedNonce;
    uint256 amt;
    bytes32 keystoreAddress;
}

Here the fields are given by:

  • uint256 l1InitiatedNonce: A unique, increasing counter of L1-initiated transactions on L1, which is expected to be tracked by the bridge.
  • uint256 amt: The amount of ETH in wei to deposit.
  • bytes32 keystoreAddress: The keystore address to deposit to.

We serialize the transaction and define the transaction hash by:

bytes transaction = abi.encodePacked(
    KeystoreTxType.DEPOSIT,
    l1InitiatedNonce,
    amt,
    keystoreAddress
);
bytes32 transactionHash = keccak256(transaction);

The deposit transaction has the following transaction logic:

function DEPOSIT(uint256 l1InitiatedNonce, uint256 amt, bytes32 keystoreAddress) {
    balances[keystoreAddress] += amt;
}

The state-independent validity condition is that:

The transaction is correctly encoded with valid fields.

There is no state-dependent validity condition.

Withdrawals

Withdrawal transactions take the following form:

struct WithdrawalTransaction {
    bool isL1Initiated;
    uint256 nonce;
    bytes feePerGas;
    bytes l1InitiatedNonce;
    address to;
    uint256 amt;
    KeystoreAccount userAcct;
    bytes userProof;
}

Here the fields are given by:

  • bool isL1Initiated: Whether the transaction is L1-initiated.
  • bytes l1InitiatedNonce: Represents the uint256 L1-initiated nonce for the transaction if the transaction is L1-initiated and the empty bytestring bytes(0x) otherwise.
  • uint256 nonce: The nonce for the transaction.
  • bytes feePerGas: Represents the uint256 fee per gas for the transaction if the transaction is not L1-initiated and the empty bytestring bytes(0x) otherwise.
  • address to: The L1 Ethereum address to withdraw to.
  • uint256 amt: The amount of ETH in wei to withdraw.
  • KeystoreAccount userAcct: The user account paying for the transaction.
  • bytes userProof: The user's ZK authentication proof for the transaction.

We serialize the transaction and define the transaction hash by:

bytes transaction = abi.encodePacked(
    KeystoreTxType.WITHDRAW,
    isL1Initiated,
    l1InitiatedNonce,
    rlp.encode([
        nonce,
        feePerGas,
        to,
        amt,
        userAcct.keystoreAddress,
        userAcct.salt,
        userAcct.dataHash,
        userAcct.vkey,
        userProof
    ])
);
bytes32 transactionHash = keccak256(transaction);

where rlp.encode represents the RLP encoding.

For EIP-712, we define the type hash by:

bytes32 WITHDRAW_TYPEHASH =
    keccak256('Withdraw(bytes32 userKeystoreAddress,uint256 nonce,bytes feePerGas,address to,uint256 amt)');

The withdrawal transaction implements the following functionality, which depends also on the following fields chosen by the sequencer as part of batch submission for sequencer batches and set to preset values for L1-initiated batches:

  • bytes32 sequencerKeystoreAddress: The keystore address to send fees to.
  • uint256 l1Origin: The L1 block number to which the batch is associated.
  • uint256 baseFeeScalar: The base fee scalar for the batch.
  • uint256 blobBaseFeeScalar: The blob base fee scalar for the batch.
function WITHDRAW(
    bool isL1Initiated,
    bytes l1InitiatedNonce,
    uint256 nonce,
    bytes feePerGas,
    address to,
    uint256 amt,
    KeystoreAccount userAcct,
    bytes userProof,
    bytes32 sequencerKeystoreAddress,
    uint256 l1Origin,
    uint256 baseFeeScalar,
    uint256 blobBaseFeeScalar
) {
    if (isL1Initiated) {
      feePerGas = bytes(0x);
      sequencerKeystoreAddress = L1_INITIATED_SEQUENCER_ADDRESS;
      require(l1InitiatedNonce != bytes(0x));
    } else {
      require(l1InitiatedNonce == bytes(0x));
      require(feePerGas != bytes(0x));
    }

    bytes32 userMsgHash = keccak256(
        abi.encodePacked(
            "\x19\x01",
            DOMAIN_SEPARATOR,
            keccak256(abi.encode(WITHDRAW_TYPEHASH, userAcct.keystoreAddress, nonce, feePerGas, to, amt))
        )
    );
    authenticateMsg(userAcct.dataHash, userMsgHash, userProof, userAcct.vkey);

    // state-dependent validity
    authenticateKeystoreAccount(userAcct);
    require(nonces[userAcct.keystoreAddress] == nonce);

    bytes memory transaction = abi.encodePacked(
      KeystoreTxType.WITHDRAW,
      isL1Initiated,
      l1InitiatedNonce,
      rlp.encode([
          nonce,
          feePerGas,
          to,
          amt,
          userAcct.keystoreAddress,
          userAcct.salt,
          userAcct.dataHash,
          userAcct.vkey,
          userProof
      ])
    );
    uint256 dataFee = getDataFee(transaction, l1Origin, baseFeeScalar, blobBaseFeeScalar, isL1Initiated);
    uint256 fees = uint256(feePerGas) * WITHDRAW_GAS + dataFee;
    require(balances[userAcct.keystoreAddress] >= amt + fees);

    // deduct fees and increment nonce
    nonces[userAcct.keystoreAddress] = nonce + 1;

    balances[userAcct.keystoreAddress] -= amt + fees;
    balances[sequencerKeystoreAddress] += fees;

    // update the state for a withdrawal
    withdrawals[keccak256(abi.encodePacked(userAcct.keystoreAddress, nonce))] = Withdrawal(to, amt);
}

The state-independent validity condition is that:

The transaction is correctly RLP encoded with valid fields and authenticateMsg(userAcct.dataHash, userMsgHash, userProof, userAcct.vkey) passes.

The state-dependent validity condition is that:

authenticateKeystoreAccount(userAcct), require(nonces[userAcct.keystoreAddress] == nonce), and require(balances[userAcct.keystoreAddress] >= amt + uint256(feePerGas) * WITHDRAW_GAS + dataFee) all pass.

Updates

The update transaction format is as follows.

struct UpdateTransaction {
    bool isL1Initiated;
    uint256 nonce;
    bytes feePerGas;
    bytes l1InitiatedNonce;
    bytes newUserData;
    bytes newUserVkey;
    KeystoreAccount userAcct;
    bytes userProof;
    bytes sponsorAcctBytes;
    bytes sponsorProof;
}

Here the fields are given by:

  • bool isL1Initiated: Whether the transaction is L1-initiated.
  • bytes l1InitiatedNonce: Represents the uint256 L1-initiated nonce for the transaction if the transaction is L1-initiated and the empty bytestring bytes(0x) otherwise.
  • uint256 nonce: The nonce for the transaction.
  • bytes feePerGas: Represents the uint256 fee per gas for the transaction if the transaction is not L1-initiated and the empty bytestring bytes(0x) otherwise.
  • bytes newUserData: The new user data to update to.
  • bytes newUserVkey: The new user vkey to update to.
  • KeystoreAccount userAcct: The user account paying for the transaction.
  • bytes userProof: The user's ZK authentication proof for the transaction.
  • bytes sponsorAcctBytes: Represents the RLP-encoded KeystoreAccount of the sponsor account sponsoring the transaction if the transaction is sponsored and the empty bytestring bytes(0x) otherwise.
  • bytes sponsorProof: Represents the sponsor's ZK authentication proof sponsoring the transaction if the transaction is sponsored and the empty bytestring bytes(0x) otherwise.

We serialize the transaction and define the transaction hash by:

bytes transaction = abi.encodePacked(
    KeystoreTxType.UPDATE,
    isL1Initiated,
    l1InitiatedNonce,
    rlp.encode([
        nonce,
        feePerGas,
        newUserData,
        newUserVkey,
        userAcct.keystoreAddress,
        userAcct.salt,
        userAcct.dataHash,
        userAcct.vkey,
        userProof,
        sponsorAcctBytes,
        sponsorProof
    ])
);
bytes32 transactionHash = keccak256(transaction);

where rlp.encode represents the RLP encoding. The update transaction implements the following functionality.

For EIP-712, we define both the type hash for the user signature and sponsor signature, separately:

bytes32 UPDATE_TYPEHASH =
    keccak256('Update(bytes32 userKeystoreAddress,uint256 nonce,bytes feePerGas,bytes newUserData,bytes newUserVkey)');

bytes32 SPONSOR_TYPEHASH =
    keccak256('Sponsor(bytes32 sponsorKeystoreAddress,bytes32 userMsgHash,bytes32 userKeystoreAddress)');

The update transaction implements the following functionality, which depends also on the following fields chosen by the sequencer as part of batch submission for sequencer batches and set to preset values for L1-initiated batches:

  • bytes32 sequencerKeystoreAddress: The keystore address to send fees to.
  • uint256 l1Origin: The L1 block number to which the batch is associated.
  • uint256 baseFeeScalar: The base fee scalar for the batch.
  • uint256 blobBaseFeeScalar: The blob base fee scalar for the batch.
function UPDATE(
    bool isL1Initiated,
    bytes l1InitiatedNonce,
    uint256 nonce,
    bytes feePerGas,
    bytes newUserData,
    bytes newUserVkey,
    KeystoreAccount userAcct,
    bytes userProof,
    bytes sponsorAcctBytes,
    bytes sponsorProof,
    bytes32 sequencerKeystoreAddress,
    uint256 l1Origin,
    uint256 baseFeeScalar,
    uint256 blobBaseFeeScalar
) {
    if (isL1Initiated) {
      feePerGas = bytes(0x);
      sequencerKeystoreAddress = L1_INITIATED_SEQUENCER_ADDRESS;
      require(l1InitiatedNonce != bytes(0x));
    } else {
      require(l1InitiatedNonce == bytes(0x));
      require(feePerGas != bytes(0x));
    }

    KeystoreAccount memory sponsorAcct;
    if (sponsorAcctBytes != bytes(0x)) {
        require(sponsorProof != bytes(0x));
        sponsorAcct = rlp.decode(sponsorAcctBytes);
    }

    bytes32 userMsgHash = keccak256(
        abi.encodePacked(
            "\x19\x01",
            DOMAIN_SEPARATOR,
            keccak256(abi.encode(
                UPDATE_TYPEHASH,
                userAcct.keystoreAddress,
                nonce,
                feePerGas,
                keccak256(newUserData),
                keccak256(newUserVkey)
            ))
        )
    );
    authenticateMsg(userAcct.dataHash, userMsgHash, userProof, userAcct.vkey);

    bytes32 payorAddress = sponsorAcctBytes != bytes(0x) ? sponsorAcct.keystoreAddress : userAcct.keystoreAddress;
    if (sponsorAcctBytes != bytes(0x)) {
        bytes32 sponsorMsgHash = keccak256(
            abi.encodePacked(
                "\x19\x01",
                DOMAIN_SEPARATOR,
                keccak256(abi.encode(SPONSOR_TYPEHASH, sponsorAcct.keystoreAddress, userMsgHash, userAcct.keystoreAddress))
            )
        );
        authenticateMsg(sponsorAcct.dataHash, sponsorMsgHash, sponsorProof, sponsorAcct.vkey);
    }

    // state-dependent validity
    authenticateKeystoreAccount(userAcct);
    require(nonces[userAcct.keystoreAddress] == nonce);

    if (sponsorAcctBytes != bytes(0x)) {
        authenticateKeystoreAccount(sponsorAcct);
    }

    bytes memory transaction = abi.encodePacked(
      KeystoreTxType.UPDATE,
      isL1Initiated,
      l1InitiatedNonce,
      rlp.encode([
          nonce,
          feePerGas,
          newUserData,
          newUserVkey,
          userAcct.keystoreAddress,
          userAcct.salt,
          userAcct.dataHash,
          userAcct.vkey,
          userProof,
          sponsorAcctBytes,
          sponsorProof
      ])
    );
    uint256 dataFee = getDataFee(transaction, l1Origin, baseFeeScalar, blobBaseFeeScalar, isL1Initiated);
    uint256 fees = uint256(feePerGas) * UPDATE_GAS + dataFee;
    require(balances[payorAddress] >= fees);

    // deduct fees and increment nonce
    nonces[userAcct.keystoreAddress] = nonce + 1;

    balances[payorAddress] -= fees;
    balances[sequencerKeystoreAddress] += fees;

    // update the state
    state[userAcct.keystoreAddress] = (keccak256(newUserData), keccak256(newUserVkey));
}

The state-independent validity condition is that:

The transaction is correctly RLP encoded with valid fields, authenticateMsg(userAcct.dataHash, userMsgHash, userProof, userAcct.vkey) passes, and authenticateMsg(sponsorAcct.dataHash, sponsorMsgHash, sponsorProof, sponsorAcct.vkey) passes if sponsorAcctBytes != bytes(0x).

The state-dependent validity condition is that:

authenticateKeystoreAccount(userAcct) passes, require(nonces[userAcct.keystoreAddress] == nonce) passes, authenticateKeystoreAccount(sponsorAcct) passes if sponsorAcctBytes != bytes(0x), and require(balances[sponsorAcctBytes != bytes(0x) ? sponsorAcct.keystoreAddress : userAcct.keystoreAddress] >= uint256(feePerGas) * UPDATE_GAS + dataFee) passes.

Signature Prover

Table of Contents

Role of the Signature Prover

Generating ZK proofs for transaction authentication is currently resource-intensive. As a result, to improve UX and transaction latency, we introduce a new entity into the system: the signature prover. This entity is expected to run robust, high-performance machines capable of generating ZK proofs efficiently to authenticate user transactions on the keystore.

Signature provers will receive, via JSON-RPC, an unauthenticated transaction payload along with a native form of authentication data (e.g. signatures), wrap the authentication data in a ZK proof, and return a fully serialized and authenticated transaction ready for submission to the sequencer.

Signature provers are free to define the interface for receiving the necessary input data for each of their supported circuits.

Relationship to Gas Sponsorship

Signature provers may chose to sponsor gas for users to eliminate the need for users to deposit onto the keystore to rotate their keys. In this case, the JSON-RPC API supports the generation of user signature proofs and sponsor proofs together, with the signature prover sending the resulting authenticated transaction directly to the sequencer.

However, sponsors may want to remain separate from signature prover if the ZK authentication requires private information or if the ZK authentication circuit is unknown to the sponsor. As a result, we do not mandate the unification of these roles at the protocol level.

Maintenance Overhead

When a signature prover is the sole provider for a particular keystore account type and associated ZK circuit, discontinuing support for that account type can pose a significant challenge for users. Specifically, if that signature prover stops generating proofs for a keystore account circuit, users relying on it for key rotations (or UPDATE transactions more generally) will need to generate ZK authentication proofs themselves, which can be a computationally demanding task.

To mitigate these risks, deprecations or transitions of circuit support should be carried out thoughtfully, with clear communication and supportive steps for users. Possible approaches include:

  • Graceful Deprecation Windows: Providing advance notice and overlapping support ensuring users have a suitable timeframe to adapt or migrate to a successor circuit.
  • Accessible Proving Resources: Make the pkey (proving key) and vkey (verification key) readily available, ideally along with a straightforward command-line or graphical tool. By hosting the necessary files in a public repository or download portal and offering a user-friendly binary for less technical users, signature provers can enable anyone to generate proofs locally after end-of-support without extensive technical expertise.

Putting such measures in place provides a safety net for users as keystore account types and circuits are phased out.

Fee Schedule

Table of Contents

Fee Schedule

The fee schedule is separated into fees for sequencer-included transactions and fees for L1-initiated transactions.

Sequencer-Included Transactions

The fee for transactions sent to the sequencer is comprised of two parts, an execution fee and a data fee. Fees from transactions sent to (and included by) the sequencer are funded from the L2 and collected by the sequencer. The execution fee is denominated in gas, which users bid on on a per unit basis. The gas cost by transaction type is listed below.

Transaction TypeGas Cost ConstantGas
KeystoreTxType.WITHDRAWWITHDRAW_GAS100_000
KeystoreTxType.UPDATEUPDATE_GAS100_000

The data fee is dynamically calculated using the following function:

function getDataFee(
    bytes memory transaction,
    uint256 l1Origin,
    uint256 l1BaseFeeScalar,
    uint256 l1BlobBaseFeeScalar,
    bool isL1Initiated
) returns (uint256) {
    if (isL1Initiated) return 0;

    return transaction.length *
      (16 * l1Origin.readL1BaseFee() * l1BaseFeeScalar
      + l1Origin.readL1BlobBaseFee() * l1BlobBaseFeeScalar)
      / 1e6;
}
  • transaction is the serialized transaction envelope specified in Keystore Transactions
  • l1Origin is the sequencer-assigned L1 origin of the batch in which the tx was executed.
    • The baseFee and blobBaseFee are the values from the L1 origin block. How this is enforced depends on the execution context.
      • For derivation purposes, the rollup node is expected to maintain an index of baseFee and blobBaseFee values on a per-block basis.
      • For ZK verification, these values are proven using SSZ Merkle proofs against the beaconBlockRoot.
  • l1BaseFeeScalar and l1BlobBaseFeeScalar are scalars applied to the L1 base fee and L1 blob base fee respectively
    • The scalar values allow the sequencer to adjust the proportion of DA costs allocated to calldata versus blobs.
    • Both values are interpreted as fixed-point decimals with 6 decimal places.

Estimation for data fees is also performed using the above function. Note that there may be divergence between actual fees charged and estimates based upon differences in L1 origin between the estimate and actual L1 inclusion of the batch.

Note that the data fee is charged automatically. Currently, it is not possible to limit the maximum data fee that a transaction is willing to pay.

L1-Initiated Transactions

The fee schedule for L1-initiated transactions is:

Transaction TypeGas Cost ConstantValue
KeystoreTxType.DEPOSITDEPOSIT_L1_COST0.001 ether
KeystoreTxType.WITHDRAWWITHDRAW_L1_COST0.005 ether
KeystoreTxType.UPDATEUPDATE_L1_COST0.005 ether

Transaction fees from L1-initiated transactions are paid on the bridge and directed towards the prover.

Unlike most rollups, depositing onto L2 is not free. This is a consequence of automatic inclusion imposing a workload on the prover. Under normal operations, the sequencer is responsible for paying the prover1. However, when the sequencer is bypassed via an L1-initiated transaction, that burden is shifted to the user.

These fees should not affect most users, since we expect users to primarily transact via native account abstraction. Deposits are primarily anticipated to be utilized by the actors powering native account abstraction (sponsors) whose operational designs generally revolve around the existence of a small cost for deposits to pay L1 gas fees in any case.

1

Currently, the sequencer and prover are both run by the same entity, and the protocol does not provide for provers to receive payments from the sequencer. However, the protocol is designed to enable such payments in the future.

Native Account Abstraction

All Update transactions can have fees either paid for by the user or sponsored by a sponsor account.

AA Wallet Integration

Table of Contents

As a complement to the keystore rollup itself, we built an adapter to integrate the identity data with ERC-4337 smart contract wallets on L2.

Design Overview

To authenticate ERC-4337 AA wallets via identity data from the keystore rollup, the validation phase of the 4337 lifecycle needs to read the keystore rollup state and use it to validate userOps. Since the keystore state root is committed to L1 storage, the read can be facilitated by two Merkle proofs:

  • Storage proof from keystore state root to L1 blockhash
  • Merkle proof from identity data to keystore state root

To integrate into modular smart accounts, we provide a ERC-6900 and ERC-7579 compatible validation module, which:

  • Verifies identity data read from the keystore against the claimed identity data in the userOp.
  • Checks the freshness of the identity data using the timestamp in which the keystore state root was accessed.

We provide a more detailed specification of the validation module here.

Keystore Validator Module

Table of Contents

The Keystore Validator (KV) is the core contract connecting rollups to the Axiom Keystore. It is a validation module for both ERC-6900 and ERC-7579 smart accounts which facilitates reading the keystore state and authenticating userOps against data from the reads. There are three primary actors interacting with the KV:

  • Keystore state syncers verify finalized keystore state roots at a certain L1 block timestamp in the module.
  • User smart accounts install the module, read the keystore state and use the data to authenticate userOps.
  • Consumer registrars deploy and add key data consumers to the module's consumer registry.

We give an overview of the details of each actor below.

Actors for the Keystore Validator

Keystore State Syncer

The exact role of the keystore state syncer (KSS) changes slightly depending on the L2. On L2s like OP Stack that support reading an L1 blockhash from L2, the module provides the interface below for verifying a keystore state root.

/// Caches
function cacheBlockhash() external;

function cacheKeystoreStateRoot(StorageProof calldata storageProof) external;

The KSS will cache an L1 blockhash in the module's storage, after which it can verify a keystore state root against the L1 blockhash with an L1 storage proof.

For L2s that do not enshrine L1 blockhash access, the module will expose the following alternative interface.

/// On L1 Broadcaster contract
function sendKeystoreStateRoot() external {
    bytes32 keystoreStateRoot = keystoreBridge.latestStateRoot();
    l2Bridge.sendCrossChainMessage(
        keystoreValidatorModule, abi.encodeCall(cacheKeystoreStateRoot, (keystoreStateRoot, block.timestamp))
    );
}

/// On L2
function cacheKeystoreStateRoot(bytes32 keystoreStateRoot, uint256 timestamp) external onlyBridge;

The KSS will initiate a bridge transaction from L1 to send the keystore state root to the module on L2.

User Smart Accounts

For smart accounts, the module supports both ERC-6900 and ERC-7579 validateUserOp(..) interfaces which call the same underlying logic.

/// ERC-6900
function validateUserOp(uint32, PackedUserOperation calldata userOp, bytes32 userOpHash) external;

/// ERC-7579
function validateUserOp(PackedUserOperation calldata userOp, bytes32 userOpHash) external;

Other forms of validation (such as ERC-6900's validateRuntime(..)) are not supported.

Consumer Registrars

As discussed in Key Data Consumers, the module uses a codehash to identify an external contract to outsource authentication against keyData to. For this to work, the contract must be deployed and registered in the module's consumer registry.

The consumer registrar facilitates deployment and registration of key data consumer contracts. It does this by exposing the following interface:

function deployAndRegisterKeyDataConsumer(bytes memory bytecode) external;

This will deploy the provided bytecode and register its creationCodehash in the module's consumer registry where creationCodehash = keccak256(bytecode) .

Key Data Consumers

Key data consumers are separate smart contracts that serve as external components of the KV, responsible for defining how keyData is processed and validated against. The keyData includes metadata that informs the KV which consumer contract to invoke for validation. Within the validation flow, once the KV has verified the authenticity of the keyData, it will forward the keyData to the consumer contract for further external use. The KV expects that keyData has the following format:

keyData[0] - domain separator (should be 0x00)
keyData[1..33] - key data consumer codehash
keyData[33..] - arbitrary key data

The codehash uniquely identifies the logic embedded within the consumer contract and effectively allows a certain keystoreAddress to signal how its keyData should be validated.

All key data consumer contracts must implement the following interface:

function consumeKeyData(bytes calldata keyData, bytes calldata authData, bytes32 userOpHash)
        external;

As an example, a key data consumer could implement signature verification logic. In this scenario:

  • keyData would be an encoding of a threshold and a list of valid signers
  • authData would be a list of signatures
  • userOpHash would be the digest signed by the signatures

Architecturally, separating the retrieval of the key data (in the keystore) from its actual use allows the former to be immutable while allowing for new forms of the latter to be introduced permissionlessly via external consumer contracts.

Immutability and Trust Assumptions of the Module

The module is deployed immutably on all supported L2s. However, Axiom will retain the ability to update the storage proof verification logic in the future to follow potential upgrades to the Ethereum L1 state trie. Unfortunately, because Ethereum L1 may change in future hard forks, there is no clear path at present to completely ossifying this module.

Appendix

This section contains supplementary material to support the main content in the following subsections:

  • Indexed Merkle Tree: A detailed explanation of the Indexed Merkle Tree data structure used in the keystore.

Indexed Merkle Tree

Table of Contents

The Indexed Merkle Tree (IMT), detailed in this paper, is a committed data structure that modifies the standard Merkle tree data structure to represent a key-value mapping with efficient exclusion proofs. It achieves this by adding additional metadata to each leaf node to enable exclusion proofs via standard Merkle proofs into the IMT. We will use IMTs to commit to a mapping between 32-byte keys and variable length values.

Structure of the IMT

An IMT is a binary Merkle tree over two types of nodes:

  • Leaf Nodes: These represent leaves of the tree and contain key-value pairs as well as additional metadata which enables efficient exclusion proofs.
  • Inner Nodes: These are internal nodes of the tree and consist of the hashes of the two child nodes as usual.

The number of leaf nodes in the tree is known as the capacity, which is initialized at 1 and can be dynamically increased upon insertion. A capacity 2 ** C IMT contains 2 ** C leaf nodes, which are either considered active, meaning they represent a key-value pair, or inactive, meaning they are free to be used for future insertions.

IMT Leaf Node

Leaf nodes of an IMT are serialized as fixed length 99-byte arrays with the following layout:

[active (1 byte), prefix (1 byte), key (32 bytes), next_prefix (1 byte), next_key (32 bytes), value_hash (32 bytes)]

where the fields are as follows:

  • active - A boolean flag indicating whether the leaf node holds an active tuple. If active == true, then key and value are the stored key-value tuple at this leaf node, and next_key is the next largest key in the key-value mapping. Otherwise, if active == false, then the leaf node must be the zero byte array [0u8; 99].
  • prefix - A boolean flag indicating whether the key is a dummy key. It is 1 if key is not a dummy key, and 0 otherwise, in which case key must equal [0u8; 32].
  • key - The key associated with this leaf node.
  • next_prefix - A boolean flag indicating whether the next_key is a dummy key. It is 1 if next_key is not a dummy key, and 0 otherwise, in which case next_key must equal [0u8; 32].
  • next_key - The next key in the IMT that is larger than this key.
  • value_hash - The keccak256 hash of the value associated with the key.

The hash of a leaf node is computed as keccak256(abi.encodePacked(active, prefix, key, next_prefix, next_key, value_hash)). We use DUMMY to represent the 33-byte dummy prefix and key [0u8; 33].

The adjacent keys key and next_key must satisfy the IMT invariant that one of the following must be true:

  • The leaf node is inactive, i.e. active == false.
  • Both prefix == 1 and next_prefix == 1, in which case key < next_key and there are no active nodes with key < node_key < next_key.
  • We have prefix == 1 and next_prefix == 0, in which case there are no active nodes with key < node_key.
  • We have prefix == 0 and next_prefix == 1, in which case there are no active nodes with node_key < next_key.
  • We have prefix == 0 and next_prefix == 0, in which case key and next_key must be [0u8; 32].

Every IMT will have at least one active leaf node.

IMT Inner Node

Inner nodes of an IMT are serialized as fixed length 64-byte arrays with the following layout:

[left_hash (32 bytes), right_hash (32 bytes)]

where left_hash and right_hash are the hashes of the left and right children of the inner node, respectively. The hash of an inner node is computed as keccak256(abi.encodePacked(left_hash, right_hash)).

Operations on the IMT

Initialization

An empty IMT is initialized with capacity 1 and a single dummy leaf node given by [true, DUMMY, DUMMY, keccak256([])]. The root hash of the empty IMT is the hash of this dummy leaf.

Value Update

To update the value associated with an existing key, we simply update the value_hash field of the corresponding leaf node.

Key-Value Insertion

Insertion of a new key-value pair [new_key, new_value] into an IMT with capacity 2 ** C involves the following steps:

  1. If all leaves are active, the tree's capacity is doubled to 2 ** (C + 1) by appending 2 ** C inactive leaf nodes to the tree and updating the root hash by hashing the existing root hash with a root hash of 2 ** C inactive leaf nodes.
  2. Find an active leaf node with prefix, key, next_prefix, next_key such that one of the following holds:
  • prefix == 1 and next_prefix == 1 and key < new_key < next_key
  • prefix == 1 and next_prefix == 0 and key < new_key
  • prefix == 0 and next_prefix == 1 and new_key < next_key
  • prefix == 0 and next_prefix == 0
  1. For the leaf node found in Step 2, update next_key to new_key and next_prefix to 1.
  2. Replace the inactive leaf node with the active leaf node [true, new_key, next_key, keccak256(new_value)] and update the IMT root hash accordingly.

This procedure maintains the IMT invariant. To verify the insertion is valid, a prover must provide:

  • If all leaves of the tree were active in Step 1, a proof of the root hash update for capacity doubling.
  • An exclusion proof for new_key by proving inclusion of the leaf node found in Step 2.
  • Merkle proofs to verify the update to the leaf nodes in Steps 3 and 4.

Inclusion and Exclusion Proofs

Inclusion proofs for a key-value pair [key, value] are given by standard Merkle proofs. A special feature of the IMT is the ability to cheaply provide an exclusion proof that a key target_key is not present. This is done by proving inclusion of an active leaf node with prefix, key, next_prefix, next_key satisfying one of the following conditions:

  • prefix == 1 and next_prefix == 1 and key < target_key < next_key
  • prefix == 1 and next_prefix == 0 and key < target_key
  • prefix == 0 and next_prefix == 1 and target_key < next_key
  • prefix == 0 and next_prefix == 0

By the IMT invariant, if such a leaf node exists in the IMT, then target_key is not present in key-value mapping.

Key Siloing

To commit to multiple key-value mappings in a single IMT, we silo keys by replacing them with their prefixed hashes with 2 siloing bytes, meaning that we store the key-value tuple [original_key, original_value] at the siloed key

key = keccak256(concat([silo_bytes, original_key]))

where silo_bytes is a 2-byte array indicating the siloing namespace for the key-value mapping.