The Complete Guide to Rollup Sorters: Concepts, Status, and Shared Sorting

Author: James Prestwich

Original compilation: 0x11, Foresight News

The Shared Sequencer is evolving by leaps and bounds, and it's time for an in-depth analysis of what it is and why it exists. The object of analysis in this article is limited to Optimistic Rollup, and ZK followers are welcome to come and give advice.

What is a sorter?

The sequencer is a semi-trusted role in Optimistic Rollup. Although transactions can be sorted by the main chain itself, this is not economical, and users must separately submit the main chain transactions corresponding to their Rollup transactions and pay the fees on the main chain. The orderer solves these problems for users by allowing Rollup transactions to share a single mainchain transaction.

The sorter aggregates multiple user transactions off-chain to supplement the sorting of the main chain, and submits them to the main chain as a single transaction collection, and the transaction costs are shared among users. The sorter can also compress transaction collections, further saving main chain data availability costs. Users who order autonomously will pay more for transactions included in a Rollup than users who rely on the orderer.

However, the sorter can control the ordering of transactions in the transaction collection. It can choose not to include user transactions, thereby forcing users to sort themselves and pay higher main chain costs. It can also extract MEV in transaction collections by means of reordering and insertion extraction. They actually have priority write access to the Rollup. It is worth noting that because the orderer can interact with the contract, only absolutely reliable transactions can be reliably enforced by the on-chain mechanism, and unreliable transactions are likely to fail when forced to order.

This makes the collator a semi-trusted party for Rollup users. While orderers cannot prevent users from accessing Rollups, they can delay users' access, cause users to incur additional fees, and extract value from users' transactions. Further constraining the behavior of the sorter through decentralization is an activeresearch topic。

What is the difference between sort and execute?

The sorter is a supplement to the main chain sorting, it does not calculate the state of the Rollup, in fact it may choose to sort invalid transactions. A Rollup node must parse and clean the sort data, export a valid history for the Rollup, and execute the history to produce the latest state. The sequencer is completely out of this process.

However, as my friendFredAs I'm constantly reminded, once the transactions are sequenced, the outcome is deterministic. This means that all Rollup nodes will agree on the result in the order generated by the sorter. Rollup has a correct state given the known history. Once a node finds this state, one or more proposers submit it to the main chain's Rollup contract.

In theory, any node can be a proposer, no permissions required. The proposer commits the state to the main chain along with the bond. If the fraud proof turns out to be an invalid state, the security deposit will be forfeited. The contract accepts the proof after the timer expires, and the user transactions contained within it are then executed on the main chain. The execution node ensures the honesty of the proposer through the fraud game, and we tend to refer to the execution node as "Rollup full node" or "validator".

In other words, once the ordering is committed to the main chain, the state becomes final and immutable. The proposer calculates and reports the final state to the Rollup contract to maintain the interests of the asset bridge from Rollup to the main chain. Proposers don't create state, they just compute and prove it. The Rollup contract does not create or finalize Rollups, it just gets the Rollup state from the proposer.

Why separate ordering and proposals?

This is a complex issue. Fundamentally, they are separated because they are separate themselves. This may sound like a tautology, but it seems like it took a long time for everyone to realize it. We look back and see that the history of Rollup's ideas has meandered over the years in Plasma and state channels. In the early days of Bitcoin-based proto-Rollup, there was no orderer, and users simply posted their transactions to the main chain. Afterwards, this design disappeared for many years, eventually becauseBarrywork reappears. Between Barry and Celestia, Rollup's research focused on the interaction of the Rollup bridge with the main chain. Before the Sovereign Rollup, no one even realized that we were actually building a better Mastercoin.

Provenance aside, sequencers solve a specific problem: minimizing transaction costs for users. However, this process introduces a new problem: the sorter can produce multiple sorting results for the same transaction at the same time. If sorting is done entirely by the main chain, there will be a single canonical sort, but user transaction fees will be more expensive. We chose to use a sorter to improve the user experience in Rollup.

Assume that there are many orderers because there are multiple proposers. Sorters can submit conflicting orderings, and we now need a mechanism to "canonicalize" specific sorted batches on the main chain. Current Rollups do this through a single, specific, known, semi-trusted orderer. Choosing a single sorter allows us to solve this problem until the arrival of decentralized sorters. Since we want multiple proposers but only one orderer, these two roles must be separated.

Data dependencies are another important reason: proposers need ordering, but orderers don't need state. The proposer depends on the output of the orderer's work, but the orderer does not depend on the proposer. Because data dependencies are one-way, boundaries need to be drawn between roles and actors allowed to focus on a single role.

