Shared Validity Sequencing

Introduction

One future for Ethereum scaling is a world with thousands of rollups. Today, the dominant rollups are optimistic rollups, and most rollup-as-a-service companies are also building optimistic rollups.

There are two main issues with the design of optimistic rollups today:

• Rollups depend on centralized sequencers, which are a vector for soft censorship and centralization of MEV rents.
• There are no good solutions for atomic interoperability between optimistic rollups. Because of the 7-day challenge period in the optimistic rollup security model, an optimistic rollup cannot verify another’s state without waiting for the fraud proof window to pass. As a result, existing designs for cross-rollup bridging and interoperability (arbitrary message passing) are centralized and asynchronous in nature.

Shared, decentralized sequencer sets have been proposed as a way to decentralize the rollup sequencer role. But existing designs only perform transaction ordering, so they only solve the first problem and don’t solve atomic cross-rollup interoperability.

In this piece, we propose a shared sequencer architecture that enables atomic cross-rollup interoperability. Shared Validity Sequencing unlocks a unified layer of native assets that can serve an entire rollup ecosystem.

Background

Consider two optimistic rollups A and B. This design generalizes to $N$ rollups, but we describe the system with 2 for clarity.

In the current world, two sequencers for A and B independently commit to an ordering of transactions for the two rollups.

The goal is to enable atomic cross-chain actions between A and B. Specifically, a transaction $a_i$ on A should be able to be included and succeed (not revert) if and only if a corresponding transaction $b_j$ on B is included and succeeds.

The canonical example of using the above primitive is for burn and mint of a shared token between both rollups. A user bridging the shared token from rollup A to rollup B requires that the burn transaction on rollup A succeeds if and only if the mint transaction on rollup B succeeds. Otherwise, funds might get lost (e.g. if the burn succeeds but the mint doesn’t) or incorrectly minted (e.g. if the burn reverts due the user not having enough funds, but the mint still is included).

Note that without executing the transaction $a_i$, it is not possible to know whether the transaction will execute successfully or if its success requires cross-domain conditionals to be satisfied. It may be impossible to enable cross-rollup atomicity without some degree of execution at the sequencer level.

Existing shared sequencer designs don’t require the sequencer to execute transactions, so they only enable a weak form of interoperability via conditional inclusion. Atomic transaction inclusion provided by a non-executing shared sequencer does not enable atomic bridging of tokens, because token mint/burn invariants cannot be enforced with the same security of the underlying fraud proof mechanism. In general, atomic conditional transaction execution is a more expressive primitive than atomic transaction inclusion.

Shared Validity Sequencing

Here we describe Shared Validity Sequencing, a shared sequencer design that enables atomic cross-chain interoperability between optimistic rollups. The design has three key components:

• a method for the shared sequencer to accept cross-chain actions
• a block building algorithm for the shared sequencer to process these cross-chain actions, while respecting atomicity and conditional execution guarantees
• shared fraud proofs between the involved rollups to enforce the guarantees for these cross-chain actions

For simplicity, we outline a system that enables atomic burn and mint actions between two rollups: a burn on rollup A succeeds if and only if a corresponding mint on rollup B succeeds. Later, we generalize the system to arbitrary cross-rollup message passing.

Cross-Chain Actions with System Contracts

Rollups today have enshrined system contracts to implement specific rollup functionality, e.g. bidirectional message passing between L1 and L2, and other special precompiles. We propose adding a system contract that allows for other smart contracts to trigger cross-chain actions.

contract MintBurnSystemContract {
    uint256 burnNonce = 0;

    // Tree containing all `burn` actions
    MerkleTree burnTree;

    uint256 mintNonce = 0;

    // Tree containing all `mint` actions
    MerkleTree mintTree;

    // Any contract/EOA can call this function on Chain A, which will trigger the
    // sequencer calling `mint` on Chain B
    function burn(address sender, address token, uint256 amount) external {
        IERC20(token).transferFrom(sender, amount);

        // Notice msgHash only gets inserted into burnTree if the `transferFrom`
        // succeeds, otherwise the entire `burn` transaction will revert.
        bytes32 msgHash = keccak256(abi.encode(sender, token, amount, burnNonce++));
        burnTree.insert(msgHash);

        emit SystemContractBurn(sender, token, amount, burnNonce);
    }

    // Only the sequencer can call this function
    function mint(address sender, address token, uint256 amount) external onlySequencer {
        IERC20(token).mint(sender, amount);

        bytes32 msgHash = keccak256(abi.encode(sender, token, amount, mintNonce++));
        // Notice msgHash only gets inserted into mintTree if the `mint` succeeds,
        // otherwise the entire `mint` transaction will revert.
        mintTree.insert(msgHash);

        emit SystemContractMint(sender, token, amount, mintNonce);
    }
}

