Transaction ordering policy

The Arbitrum sequencer receives transactions from users and publishes an ordered sequence, which serves as input to the execution stage of Arbitrum. Currently the sequencer follows a first-come, first-served (FCFS) sequencing policy.

There’s a lot to like about FCFS. It’s simple and easy to explain. It is seems intuitively fair. It minimizes latency because the policy allows each transaction to be appended to the sequence immediately on arrival.

Other rollup protocols use FCFS as well. Optimism does, and based on descriptions of other systems they seem to do so as well.

Is there an argument for an alternative policy? In particular, does someone want to advocate for a specific, implementable transaction ordering policy, based on the pros and cons of that policy vs FCFS?

34 Likes

TLDR

We argue that frequent batch auction-style FCFS should be adopted in order to make the fairness notion more robust and welfare-maximizing (in sense of providing better UX and making the network long-term incentive aligned with the correct parties).

Specifically, we suggest that the “fairness granularity,” the interval during which all transactions received by a node are assumed to have happend at the same time, should be set to an interval of at least 500ms (conservative lower bound, will elaborate later).

Fairness granularity advocation in the original Themis FCFS paper

This means that instead of reporting a strict ordering (by receive-order time) of transaction, each individual node report a partial ordering to the leader of the ordering consensus protocol. And after aggregating each individual nodes’ preferences, the leader gets a weak ordering (by FCFS) with unordered batches in it (caused by condorcet paradoxes and the initial partial ordering). Now the leader tries to resolve the order of the unordered batch using auctions (e.g., using coinbase.transfer).

We use FBA-FCFS (frequent batch auction first come first serve) to refer the the proposed ordering protocol.

We show this proposal is better than the original non-FBA version of FCFS in two ways:

  1. makes the fairness of the ordering more robust (in the sense of network latency tolerance) than the vanilla version, allowing the domain to provide a smoother UX
  2. more fair in the sense that it removes the negative externality caused by inefficient resource allocation and increases the welfare (an upper bound on ordering efficiency) of users, thus allowing the domain to attract much more future users (who aren’t visible currently)

We also address potential concerns of this proposal:

  • FBA-FCFS incurs negligible latency overhead
  • FBA-FCFS validators has no incentive to coarsen the fairness granularity

Assumption

First, we list some assumptions currently made by existing FCFS proposals (note there are no new assumptions):

  • the system has a permissioned mempool that is only visible to the validators, and the privacy on top of the permission is trusted at the moment
  • anybody is able to submit a transaction, the transaction is assumed to be broadcasted to all the validators at the same time
  • the validators are geo-distribtued well enough
  • there exists some social norms that can, with good enough accuracy and efficiency, slash dishonest validators
  • there exists network latency services that allow VIP agents to broadcast transactions to every validator faster than non-VIP agents, allowing them to be ordered first in vanilla FCFS with decent probability

We define dishonest as either of the below:

  • the validator violating the privacy assumption of the mempool and leaking transaction contents to sophisticated parties who can gain an ex-post knowledge of the transaction sender’s private information before finality.
  • the validator manipulates the ordering of the transactions in a way such that transactions (not in the same batch) received later is placed before transactions received sooner.

We give some examples of activities that are impacted by ordering rules:

  1. sandwiching: requires the validator to both violate privacy and receive-order honesty
  2. generalized frontrunning: requires the validator to both violate privacy and receive-order honesty
  3. liquidation/arbitrage/NFT sniping: doesn’t require the validator to violate any honesty assumptions
  4. market making/statistical arbitrage: doesn’t require the validator to violate any honesty assumptions

It is clearly desirable to eradicate activities 1&2 and democratize activities 3&4.

Robustness

First, we want the ordering protocol to level the playing field between privileged and unprivileged users (who might have worse network latency). Specifically, with reasonable network latency assumptions, the fairness granularity should never be zero (or else, priviledged users will always win present preference conflicts) to allow for a smooth/fair UX for all users.

More importantly, we know that there exists a huge incentive for sophisticated users (i.e., MEV searchers, validators) to manipulate a vanilla FCFS system (violating the receive-order honesty) without incurring much risk.

This imposes a great risk to the long-term stability of the protocol because players cannot be trusted to be honest in an environment where they are encouraged to break the honesty assumption with minimal risk: optimal latency and ordering manipulation is always achieved by colocation with validators, which encourages vertical integration between validators and searchers which hurts the overall decentralization of the system.

On the contrary, if a FBA-FCFS system is adopted, the validators can be trusted to be honest as all the centralizing/dishonest vectors have been contained in the auction, making the protocol long-term stable (as we all know, only with sufficient honesty/security of a network can the domain gain significant traction of future users). Honesty assumptions and incentive aligenment has to go hand in hand.