To answer the original question, we separate proposers and orderers because they are separate themselves. Proposers work downstream of the orderer. Rollup grants trust and authority to the orderer, while the proposer is just an ordinary worker.

State of Orderers, Proposers, and Validators

Arbitrum and Optimism are two common ORU schemes. I want to briefly introduce the main roles among them, no code will be involved, just the specification and documentation. Discussion of Optimism will be limited to the (not yet deployed) Bedrock design.

Arbitrum

In addition to batching and compressing user transactions, the Arbitrum collator also runs a full node. Transactions are sent directly to the orderer, which creates a trusted WebSocket feed when transactions are ordered. Arbitrum uses this feed as a source of "soft" confirmation. The sorter makes a promise about the sorting result, and users can generally rely on that sorting. Nodes, MEV Seekers, or other actors can use this feed to precompute the Rollup state.

The sorter periodically publishes sorted compressed transactions to the main chain. Finalization of the main chain represents the "hard" confirmation of the Rollup. Once the ordering is established on the main chain, it becomes an immutable part of the Arbitrum chain, where all transactions in the ordering become final and the resulting state becomes final.

Naturally, since the sequencer sets the order of transactions, it has priority write access. A sorter can control what is sorted, and thus the ordering of transactions in the Rollup history. Of course, users can use thedelayed inboxMandatory inclusion of transactions. Seekers have gone to great lengths to minimize the latency of their WebSocket transaction feeds, so they will likely form a robust MEV marketplace to sort Arbitrum transactions.

There are 13 approved Arbitrum proposers, each of whom isRBlockETH is escrowed in a specific commitment of . Users can choose to rely on a percentage of their stake to make final decisions about Rollups without running a Rollup full node. While Arbtirum validators can identify fraud, only proposers can challenge the validity of commitments through fraud proofs. In fact, only proposers can become full validators.

Justice, like a sequencer, is blind, it must carry a sword

Optimism

Like Arbitrum, the Optimism collator runs a full node in addition to batching and compressing user transactions. Transactions are sent directly to the orderer, which creates trusted pre-confirmations when ordering. Optimism users can use these confirmations as a source of final soft confirmations. A sorter makes a promise about an ordering, and users can generally rely on that ordering. Nodes, MEV Seekers, or other actors can use these confirmations to precompute the Rollup state.

The sorter periodically publishes sorted compressed transactions to the main chain. Finalization of the main chain represents the "hard" confirmation of the Rollup. Once the main chain has established a sequence, it becomes an unalterable part of the history of the Optimism chain. All transactions sorted in it become the final state, and the resulting state also becomes the final state.

Naturally, since the sequencer sets the transaction order, it has write access first. A sorter can control what is sorted, and thus the ordering of transactions in the Rollup history. Of course, users can force transactions to be included in the main chain. As the originator of the MEV auction concept, it seems likely that a robust MEV marketplace for ordering Optimism transactions will be formed.

Optimism has 1licensed proposer. This proposer signs a specific commitment to the main chain, called a "state output" or "L2 output root". Users can choose to rely on proposers when making final decisions about Rollups without running a Rollup full node. While Optimism validators can identify fraud, only a permissioned challenger can challenge the validity of a commitment by signing. A challenger can delete an L2 output root at any time without fraud proofs. In fact, only permissioned challengers can become full validators.

summary

With the current two major Rollups focusing on the same design, it can get very confusing. They often use different names for the same concept, but their designs are pretty much the same.

shared sorter

With a new understanding of sorters, let's move on to what I really want to talk about: shared sorters. What happens when Rollups share the same sorter?

What do the different Rollups mean?

borrowBen's definition, we should think of Rollup as a state, a state transition function, and a proof system. A Rollup has contracts and accounts, and it has a virtual machine to process transactions to update those contracts and accounts, while a non-sovereign Rollup has a proof system to run a bridge to the main chain. Each component comes in multiple designs, and they can be mixed and matched to some degree.

However, some components are more equal than others. Overall, we should probably think of state as the essence of chains. Chains do not tend to change their state. After all, Ethereum developers changed the virtual machine many times, changed the consensus mechanism many times, but only changed the state once. The state is the Rollup, and the virtual machine and proof system exist to support it. Therefore, different Rollups have different states. They may share a proof system or an STF, but two Rollups can never share the same state.

Extract, inspect and filter

Rollups get their state from the main chain history. In order to do this, each Rollup must define a "fetch" function. The extraction function divides the main chain history into Rollup history and non-Rollup history. STF processes Rollup history to create Rollup states. In effect, the fetch function becomes a "lens" through which Rollup checks the main chain.