A copy of this contract lives on both rollups, and is used for atomic bridging of native tokens. On rollup A, burnTree contains all included burn actions. On rollup B, mintTree contains all included mint actions. The desired invariant is that burnTree on A is identical to mintTree on B, or equivalently that their Merkle roots are equal.

Block Building with Shared Validity Sequencing

Under this design, rollups A and B share a sequencer. This shared sequencer is responsible for posting transaction batches and claimed state roots to the L1 for both rollups. The shared sequencer can be a centralized sequencer, like rollup sequencers in production today, or the leader from a decentralized network of sequencers.

The only requirement we impose is that the shared sequencer must post transaction batches and claimed state roots for both rollups to the L1 in the same transaction. While different rollups can choose different methods for transaction ordering and block building, our modification to the block builder should be compatible with most ordering mechanisms.

The shared sequencer receives transactions and builds blocks for both A and B. For each transaction on A, the sequencer executes the transaction and checks if it interacts with the MintBurnSystemContract. If a transaction successfully executes and interacts with the burn function, the shared sequencer attempts to execute a corresponding mint transaction on B. If the mint transaction succeeds, the shared sequencer includes the burn on A and the mint on B; then, if the mint transaction fails, the shared sequencer excludes both transactions.

The above block building modification is a simple extension to existing block building algorithms. It only requires that the shared sequencer builds blocks for both rollups, and that the sequencer executes transactions and inserts conditionally triggered transactions from one rollup to another.

Shared Fraud Proofs

The most important part of an optimistic rollup is working, permissionless fraud proofs; this is how the rollup inherits security from the underlying L1 (today, Optimism has no fraud proofs and Arbitrum has whitelisted fraud proofs). We have described how the shared sequencer can conditionally include transactions on two chains it simultaneously sequences. Now we describe how conditional inclusion can be enforced with fraud proofs.

Fraud proofs are a mechanism on the L1 to ensure that the rollup sequencer is honestly processing transactions and updating the state. There is a simple and elegant way to extend existing fraud proof mechanisms to ensure that the sequencer is honestly processing cross-chain actions and including these conditional transactions properly.

The MintBurnSystemContract described above maintains a Merkle tree of all burn transactions on one rollup and their corresponding mint transactions on the other rollup. Entries only enter the Merkle tree if and only if the transaction succeeds. Thus, to ensure that all burn transactions on rollup A have a corresponding mint on rollup B, it suffices to check that the Merkle root of burnTree on A matches the Merkle root of mintTree on B.

Only a small change is required to the existing fraud proof mechanism for rollups A and B. If the root of the burnTree on A does not match the root of the mintTree on B, that is considered improper sequencing and the responsible sequencer can be penalized.

An alternate mechanism to enforce cross-chain atomicity guarantees is for the L1 smart contract that accepts rollup transaction batches to additionally require a Merkle proof that the root of the burnTree on A matches the root of the mintTree on B against the claimed state roots upon batch submission.

Generalizing Beyond Mint and Burn

We have outlined Shared Validity Sequencing with just mint and burn functions. But it is easily generalized to arbitrary message passing and conditional transaction execution between multiple rollups. A cross-rollup action can be invoked where the enforced invariant is that either all triggered contract calls succeed and are included, or that none of them succeed.

