# The Espresso Market Design
*Authors: Benedikt Bünz, Ben Fisch, Ellie Davidson*
*We thank Justin Drake, Maryam Bahrani, Tim Roughgarden, Scott Kominers, Davide Crapis, Christoph Schlegl, Bruno Mazorra, Philipp Strack, and others for helpful discussions and feedback on our design. Thanks to Ed Felten for pointing out a mistake in the analysis section of a previous version.*
Espresso is building a marketplace for sequencing. For high-level motivation and background, please read our previous post [Based Espresso: ad-hoc shared sequencing](https://hackmd.io/kkVJEfd0THeMYhSD1no0Eg). In this post, we present the detailed marketplace design along with justifications for our design decisions.

## Overview

Espresso provides the following separate but complimentary services:
1. A marketplace that enables rollups to sell sequencing timeslots to *sequencers* (also known as proposers). A sequencer that successfully purchases a timeslot has the right to propose blocks for the rollup during that timeslot.[^1] A sequencer can simultaneously purchase sequencing rights for multiple rollups, becoming a shared sequencer for these rollups.
2. A *finality gadget* that notarizes proposed blocks through a non-executing, proof-of-stake consensus. After the finality gadget has notarized a sequence of rollup blocks, they cannot be changed or reordered.

[^1]: Rollups may also sell restricted sequencing rights (e.g., that are subject to an ordering policy, inclusion list, etc, but that is beyond the scope of this article).

The marketplace has several advantages, including the benefit of outsourcing the sequencing to specialized parties. The most significant benefit, however, is that sequencers that buy the sequencing rights for multiple rollups can guarantee atomic execution between these rollups. Atomic execution allows sequencers to satisfy cross-rollup user intents and give [strong preconfirmations](https://hackmd.io/@EspressoSystems/bft-and-proposer-promised-preconfirmations) for cross-rollup transactions. We discuss the benefits of this ad-hoc shared sequencing in this [article](https://hackmd.io/kkVJEfd0THeMYhSD1no0Eg).

In this post, we lay out the design and analyze the properties of the Espresso marketplace. The HotShot finality gadget, which you can read more about [here](https://hackmd.io/@EspressoSystems/HotShot-and-Tiramisu) and [here](https://github.com/EspressoSystems/HotShot/blob/main/docs/espresso-sequencer-paper.pdf), is independent of the marketplace, but serves multiple essential functions:
1. It enforces the sale of sequencing rights to a given sequencer and ensures the entire network agrees on who is sequencing for each rollup in a given timeslot. To do this, it acts as a timekeeping service.
2. It ensures that a current rollup sequencer's block proposal is included and cannot be forked away.
3. It enables handing over the sequencing rights from one sequencer to another, ensuring that the next sequencer builds off the latest finalized rollup state.
4. It enables users and applications to get strong preconfirmations on the current state of multiple rollups. We [recently demonstrated](https://medium.com/@espressosys/espresso-systems-partners-with-across-to-bring-fast-secure-bridging-to-ethereum-rollups-20bfffefa3e2) with Across how this can help facilitate fast bridging between rollups, among other advantages.
## Espresso Marketplace design

Our marketplace has two primary goals:
1. Through the marketplace, sequencers can obtain the **sequencing rights for multiple rollups at the same time**. This allows sequencers to express the additional value for shared sequencing, such as coordinating atomic cross-rollup transactions.
2. Rollups participating maintain sovereignty. They can choose to join and leave the marketplace and are guaranteed that if their sequencing rights are sold they'll **accrue more value** than they would otherwise (sequencing exclusively on their own).

Additionally, the marketplace should have the following properties:
* **Optionality**: A rollup only sells its sequencing rights if it can create more value than sequencing on its own.
* **Efficiency**: The marketplace's outcome allocates sequencing rights to those who value bundles of rollup blocks the most. Additionally, if there is positive value to be made from sequencing two rollups together, they will be sequenced together.
* **Stability**: The marketplace settles into an equilibrium such that participants do not need to continuously reason about their actions so long as outside parameters do not change. Market stability helps with price discovery since the sequencers' value functions are unlikely to change frequently. For example, a bidder in a stable marketplace does not need to reason about their bid price continuously.
* **Anti-Monopolization and Censorship Resistance**: No sequencer, even one with more sophisticated MEV capabilities, can maintain a monopoly on creating blocks for a single rollup or bundle of rollups.
* **Incentive compatibility** (optional): Marketplace participants should report the true value of rollups or bundles of rollups.

To achieve the above goals and properties, we use a **combinatorial lottery mechanism** to assign sequencers to particular rollup blocks. Potential sequencers act as buyers in the lottery by purchasing lottery tickets for bundles of rollups. Rollups act as sellers, selling their sequencing rights on a per-slot basis. If a potential sequencer has a winning ticket for a particular bundle of rollups for a specific slot, they become the shared sequencer for those rollups during that slot.

## Terminology
* **Slot:** A time period during which a rollup sells its blockspace. An auction is run for a slot at a time, but there may be many different sequencers for a single rollup within a single slot. A rollup does not have to participate in the auction every slot.
* **Bundle:** A subset of all rollups participating in the marketplace. This subset represents rollups sequenced by the same sequencer. A bundle can be comprised of any combination of rollups in the system. Two particular bundle types are the *singleton bundle*, which consists of only one rollup, and the *full bundle*, which includes all rollups.
* **Reserve Price:** The minimum amount a potential sequencer must bid to earn sequencing rights for a particular rollup during a specific slot.

## Combinatorial Auction
First, we specify how the sequencer assignment mechanism can be run as a combinatorial auction. Then, we show how to transform it into a lottery and discuss the advantages of a lottery versus an auction.

The combinatorial auction can be viewed as a first-price combinatorial pay-as-you-bid auction that consists of three phases: the **bidding phase**, **assignment phase**, and **sequencing phase**.

We make several assumptions before we further discuss the auction:

- Proposers view rollups as complements; the value of sequencing two rollups is always greater than or equal to the sum of the value of sequencing each rollup individually.
- There are non-zero (positive) values for the sequencing rights for each rollup.
Proposers can compute an expected value for rollups and bundles of rollups. This is necessary as we run the auction before the block contents are known.
- All rollups participating in the shared sequencer auction are registered and are known by the mechanism. Each rollup specifies an address that receives the revenue from the auction.

*High level schematic of the mechanism and sequencing design:*

### Bidding Phase
During the bidding phase, each potential sequencer submits bids to the marketplace for the bundles they want to sequence. Sequencers can submit bids on any bundle they wish. All bids are public, and potential sequencers can submit as many bids as they'd like before the end of this phase. Potential sequencers pay their bids upfront when submitting their bid, like in pay-as-bid auctions. Paying bids up front serves two purposes: First, it ensures sequencers have adequate funds to cover their bid. If bids were paid at the time of the block proposal, a malicious sequencer could submit an adequately funded bid and win the auction but drain their funds before the bid is executed, resulting in gaining sequencing rights for free. Secondly, pay-as-bid auctions have advantageous economic incentives, which we will discuss later. Note that non-winning bids will always be refunded.

The bidding phase takes place well before the sequencing slot. This is necessary to allow the marketplace time to calculate the auction winners and make them known to the HotShot finality gadget.

### Assignment Phase

The assignment phase (also sometimes reffered to as closing phase) determines the auction's outcome and assigns sequencers according to that outcome. The auction outcome is determined by selecting the set $S$ of bundles $B_1,\dots,B_k$ such that:
1. The bundles partition the set of rollups $R$ (each rollup appears only once in the winning set)
2. Set $S$ has the maximum sum of bids across its bundles compared to other possible sets.

More specifically, let there be $n$ rollups, and $r_i$ denote the reserve price for the $i$th rollup. For every bundle $B \subseteq [n]$, let $b(B)$ denote the value of the highest bid submitted for bundle $B$. For each singleton bundle $\{i\}$ let $v(\{i\}) = \max(b(\{i\}), r_i)$. This definition implicitly interprets rollup reserve prices as bids for singleton bundles. For all other bundles (of size at least 2), let $v(B) = b(B)$. For any partition $\Pi = \{B_1,...,B_k\}$ of [n] into disjoint subsets let $v(\Pi) = \sum_i v(B_i)$. The auction finds the partition $\Pi^* = \mathsf{argmax}_{\Pi} v(\Pi)$ that maximizes auction revenue. Sequencing rights for every bundle in $\Pi^*$ are then allocated to the sequencer that submitted the highest bid. In the case of singleton bundles, if the reserve price were the highest bid, the rollup itself would be allocated sequencing rights for the singleton bundle. See the figure below for an example.

<figure>
<img src="https://hackmd.io/_uploads/HkUek5Fy0.png"
alt="Example winning set of bundles with maximum revenue">
<figcaption>Four possible sets that satisfy the partition property for rollups A, B, C, D, and E. In this example, the full bundle maximizes the revenue across rollups, so it is the winning set of the auction. </figcaption>
</figure>

Note that since bundles can consist of any combination of rollups in $R$, finding the revenue-maximizing set of bundles is potentially an exponentially difficult problem that could take an intractable amount of time to solve:
Real-world bundles will likely be a small subset of all possible bundles since not all bundle possibilities will make economic sense to bid on. Thus, the marketplace will likely only have to solve across a few combinations of bundles.
We can optionally timebox solving for the winning set $S$. At the end of this timebox, the solver will publish the most revenue-maximizing solution they've found thus far.
There is a challenge period during which anyone can submit a more optimal solution. Since all bids are public, any party can submit a solution.
Since a solution is the sum of bids across all bundles in the set, it is easy to verify that one solution is more revenue-maximizing than another by simply comparing the sums of their bundle values.

At the end of this phase, the finality gadget finalizes the auction outcome.

### Sequencing Phase
The auction winner of each bundle inside the winning set $S$ earns the sequencing rights for that bundle during the specified slot. These winners are now the sequencers for the individual rollups in their bundle; they will propose the next block for each rollup in the bundle and submit the proposal to the HotShot finality gadget. Each sequencer proposes its blocks to the network when the slot arrives in the finality gadget. The network verifies that proposals come from each bundle's correct auction winners and finalizes the results. Finally, losing bidders for said slot are refunded their bid.

### Revenue allocation
Recall that one of our primary goals was to ensure rollups are always better off participating in the marketplace than sequencing alone. Therefore, given a particular auction outcome, we must split the revenue amongst the rollups. If the winning set $S$ contained only singleton bundles, then the marketplace could give each rollup revenue equal to the bid on their singleton bundle. However, to enable shared sequencing, we sell rollups as bundles. Therefore, we need a mechanism to split the remaining revenue generated from bundling rollups. The core idea is that each rollup receives revenue proportional to the maximum bid on the singleton bundle that only includes the rollup. We specify the mechanism in more detail below. It has the following parameters:

- $b_i$: denotes the highest bid on the singleton bundle ${i}$, interpreting the reserve price $r_i$ as a bid.
- $b(B)$: denotes the highest bid on the bundle

#### Mechanism:

- Each rollup receives $b_{i}$ as a payment to a specified address. That is, the rollup receives **at least** the maximum bid on its singleton bundle (or the reserve price). This guarantees that the rollup is better off in the marketplace than on its own so long as it sets its reserve price to be greater than the revenue it would make sequencing on its own.
- If a rollup $i^*$ is included in a bundle $B= \{ i_1,\dots,i_k \}$ of $k$ rollups and $b(B)$ is the winning bid on that bundle then it **additionally** receives:

$$
(b(B)-\sum_{j=1}^k b_{max,i_j})\cdot \frac{b_{i^*}}{\sum_{j=1}^k b_{i_j}}
$$
That is, the rollup receives an amount of the shared sequencing revenue proportional to the highest singleton bundle bid, which signifies the revenue a rollup could have made on its own.

### Fees
The marketplace charges a small fee. That fee is burned and designed to disincentivize, setting a dishonestly high reserve price. The fee consists of two components: a fee proportional to the reserve price and a fee proportional to the shared sequencing revenue.

#### Execution and congestion fees
The marketplace does not touch rollup's execution fees (i.e., gas fees). These remain as they are today. Additionally, sequencers submit their blocks to the [HotShot finality gadget](https://medium.com/@espressosys/espresso-hotshot-consensus-designed-for-rollups-b080ba7362d1). HotShot ensures that after submission, no one can change the order of transactions for a rollup. This allows the next sequencer to build on the previous block safely and also enables [faster bridging](https://medium.com/@espressosys/espresso-systems-partners-with-across-to-bring-fast-secure-bridging-to-ethereum-rollups-20bfffefa3e2).

## Lottery to Prevent Monopolization
The combinatorial auction fairly splits the revenue among rollups and ensures that sequencers that value rollups the most earn sequencing rights. One concern with auctions, however, is that the same party will win too often.

Recall that the auction is run before the block data is known. This means sequencers bid based on the expected value of bundles instead of their real value (this is different from the current PBS in Ethereum). This expected value should remain the same over time. Therefore, the same sequencer may win the same rollup in every instance of the auction.

We convert the combinatorial auction into a combinatorial lottery to mitigate this concern. Our design has similarities to the recently proposed [execution tickets](https://ethresear.ch/t/execution-tickets/17944) idea. We describe the core changes below:

* Instead of collecting bids per bundle and selecting the highest bid for a particular bundle, we sell up to $t_{\max}$ lottery tickets per bundle at a price $p_B$. Note that we can dynamically exclude bundles which have limited demand in order to simplify bidding/winner determination.
* The total number of lottery tickets sold multiplied by the price per ticket acts as the bid on a particular bundle. We then run the winner determination algorithm in the same way as the auction to determine the winning bundles. The lottery is equivalent to a pay-as-you-bid auction, where each person pays their bid (if their bundle is part of the winning allocation) and receives a proportional allocation, e.g., a percentage of the sequencing rights.
* Given a set of winning bundles the sequencers for the next slot are sampled randomly from the lottery ticket holders.
* We can use one lottery sale for multiple blocks by using fresh randomness. For example, one ticket may be valid for 100 blocks and 100 draws from the lottery. We use a random beacon to sample the lottery outcome.
* Each ticket has a price $p$. If more than $t$ tickets are sold, the price is adjusted upwards in the next iteration of the lottery. Similarly, if less than $t$ tickets are sold, the price is adjusted downwards for the next iteration.
* The price adjustment is similar to the EIP1559 base fee adjustment or the PoW difficulty adjustment. It helps find the equilibrium cleaning prices. See a possible price adjustment proposal in the next section.
* We reset the price of tickets for each bundle using ticket prices on subsets of the bundle
* The redistribution happens precisely in the same way as in the auction version

### Price Adjusting (Proposal)
We propose a possible ticket price adjustment algorithm below. We model the design after EIP1559 and the difficulty adjustment of PoW. We invite the community to analyze this proposal and suggest other approaches.

There is a target amount of tickets $t$ that we want to sell. We will, at most, sell $t_{\max}=2t$ tickets. The price for the first $1.5t$ is constant, and then it increases linearly from $1.5t$ to $2t$. This ensures that if the demand does not massively change, everyone pays the same ticket price, but buying all tickets becomes increasingly more expensive. This ensures that a single bidder can only price out all other bidders by increasing its ticket price.


*Ticket price*: The x-axis is the percentile of the ticket sold. The y-axis is the price assuming $p_S=1$. Price is fixed and then grows linearly for the last quarter of the tickets

In the second plot, we show how to compute the ticket price for the next lottery iteration. It is adjusted based on whether there was an over or under-demand for tickets in the previous iteration. We ensure the ticket price at most doubles or halves between any two iterations.

* Let $t_{\max}=2t$
* Initialize the minimum price of bundle $B$ to be $b_B=\max_{B' \subset B} v(B')$ and the ticket price as $p_S=b_B/t$. That is, let the minimum price of all tickets for bundle $B$ be the maximum bid on said bundle from the previous iteration. Let the ticket price $p_B$ be the bundle price divided by $t$ number of tickets.
* Sell the first $1.5 t$ tickets at $p_B$
* The $i$th ticket between $1.5t$ to $2t$ is priced at $p_B+(i-1.5t)\cdot 2p_B/t$. That is, tickets between $1.5t$ and $2$ increase linearly in price.
* The total pricing function is $\max(p_B,p_B+(i-1.5t)\cdot 2p_B/t)$, such that the price of the final ticket is $2p_B$
* Assuming $n$ tickets, the marketplace sets the next round tickets price $p_B'$ to be $\max(p_B/2,b_B/t, n/t\cdot p_B)$, That is, the price of the next iteration's tickets are the maximum of half the old ticket price, the minimum ticket price as computed above, and the $n/t\cdot p_B$.


Plot for update function, with $n/t$ in the x-axis and $b_s=0.5,p_s=1,t=1$

## Right of first refusal for the L1 proposer (Based sequencing)
As we laid out in our [Based Espresso](https://hackmd.io/@EspressoSystems/BasedEspresso) post, the Espresso marketplace and finality gadget are most powerful when the L1 proposer is the sequencer for one or multiple rollups. The reason is that the L1 proposer can simultaneously build the L1 block along with the rollup blocks, allowing it to satisfy user intents and enable interoperability across both the rollups and the L1. This design satisfies the definition of [based sequencing](https://ethresear.ch/t/based-rollups-superpowers-from-l1-sequencing/15016).

If we run the marketplace lottery within the lookup time of the L1 proposer, then the L1 proposer can participate in the lottery like any other potential sequencer. However, this still does not guarantee that the L1 proposer will win the sequencing rights, as it might get unlucky in the lottery. To alleviate this problem, we use a simple idea: give the L1 proposer a *right-of-first-refusal*. After all the lottery tickets have been purchased for a particular slot, the L1 proposer can opt to buy out all the tickets for a winning bundle (or multiple bundles). This gives it the exclusive rights to build the L1 block *and* the rollup blocks for rollups within that bundle. The right-of-first-refusal does not require any changes to the L1. Only that the L1 proposer optionally takes this so-called right of first refusal. The L1 proposer would reimburse the owners of the winning tickets for their tickets plus an optional surcharge.

## Analysis
We now analyze the different properties of the marketplace and whether they achieve the desired goals laid out [earlier](#Espresso-Marketplace-design). We give informal arguments, but the analysis of each property deserves further study and research.

### Optionality
Optionality ensures that an honestly reporting rollup will receive more revenue from the marketplace than it could have generated on its own. This is achieved by the rollups' ability to set a reserve price. The rollup is not allocated to a marketplace sequencer if no bid clears the reserve price.

### Efficiency
The marketplace is efficient if it allocates the sequencing rights of a rollup to the sequencer that values it the most (perhaps as part of a bundle). This guarantees that if two rollups have shared sequencing complementarities, they will necessarily be allocated together. We make the simplifying assumption that all bidders in the marketplace view all goods, i.e., all rollup sequencing rights, as complements. The justification is that a sequencer controlling multiple rollups can always resell the individual sequencing rights.
We first analyze the efficiency of the [auction variant](#Combinatorial-auction) of the marketplace. The combinatorial auction picks the allocation that maximizes the auction revenue. This winner determination is equivalent to the efficient allocation *if* all marketplace participants are honest. While we do not claim that the marketplace is entirely incentive-compatible, we postulate that the combinatorial auction still delivers a highly efficient outcome in equilibrium. Testing this hypothesis requires an equilibrium analysis. However, it was [shown](https://www.ifi.uzh.ch/ce/publications/Core_Payment_Rules.pdf) that in a wide range of domains and under almost any payment rule, combinatorial auctions are highly efficient in equilibrium.

Additionally, we do not run a combinatorial auction but a lottery. A lottery is isomorphic to a pay-as-bid auction where multiple bidders (who buy lottery tickets) pool their funds together to form a single bid with a proportional allocation. Note that while this can lead to lower revenue it does increase the diversity of winners. As a simple example consider an infinitely divisible good being sold, where both bidders have value $1$ for the good. In a second price auction one bidder would win every unit and pay $1$, i.e. its value. In a pay-as-bid auction with proportional allocation (i.e. a lottery) each bidder would get $0.5$ units and pay $0.25$. The reason is that the bidder makes $0.25$ in profit. If they were to bid $0.25+\delta$ they would win $(0.25+\delta)/(0.5+\delta)$ of the good and pay $0.25+\delta$ for a profit of $(0.25+\delta)/(0.5+\delta)-0.25-\delta$. This is maximized for $\delta=0$. This shows that bidding $0.25$ is an equilibrium (it is the best response to the other bidder's best response) and that in equilibrium a) both bidders win half of the time and that the revenue is lower than in the winner takes all auction.
### Stability
The marketplace is run as a *repeated* game, selling essentially the same good each round. This should significantly improve stability, as whenever the equilibrium is reached, the pricing of bundle lottery tickets should stay constant, as both the goods and the bidders remain essentially identical.
### Anti-Monopolization and Censorship Resistance
The marketplace inherently helps decentralization as it enables rollups, which today almost entirely use centralized sequencers to pass off the sequencing rights without having to relinquish the sequencing revenue. Additionally, we designed the mechanism to be a lottery instead of an auction. The key motivation is that multiple bidders can buy lottery tickets for the same rollup (or rollup bundle). The sequencing rights will be randomly split between all the lottery tickets. However, this begs an obvious question:
*Why wouldn't the bidder with the highest value buy all the lottery tickets for a particular rollup?*
We answer this question with multiple arguments:
1. Bidders may only want a limited amount of sequencing space. This is especially the case when bidders, i.e., sequencers, have private order flow, which they can use to fill some but not all blocks profitably.
2. Bidders with limited capital can still participate in the lottery but not in the auction.
3. Some bidders may be altruistic or irrational and bid higher than their sequencing revenue to include censored or otherwise disadvantaged transactions.
4. It is clear that a lottery should not be worse than a plain auction, as an auction winner can always buy sufficiently many lottery tickets to get the same economic exposure as in the auction.

Overall, this question deserves significantly more investigation, but point 4 is likely the strongest argument. The same issue arises in execution tickets and is discussed under multi-slot MEV [here](https://ethresear.ch/t/execution-tickets/17944). Execution tickets use a simplified version of this design, where only a single sequencing right is sold.

### Incentive compatibility
We do not claim that this mechanism is incentive-compatible.
The unique incentive-compatible and efficient mechanism is the famous VCG mechanism. However, there are many [practical and theoretical reasons](https://milgrom.people.stanford.edu/wp-content/uploads/2005/12/Lovely-but-Lonely-Vickrey-Auction-072404a.pdf) why the VCG mechanism is often not the best choice in practice. The VCG mechanism does not even guarantee that the market is balanced, i.e., the sellers (in our case, the rollups) receive at most as much as the buyers (sequencers) bid.
Despite this, we hope that the repeated nature of the mechanism will enable participants to execute a winning strategy efficiently. To aid the repeated nature of the auction, we propose a smooth [price update rule](#Price-Adjusting-Proposal), which smoothly adjusts the lottery ticket price from round to round if there is over or under demand. This update rule aims to aid in price discovery and equilibrium finding.