Rollup enables the sorter to choose to extract the output of the next run of the function. The sorter selects the data that the Rollup node will see and process next, so it has some control over the operation and next state of the STF.

After the sorter creates a view of the main chain data, the Rollup node runs the filtering function. Because a sorter does not necessarily know the state of the Rollup it serves, it is allowed to include invalid transactions in its sorting. After extraction, Rollup nodes see these invalid transactions and delete them. When given an invalid transaction, Rollup nodes do not error out (like the main chain does), but simply ignore it and continue. L1 must suppress spam to maintain consensus, while Rollup does not.

shared sorter

A shared sorter provides input to the extract functions of two or more Rollups. Therefore, it sets new history records for both, controlling the input of STF. It can do this for each Rollup individually, or for both. When history is set individually, it works exactly like the unshared sorter.

However, when creating new histories for two Rollups at the same time, the Shared Sequencer can exercise some additional power by atomically "linking" the histories of the two Rollups. The sequencer generates sequences for each Rollup simultaneously, and ensures that both are acknowledged or neither are acknowledged. This allows the orderer to exercise control over the history of both chains, and thus have some degree of control over the next state of the Rollup.

Atomic inclusion (not atomic execution)

At this point, I must reiterate that a sorter can exercise a great deal of discretion in the sorts it produces. This means that while users can use a shared orderer to transact on multiple Rollups without interacting with the main chain, they do not necessarily rely on the orderer to generate any specific relationship between those transactions. Proponents of shared sorters envision a new structure in which users can specify the atomicity of containment, that is, the sorter can be forced to sort a set of transactions in multiple Rollups at the same time through the shared forced ordering mechanism. This will allow users to ensure that all of these atomic transactions are included in the Rollup history, or none at all.

It's not as good as it looks. Because only infallible transactions can enforce ordering, only infallible transaction sets are guaranteed to execute atomically when atomically included. As we said before, containment and execution are separate. Rollup filters out invalid transactions through a filter function after inclusion and before execution. Suppose the orderer fetches the user's atomic set and causes a transaction to fail or invalidate. The transaction will be filtered after sorting and will not be executed. This means that atomic inclusion is not sufficient to guarantee atomic execution unless all transactions involved are infallible.

Specifically, simple sends and withdrawals can be performed atomically, but anything error-prone, like swaps or DeFi interactions, cannot. Unfortunately, most high-value interactions consist of 1 or more error-prone transactions, so it seems difficult to make atomic inclusion work. This effectively rules out DeFi composability for cross-Rollups via shared sequencers. Shared orderers are not a panacea, users' assets may be locked in an asynchronous cross-chain model until the end of the process.

Atomic Execution of Rollup Composition

Remember how we talked about how the orderer provides trusted execution guarantees before publishing the order to the main chain? You can imagine a shared sequencer doing the same for multiple Rollup systems. A shared orderer can run full nodes for each Rollup and use them to determine whether a transaction was successful or not. It can then promise that it will not produce an ordering of atomic transaction sets that do not all succeed.

Of course, this system is trustworthy. You'd trust the sorter not to lie. You're probably thinking by now "can we turn this into a trustless system by restricting the behavior of the sequencer?" I'm happy/sad/confused to say the answer is "yes, but". Yes, but the way we do it is by combining the STFs of each Rollup to create a single STF that executes all combined Rollup transactions. That is, we must make all virtual machines atomic between all Rollups. This is equivalent to making them the same Rollup. So yes, we can achieve untrusted atomic execution by combining multiple Rollups into one. This might be a good idea1, but I doubt its feasibility.

Atomic execution of contingent relations

I've written about this elsewhere, and another solid option is to integrate explicit contingent relationships between transactions and Rollup state. This shifts the burden of evaluating contingencies onto proposers, since they must compute and propose state roots based on their trust in remote rollups. However, I think we can simplify it by repeatedly applying the filter function. Assuming contingency is explicit in a certain transaction and block, we can run the filter twice, once assuming the predicted state is valid and once assuming the predicted state is not. This can be extended to n predicted states at the cost of 2^n evaluations of the filter function.

in conclusion

in conclusion

The Sequencer is a watchmaker's genius, setting the Rollup history and watching it tick-tick to its destined state. There isn't much difference between Optimism and Arbitrum, but there are security differences between the two. Nobody knows what the sorter does. Shared sorters can do atomic inclusion, but not atomic execution, and atomic inclusion cannot be incorporated into atomic execution without Rollup composition or some other execution mechanism. All this bragging about sharing a sequencer for seamless interoperability is junk science.