# CAMCOS Spring 2022 Project - Rollup Pricing Models

Slides: https://docs.google.com/presentation/d/1Pbugs53RuXZUQEFrF89Zw04wLhDccqC6M_xWp6mD-DQ/edit?usp=sharing

## Introduction

**Ethereum** is one of the most widely-used blockchains in the world; as such, it constantly faces scaling challenges. One of the leading paradigms that targets scaling is **L2 rollups**, which are protocols that are built on top of the base Ethereum (**L1**) chain by aggregating and compressing transactions, executing them on a virtual machine on a different layer.

Abstractly, an L2 protocol's implementation involves **operators** who operate the L2 protocol and interfaces with L1. Even without L2, L1 operation on Ethereum (or any other blockchain) requires some sort of market to incentivize the creation and transcription of user transactions. Each L2 protocol typically needs to have:

- a selection of **services**; the most vanilla example of a L2 rollup service is the L2 operator "trying" to include transaction data into an L1 block. More services, at possibly higher cost, would include services such as including a transaction at the beginning of a block, or guaranteed inclusion of a transaction in the next N blocks;
- a **pricing model** for these services; as each user of an L2 rollup can theoretically choose to directly interact with L1 or with other L2 protocols, the L2 protocol needs to come with "fair" pricing models that incentivize the users to use its cervices while also incentivizing the L2 operators to provide their services.

In our work, we will look at different designs of L2 services and pricing models. After some preliminaries on L2 concepts, we analyze these designs through abstracted versions of popular existing L2 protocols and comment on the tradeoffs of different decisions. While we primarily work with L2 rollups as the guiding protocols, our insights should be applicable to fairly general classes of L2 protocols and to even non-L2 protocols that have similar incentive structures, such as Flashbots.

## 1. Preliminaries

### 1.1 Layer-1, Layer-2, and Operators