We observe that from the four examples, 1&2 requires the validator to break both the privacy and receive-order honesty assumption. Thus, to strengthen our ordering protocol, we need either (i) opt-in privacy, through threshold encryption and mechanism similar to cr-list, or, (ii) rely on the social norm slashing mechanism to discover privacy violations (which is assumed in the original vanilla FCFS anyway, and this behavior would be very easily discoverable by any data services, txn scanners, or block builders).

This means that with privacy components in the protocol, we can indeed eradicate 1&2 while making the fairness more robust. Of course, the tradeoff here is that in the vanilla version of FCFS, validators can violate the privacy assumption and still won’t be able to conduct activities 1&2 efficiently, while in FBA-FCFS the validators can just violate the privacy guarantees and conduct 1&2 effectively. Note that this tradeoff is mitigated (on top of the two methods mentioned in previous paragraph) because:

  • as more application layer protocols realize the importance of MEV-resistant design, activities 1&2 will be eradicated at a higher level in the transaction supplychain. Ordering layer is not the best abstraction layer to solve the negative externalities of non-private transaction MEV.
  • public mempools are generally unseriable (as demonstrated by various pre-trade privacy/zk pushes), in future we will see more privacy solutions

Fairness

The acitivities in case 3&4 constitues a significant portion of all on-chain acitvities. And currently, most on-chain activities are (systematically relevant) DEX activities. In fact, 65%+ of Uniswap volume is from (statistical) arbitrage, and among the other 35% it’s a few big market makers. Thus, it is safe to say that, in majority of the time, there exists a conflict of preference of agents as they all want to capture this permissionless MEV opportunity, i.e., they have common value over the resource of “what the next on-chain state should be.” We breviate this resource to spec-on-state, which means which specification should the next state satisfy (which is sometimes abstracted in the notion of a “blockspace” and its attributes).

Uniswap V3 Volume is dominated by acitivies 3&4

Our goal, then, should be to minimize the negative externality cause by the allocation of this resource of spec-on-state within burst periods (which occurs extremely often).

We observe that vanilla FCFS incurs much more negative externality than FBA-FCFS because sophisticated agents (e.g., MEV searchers) are encouraged to both spam the network and play a latency auction (whose endgame is spinning up multiple searcher bots instances distributed across the network to capture opportunities, which is also spamming). This is primarily caused by the fact that agents in the network have no way of expressing their preference and thus enter a stage of uncoordinated coordination (auction by other means). This means the allocation has many undesirable properties:

  1. the sequencers/proposers/validators have inherent huge advantages because they can be the first ones to see the transactions and therefore the first to react (also the colocation is perfect so have very low network propagation latency). This implies that they are more likely to collude with sophisticated users and thus creates centralization in sequencers/proposers/validators, which harms geographical decentralization, network security, censorship resistance, and liveness.

  2. the allocation probably takes the form of an all-pay auction (as in the case of most latency games, where backroom deals are signed/AWS instances are colocated in an uncoordinated manner) which makes the network-wide welfare decrease. And this costs will always be channeled by sophisticated users to unsophisticated users in the form of a less efficient market and worse UX. For example, market makers will charge a larger spread to retail users because they have a higher operating cost, as shown in traditional HFT, or that arbitraguers will not move the price of a pool because it costs them too much to do so, thus forcing users to trade in unfavorable out-dated prices. In the end, the permissionless economic value will be captured by some party, it could be captured by Amazon/Google who are neither incentive aligned with the Arbitrum ecosystem nor the crypto community, or, it could be captured by users.

  3. the allocation mechanism is inexpressive, in this case, the agents have no mechanism of expressing their preference for activies (which sums up to 90% of the network activity), which means there is huge inefficiencies caused by Price of Anarchy. For example, in spam/randomized ordering auctions, the validators are forced into a more severe transaction quality trilemma, which imposes a direct tax on users. Essentially, the inefficiency, in equilibrium, equals to the amount that normal users are charged (compared with what they would’ve been getting in FBA-FCFS case), driving users away.

  4. users are inable to have their true preference aggregated (because the mechanism/ordering protocol has only partial information and has no clue of how much money the agents spent on latency optimization), this also means that the MEV is internalized by latency services, whose entire business model is encouraging more MEV extraction and isn’t incentive aligned with Arbitrum in the prosperity of the domain and its long-term value accrue/user acquisition. Not internalizing the auction value to the domain also means that there exists no way of future re-distribution of the value, which has been shown to be damaging to the security of the network.

  5. the game is not transparent, thus raises the barrier of entry, favoring sophisticated users over ordinary retail users more. This would make activies 3&4 more centralized and therefore the profit to be more centralized.

On the other hand, if we use a direct allocation mechanism (e.g., using coinbase.transfer) during those burst periods, we circumvente all five disadvantages of vanilla FCFS listed above while still retaining the benifits of low latency fast finality receipts and fairness.

the price impact (burst of common value) period duration in forex markets
the average time between the occurrence of two events (trades or changes at the top of the order book)

