# ++Summary Note:++ Transaction Fee Mechanism Design for the Ethereum Blockchain
In this summary note, I will review and discuss two articles I have read in detail in the past several days.

**Article #1:** [Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559](https://arxiv.org/pdf/2012.00854.pdf)

This article was written by [Tim Roughgarden](https://timroughgarden.org/), who is a professor of computer science and member of Data Science Institute at Columbia University. I thoroughly enjoyed reading this article and learned a lot.

The article mainly discusses game-theoretic strengths and weaknesses of Ethereum [EIP-1559](https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1559.md) by focusing on [incentive-compatibility](https://www.britannica.com/topic/incentive-compatibility). Two major takeaways for me is the following:

1. ++Block space is the scarce resource++. Each block has a target size of 15 million gas, which represents a limited computational capacity in layman's term. Therefore, users must compete for this limited resource such that their transactions can be included in a block.
2. EIP-1559 effectively reduces the ++variation of transaction fee++, not the transaction fee itself. Reducing transaction fee is a scalability problem, not a TFM design problem. A direct implication of this outcome is easy fee estimation and improved user experience as a result. The variable blocksize flexibility reduces delays for some customers during the high demand period, thus also improves user experience. In addition, EIP-1559 achieves all those positive impacts without compromising security of the network.

My summary note comprises of four points as follows:
## Transaction Fee Mechanism (TFM)
First of all, what is transaction fee mechanism (TFM)? Put it simply, it is a mechanism that governs **++who pays what to whom++**. Three parts of this question:
- _Who_: Creators of blockchain transactions.
- _What_: What is being paid in what form? The creator's bid in its entirety or a portion of it?
- _Whom_: Who gets paid? Where does that asset flow to? Who has the right to claim that payment?
## TFM in Ethereum Blockchain
Here, we first need to define two types of auctions:
- **First price auction**: In this type of auction, all bidders submit their bids simultaneously. As a result, no one knows the bid of any other bidders. That's why it is also called a blind auction. The bidder with the highest bid wins and pays the entirety of his bid, regarless of how much higher his bid is comapred to second highest bid. For instance, suppose Alice and Bob, are bidding on whose transaction gets confirmed first on the blockchain. Alice's bid is 35,000 Gwei and Bob's bid is 42,000 Gwei. In this case, Bob's bid is higher and his transaction will be included in the block ahead of Alice's transacition. Bob will pay the entire 42,000 Gwei. Ethereum's TFM had always been first-price action prior to EIP-1559 implementation.
- **Second price auction**: The general mechanism of second price auction works in the same way as first price auction, except the amount of final payment paid by the winning bid. The highest bidder only needs to pay the bid made by the second-highest bidder (i.e., losing bid). In our example above, Bob is still the winnder under second-price auction but instead of paying his entire bid, he just needs to pay 35,000 Gwei, Alice's bid. Second price auction does not work in Ethereum network because such type of auction can be manipulated via fake transactions.
- **EIP-1559**: EIP-1559 has three core components. First let's define some variables for a transaction denoted as $t$.
- $b_t$: Base fee for a transaction.
- $c_t$: Max fee for a transaction.
- $\delta_t$: Max priority fee (i.e., tip).
- $g_t$: Gas used for the transaction.

The first three variables are defined as per unit gas. The base fee $b_t$ is a protocol parameter. It is adjusted dynamically according to the users demand level to the block space. The creator of a trancation is responsible for specifying max fee $c_t$ and max priority fee $\delta_t$. The last parameter $g_t$ depends on the computational requirement of the transaction. Given those values, we can calculate how much the creater of transaction $t$ is going to pay:

$$
g_t\cdot\min\{b_t+\delta_t, c_t\}
$$

Next, let's uncover each component in depth.
- ++Base fee++. Base fee in EIP-1559 plays the role of a reserve price and changes according to supply and demand dynamics of the network. It is also the minimum fee the creator of a transaction needs to pay to earn _the right_ of the inclusion in the block. It is determined by on-chain block history, not the current block information. In particular, for a given block target size (15 million gas currently), the base fee is determined entirely by the size of the previous block. One important fact about base fee is that this payment is burnt rather than transferred to the block's miner or validator. In summary, base fee in determined by the network and burned.
- ++Max fee++. The creater specifies the maximum willingness to pay. If the transaction inclusion costs more than the max fee per unit of gas, the transaction will not be included.
- ++Max priority fee or tip++. Since base fee is burned under EIP-1559 mechanism, the short-term incentives of the miners/validators are weakened, which will have a negative impact on security. EIP-1559 proposes that users seeking special treatments, for example fast inclusion to the block or a specific way of ordering their transactions, can supplement the base fee with a tip that will be paid to the miner/validator.

Thus, the final transaction fee a user has to pay is the smaller of ($b_t+\delta_t$) and $c_t$ per unit of gas.

Another important change proposed by EIP-1559 was the vaiation in block size. In particulr, EIP-1559 doubles the maximum block size, with 15M gas (current) serving as the target block size. When there is high demand, block size can increase to 30M gas. Therefore, with EIP-1559, the max block size is 30M gas. You may wonder why set a cap. The reason is that the larger the block size, the higher the computational requirement to process them in time for the next slot. Ideally, this flexible block size with a cap will shorten the delay experienced by the user in case of congested network.

I summarize the Ethereum TFM in the graph below.

digraph hierarchy {

nodesep=1.0 // increases the separation between nodes

node [color=Red,fontname=Courier,shape=box] //All nodes will be this shape and colour
edge [color=Blue, style=dashed] //All the lines look like this

Ethereum_TFM->{Pre1559 Post1559_PreMerge Post1559_PostMerge}
Pre1559->{First_Price_Auction}
Post1559_PreMerge->EIP1559_Miner
Post1559_PostMerge->EIP1559_Validator
{rank=same;First_Price_Auction EIP1559_Miner EIP1559_Validator}  // Put them on the same level
}

Post merge, the miner is replaced with validator. We can summarize EIP-1559 mechanism using the definition we have for TFM:
1. Instead of a single price as in first price auction mechanism, the creator of a transaction now specifies a _tip_ and _fee cap_ for inclusion.
2. _Who pays what?_ The creator of the transaction $t$ pays $g_t\cdot\min\{b_t+\delta_t, c_t\}$ in Ethereum native token ETH.
3. _Who gets the payment?_ Base fee $b_t$ is burned and the remainder $g_t\cdot\min\{\delta_t, c_t-b_t\}$ is transferred to the miner/validator of the block.
## Market for Ethereum Transaction
In this part, we cover topics from a macro angle, in particular, market-clearing price and market-clearing outcome, which set the stage for incentive-compatibility discussion.

1. _Market-clearing price_
As its name suggests, market-clearing price is the price that clears the market. When a market clears, supply and demand is perfectly matched: all demands are satisfied with all the supply. For instance, a linear demand curve for Ethereum block space has the form
$$D(p)=\max\{0, a-bp\}$$
where $p$ denotes the gas price and $a, b(\geq0)$ are the non-negative parameters. In this case, market-clearing price is the price at which the total demand for gas equals the available supply of 15M gas. $a=30M$ and $b=150K$, the market-clearing price can be calculated by
$$15000000=30000000-150000(p)\Longrightarrow p = 100$$.
One important take away here: ++Market clearing price is the ideal gas price for a block.++
2. _Market-clearing outcome_. Let's suppose market-clearing price is $p^*$ and it is a common knowledge for all users. In the market-clearing outcome, three things happen:
- users with maximum willingness to pay (WTP) at least $p^*$ per unit of gas will have their transactions included in the block, while those with lower WTP will be priced out.
- The supply of 15M gas will be 100% utilized. In addition,
- The supply of 15M gas will be allocated precisely to the highest-value transactions.

Therefore, an ideal outcome of a TFM has two parts to it:
1. Every block is fully utilized with highest value transactions, and
2. Every transaction pays the market-clearing price.

We can say that under first aution mechanism, users are trying to estimate what the market-clearing price would be and bid accordingly; under EIP-1559, the protocol continuously adjusting base fee in search of the market-clearing price.

One important note here. There is another price called _**revenue-maximizing price**_. Revenue-maximizing price is different from market-clearing price. I will not go into details here about how it might be different from market-clearing price, but keep in mind that those two might not align with each other and it might cause collusion.

## User Experience
In this section, I want to quickly discuss what ++user experience++ actually means in the context of users interaction with the Ethereum blockchain. Here, the metric I use to evaluate the user experience is ++the gap between what a user actually pays and what that user should pay++. The larger the gap, the worse the user experience. Accordingly, making the transaction fees more predictable will lead to a better user experience since when the fees are more predictable, it is easier to estimate what the actual fee would be. The users can pay accordingly.

Then what was the problem with first-price-auction fee mechanism? It is actually fundamental to first-price auctions: users overpay regularly, specifying gas prices that are significantly higher than the market-clearing price. Tom Roughgarden gave a really good example to explain how that actually happens. Imagine two different situations: buying a house in a real estate market and buying a book on amazon. the former is done via auctions and the latter is via posted-price mechanism.

When buying a house, you are competing with other potential buyers and think really hard about what price you should offer. And making it worse, no matter what you offer, you would regret in hindsight. Why? Because you uderbid and did not get the house or overbid and paid more than what you needed to get the house.

Now again, imagine buying a book in Amazon. Price is posted and you either take it or leave it. The outcome is economically efficient because every user with WTP > price will buy the product and those without high enough WTP don't.

## Incentive-Compatible TFM

Tom identifed three game-theoretic guarantees for a TFM. They are as follows:
1. Miners should be incentivized to carry out the mechanism as intended, and strongly disincentized to carry out malicious activities, such as including fake transactions.
2. The creator of a transaction should easily specify the optimal gas price for inclusion.
3. Combining (1) and (2), miners and users should not be able to collude and strictly increase their utility by moving payments off-chain.
### Basic Model
Let's define some macro-level variables first:
$$
\begin{align}
G&=\text{the maximum block size in gas (12.5M under status quo and 30M under EIP-1559)}\\
\mu&=\text{marginal cost of gas to the miner/validator}\\
M&=\text{the set of transactions in the mempol at the time of the current block's creation}
\end{align}
$$

On the mico-level for a transaction $t$, we have
$$
\begin{align}
g_t&=\text{gas limit}\\
v_t&=\text{value in gwei per unit of gas}\\
b_t&=\text{bid in gwei per unit of gas}\\
\end{align}
$$
The gas limit is the amount of gas required to carry out the transaction. The value is the transaction's creator's WTP for its execution in the current block. The bid is the gas price the creator actually offers to pay, which is usually less than the value. The bid is under the creator's control.
### Three Rules
We described fundamentals of a TFM mechanism at the beginning of this note. Here, we again mention them:
1. Which transactions should be included in the block? - **Allocation rule**
2. How much the creators of those transactions have to pay? - **Payment rule**
3. To whom their payments is directed? **Burning rule**

Given our notation, Tom's definitions are as follows in his article:
#### Allocation rule
$B_1, B_2,\dots, B_{k-1}$ denote the sequence of blocks in the current longest chain ($B_1$ is the genesis block and $B_{k-1}$ the most recent block). As of this writing, the most recent block was 15860431.

"An _allocation rule_ is a vector-valued function $\mathbb{x}$ from the chain history $B_1, B_2,\dots, B_{k-1}$ and mempool $M$ to a 0-1 value $x_t$ for each pending transaction $t\in M$."

A value 1 indicates the inclusion of a transaction $t$ in the block; a value of 0 indicates its exclusion.

Due to the constraint on the max block size, not all allocation outcomes are feasible. As a result, a feasible allocation rule can be defined:

"An allocation rule $\mathbb{x}$ is ++**feasible**++ if for every possible history $B_1, B_2,\dots, B_{k-1}$ and mempool $M$,"
$$
\sum_{t\in M}g_t\cdot x_t(B_1, B_2,\dots, B_{k-1}, M)\leq G
$$

#### Payment rule
"A _payment rule_ is a function $\mathbb{p}$ from the current on-chain history $B_1, B_2,\dots, B_{k-1}$ and transactions $B_k$ included in the current block to a nonnegative number $p_t(B_1, B_2,\dots, B_{k-1}, B_k)$ for each included transaction $t\in B_k$."

The value $p_t$ represents the payment from the creator of an included transaction $t\in B_k$ to the miner/validator of the block $B_k$ (in ETH, per unit of gas).

In first price auction, the creator always pays his bid, regardless of the blockchain history.

#### Burning rule
"A _burning rule_ is a function $\mathbb{q}$ from the current on-chain history $B_1, B_2,\dots, B_{k-1}$ and transactions $B_k$ included in the current block to a nonnegative number $q_t(B_1, B_2,\dots, B_{k-1}, B_k)$ for each included transaction $t\in B_k$."

The value $q_t$ indicates the amount of ETH burned by the creator of an included transaction $t\in B_k$. There is no burning under first price auction. Burning was introduced under EIP-1559.

The miner/validator controls the allocation. Given an on-chain allocation, the protocol specifies on-chain payments and fee burns.

Given those three allocation rules, Tom gives his definition formally as follows:
"A _transaction fee mechanism_ (TFM) is a triple ($\mathbb{x, p, q}$) in which $\mathbb{x}$ is a feasible allocation rule, $\mathbb{p}$ is a payment rule, and $\mathbb{q}$ is a burning rule."

One last missing piece here is rationality assumption: Users will not pay more than their willingness to pay. Its implication in terms of designing a TFM is that a TFM cannot force users to pay more than their WTP. Formally,

>A TFM $\mathbb{x, p, q}$ is _individually rational_ if, for every history $B_1, B_2, \dots, B_k$,
$$
p_t(B_1, B_2, \dots, B_k)+q_t(B_1, B_2, \dots, B_k)\leq b_t
$$
for every transaction $t\in B_k$.

### Utility Function
In this section, I will provide Tom's definitions of individual utility functions for miner/validator and the transaction creator, and join utility function of these two players.

#### Miner/validator
As I mentioned earlier, miners control the allocation. One possible consequence of this miner power if the inclusion of fake transactions when it is economically beneficial to the miner. As a result, miner's utility function includes this component.

> For a TFM ($\mathbb{x, p, q}$), on-chain history $B_1, \dots, B_{k-1}$, mempool $M$, fake transactions $F$, and choice $B_k\subseteq M\cup F$ of included transactions (real and fake) the utility of a miner is
$$
u(F, B_k):=\sum_{t\subseteq B_k\cap M}p_t(B_1, B_2, \dots, B_k)\cdot g_t-\sum_{t\subseteq B_k\cap F}q_t(B_1, B_2, \dots, B_k)\cdot g_t-\mu \sum_{t\in B_k}g_t.
$$

The first term is sum over the real included transactions. The fake included transactions will have net zero impact since the miner pays himself. The second term is sum over the fake transactions. The burned fee from fake transactions is a loss to the miner. The last term is the gas costs occurred to the miner.

#### Transaction creator
In a nutshell, a user will maximize surplus from the transaction. From the transaction creator perspective, the difference between WTP and the bid is the surplus. As a result, the user/transaction creator's utility function is as follows:
> For a TFM ($\mathbb{x, p, q}$), on-chain history $B_1, \dots, B_{k-1}$, mempool $M$, the utility of the originator of a transaction $t \notin M$ with WTP $v_t$ and bid $b_t$ is
$$
v_t(b_t):=\begin{cases}
\Bigg(v_t-p_t(B_1, B_2, \dots, B_k)-q_t(B_1, B_2, \dots, B_k)\Bigg).g_t \qquad &\text{ if }t\in B_k\\
0, &\text{otherwise}
\end{cases}
$$

The creator of a transaction bids in such a way that it maximizes the utility function above.
#### joint utility function
Now, we can look at miners and users utility function jointly.
> For an on-chain history $B_1, B_2, \dots, B_{k-1}$, the _joing utility_ of the miner and users for the block $B_k$ is
$$
\sum_{t\in B_k}(v_t-q_t(B_1, B_2, \dots, B_{k-1}, B_k)-\mu)\cdot g_t
$$

We assume that the objective of miners and users is to maximize their joint utility.

### Incentive Compatibility
TODO

**Article #2:** [Understanding rollup economics from first principles](https://barnabe.substack.com/p/understanding-rollup-economics-from)

This blog post was written by Barnabé Monnot, who is a member of Robust Incentives Group at Ethereum Foundation. This post really helped me understand the main players in rollup eco-system and the interactions between them.

TODO.