contract GeneralSystemContract {
    uint256 triggerNonce = 0;
    MerkleTree triggerTree;

    uint256 actionNonce = 0;
    MerkleTree actionTree;

    address crossChainSender = address(0);

    // Any contract/EOA can call this function on Chain A, which will trigger the
    // sequencer calling `action` on Chain B
    function trigger(address addr, bytes calldata_, uint256 gasLimit) external {
        bytes32 msgHash = keccak256(
            abi.encode(msg.sender, addr, calldata_, gasLimit, triggerNonce++)
        );
        triggerTree.insert(msgHash);

        emit SystemContractTrigger(msg.sender, addr, calldata_, gasLimit, triggerNonce);
    }

    // Only the sequencer can call this function
    function action(
        address sender,
        address addr,
        bytes calldata_,
        uint256 gasLimit
    ) external onlySequencer {
        crossChainSender = sender; // Set the crossChainSender
        (bool status, bytes data) = addr.call{gas:gasLimit}(calldata_);
        require(status == true); // Require call succeeded
        bytes32 msgHash = keccak256(
            abi.encode(sender, addr, calldata_, gasLimit, actionNonce++)
        );
        actionTree.insert(msgHash);

        emit SystemContractAction(sender, addr, calldata_, gasLimit, actionNonce);
        crossChainSender = address(0); // Reset the crossChainSender
    }

    // Allows triggered actions to get the original msg.sender on the source chain
    function messageSender() external returns(address) {
        require(crossChainSender != address(0));
        return crossChainSender;
    }
}

Properties of Shared Validity Sequencing

Comparisons with Monolithic Chains

A set of rollups supporting atomic cross-rollup transactions via Shared Validity Sequencing can be thought of logically as one large chain with multiple shards. There are benefits versus a monolithic rollup:

• Local fee markets for each individual rollup
• Pricing mechanisms for sets of locks: a cross-rollup action effectively acquires a lock over both chains
• Out-of-the-box sharding: one can choose to trust some shards and validate others
• Support for different execution environments, e.g. app chains with runtimes optimized for a specific use case

These are all differentiators against a monolithic rollup today. In comparison to a high-performance base layer like Solana, which supports parallel execution and a weak form of local fee markets, the biggest differentiators are native support for different execution environments and compatibility with the Ethereum roadmap. However, multiple rollups combining to make a single, sharded state machine under Shared Validity Sequencing is a coarse and inefficient implementation relative to a base layer designed to support parallelism from day 1. Throughput, fees, and time to finality will always be limited by Ethereum.

Sequencer and Node Demands

In contrast with shared sequencer designs that order transactions without executing them, Shared Validity Sequencing places more load on the shared sequencer. The shared sequencer needs to execute all transactions, both to access the current state and to determine whether they should trigger execution of other transactions. Note that execution across different rollups can still be sharded by default.

A full node operator for rollup A must also run a full node for rollup B, because the validity of A depends not only on valid state transitions for A but also on validity of the cross-rollup state (A + B). To verify the validity of A, the node operator must also verify the validity of cross-rollup state (A + B), which requires verifying the validity of B.

Sovereignty

This model couples the validity of rollups A and B, as the validity of their respective states now depend on each other. This is an opinionated decision made by the rollups to couple for composability. Their applications have more sovereignty than if they were deployed on a monolithic chain, but less than if they were app chains. We will explore the tradeoffs between these models in a future post.

Application to ZK Rollups

ZK rollups have asynchronous interoperability out-of-the-box, as they can directly verify each others’ ZK proofs. But there are still benefits to having atomic interoperability, including better UX and synchronous composability.

While this design for Shared Validity Sequencing is built for optimistic rollups, it can be modified slightly to work with ZK rollups. The MintBurnSystemContract and sequencer block building algorithm remain the same. The shared fraud proof is replaced by the proposed alternate mechanism, where the L1 smart contract that accepts batches of transactions and verifies a ZK proof of the rollup state transition now must also verify that the root of burnTree on rollup A matches the root of mintTree on rollup B.

With ZK rollups under this design, a full node operator for A does not need to run a full node for B. To verify the cross-rollup invariant, it can simply verify the state transition proof for B, and use a Merkle proof to get the MintBurnSystemContract state of B.

Conclusion

In this piece, we described Shared Validity Sequencing, a shared sequencer design which enables atomic interoperability between rollups. Under this design, the sequencer is responsible for executing transactions in addition to ordering them, allowing enforcement of cross-chain invariants while increasing load on sequencer and node operators. Rollups get atomic interoperability and its associated benefits (e.g. unified native asset layer) by opting into shared validity with other rollups. This system generalizes to multiple rollups, including ZK rollups.

Shared Validity Sequencing and its tradeoffs may make sense for some rollup ecosystems. To collaborate with us, please reach out to collaborators@umbraresearch.xyz.