Shared Sequencing

Research
1

Introduction

The blockchain ecosystem is evolving rapidly, with multiple chains and Layer 2 solutions proliferating. However, this growth has highlighted a significant challenge: the current design of rollup sequencing and L1 blockchains doesn’t allow for efficient expression of preferences or extraction of value across different chains or domains. This limitation is becoming increasingly problematic as liquidity and applications fragment across various L2s.

Shared sequencing marketplaces have emerged as a potential solution to this problem. These marketplaces, being developed by companies like Espresso, Astria, and NodeKit, allow third parties to sequence L2 batches concurrently. While this approach shows promise, it also introduces new complexities in mechanism design and economic incentives. The potential benefits include:

  • Reduced exposure risk by enabling cross-domain atomicity
  • Mitigation of negative externalities from cross-domain MEV extraction
  • Increased rollup revenue
  • Decentralization of rollup sequencers

Shared Sequencer Marketplace

A shared sequencer marketplace consists of a mechanism that enables rollups to sell sequencing timeslots to third parties called sequencers. A shared sequencer mechanism consists of:

  • A bidding language, that is a subset X,
  • An allocation rule x, that maps the set of bids of sellers and buyers to an allocation,
  • A payment rule p, that maps the set of bids of sellers and buyers to payments.

Ideally, a sequencer should be able to simultaneously purchase sequencing rights for multiple rollups, becoming a shared sequencer for these rollups, allowing the sequencer to use or sell the optimality of cross-domain atomicity.

shared_seqimage
shared_seqimage753×435 22.2 KB

Shared Sequencer Marketplace Desiderata

The following properties are well-known in the mechanism design literature and can be outlined as:

  • Buyer Individual Rationality: No buyer pays more than their bid amount.
  • Seller Individual Rationality: Each seller receives at least their asking price.
  • Weak Budget Balance: The auctioneer incurs no net loss; total payments from buyers meet or exceed total payments to sellers.
  • Sybil-proof & Shill-proof: Agents cannot increase their payoff by submitting multiple fake bids.
  • Non-wastefulness: The right to sequence is always allocated to either some buyer or the seller.

Assumptions and Model

There are m sellers, each with a distinct item i n [m] = 1, 2, dots, m with a valuation r_i (the minimum amount of cash such that they are willing to accept to sell their slot) which can be either public or private.

There are n buyers, each with a valuation v_i(A) for the bundle A ubseteq [m] (the total value they gain by sequencing all slots in A).

Items present complementarities, which is modeled by assuming buyers’ valuations are superadditive:

Definition: Superadditive

A buyer’s valuation v is superadditive if for any disjoint sets A ubseteq [m] and B ubseteq [m],

v(A up B) eq v(A) + v(B).

A single-minded valuation is a type of valuation function that models goods that are perfect complements. Formally, let M =[m] be the set of items. A bidder i with a single-minded valuation is interested in only one specific bundle S_i n 2^{M} and has a value v_i for that bundle. The valuation function v_i: 2^M o athbb{R}_{eq 0} is defined as follows:

v_i(T) = egin{cases} v_i & ext{if } S_i ubseteq T, 0 & ext{otherwise}. nd{cases}

In other words, bidder i values any bundle T ubseteq M at v_i if and only if S_i ubseteq T; otherwise, the value is 0.

Assumption: Agents have private independent valuations. The distributions from which agents’ valuations are drawn are common knowledge. All agents have quasi-linear utilities and are risk-neutral.
These assumptions, while standard in auction theory, serve as a practical framework to understand the behaviors of agents within block bidding. Despite its departure from absolute realism, it offers a necessary starting point for theoretical investigations. Although prior-free mechanisms might be preferred in ideal settings, such mechanisms face inherent limitations, as evidenced by impossibility results even in simple bilateral trading scenarios. Moreover, continuous repetition of auctions over time enables one to infer information regarding agents’ valuations, mitigating the constraints imposed by common knowledge assumptions.