At the most fundamental level, a **blockchain** is a state machine where different users can submit state updates called **transactions**. Transactions can do many things (add users, define abstract registers, run **smart contracts** (informally, "software" saved on the blockchain that can be executed later), but the most common transactions are **simple transactions** [^28], which are transfers of ETH from one user to another with low structural overhead.

Typically, users send transactions they want into a common **mempool** with different **fees** (user-supplied tips), and having **miners** collect and publish transactions into **blocks** (bundles of transactions) with some sort of greedy algorithm where the minors collect the transactions with the highest fees. We can consider the protocol that governs block creation the **layer-1 (L1) protocol.**

A **layer-2 (L2) protocol** is simply a set of rules for a system designed to take some of the load of the L1 blockchain (aggregating transactions into blocks, computing state changes, etc.) "off" of the L1-chain. Typically, a L2 protocol is implemented as a smart contract (one for simplicity; thought it could be several interlinked smart contracts in practice) on the L1 network. The users running the L2 protocol are called **operators**, who play a similar role as L1 miners, though the L2 protocol are themselves users of L1. We use "operators" as a catch-all term, as different designs might call them different names, such as "operator," "node," "sequencer," "aggregator," etc. or have several different typers of operators in the same protocol. Typically, a smart contract the protocol places on L1 establishes an address as the operator of the L2 or allows the protocol users to link themselves to their L2 identity as operators.

The operator(s) are incentivized to follow protocol in two ways, very similar to how (L1) blockchains work in general:
- operators are *rewarded* for doing things correctly, such as having transactions included in the L1 chain. This is similar to how miners receive block rewards in Bitcoin or Ethereum for successfully creating a block.
- operators can be *punished* for provably deviating from design or failing to meet guarantees. Typically, being an operator involves depositing some funds on L1, and when an operator is found to have broken one of the rules they are **slashed**, meaning that the operator loses some portion of the deposit. This is not unlike the security deposit a renter might make for an apartment.

### 1.2 Rollups

Blockchain technology is affected by massive limitations in scalability[^1]. Increasing the transactional throughput of blockchains is the primary focus of blockchain research today [^2]. While the general definition of "L2 protocol" contain many different types of goals and implementations, we will primarily be focused on **rollups** [^29], which are L2 protocols where transactions are executed outside L1 and then the transaction data are included in L1 blocks. Loosely speaking, L2 rollups "roll up" many L1 transactions into more compressed forms.

Roughly speaking, there are 2 families of rollups [^2]:
- **zero-knowledge(zk)-rollups** roll-up transactions off-chain and submits the transactions along with **validity proofs** that validate their correctness. These are similar to "signatures" in that they can be confirmed quickly, but creating the proofs are relatively expensive[^3].
- **Optimistic rollups** do not supply validity proofs and are more focused on speed. In exchange, there needs to be protection against invalid / **fraudulent** behavior encoded in the transactions. Optimistic rollups use a system of **fraud proofs**, which involve users proving the existence of fraudulent transactions to the blockchain and the resolution of those challenges on the L1 main chain[^3].

In (most implementations of) both rollups, the efficiency comes from the transaction data being written to Ethereum as calldata [^13]. We "black box" this and other implementation details in our work. Our main requirement is simply that the rollups offer savings of *gas*, which we now review.

### 1.3 Gas and EIP-1559

As we study pricing models, it is important to understand the pricing models of the user/miner market on L1. Like Bitcoin, Ethereum started with the following simple design:

1. users submit transactions; each transaction has a **gas limit**, which is a measure of the complexity of the computation it does on the Ethereum "virtual machine" (EVM), and a user-supplied **tip** per unit of gas. These transactions are shared over a peer-to-peer network, and the set of outstanding transactions are typically refered to as the **mempool**.
2. miners collect, up to a maximum gas limit per block, of transactions ordered by the tip to them; they then mine the block (using the well-understood protocol of **proof-of-work** [cite]). When successful, they are rewarded by the tips of all transactions included in the block plus a per-block **block reward**.

In light of the L2 analysis to come, one can think of this as a market where the miners play the role of "operators", who are competing with each other to put down blocks to be accepted by the main protocol.

In August 2021, the **Ethereum Improvement Proposal 1559 (EIP-1559)** introduced a new system. This system's main intention was to create a fixed fee for each block while allowing the block sizes to be able to flucuate appropriately to deal with the network's congestion dynamically. [^16] The above design is then changed into the following:

1. users still submit transactions; each transaction has a **gas limit** and the user still supplies a **max fee** which must be at least the **basefee** (see below).
2. the protocol computes a **basefee** that updates every block with the function: $b_c = b_p * (1 + 1/8 * \frac{g_p - g_t}{g_t})$. Here, $b_c$ is the current block's basefee (with units of fee per gas), $b_p$ is the parent block's basefee, $g_p$ is the parent block's amount of gas, and $g_t$ is the fixed gas target for each block. [^16] The basefee increases for the block if the amount of gas in the parent block is higher than the fixed gas target, and decreases if the parent block's gas is lower than the gas target.
3. When a miner picks up a transaction into a block, the user pays the entire amount of the max fee. Out of this, the basefee is **burned** (destroyed permanently), and the miner gets all the tips on top of the basefee. As an example, if the user offers a tip of 300 gwei and the basefee is 200 gwei, the miner pockets 100 gwei and the user loses 300 gwei when her transaction is accepted.

The target amount of gas per block ($g_t$) is 15 million gas, where the maximum block size is 30 million gas. Notice the maximum block size is double the target block size, this means we can think of EIP-1559 as automatically adjusting based on the demand of the gas resource, with a "slack parameter" ($\frac{maximum}{target}$) of 2x.

In our work, when relevant, we will consider the consequences of EIP-1559 on our pricing models (typically in the context of having a L1 base fee that an operator would have to pay to put some transactions on L1). While we put less emphasis on it being a work-in-progress, we will also consider the ramifications of **multi-dimensional EIP-1559** (to be discussed later) when possible.

## 2. Basic Revenue and Pricing Models

Recall that the two main roles involved in an L2 protocol are **users**, who send transactions to the operators, and **operators**, who take these transactions and interface with L1. Operators need some incentive to participate, especially because they are going to be responsible for paying L1 fees to get their user transactions included. This question motivates us to study different **pricing models** (an explicit calculation of how much money the operator should charge, usually implemented as parameters of the L2 protocol).

In this section, we start the basic analysis of the pricing model of these protocols. Our main guiding principles are:
- **simplicity**. Most notably, we abstractize the protocol into a single "operator." Later work can focus on multiple operators and having different roles.
- **incentive-compatibility**. In particular:
- the operator "generally" wants to make money on every transaction. We do not need this to be strictly true on every transaction as this can be easily seen to cause very limited pricing models; also, in the operators' utility can be dominated by long-term gains from having many people use the L2 protocol.
- the users generally do not want to be overcharged; again, this is not always necessary as sometimes there are other reasons to use an L2 (anonymity, etc.) that might incentivize a user to use it instead of L1.

Our approach is to provide a parametrized model of the revenue to the operator and then discuss how the parameters would be specified given different tradeoffs. We will then compare and contrast our claims with the pricing models in existing L2 protocols.

### 2.1 Protocol Setting

First, we need to pick a parametrized family of protocols before giving a price model. We start with a basic design that we believe captures the essentials of rollups:
1. **Users** and an **operator** participate in this protocol. L2 users want to have their transactions included and the operator will collect these transactions and send them to L1.
2. First, each participant (both users and operators) have some concept of a balance on L2 (possibly done on L1 as a transaction to a central account associated with the L2 protocol). Unless otherwise stated, when we say "giving" or "receiving" money, we mean these operations take place on the L2 ledger.
3. During each block creation phase of L1, the L2 users can send the operator one or more transactions; each transaction $X$ contains:
1. some data (irrelevant to the price model) and
2. a fee $F_X$. While the tip is a single number, it can be approximated as a function of different variables (such as the L1 base fee or a "default" constant fee for L2 inclusions), and this breakdown can be given to the user through the client (such as how Amazon would show a breakdown of your single payment as a sum of a cost, a tax, and a delivery fee, but from the protocol perspective you've just sent Amazon a single fee)
5. The protocol tries to put batches of these transactions into L1 every **cycle** (an abstract notion of time which could be e.g. a number of seconds or a number of blocks). An operator will choose to collect a subset of the transactions and put them into a batch $B$. Then the operator will interact with the L1 miners to include $B$ into L1 before the cycle is up. We call what the operator loses here their **(operator) cost function** $C_O$.
6. When $B$ is included in L1 (as a transaction, a subset of a block, or even an entire block) the balances of the users and operator changes:
1. for each transaction $X \in B$, the L2 user loses some cost which we call the **(user) cost function.** By default, this is just her fee $F_X$.
2. The operator receives some payoff which we call the **(operator) revenue function**. By default, this would be $R_O = \sum_{X \in B} F_X$.

The above is a representative toy model / abstraction meant to focus on only the aspects of protocols relevant to pricing:
- For example, our basic model does not mention concepts such as the slashing of operators for fraudulent activity, which would involve something like having the operator first place some amount on L1 as deposit and then allowing defrauded L2 users to submit fraud proofs to a smart contract on L1 that would slash (destroy) part of the deposit.
- Also, in item (2) above, we are not concerned with how people exit or enter the L2 protocol (in practice, probably some L1 transactions involving a smart contract), since it's not relevant to the pricing model.

### 2.2 Revenue, Cost, Profit

Given such a protocol, studying the pricing model requires studying the following interrelated concepts for the *operator*:
- **revenue**: the function $R_O()$ in (7) above, which is the total income that the operator obtains by providing their service.
- **(operator) cost**: the cost the operator pays in L1 to get the batch included.
- **profit**: the difference between the above numbers; operator cost can be positive or negative. We assume the operators are fine as long as the profit is above zero on average

Suppose the operator creates a batch $B$ of transactions. Our main **revenue** model is:
$$ R_O = \sum_{X \in B} F(X).$$
A couple of considerations:
- The **pricing model** essentially comes down to prescribing $F_X$. We can imagine that the user interface would contain an instruction saying "you should probably pay around / you must pay at least this price...". In the next subsection we will explore the pricing model.
- We will assume a dual **(user) cost model** of $C_U(X) = F(X)$ for each transaction $F_X$; notice we have alternative options, such as refunding the user for overpaying, where the fee we price the user with our pricing model may not match what they actually end up paying.
- recall that the "operator" plays the role of the entire protocol, so when we say "operator revenue" we mean revenue that can be split up between the different roles that may exist within the protocol. This puts a separation between the protocol vs. user fee pricing problem (which we are interested in) and the revenue allocation problem within the protocol (which we are not)

Our **(operator) cost model** is
$$C_O = G(B) * f_C. $$
In this equation:
- $G(B)$: this is the amount of "real gas" that the batch $B$ ends up consuming on L1 *using our L2 protocol.*
- In an L2 protocol where we simply batch the transactions as actual L1 transactions, $G(B)$ should be the sum of the (L1) gas costs of the transactions in $B$ and there would be no "saving" in gas.
- If our L2 protocol doesn't involve changing L1 state and simply writes a single transaction to L1, such as a merkle root of some state transition on L2, then $G(B)$ would be very small (for example, the gas required for a single write operation).
- $f_C$: this is the fee (in units of Ether per gas) that the operator pays from putting the batch on L1. Typically, this should be a bit above the EIP-1559 basefee at the time of the write.

Our **profit model** is then
$$P_O = \left(\sum_{X \in B}^n F(X)\right) - G(B) * f_C.$$

| Variable | Meaning | Given By |
| ------- | -------- | -----------------|
| $F(X)$ | user fee | the users, at transaction submission time |
| $G(B)$ | (compressed) gas usage | protocol design, as a function of $B$ |
| $f_C$ | L1 inclusion fee | the L1 market, at L1 inclusion time |

Our basic model can be generalized:
- it is possible, especially in regimes where computation is costly/hidden, to include the cost of slashing or frauds in the cost model. For our basic model, we can assume that the operator has enough bandwidth to simulate the EVM computation and avoid frauds altogether.
- we can give a (protocol-dictated) multiplier on how much of the collected fees to keep for the specific operator. The rest could e.g. go into a central account for the protocol itself and/or be distributed among future operators. This would change the revenue model to $$R_O = k_R \left(\sum_{X \in B} F(X) \right),$$ where $k_R$ is a number somewhere near $1$.
- right now, we have set up a game where the money changes hands directly from the users to the operator. We can also have the protocol itself to have a separate deposit that can be used to keep some shared resource for rewards and punishments. As an example, we can give an "inclusion award" $r$, somewhat like a block reward for miners, as a per-batch reward to the operator. This would be changing the revenue model to $$R_O = \left(\sum_{X \in B} F(X) \right) + r.$$

However, our goal is to *make the simplest model possible that captures most of the important considerations,* so we do not include these features right now. (as an example of the expressiveness of the simple model, we can already do something like the inclusion-award by just having $F(X)$ incorporate a per-transaction flat tip, which in effect does the same thing for the operator)

### 2.3 Basic Price Model - First Draft

We are now ready to give a price model. Recall this is equivalent to producting a price function that can be computed by the user as a default price for what their actual fees $F(X)$ should be. In practice, even if we provide a "flat price", $F(X)$ is influenced by the market demand (for example, the users may compete with each other), but our first step is to assume that we are good at hitting some sort of base price, as how EIP-1559 is designed to keep gas costs near the basefee under most situations that don't involve rapidly-increasing demand. Our ideal, such as with EIP-1559 as analyzed by Roughgarden [^27], is to have a **posted-price** ("take-it-or-leave-it") mechanism.

To start, we want to break down $G(B)$ and $f_C$ and compare them to other numbers we can control. As a first approximation, we assume that
$$G(B) \approx \sum_{X \in B} G(X).$$
In other words, we assume that $G(B)$ equals the sum of some "per-transaction" gas usage $G(X).$ This, while intuitively true, is only an approximation. For one, we can include our batch $B$ as one or many transactions. This will affect the overhead cost differently. Also, gas costs depend on ordering at batch-time. As a simple example, maybe two transactions are "identical" in that they both have a user depleting some finite resource (say a token). Then the first chronological transaction will succeed while the second transaction will fail ("revert") and thus use a different amount of gas, and the opposite would happen if we switched the order.

The big picture here is that while we want to (and people in practice do) think of gas usage as a function of the transaction $X$ "in isolation", in reality gas usage is a much more complicated joint function of the transaction and the state of the blockchain, *including* which transactions were included before $X$ in the same block that $X$ is introduced. This is why in Ethereum L1 transactions users give a *gas limit* as opposed to an exact computation of gas [^4]. To keep things simple, we assume that we are in a setting where this approximation is good enough.

Now, it is clearly important to use the current L1 basefee as an input to the pricing model, so let's define $f_b$ to be the current L1 basefee. In particular, $f_C$ (the cost the operator pays to get included in L1) really "should" just be around $f_b$. However, we should probably overcharge a bit, because there is potential for the basefee to increase (specifically, between the time that a user transaction is sent to the operator and the time the transaction is included in L1) and we want to shield the operator from that risk. One way to implment this is to introduce a "premium" for the variance of the basefee in our price model.

With this setup, the following is a natural "first draft" of our price model:
$$ \text{suggested } F(X) = G(X) * k * (f_b + f_t),$$ where
- $k > 1$ is a multiplicative premium to cover the variation of basefee, as just discussed. This can be thought of as the users paying extra to benefit from L2 solutions. [^23] [^26]
- $f_t$ is an additive tip / premium. This serves a similar role as $k$ in that it is protection against variance and a source of value for the operators. Together with $k$, you can think of these two parameters as providing a "safe" linear function of the estimated basefee. We can simply use just one of them, but having both provides some conceptual flexibility.

**Example.** Let us start with a simple case where all the transactions are identical (say a simple transaction) and inclusion into L1 is stable.
1. For simplicity, we say that there are >> $100$ pending transactions (all simple costing $21000$ gas) in the L2 mempool and the operator wants to batch $100$ of them.
2. We assume for all such transactions $X$, $G(X) = 2100$ (in other words, there is a "compression" of $1/10$ when we use the rollup versus not), and we set $k=2$ and $f_t = 1$.
3. Then our price model for any of these transactions $X$ is $$\text{suggested } F(X) = 2100 * 2 * 21 = 88200 \text{ gwei}.$$
4. We suppose that on average, the users pay $16800 \text{ gwei}$ higher than suggested, corresponding to "tipping" $4$ gwei/gas on top of the suggested $F(X)$ for $25$ gwei/gas as opposed to $21$. This gives $$F(X) = 2100 * 2 * 25 = 105000 \text{ gwei}.$$
4. Suppose the current basefee is $f_b = 20$ gwei/gas. Upon submision to L1, the basefee had increased to $22$, and the actual cost (per gas) the operator had to pay was $f_C = 24$.

Under these assumptions,
1. the revenue to the operator is $100*F(X) = 10500000$ gwei.
2. the cost to the operator is $100*2100* 24 = 5040000$ gwei.
3. the profit to the operator is $8500000-5840000 = 3780000$ gwei.

It remains to show from the user perspective that they should actually use the L2 from a pure cost perspective (not taking into account other potential reasons such as privacy etc.).
1. if they used L1, each user "would have" paid $21,000* 24 = 504000$ gwei. (assuming they have the same ability as the L2 operator to pick the right tip)
2. instead, they end up paying $C_U = F(X) = 105000$ gwei.
3. therefore, each user saved about $80\%$ of their costs from simply using L2 instead of L1.

We can conclude that, at least in this example, such a scheme is quite incentive-compatible.

### 2.4 Basic Price Model - Second Draft

If we plug our basic price model into our profit model, we get
$$ P_O = \sum_{X \in B} \left[ k * G(X) * (f_b + f_t) - G(X) * f_C\right].$$
We can think of this as a sum over the profit "per transaction $X$" of
$$ P_O(X) = k * G(X) * (f_b + f_t) - G(X) * f_C = G(X) \left[ k(f_b + f_t) - f_C\right].$$
The parameters the operators can control are $f_t$ and $k$. Thinking of $f_b$ as the primary input given to us by the state of the blockchain, we can think of this situation as choosing a linear function of $f_b$ so that the above quantity is almost always positive, but not to be too positive (read: greedy) so that the users are also incentivized to participate.

Recall $f_C$ is what the operator pays to the L1 miner. This means $f_C = f_{b'} + f_{tm'}$, where
- $f_{b'}$ is the basefee at the time the operator submits $B$ to L1. In particular, it might have fluctuated from its initial value $f_b$, which is set at the time the *user* submits $X$ to L2.
- $f_{tm'}$ is the tip the operator pays to the L1 miners on top of the basefee to be included, since the operator is playing the role as a user in L1.

This motivates us to (especially considering $f_b \approx f_{b'}$) also break down $f_t$ into two parts:
- the tip the user "allocates" (through the protocol's suggestion/enforcement of their fee $F_X$) to the L1 miner. We call this $f_{tm}$ to denote it going to the *miner.*
- the tip the user "allocates" to the operator directly. We absorb the constant coefficient $k*G(X)$ into it and call it $f_{to}$;

The reason we absorb the coefficient is to stress that $f_{to}$ is a flexible choice that might not depend on $G(X)$ directly, whereas for $f_b + f_{tm}$ it makes structural sense to bundle them with a coefficient of $k*G(X)$ as $G(X)$ would be the estimated L1 gas. The two really play quite different roles. Putting this together , we have rewritten our per-transaction price model as
$$ \text{suggested } F(X) = k * G(X) * (f_b + f_{tm}) + f_{to}$$
and profit model as
$$ P_O(X) = k * G(X) * (f_b + f_{tm}) + f_{to} - G(X) * (f_{b'} + f_{tm'}). $$
- We can think of $f_{tm}$ and $f_b$ as approximations of $f_{tm'}$ and $f_{b'}$ respectively, so there is an estimation problem here (of $f_C$) that is essential to our problem.
- It seems reasonable to control $k > 1$ and $(f_b + f_{tm}) \geq f_C$. If on expectation these are both satisfied without too much variance, then the operator would probably consistently make money. $k < 1$ seems like a losing proposition to the operator, but big enough $k$ might make up for $f_t$ being too small.

### 2.5 Tweaking Parameters

With our second draft, we have broken down the parameters we have control over into some fairly independent parts with clearer meanings:
- $k$, a multiplicative premium to the operator
- $f_b + f_{tm}$, the "cost of work" meant to cover the operator interacting with L1
- $f_{to}$, a linear premium to the operator.

We now discuss these parameters separately.

#### 2.5.1 Tweaking $k$

On first glance, it seems that $k$ can be arbitrarily set, but there is one concern we have not touched yet, which is the incentive of the user.

For every $X$, we define $g(X)$ to be how much gas $X$ would cost as a user's "secondary option." This is a necessary notion for us since we need to know what the upper bound price would be for a user to prefer not using the rollup at all (else we would get into the situations of the L2 rollups charging arbitrarily high rates). In a non-competitive market, we can think of this as the gas cost if $X$ were encoded as L1 transactions instead. For simplicity, we make this assumption going forward as a useful boundary case (in a competitive market, with lots of rollups around, this might asymptote to be close to $G(X)$). We write the relationship between $G(X)$ and $g(X)$ as $$ G(X) = c(X) g(X),$$ where we call $c(X)$ the **(gas) compression rate** for $X$, which we can assume to be at most $1$.

From the user's perspective, the counterfactual is to pay $g(X) f_C$, which is how much it takes for the user to get the computation into L1 as their secondary option (one could argue that maybe the operator is better than the user at finding $f_C$ so we shouldn't be using the same value, but this is a good enough first-order approximation). Thus, we can estimate that the user is incentivized to use our L2 protocol instead if $G(X) * k < g(X),$ or if $k < \frac{1}{c(X)}.$ Combining the operator's and the user's incentives gives
$$ 1 < k < \frac{1}{c(X)}.$$

On one extreme, the "best estimate" price to the user would be to set $k = 1$ and $f_{to} = 0,$ but this would be unfair to the operator who is now not incentivized to participate, since they are shouldering the costs for the variance of $f_C$. In fact, what we have is a type of bias-variance tradeoff where the operator should pick up some extra expected value in return for the variance.

Overall, it helps to think of $k$ as a choice of how much of the total "gains from gas compression" to keep for the protocol in a positive-sum game. In some sense, the users and the operators are splitting a cake created by each transaction created from the compression with total value roughly $$(k-1) G(X) * f_C,$$ and we want to give both of them enough of the cake to make them happy.

#### 2.5.2 Tweaking $f_{to}$

Recall that our price model is $k * G(X) * (f_b + f_{tm}) + f_{to}$, and our $f_b$ and $f_{tm}$ correspond to the part of the user fee that "pays for inclusion in L1". The remaining term, $f_{to}$, can be thought of as a flexible number that can mean many things depending on our interests and intentions:
- if we think of it as additional protection against the deltas of $(f_{b'} - f_b)$ and $(f_{tm} - f_{t'})$, we can model it by looking at the historical variance of $f_b$.
- if we think of it as a "service fee" for the operators, then we can solve backwards for it given some desired level of revenue for the operators, and there is no obvious principled way of deciding what this fee would be otherwise.
- we can just set $f_{to} = 0$. This corresponds to continuing in the tradition of EIP-1559 by giving the users the estimates for $f_C$ (the $f_b + f_{tm}$ component) as a "base price" and hoping the remaining first-price auction with $f_{to}$ is small in comparison.
- we can use this as an opportunity to provide different levels of urgency for the L2 users, where we propose different $F(X)$ corresponding to different $f_{to}$ depending on the user setting their own level of need. For example, the users can self-sort into "low / median / high" priority, and be suggested different levels of $f_{to}$ (reflected in $f_t$).

Thus, we see that dealing with $f_{to}$ is somewhat orthogonal from $f_b + f_{tm}$ and has a lot of flexibility. Like $k$, as long as it isn't too high to make this L2 obviously worse than other alternatives (like L1) this will not be a big issue in terms of incentives.

We offer a specific example of how to approach $f_{to}$ that has a nice "recursive" nature and fits with the existing practices, which is to *price $f_{to}$ itself as a basefee.* Thinking of the L2 rollup as its own blockchain, the natural way to price $f_{to}$ in a manner analogous to EIP-1559 would be:
1. set $f_{to} = G_2(X) * f_{b2} + f_{to'}$.
2. Here, $G_2(X)$ can be seen as a "Layer 2 gas usage" corresponding to the user using the L2 protocol's services. Notice that it is completely natural to just use the corresponding L1 gas usage as a proxy (including the compression premium $k$), which corresponds to the simple $f_{to} = f_{b2} + f_{t2}$. We just write it this way for more generality.
3. The term $f_{b2}$ is the **Layer-2 basefee** and can be updated e.g. in a similar way as EIP-1559, based on L2 usage instead of L1.
4. $f_{to'}$ is just a catch-all to cover other fees additively.

This would create price models of the form
$$ \text{suggested } F(X) = k * G(X) * (f_b + f_{tm}) + G_2(X) * f_{b2} + f_{to'}.$$
The profits models would need to be adjusted if $f_{b2}$ is to be burned, for the same reasons $f_{b}$ would be burned in standard EIP-1559. The analysis here is similar to Roughgarden[^16].

#### 2.5.3 Tweaking $f_b + f_{tm}$ as Estimation

Recall this final part corresponds to $f_C = f_{b'} = f_{tm'}$, which is the fee that the operator pays to the L1 miner at time of inclusion. Thus, we can treat this problem as an *estimation* problem for $f_C$. The most obvious way to proceed is to use some predictive model based on the history of transactions (notice we can use information from both the L1 chain and the L2 chain!) over some time period.

In our figure above, some predictive model uses the historical fee data to predict the future basefee (and/or the tip required to be included into L1). As in Etherscan[^5], where a dashboard renews the gas fee information every 15 seconds, we can think of the L2 protocol as providing a "basefee plus tip oracle" that updates at some rate, and changes the suggested/required $F(X)$ for the L2 user using the oracle for the value $f_b + f_{tm}$.

There are many approaches to the predictive model. We give a very non-exhaustive list:
- a very simple approach is to just give some standard summary statistic, such as the mean/median fees over the last $15$ blocks.
- a slight improvement would be to use a function that prioritizes latest information (for e.g. NFT spikes, where the basefee and tips can both skyrocket).
- we can use some arbitrarily complex machine learning model. In [^6], the author use one-year historical gas price to train Prophet model and the deep learning models, Long-Short Term Memory (LSTM) and Gated Recurrent Unit (GRU). In particular, the LSTM reached 89% accuracy. Thus, this is at least a reasonable approach in theory. In practice, the lack of transparency and complexity may make this a bad option, despite possibly better success at predicting basefee.
- instead of trying to estimate perfectly, we can try to overestimate; this prioritizes operators over users. For the basefee there is an actual upper bound in terms of the number of blocks, because the increase of basefee is limited per block by the multiplicative factor of $9/8$. However, there is no theoretical upper bound for the tip. We can e.g. use some statistical/machine learning algorithm and then take a 95% upper bound of the result.
- we can also *underestimate*, which prioritizes users over operators. A natural underestimate is to just use $f_b$, which one can think of as setting $f_{tm} = 0$. In this case, the L2 operator is simply claiming to take the entire cost of the tip, though she may still be very safely positive thanks to $f_{to}$ (which can be raised arbitrarily) or high $k$. When $k$ and compression factors are high, this is a very viable option to attract users seeking low fees.

It is worth mentioning that we may want to do more than just predict $f_C$ with the same predictive setup. Not only do we have L1 data, we also have L2 data (keeping track of users' $F(X)$ that weren't included, etc.) that can give a better idea of what $F(X)$ to specify (or even to account for special cases, such as NFT drops, etc.). The key point is that the process for which we suggest $F(X)$ to users is not an on-chain operation, so it can involve arbitrarily complex operations as long as it becomes a simple oracle for the L2 users to use.


#### 2.5.4 Tweaking $f_b + f_{tm}$ variation: Inclusion-time Pricing

We now give a natural variation of our basic model to cover another family of approaches to pricing. In the model we have so far, users are paying at *transaction submission time*, since they are given estimates of $F(X)$ and their user cost function is exactly $F(X)$. However, another natural approach is for them to supply some estimated upper bound instead, but be charged only at *transaction inclusion time* (specifically, when the batch $B$ is included in L1).
1. The most obvious benefit of this is it in some sense skips the estimation phase; if the goal of $f_b + f_{tm}$ in our earlier section is to estimate $f_C$, we can just have it deduct $f_C$ instead of trying to guess it.
2. We can also think of this approach (abstractly, not in implementation) as giving a kind of refund; the users are specifying some upper bound on their cost (e.g. their deposit in L2) that they are willing to pay for each transaction, and money is given back to them.

Specifically,
1. At transaction submission time, the L2 users still specify a maximum fee $F(X)$, possibly guided by some protocol-supplied estimation.
2. Unlike our basic model, users are not charged $F(X)$ at the time of transaction inclusion in L1 when the operator pays the fee $f_C$. Instead, they are charged a price based on the state of $L1$ at that time. Formally, the user submitting $X$ is charged based on *re-calculating* $F(X)$ with the $(f_b + f_{t})$ replaced by some L1 information, such as:
a. $f_C + t$: what the operator actually paid to the miner plus a constant tip;
b. $f_C$: what the operator actually paid to the miner;
c. $f_{b'}$: the actual L1 basefee at the time of inclusion.
If we were e.g. using the second choice, we would replace the user cost model of $F_X = k * G(X) * (f_b + f_t)$ with $k * G(X) * f_C$.
4. We need to avoid the users "overdrawing" from their L2 deposits. The simplest way to do this is to compute some "threshhold value" $L$ at time when the operator considers *submitting* her batch to L1, and she does not include any transactions from a user whose deposit (and $F(X)$, as a first approximation) does not have enough money to pay for the case where the basefee $f_{b'}$ is at least $L$.
a. computing $L$ is similar to the estimation case: we can use anything from a simple linear function (e.g. 1.5 times the previous basefee) to some ML model based on the previous basefees.
b. especially if it might take time for the transaction to be included, we should consider the $L$ "frozen" from the assets of the user so they don't overdraw themselves if they use the L2 service twice in quick succession.

A natural way to extend this approach is to provide more resolution on exactly how much gas is saved at inclusion-time, and divide the savings between the different users who submitted transactions. This seems to be a tricky problem and may be hard to make incentive-compatbile [^30], which is another reason we stick to our simple model where we just consider heuristic compressions $c(X)$.

The main benefit to this appraoch is that it may attract more users as the protocol can now claim very enticing offers, such as promising that the users will only pay the base fee at the time of L1 inclusion, and no more (not even a tip). In other words, this implementation has "zero L1 price slippage."

The main problem with this proposal is a dichotomy of two difficulties:
- if we consider the tip to the miner at the time of inclusion (so this would include both the approaches of using $f_C$ and $f_C + t$ above), this sets up an off-chain agreement between the operator and the L1 miner: the operator can propose to set a very high $f_{t'}$ for the miner and e.g. split the high fee between the miner and the operator. Then the user will be charged an arbitrarily high fee (possibly protected by $L$, but the point is that the operator is not disincentivized to increase this number). Thus, it is not incentive compatible to have $f_{tm'}$ be charged at the time of inclusion. Two nuances:

- This argument extends to cases where we have any nontrivial *function* of $f_{tm'}$ be considered at the time of inclusion.
- This problem can be ameliorated: if there is a reasonable limit to the amount of OCA that can be generated, and/or we disallow high tips (e.g. tips higher than some statistic based on tipping history). However, with these types of fixes another problem appears: users are not incentivized to differentiate themselves above the maximum limit, so many users might just end up sending the maximum and this just becomes a flat tip model. In any case, we would need to trade some higher complexity for it.
- The above analysis effectively dictates that the price should only depend on the basefee $f_{b'}$. So that remains us to consider just something like recalculatingthe suggested $F(X)$ with $(f_b + f_t)$ replaced by $f_{b'}$, the basefee $f_{b'}$ at the time of the inclusion. By default, this would mean the operator is losing the tip they pay to the L1 miners. What this means is the protocol really needs to incentivize the operator with higher $k$ and $f_{to}$. In the limit that $k$ approaches $1$, without very high $f_{to}$ this rollup would not be incentivized to survive. It is also important to keep in mind that if we were going to do this, there is no obious benefit over the similarly generous submission-time pricing of just charging $f_b$.


Our preliminary conclusion: inclusion-time pricing is more complex and trickier to get right, with locally-solvable OCA problems. We do not recommend it unless we obtain some obvious big benefit over submission-time pricing.

### 2.6 Market Research

To see how our price model desgin compares to the practical price models in the market, we researched three leading L2 networks: Optimism, Arbitrum, and zkSync. The first two are optimistic rollups and ZkSync is a zk-rollup. First, we will briefly sketch the differences between the protocols. Then, we will compare their price models in light of our framework.

#### 2.6.1 Implementation Details

A preliminary comparison between the protocols follows:
- Arbitrum and Optimism are both optimistic rollups and thus share many similarities. However, Arbitrum seems to have better gas cost reduction (50x to 270x) than Optimism (up to 10x).
- ZkSync uses validity proofs (based on zk-SNARKs) which are more complex and require heavy computation to create. However, its validation is much faster compare to Arbitrum and Optimism. Its gas price is also cheaper compared to optimistic rollups. Optimistic Rollup, the current estimate is about 4k gas per transfer tx, post EIP2028/Istanbul. For Zk Rollup, The cost of public data per transfer tx in Matter Testnet is currently 16 bytes, which will cost 272 gas post EIP2028/Istanbul [^41]. [by how much? give sepcific samples/summary statistics]

| | Arbitrum |Optimism|ZkSycn|
| ------- | -----------|----------|--------------|
|Type|Optimistic Rollup|Optimistic Rollup|ZK Rollup
|Proof|Fraud Proof; Multi-round proofs|Fraud Proof;Single-round proof|zero knowledge proof
|Validation Time|At least 7 days| 7 days|~10 minutes[^35]|
|Virtual Machine|AVM|OVM [^10]|Some don't have EVM support|
|Reduction of Gas Cost|50x to 270x|up to 10x|~100-200x[^38]
|Gas Price|L2 gas price is set by the operator (aggregator), L1 gas price is estimated. The network charges 15% on top of the fee |L1 and L2 gas prices at that time (If the L1 gas price spikes, Optimism pays the new cost). [^8]|~ 1/100th L1 cost. It might just cost a few cents if the number of users are big enough[^15]|

The operator roles between the protocols are also different. Remember that in our framework, "operator" is a catch-all term for the entire protocol. In the comparison below, we contrast how the primary operating role works between the three protocols.

| | Arbitrum[^37] | Optimism[^36] |ZkSync[^35]|
| ------- | -----------------| ---------------- |--------|
| Responsibility |Wrap txs and send them to L1 smart contract| Verify txs and compute state pubilished by the aggregators.|Roll up txs in a block and submit the root hash of new state along with a SNARK to L1 smart contract
Operator Role|User sends a deposit to the on-chain smart contract| Anyone who posts their own bond and challenge the assertion| At this point, the operator is the server
Punishment| Deposit will be slashed| Deposit will be slashed (*) | N/A

For the punishment structure for Optimism rollup, if fraud is successfully proven, a X% of deposit gets burned and the remaining (1-X)% gets distributed proportionally to every user that provided data for the fraud proof [^42].

#### 2.6.2 Price Model

As in our price model, the compensation for all 3 protocols come from user payments included in their transactions. In summary:
- Arbitrum uses an estimated gas price and an L2 basefee.
- Optimism uses the current basefee along with a dynamic overhead cost and a fixed overhead cost to cover the variation of the basefee. Optimism also promises to pays the new cost if the L1 gas price spikes. Also uses an L2 basefee.
- ZkSync does not use a L2 basefee. The most noticable "flat fee" term is the SNARK cost.

In this section, we write these protocols' price models in our language for easy comparison.

#### Arbitrum
Our abstract "operator" in Arbitrum can be thought of as a combination of the Arbitrum network itself and its **aggregators** (users who want payment by providing services to other users). Users can choose to submit their transactions through an aggregator or Arbitrum network. The price model given below [^37]:
$$F(X)=1.15*G_A(X)*f_{b_2} + G(X)*1.15 * f_{C'}$$ where:
1. $G_A (X)$ is the gas usage per transaction X in **ArbGas**, the cost of a compution on Arbitrum.
2. $f_{b_2}$ is the base price per unit of ArbGas of an L2 transaction. $f_{b_2}$ is set by each aggreator using an Arbitrum precompile, subject to a system-wise maximum: $f_{b_2} \ge \frac{f_{C'}}{100}$
3. $f_{C'}$ is the estimated L1 gas price at the time X is included in L1. In our language, we can think of this as $f_b + f_{tm}$.
4. $G(X)$ is the L1 gas cost for transaction X to be included in L1.
5. The number $1.15$ is a cost to the user but not necessarily revenue for the aggregator. Recall that for us, the "operator" refers to the entire protocol. In this case, the additional 15\% goes to the protocol and not the aggregator[^39].

In the above model, $1.15*G_A (X) *f_{b_2}$ is called **L2 fee**, which helps the aggregator cover the cost of servicing a transaction X. $G(X) *1.15*f_{C'}$ is called **L1 calldata**. It is the fee per units of L1 calldata directly attributable to the transaction. Currently each non-zero byte of calldata is 16 units, and each zero byte of calldata is 4 units. Besides the L1 and L2 fee, users using Arbitrum also need to pay for **storage fee**, a fee per location of EVM contract storage, based on the change in EVM storage usage due to the transaction. For the simplicity of this section, we do not cover the storage fee.

#### Optimism
Our "operator" in Optimism would refer to a single party called the **sequencer**. Below is the price model that Optimism is using[^36]:

$$F_O(X)=G_O(X)*f_{b_2} + k*[G(X)+d]*f_b$$

where $G_O(X) * f_{b_2}$ is called the **L2 fee** and $G(X) *k* f_b$ is called the **L1 fee**. We look at each layer's fee separately:
1. Layer 2 fee:
- $G_O(X)$ is the amount of computation and storage that they use for each transaction X. Unlike Arbitrum, Optimism combined computation and storage gas together.
- $f_{b_2}$ is the gas price per unit of gas. Unless there is a heavy congestion on Optimism, $f_{b_2}$ is usually equal to $0.001 \; gwei$. We can observe the values of $f_{b_2}$ on the Optimism dashboard [^10]
2. Layer 1 fee: The L1 data in Optimism based on four factors:
- $k$ is a **dynamic overhead cost** which scales the L1 basefee paid by a fixed number. This number is currently set to 1.24 [^8] ($k$ covers the change in L1 gas price between the time the transaction is submitted and when it is published, as well as the income the system needs to keep it running).
- $G(X)$ as defined above is the gas cost to publish the transaction X to L1
- $d$ is a **fixed overhead cost** of adding a transaction to a batch decreases as the total batch size increases. It is denominated in gas, and currently set to 2100 [^8]
- $f_b$, as defined earlier, is the current gas price on Ethereum (at most the user will pay no more than $25\%$ expected)[^8]

Therefore, given there is no congestion and the fixed overhead cost as well as the dynamic overhead cost is still 2100 and 1.24, the price model of Optimism can be written as:
$$F_O(X)=0.001G_O(X) + 1.24*[G(X)+2100]*f_b.$$

Optimism's price model is also very similar to what we have. A small difference here is that Optimism puts a shift on the fixed overhead cost ($d = 2100$). While it is easy to manipulate the variables to force it into our framework (for example, we can just say there's an additional $2100f_b$ going into $f_{to}$, it is different enough that we find it worht mentioning. Morally, it plays the same role as $k$ or $f_t$, providing insurance against the changing of basefee.

#### ZkSync (version v1.x)

Unlike the other two, ZkSync has only one operator/server and users cannot become the operator. Its price model has an "off-chain" and an "on-chian" component[^35]. That is:
$$F_Z(X)= F_{off}(X) + F_{on}(X)$$
where:
1. $F_{off}(X) = St(X) + Sn(X)$, a sum of $St(X)$ (the cost of the state storage) and $Sn(X)$ (the SNARK generation cost). This part depends on the use of hardware resouces and is therefore invariable. Their benchmarks give estimates of $~0.001$ USD per transfer.
2. $F_{on}(X) = (k*G(X) +0.4K )*f_b$:
- $k*G(X)$ is the gas cost the vallidator need to pay Ethereum to verify the SNARK for transaction X.
- $0.4K$ is the additional gas per transaction to publish the state delta.
- $f_b$ is the current gas price in Ethereum network as defined earlier.

Now, we can rewrite ZkSync's price model as below:
$$F_Z (X) = F_{off}(X) + (k*G(X)+0.4K)*f_b$$

#### Comparision
The table below is a summary of our research on the top three leading rollups:
| | Revenue |
| ------- | -----------------|
|Arbitrum|$1.15*G(X) * (f_b + f_{tm}) + 1.15G_A(X)*f_{b_2}$ |
|Optimism| $1.24[G(X)+2100]*f_b + 0.001*G_O(X)$|
| ZkSync|$F_{off}(X) + (k*G(X)+0.4K)*f_b$
|Basic price model| $$F(X)=G(X)*k*(f_b+f_{tm}) + f_{to}$$|
|Basic price model (w/ L2 fee)| $$F(X)=G(X)*k*(f_b+f_{tm}) + G_2(X)f_{b_2} + f_{to}$$|

It is clear that the price models of the three leading rollups are very similar to the basic price model.

### 2.7 Summary

---
**Summary**:

1. we recommend having the users pay at transaction-creation time a fee $F(X)$ that is given to them as an estimation from the protocol based on an accurate estimation of the basefee plus tip ($f_C$) on L1.
2. we recommend the operator costs be recouped through higher $k$ and $f_{to}$ being set close to $0$. However, in a competitive game-theoretical limit $k$ would approach $1$ and we would need to increase $f_{to}$.
3. in the situation where $k$ is high enough that the operator is not at risk of losing money, we can consider a system where the users pay at transaction-inclusion time. This is more complex than our standard system and would be more tricky to get the incentivice compatibility correct, but does not seem to be fundamentally untenable.
4. Three of the leading rollups that exist seem to use pricing models that broadly fit our framework.
---

## 3. Rollups and Services


We have considered the most basic type of "service" that an L2 operator provides, which is to try to include transactions into L1. Slightly more concretely, we define **services** to be offers of specific outcomes involving the process of including the transaction on L2 and/or how it will be recorded on L1. These services all require tweaks to the basic pricing model.

We classify the space of possibilities for different types of services, also examining those that are already implemented in practice. Furthermore, we look specifically at how lazy evaluation might be brought to ethereum L2's in this light.

### 3.2 Accountability and Data Availability

We find it useful to differentiate the types of L2 protocols in terms of their **accountability** design and **data availability.** We define these notions below:

We loosely define **acountability** of a service as the degree that we can enforce rational operators to abide to the terms of the service. The two primary methods of enforcement are fraud proofs and validity proofs, mirroring the dichotomy of optimistic rollups and zk-rollups:

<center><img src="https://i.imgur.com/O9uwr4Z.png" width="50%" height="50%" /><img src="https://i.imgur.com/JdbJX8Z.png" width="50%" height="50%" /></center>

Examples in the real world: an immediate cash transaction is accountable[left], a queue is not[right](that is the vendor may not do anything if some one cuts).
Operators are held accountable usually through one of the following two mechanisms.
- **Fraud proofs** are 'optimistic'. This means the protocol assumes that generally sequencers and L2 users will behave correctly(sequencers take responsibility for L2 users when they publish an L2 batch). To disincentivize bad actors the protocol allows 'fraud' to be proved and submitted on L, which then punishes those responsible. There is a record of the L2 state that is observable on Ethereum L1, so if anyone sees an infraction, a punishment can be assigned to the sequencer based on the severity of the infraction. This means that users of the L2 must watch the recorded L2 state or that other people must be incentivized to check that the L2 state is reached with valid steps. The fraud proof itself consists of showing the state A before the infraction, the operation $o$ that was bad, and the state that should have been reached after $o(A)$.[^14]
- **Validity proofs** have a pessimistic implementation; this means state transitions only occur when proven. This avoids bad states but requires a mechanism to ensure the state transitions are correct. Validity proofs work by proving that the sequencer knows that a particular state is true before they publish a batch. They prove that they know a state is correct and follows the rules by outputting from a function that takes the L2 information as inputs. This output is then published with the L2 state on L1. This means that creating false transactions before hand is difficult by some probability, a metric set by the specific L2 protocol. The validity proof itself usually consists of a merkle tree consisting of verified transactions that have been divided into a batch.[^14]

Both styles of proof serve to establish a basis for trusting the operator. When a user puts money into an L2 that doesnt have any method of ensuring the rules are followed then they are essentially back to a reputation based system, which distributed ledgers are fundamentally trying to get away from. However, lack of accountability alone is *not* necessarily a deal breaker; the most basic service we outlined in Section 2 is not accountable, and it might still be a robust service to exist in the real world -- maybe operators are incentivized to participate to make money, and if they don't include transactions they start losing this source of revenue.

We define data availability as follows:
- **Data available** means that from the perspective of an L1 user the L2 state is fully recoverably recorded. Data availablity allows for lighter L2 implementations and in particular maniplation of L2 state from L1.
- **Data off-chain** means that the full L2 state is not available from L1. An off-chain L2 uses a hash or some similar highly compressed that represents it on L1. There is much greater scaling with L2's that store data off- chain. At some point lossless compression is optimal and greater scaling will require off-chain storage[^9].

The following table gives representative families/implementations of real-life rollups that correspond to the $4$ quadrants created by our two axes:
| |Data available|Data off-chain|
|---|---|---|
|**Fraud proofs**|Optimistic rollups|PLASMAs|
|**Validity proof**|Zero-Knowledge rollups|Validium|

Currently, most L2's with off-chain data and validity proofs are primarily based off of simple transactions (including token transfers). However recently Scroll published progress to a full Zero-Knowledge EVM so that limitation is more development limited than structural[^10].

new:
We consider data availability a service which aids in liveliness and reduced dependancy on distribution. The offer of this service is why we focus on rollups.

### 3.3 A Taxonomy of Services

Recall that when an L2 design chooses a paradigm of proof (fraud or validity), this forces a specific L1 smart contract design. We are looking at services for which an operator can be held accountable within a design.

The following tables considers different additions to the rules of an L2 that would add explicit support for more complex behavior on an L2. For the first table, we show extensions of the main idea of "including a transaction into a block," starting with our most basic service of simple transaction inclusion:
Services being developed on some L2 are denoted with **[x]**.
|Name|Service|Details|Target Audience / Existing Implementations|
|---|---|---|---|
|Simple Inclusion|User sends a single transaction to be included.|none |everyone|
|Sequenced|User sends a sequence of transactions, and the transactions must be included in order (although skipping transactions is okay) |More complex for operator to verify several transactions in single batch. |A game or a highly order-dependent type of software written on blockchain. Can aid in reducing the impact of L1 reorgs on L2 data structures|
|Atomic| User sends a sequence of transactions. All the transactions must be included in the same batch, if any are to be included. | (similar as above) | Paying out a contract / game / mempool to many people at once. **[x]** [^32]|
|Grouped|User sends a sequence of transactions. The transactions, if included, must be atomic and executed in a contiguous sequence. |can be a modest overhead based on number of tx, sequencer can to some extent just treat them like one large tx with 1 gas value and 1 price. most of the cost would be opportunity|A user trying to deny arbitrageurs MEV. A user trying to execute more complex order-depedent logic that might fail if other transactions intersperses with this one (e.g. some sort of logic involving a smart contract with global state that other users can influence).|
|Ordering|User can specify a position or sequence of desired transactions |Creates an explicit place to value transaction order. Extends transaction headers or needs secondary market. Adds to the batch packing knapsack problem with some orderings being parallel and some competing.|MEV, more complicated L2 apps. This exists as a service on L1 in flashbots **[x]** |
| Contingency |A user submits a transaction with a list of observalbe requirements, the batch/L2 state must fulfill these or not include the transaction |Generates possibility of significant overhead as the operator must have full node access to the enitre history as well as simulate the state changes of other transactions in the same batch. |Enables complex transactions, both enabling MEV and aiding in avoiding MEV. Can be used to create cross chain or cross L2 bridges for ease of exchange. Can be used to create instantaneuous escrow.[^33][^34] zkopru and hermez working on implementation.[^27] **[x]** |

<center><img src="https://i.imgur.com/3ReGReJ.png" width="20%" height="20%" title="A set of atomic transactions"/> This is an atomic transaction that is also grouped within the batch.</center>

We now present another table on types of features "orthogonal from inclusion" that can be mixed and matched with the previous type of services and/or each other:

|Name|Service|Notes|Target Audience / Existing Implementations|
|---|---|---|---|
|Anonymization|Varying degrees, simplist is only recording tx record not details on L1|implementation dependent some degree given by zk, also methods that don’t store data on L1| high value tx, tx with possibility of being front run, non simple tx **[x]** [^34]|
|L2 confirmation|Generates a message on/off chain to an address when the sequencer does an attempt at including the tx in a batch|message after L1 posting returned to users |urgent tx that may be canceled, cautious userscurrently indirect via sequencer feed(can move to accountable if feed is commited too)[**x**] |
|L2 confirmed to user|Sequencer generates a token that is sent to the user with signed a batch #. If the tx is not recorded in L2 and appearing on L1 the user can submit the token on L1 and recieve a slashing reward | <!-- message w/token after sequencer decides to include that proscribes a L2 batch # so a user that is not included after that point can slash the sequencer. --> Generating the token and returning it are overhead to the sequencer and requires user monitoring. | any user wanting tracking, commerce, high value tx that want to be sure things occur|
|Escape hatch|L1 smart contracts running L2 support user generated proof of some L2 ownership that allows L2=>L1 fund transfer|requires some increased complexity for zk rollups, more so for optimistic, increases cost of setting up initial L2 smart contracts on L1 but need not increase tx overhead|safety concious users, users interested in riskier/newer L2s, used by many zk rollups and some optimistic, if L1 is truly agnostic this is a strong guarantee **[x]**[^31]|
|Recurring tx|The sequencer accepts a set of transaction where the transaction is repeated is succesive blocks as user selects|adds off chain storage cost to sequencer depending on size and time constraints, can be verified after the fact that something is in sequential batches. Risky the longer time period is offered if strict guarantee. Increased tx size so that inclusion of all batched tx is verifiable. similar would be delayed or slow below|Support of anonymizing protocols, running smart contracts, proof of liveliness |
|Slow tx/lower cost|Somewhat a default behavior, this allows explicit binning for user and sequencer.|Adds offchain storage cost to sequencer but may allow them to profit off the priority fee difference over the time period. User is trading paying the storage cost for letting the sequencer place it freely but in a bounded batch#.(so distinct in that the user is getting a guarantee it will be by some batch number.) So the sequencer is also required to do some predictive work|non urgent users, cost concious users, large numbers of unordered simple tx.|
|Delayed tx|User defines a time or batch number after which they want the next batch to include their tx. Longer times require price increases or better prediction|Adds offchain storage cost, risk of L1 priority fee increases, cost of generating a token for the user(for strong guarantee). opportunity cost of inclusion at the later block for other tx.[alternatively just allow users to specify batch # for tx w/o guarantee of inclusion]|more complicated trading/MEV, L2 apps(games or automated payments like billpay)|Storage|

*The L1 smart contract contains an escape hatch allowing the direct withdrawl from L2 by a user interacting with L1.*

Some remarks:
- Anything involving guarantees of more than 1 tx has the overhead of increasing the tx size for verifiability. In most cases this probably only needs to be about a byte.
- Many of these services are orthogonal, although there is some hierarchical structure. For example, "atomic" is a strict prerequisite for "grouped".

Here is a compact version of the types of overhead associated with each transaction:

Adding most additional transaction types will include some one-time implementation cost. Some computational storage or communication overhead. Furthermore the L2 will become less efficient as the abillity to compress transaction data decreases the more unique calls that are made in a batch. Therefore L2's may be better off selecting transaction types that support only the feature set they are trying to promote. An example of this is existing L2's that only support simple transactions tend to have higher compression ratios. One question is how much of the advantages in compression for ZKP systems is the reduced scope and corresponding compression advantages; vs the validty proof structural advantage.

The services offered would impact the price model primarily in $G(X)$ where the interactions with other transaction types would be reflected and the additional computation would be captured. Some of the transaction type services can offer reduced prices from interacting with $C$ as having well structured data increases the compression ratio.

### 3.4 Considering the effects of adding services to L2 pricing.
Data avalability as a service allows a larger compression ratio, by going past the lossless limit. Using this allows the price for inclusion to drop. Further service pricing is influenced by the increased difficulty of ensuring liveliness. This difficulty arises from the possibility of a centralized operator ceasing to post to L1[^40]. This is problematic as it locks the funds on L2. Unless there are redundancy mechanisms such as escape hatches. These difficulties also serve to reduce the price that can be charged but are of smaller magnitude than the compression savings.

The category we describe first, transaction specific services are those that are most likely to be directly priced by $G(X)$. This is because most of them have a measurable cost in execution that is assigned to the operator. The support of certain transaction types can draw users to the L2, and enable development of dependent features that would be more costly or unaccountable in other systems.

When considering the pricing for environmental services both $k$ and $G(X)$ are relevant however $k$ is more the focus. This is because $k$ captures the effiency and long term costs of the transaction. This could alternatively be in a basefee. In both cases the environmental cost to the operator are in implementing and maintaining the features security with respect to the funds stored on L1. By offering these features an L2 operator can distinguish themselves from other operators.
<center><img src="https://i.imgur.com/QILpFQT.png" height= 40% width="40%"></center>

*See that L2 prices may compete with other operators instead of L1.*

L2 operators with some of the environmental services are also able to mitigate some of the risks associated with depositing on an L2. For instance a user requires a lower degree of trust of an operator with a solid escape hatch. Similarly considering the immediacy of finality and distributedness for liveliness are impacted by the type of proof offered and the availabilty of the data. Others have made similar observations such as Patrick McCorry[^40]. The generality of Ethereum's mainnet is its strength, but also gives opportunities for L2 operators to create service niches.

## 4. Interacting with a Multidimensional Fee Market

The intention of **multidimensional EIP-1559** is to shift from pricing a one dimensionally priced resource (gas) with a basefee to one where different resources are dynamically allocated simultaneously, each with their own basefees. This aims to more accurately price different resources used by the EVM.

### 4.1 Multidimensional EIP-1559 Preliminaries

One of the takeaways of EIP-1559 is that it can be thought of as a mechanism that automatically prices many types of resources, most dominantly EVM computation, as a single resource of gas. This concept can be generalized. As an example, real-life computer computations can use different resources (space, time, registers of one type versus another, etc.). Even a specific resource such as time can be split into sub-resources; for example, maybe all computation of a theoretical computer is done in terms of additions and multiplications, which are optimized differently; then it makes sense to split up "computation" into "number of additions" and "number of computations." In summary, we can look at resources that transactions use under higher resolution than just "gas", such as:

- computation: this is the primary resource that gas currently represents
- calldata usage: the block data that serve as parameters to function calls
- storage: writing into EVM storage
- balances changed: the number of balances corresponding to user Ethereum accounts that are changed by a transaction

| Parameter | Ethereum | Rollup |
|---|---|---|
| Nonce | ~3 | 0 |
| Gasprice | ~8 | 0-0.5 |
| Gas | 3 | 0-0.5 |
| To | 21 | 4 |
| Value | ~9 | ~3 |
| Signature | ~68 (2 + 33 + 33) | ~0.5 |
| From | 0 (recovered from sig) | 4 |
| Total | ~112 | ~12 |

Figure 1: Data usage on mainnet by parameter [^19]

The main idea of the proposed **multi-dimensional EIP-1559** [^17] design is the following: One can argue that these resources, which are all abstractly currently combined into "gas", all possibly have different limits on their burst (over a short term horizon, such as over one block) and sustained (over a long-term horizon, such as over a year) capacities. Multidimensional EIP-1559 proposes that each of the resources of the Ethereum Virtual Machine be priced seperately. The idea is then, the blockchain might be able to better handle situations with different types of demand. The multi-dimensional fee market is expected to have much rarer boundary cases of block sizes compared to the current fee market.[^17]

The client code for the user would need to update nontrivially. Whereas before there was only one key resource (the basefee) to keep track of, now there are $R$ resources. There are a few consequences that make the understanding of the market more complicated:
- there are now $2^R$ different ways each block for the basefees to increase and decrease each turn;
- the heuristic of how to put transactions into a block gets more complicated. With just 1 dimension, it is easy to do a greedy algorithm by sorting by the highest gas price; this is not perfect but is a good enough approximation in usual conditions. With multiple dimensions, especially during "surge pricing," the operators will be solving a multidimensional knapsack problem to figure out the best transactions to include.

We wrote some preliminary simulations to study multidimentional EIP-1559:

<img src="https://i.imgur.com/9t3ISWu.png" width="400" class="center"/></img>
<img src="https://i.imgur.com/xXvqehQ.png" width="350"/></img> <img src="https://i.imgur.com/PHAnZAZ.png" width="350"/></img>

Figure: the top image shows a regular basefee oscillating under a normal EIP-1559 model under some randomly-generated transactions and models of demand. The lower-left image shows multidimensional EIP-1559 with 2 resources that are completely corrleated (scaled 7:3) using the same sequence of transactions and demand as the top image, which gives identical graphs. The lower-right image shows multidimensional EIP-1559 with anticorrelated resources (again with the same sequence of transactions). Note that the unequal proportions of the two resources are "discovered" by the invisible hand of multidimensional EIP-1559.

### 4.2 Multidimensional Pricing Models

We now extend the pricing model from Section 2. In the standard (EIP-1559) case, it is the users benefit to post transactions with a "low" basefee, as the user pays less in fees to get the same transaction across (assuming the priority fee was not significant). [^7] While this concept is easy for users to understand when we only have one dimension (gas), in the muldimensional fee market, this concept gets much more complicated.

Here are the things that change for the protocol with $R$ resources:
1. Each transaction now has $R$ "gas limits." To generalize beyond that, let's call these **resource limits** $G_1(X), \ldots, G_R(X)$; there is still just one max fee $f(X)$.
3. Instead of having a basefee $b$, we now have multiple basefees $b_1$ through $b_R$, each corresponding to a resource and having its own update rule.
2. Now including a transaction will cost $f(X) + \sum_{i=1}^R G_i(X) b_i$, and the revenue of the miner would be just $f(X)$, as the amount $\sum_{i=1}^R G_i(X) b_i$ will be burned.

**Remark.** It is also possible to consider decoupling the $f(X)$. In other words, have the transaction supply one max fee $f_i(X)$ for each of the resources, and the cost of including a transaction is now $\sum_{i=1}^R G_i(X)f_i(X)$ while the revenue is now $\sum_{i=1}^R G_i(X) (f_i(X) - b_i).$ It's interesting to note that the(L1) user can give a negative tip in a resource, as long as the overall tipping is positive it will be incentive-compatible for a miner to take it! In some sense these two approaches are mathematically equivalent, but can be conceptually quite different.

Recall that our pricing model in the single-dimensional case was
$$ \text{suggested } F(X) = k * G(X) * (f_b + f_t).$$
The natural extension of this is
$$ \text{suggested } F(X) = \sum_{i=1}^R k_i G_i(X) * (f_{b, i} + f_{t, i}),$$
where we now have $R$ copies of each variable corresponding to the $k$ different resources. While most of these are self-explanatory given Section 2, we make some brief remarks on certain parameters:

- $k_i$: Recall we had a single constant $k$ designed for the sequencer to get the users to pay a premium for using the rollup, a "fair" pricing of which would be to capture the fluctuation of the basefee. A priori there is no especially bad reason to make all of the $k_i$ identical; a safe price for the operators would be based on the highest-variance basefee among all the resources. They can also be priced differently, of course.
- $G_i(X)$: even though multidimensional EIP-1559 has not yet been implemented, one can get a sense of how compressable each resource is (captured in our model by $C_{G, i}$). Refer to figure 1 which represents bytes of data used in a simple Ethereum transaction.
- $f_{t, i}$: notice that it is a bit easier to reason about what $f_{t, i}$ means if we use the "decoupled" model.

Profit Model:
$$P_O = \left(\sum_{X \in B} F(X)\right) - \sum_{i=1}^RG_i(B) * f_{C,i}.$$

The main idea is that our basic price model extends easily to multi-dimensional EIP-1559. There is much room for future work to work out nuances (for example, what to do if we have an interaction of known correlations and anti-correlations between the different resources).

## 5. Conclusion and Future Work

Our pricing model in Section 2 is a basic but also flexible framework for L2 rollups that can generalize to broader L2 services. The basic model fits many different types of rollups while allowing nuances specific to the implementations to be added. We provide some examples of these nuances, generalizations, and potential extensions, and also performed preliminary incentive-compatibility analysis.

As we look forward into the future of Ethereum and L2 services, understanding L2 services beyond simple transactions becomes important as an ecosystem of L2 (and also other services that do not quite fit inside L2, such as Flashbots, that provide related functionality) emerges. Our Section 3 is a preliminary attempt to categorize and understand the complexity of that space. We hope that our flexible pricing model can adjust accordingly for these additions. In doing so, we would need to account the more complex types of desires the users have (MEV, privacy, etc.) to do more serious analysis.

Besides the growth of service complexity, new paradigms and EIPs to Ethereum would be the most obvious place to perform extended research growing out of our work.
1. As we touch upon in Section 4, it is important to consider the potential eventual adaptation of multidimensional EIP-1559. With added priced resources, the fee market gains in complexity but our basic pricing model is able to generalize easily into multidimensional EIP-1559. In helping to understand how the multidimensional fee market would look to a user, the multidimensional EIP-1559 simulations create a basic groundwork to see how basefees correlation amongst one another can affect the price on inclusion. Future work would likely involve more assumptions about the different resources, or splitting into cases based on different implementations (as a specific example, do we have a single max size after converting all resources to gas, or do we have multiple max sizes, one for each resource? There are subtle differences for the client algorithms and also pricing models here)
2. Another paradigm that is gaining traction but we did not mention is **proposer/builder separation**[^25], the idea where **block-builders** are responsible of filling in complete block contents and a fee for the **proposer** to collect, who chooses the batch of content. Both of these roles were taken by the **miners** previously. Our work should be very relevant to studying the kind of markets that arise from proposer-builder separation. In the end, we need a mechanism that is acceptable to both users and operators, but it might be tweaked further to be incentive compatible to builders and proposers as well.

## Reference List

[^1]:<https://pdfs.semanticscholar.org/cf12/16d4421a4e4225fffd96505ec679376f6758.pdf> Nowiński, Witold, and Miklós Kozma. "How can blockchain technology disrupt the existing business models?." Entrepreneurial Business and Economics Review 5.3 (2017): 173-188.

[^2]:<http://reader.elsevier.com/reader/sd/pii/S209672092100026> Bruschi, Francesco, et al. "A scalable decentralized system for fair token distribution and seamless users onboarding." Blockchain: Research and Applications 3.1 (2022): 100031.

[^3]:<https://hop.exchange/whitepaper.pdf> Whinfrey, Chris. "Hop: Send tokens across rollups." 2021.

[^4]:<http://inf.news/en/tech/bc8c0fa2ea6e0e2f3fe8963205cc8a36.html> Inf news. "How much cheaper are Arbitrum and Optimism than L1?."2022.

[^5]:<https://etherscan.io/gastracker> Etherscan. "Ethereum Gas Tracker." 2022.

[^6]:<https://ieeexplore.ieee.org/document/9529485> Mars, Rawya, et al. "A machine learning approach for gas price prediction in ethereum blockchain." 2021 IEEE 45th Annual Computers, Software, and Applications Conference (COMPSAC). IEEE, (2021).

[^7]:<https://help.optimism.io/hc/en-us/articles/4416677738907-What-happens-if-the-L1-gas-price-spikes-while-a-transaction-is-in-process> Optimism. "What happens if the L1 gas price spikes while a transaction is in process."2022.

[^8]:<https://medium.com/ethereum-optimism/ovm-deep-dive-a300d1085f52> Ethereum Optimism. "Ethereum optimism ovm deep dive."2020.

[^9]:<https://public-grafana.optimism.io/d/9hkhMxn7z/public-dashboard> Optimism. "Public Dashboard." 2022.

[^10]:<https://medium.com/ethereum-optimism/fancy-numbers-how-we-lowered-fees-for-optimism-users-a3bb80cbc65f> “The Road to Sub-Dollar Transactions Part 1: Slashing Fees by 30%.” Medium. Optimism PBC Blog,2022.

[^11]: Shannon, Claude Elwood. "A mathematical theory of communication." The Bell system technical journal 27, no. 3 (1948): 379-423.

[^12]: <scroll.io/blog/zkEVM> Scroll Team. "Scroll zkEVM" 2022.

[^13]:<https://ethereum.org/en/developers/docs/scaling/optimistic-rollups/> Smith, Corwin, and Richards, Sam. "Optimistic Rollups." Ethereum docs 2022.

[^14]: <https://medium.com/fcats-blockchain-incubator/how-zk-rollups-work-8ac4d7155b0e> Brown, Simon. "How Zk-Rollups Work" Jul 6, 2021.

[^15]: <https://learn.bybit.com/blockchain/zk-rollups-eth-scalability/> "ZK-Rollups Guide: ETH Scalability — and Why It’s the Next Big Narrative."(2022).

[^16]: <http://eips.ethereum.org/EIPS/eip-1559> Vitalik Buterin, Eric Conner, Rick Dudley, Matthew Slipper, Ian Norden, Abdelhamid Bakhta, *EIP-1559: Fee market change for ETH 1.0 Chain*, 2019.

[^17]: <http://ethresear.ch/t/multidimensional-eip-1559> Buterin, Vitalik. *Multidimensional EIP 1559*. 5 Jan. 2022

[^18]: <http://www.dropbox.com/sh/ag4e5qp4zv5whwv/AACRbdIdJB7mTi40_4ntbAxXa/Papers?dl=0&preview=Roughgarden+-+EIP1559.pdf&subfolder_nav_tracking=1> Roughgarden, Tim. "Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559." (2020)

[^19]: <http://vitalik.ca/general/2021/01/05/rollup.html> Buterin, Vitalik. *An Incomplete Guide to Rollups*. 5 Jan. 2021

[^20]: <http://docs.google.com/presentation/d/1mNi7mjBH4OOPOLw945Vow4q2-tHPVKh9P_wG518fMD0/edit#slide=id.g120aa33d150_0_36> Monnot, Barnabe. "The Road to Ethereum". 11 April 2022.

[^21]: <http://eips.ethereum.org/EIPS/eip-4488> Vitalik Buterin, Ansgar Dietrichs, "EIP-4488: Transaction calldata gas cost reduction with total calldata limit [DRAFT]," Ethereum Improvement Proposals, no. 4488, November 2021.

[^22]: <http://ethereum.org/en/developers/docs/evm/> "Ethereum Virtual Machine (EVM)". ethereum.org (2022).

[^23]: <https://medium.com/huobi-research/an-in-depth-look-at-rollups-tech-application-and-data-eb8f91bf369b> Huobi Research. "An in-depth look at Rollup’s tech, application, and data" Aug 2021.

[^24]: <http://finematics.com/rollups-explained> Jakub, "Rollups – The Ultimate Ethereum Scaling Solution". *Finematics* 8 February 2021.

[^25]: <http://ethresear.ch/t/proposer-block-builder-separation-friendly-fee-market-designs> Buterin, Vitalik. "Proposer/block builder separation-friendly fee market designs". June 2021.

[^26]: <http://ethereum.org/en/layer-2/> “Layer 2.” ethereum.org (2022).

[^27]: <https://arxiv.org/pdf/2012.00854.pdf>
Roughgarden, Tim. "Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559." arXiv preprint arXiv:2012.00854 (2020).

[^28]: <https://ethereum-magicians.org/t/some-medium-term-dust-cleanup-ideas/6287> Buterin, Vitalik. "Some medium-term dust cleanup ideas" May 2021.

[^29]: <https://ethereum.org/en/developers/docs/scaling/> : Ethereum Development Docs, "Scaling." Last modified April 2022

[^30]: <https://www.youtube.com/watch?v=JfaxBythV4Q> : Felten, Ed. "Fair and sustainable fees for L2." ETHconomics @ Devconnect, 2022.

[^31]: <https://support.deversifi.com/en/article/deversifi-withdrawing-tokens-1vo38bg/> DeversiFi. "Withdrawing Tokens From DeversiFi" March 2022.

[^32]: <https://hackernoon.com/layer2-interoperability-starkex-vs-loopring-vs-hermez-vs-connext-5y1p37vs> Sin7y. "Layer2 Interoperability: StarkEx Vs. Loopring Vs. Hermez Vs. Connext" hackernoon. July 2021.

[^33]: <https://medium.com/starkware/conditional-transfers-the-key-to-interoperability-2e1de044fb65> StarkWare. "Conditional Transfers — The Key to Interoperability" 2021.

[^34]: <https://dydx.exchange/blog/alpha> dydx. "L2 roadmap" 2022.

[^35]: <https://docs.zksync.io/userdocs/> zkSync. “Welcome to Zksync.” zkSync Documentation (2022).

[^36]: <https://community.optimism.io/docs/how-optimism-works/> Optimism team. “How Optimism Works.” Optimism Docs (2022).

[^37]: <https://developer.offchainlabs.com/docs/inside_arbitrum#gas-and-fees> “Inside Arbitrum · Offchain Labs Dev Center.”Offchain Labs Dev Center (2022).

[^38]:<https://docs.zksync.io/userdocs/tech/#zk-rollup-architecture> zkSync. “Technology.” zkSync Documentation (2022).

[^39]: <https://developer.offchainlabs.com/docs/inside_arbitrum#fees> “Inside Arbitrum-Offchain Labs Dev Center.” Offchain Labs Dev Center (2022).

[^40]:<https://mirror.xyz/0xaFaBa30769374EA0F971300dE79c62Bf94B464d5/k8Fr68ELdjIwJpGPpag_dnUarnypD5IUahpp6wT0qmk> McCorry, Patrick(0xaFaB). "Mental models for L1 and L2" 2022.

[^41]:<https://blog.matter-labs.io/optimistic-vs-zk-rollup-deep-dive-ea141e71e075> Gluchowski, Alex. "Optimistic vs. ZK Rollup: Deep Dive." 2019.

[^42]:<https://hackernoon.com/comparing-3-promising-layer-2-solutions-based-on-optimistic-rollups-6r5h245j> "Comparing 3 Promising Layer 2 Solutions Based on Optimistic Rollups."2021.