Based on data in traditional markets (shown above), we know that the burst period in one pair of assets in the crypto market can be conservatively modeled (lower bound) as coming in every 500ms and lasts around 200ms. And since crypto has many frequently traded pairs with meaningful volume (relative), the price discovery happens much more often.

In fact, we found that in aggregation, the burst period on Ethereum takes around 1245ms, and 75.37% of the conflict of preferences happen in 4.115% of the time. For example, the burst period in block 13227081 consists 96.38% of the MEV load while only taking up 3.53% of the block time (640ms). Similarly, the burst period in block 13227483 took 922.5ms: it summed up 91.614% of the MEV within that block during less than 5.6% of the time (the diagram of MEV as a function to time is shown below). This means that if the same situation were to happen on vanilla FCFS, then, compared with FBA-FCFS, we will be bearing the extra negative externalities (e.g., centralization, higher fees, worse execution, etc,.) from 11.92x more conflict of preferences.

MEV(t), the darker/larger the circle, the more conflicts there are at that moment in time

This means that the fairness granularity parameter, at least, should be chosen over 500ms. Moreover, if we factor in global delay uncertainties over the Internet, the interval would be larger than 500ms up to a few seconds.

As for latency UX concerns, 500ms auctions can be achieved with negligible latency cost to users as Solana has blocktime of 400ms and full block auctions are being conducted. Also, auction need only to happen per public information reveal (i.e., at the start of the block) because that is when the burst period starts.

Note that the 500ms bound is not fixed, the shorter we make the auction interval (fairness granularity), the fairness guarantee becomes less robust: it is easier for the validators to be malicious without penalty.

Conclusion

We presented FBA-FCFS and argued why it maintains the same no-frontrunning guarantee to users, while improving UX and fairness guarantees.

by Flashbots :zap::robot: with love :love_letter:

11 Likes

Is there a clear description of the FBA-FCFS policy? I think we can infer that it divides time into intervals of length g and orders by bidding within each interval (resolving equal bids by FCFS). Is that right?

6 Likes

The precise description is same as the one in page 20 and 21 of the Themis paper’s Definition 6.2 of fairness granularity (https://eprint.iacr.org/2021/1465.pdf) except that we resolve the ordering within the interval (or, in general, condorcet cycles) using auctions.

6 Likes

And how do the auctions work? Do you auction off the right to arbitrarily reorder transactions within the interval? Or do you order transactions within the interval based on the tips they offer? Or something else?

7 Likes

The intra-chunk ordering can be done in multiple ways.

The easiest one is ordering by fees (tip), and break ties as @edfelten suggested using receive-order. This adds negligible overhead for sequencers and will be good for settings where user preferences in burst periods are mostly common value (i.e., preferences are not diverse), which is the case in atomic MEV arbs or liquidations.

It is also possible to add more UX features into intra-chunk ordering. For example, the validators could add revert protection for users which reduces spam. Or, they could provide conditional payments like coinbase.transfer in Ethereum that allow users to express more diverse preferences which enable features that are already being explored by application teams building on Arbitrum (e.g., Shell Protocol’s design of a composable transaction/trade batching engine). If those additional UX features are wanted, the sequencers can implement themselves to have the architecture embedded within the sequencing node (with an estimated added end-to-end latency of ~6ms, assuming same transaction load as current Ethereum). If the sequencers don’t want to implement themselves, they can also work with third-party trusted services.

10 Likes

@sxysun thank you for the detailed write-up, definitely interesting and along the lines of things I’ve been thinking about lately.

I’m a bit confused by the discussion in this thread though, and what the goals of both parties are:

  • @edfelten seems to be looking for a policy for the current state of the arbitrum rollup, with a centralized sequencer
  • @sxysun proposed a solution which requires a decentralized sequencer

@edfelten can you clarify whether you’re looking for a policy that works for a centralized sequencer, or for a decentralized sequencer.

All in all, sounds to me like flashbots starting to shill it’s SUAVE “a turnkey decentralized block builder for rollups” (https://twitter.com/hasufl/status/1580983853824765952?s=20&t=6H_qi4R1GlLMkwAhTzbPww) service and trying to frontrun the arbitrum-chainlink FSS relationship: this promises to be an interesting year.

@sxysun could you clarify whether the set of FBA-FCFS nodes would be rollup sequencers themselves, or a different set of “keeper” nodes similar to what Chainlink FSS is proposing?

7 Likes

I’m discussing the issue in the context of centralized sequencing because I think the relevant question–what transaction ordering policy we should seek–is orthogonal to decentralization. Once we know what ordering policy we want, there are good ways to apply that policy in a centralized or decentralized setting.

9 Likes

agree with @edfelten here the solution is regardless of the sequencer set. It can be a centralized rollup sequencer, or a decentralized set of Arbitrum sequencers themselves.

12 Likes