Assumption: We differentiate between two types of sellers, active and passive.
Active sellers have valuations over their own blocks, optimized through sequencing. Passive sellers, if they choose, can sell their blocks via separate auctions and observe the resultant revenue but do not have an intrinsic valuation over their own blocks.

This assumption clarifies the roles and strategic options available to sellers operating within the blockchain market. Active sellers, equipped with information and expertise in identifying and capitalizing on Miner Extractable Value (MEV) opportunities, optimize the sequencing of their blocks. They may also choose to sell their blocks through separate auctions, leveraging their knowledge and capabilities to maximize returns. In contrast, passive sellers lack the ability to extract additional value from their blocks and can only sell them through separate auctions. Monitoring the revenue generated from these auctions offers passive sellers valuable insights into the market’s valuation of their blocks. This assumption is plausible, especially considering the potential for L2 sequencers to implement analogous mechanisms akin to MEV-Boost for their own roll-ups.

Assumption: Agents realize their values at the moment they build their blocks. Before that time, they know the expected value they can make.

In general, arbitrage opportunities and other MEV opportunities, such as liquidations, depend fundamentally on the current state of the blockchain and the transactions in the mempool. That is the main reason we assume that agents realize their value at the moment the block must be built. While certain nuances, such as private order flow, may exist, for the sake of simplicity, this assumption focuses on the moment of block construction as the critical juncture for value realization.
The second assumption here might be quite strong because agents don’t have a fixed expected value for their earnings. Instead, they rely on signals indicating how much MEV they might get in the future. However, these signals might not always match reality perfectly. It’s similar to how in oil auctions, predictions about the value of oil depend on what other buyers signal. So, a model that takes into account these interdependencies might be more appropriate here—i.e., a model that takes into account interdependent valuations of the buyers and sellers. But exploring this is out of the scope of this paper.

Assumption: There exist credible commitments that sellers must adhere to. More specifically, the validators and sequencers of future blocks are known in advance and can commit to delegate the right to construct blocks to third parties.

Smart contracts facilitate the establishment of credible commitments within the blockchain environment, ensuring the enforceability of agreements between parties. For instance, block proposers may commit to future block production rights, with mechanisms in place to deter contract breaches, either through slashing conditions or protocol-level enforcement.

Assumption: Buyers and sellers do not form coalitions; each agent acts strategically and independently.

Although the absence of coalitions may appear idealized, it simplifies the analysis by focusing on individual agent behavior. This is a standard assumption in mechanism design. In addition, it is important to note that the formation of coalitions in anonymous environments can be quite expensive.

Marketplace Performance Measure

The Bayesian Price of Anarchy (PoA) over a set of feasible value distributions athcal{F} is defined as:

ext{PoA}{athcal W}(M,athcal F):=ax{athbf{V} n athcal F}ax_{s n ext{BNE}(M, athbf{V})} rac{ext{OPT}(athbf{V})}{athcal W(M,s,athbf{V})}

Similarly, the Bayesian Price of Stability (PoS) over a set of feasible value distributions athcal{F} is defined as:

ext{PoS}{athcal W}(M,athcal F):=ax{athbf{V} n athcal F}in_{s n ext{BNE}(M, athbf{V})} rac{ext{OPT}(athbf{V})}{athcal W(M,s,athbf{V})}

Results

One of the key findings in the analysis of ex-interim auctions, also known as Just-In-Time (JIT) auctions, reveals a counterintuitive phenomenon akin to Braess’s paradox in network theory. This paradox demonstrates that increased expressiveness in auction mechanisms can sometimes lead to reduced welfare and revenue.

Theorem: Braess’s Paradox for Just-In-Time Auctions

The revenue and welfare outcomes of Just-In-Time mechanisms employing proportional payments or Shapley payment mechanisms can, in some cases, be lower than those achieved through simpler simultaneous first-price auctions.

This surprising result highlights a crucial insight: increased expressiveness in auction design does not always translate to improved outcomes. In fact, it can potentially reduce both welfare and revenue in certain scenarios. The underlying mechanism for this paradox lies in the strategic behavior of sellers. In equilibrium, the reserve price set by sellers for their items when sold as a bundle can exceed the optimal reserve price that would be set if all blocks were controlled by a single entity. This discrepancy arises from the decentralized nature of the marketplace and the individual incentives of multiple sellers.

Further analysis of ex-interim auctions reveals even more striking limitations:

Theorem: Bayesian Price of Anarchy of Shared Sequencing Marketplace

The revenue and welfare price of Stability (and thus Anarchy) of any non-wasteful and weak budget-balance ex-interim mechanism with msellers is mega(m^{1/3}) (and mega(m^{1-arepsilon}) for every arepsilon > 0 if the mechanism is dominant-strong incentive-compatible for sellers), even when buyers’ valuations are public information.

The implications of this theorem are profound. It suggests that in the worst-case scenario, operating any shared sequencing marketplace is not significantly more efficient than running m separate instances of a proposal-builder separation (PBS) mechanism. This limitation persists even under idealized conditions of complete information about buyer valuations. The proof of this theorem relies on considering a simplified scenario with a single-minded buyer valuing the entire set of items at $1$. In this setup, each seller effectively holds veto power over the sale, transforming the problem into one that closely resembles the challenges encountered in public goods funding.

On the other hand, when there are credible commitments and sellers can sell their rights for processing future slots before their valuation is realized, we obtain positive results.

Proposition: Positive Results with Credible Commitments

With single-minded bidders with public valuations over m, there is a (Bayesian) mechanism that is ex-ante individually rational for both buyers and sellers, weak budget-balance, and has a Price of Anarchy at most 2.

The mechanism consists of the following. Note that this is not true if we change ex-ante to ex-interim individual rationality.

These results underscore the complexities involved in designing efficient mechanisms for cross-blockchain resource allocation. They highlight the need for careful consideration of strategic behaviors and the potential limitations of seemingly intuitive approaches to improving market expressiveness and efficiency.

Conclusions and Takeaways

The analysis of cross-domain auctions and shared sequencing marketplaces reveals significant challenges in designing efficient mechanisms for blockchain resource allocation. Our findings demonstrate a paradoxical effect akin to Braess’s paradox, where increased expressiveness in auction design can lead to suboptimal welfare and revenue outcomes. Notably, ex-interim auctions face severe limitations, with the Bayesian Price of Anarchy for non-wasteful and weak budget-balanced mechanisms scaling as mega(m^{1/3}) for m sellers, potentially approaching mega(m^{1-arepsilon}) under stricter conditions.

The insights from this research could play a pivotal role in advancing the efficiency of cross-domain auctions, which is particularly relevant to protocols like Mantis developed by the Composable Foundation. By analyzing how auction design affects the allocation of blockchain resources across different domains, this research highlights potential improvements to the coordination and settlement of cross-domain solvers and searchers. In particular, addressing inefficiencies and potential paradoxes (such as the Braess-like effects identified in the study) can contribute to the creation of mechanisms that both optimize welfare and enhance revenue outcomes. The ultimate aim is to design auction systems that remain effective even under general conditions, where distributional assumptions are either not known or must be inferred in real-time through online mechanisms.

For Mantis and similar protocols, this work holds promise in reducing the risks of centralization and inefficiencies associated with current slot auction designs. It suggests that with credible commitments and improved mechanism designs, the allocation of resources can be made more robust against market imbalances and inefficiencies like multi-block Miner Extractable Value (MEV). Future exploration in this domain could lead to a more decentralized and efficient allocation of resources, thereby contributing to the stability and performance of cross-domain ecosystems managed by the Composable Foundation.