EIP 1559 simulations

barnabe · April 21, 2020, 2:54am

Thanks Dan!

I really like all the cases you have isolated, here but also in your EIP. This is very helpful. I agree that getting a sense of what normal conditions are, or what is the “usual” mix of transactions would be sensible. I am hoping to collect data on this and try that analysis.

I’d like to be clearer what the transaction parameters are in the escalator. As I understand it currently, there is some price level p. For now say I only set two parameters, feecap and time_preference.

I submit my transaction at t=0, with fee p and a hash of the block at t.
If it is not included, at t=1, my transaction fee increases by (feecap - p) * t / time_preference. Meaning, if I really want to be included at least 1 block from now, I set time_preference to 1 and my bid jumps to my fee_cap in the next slot.

Is there a need for something like the initial_bid of the Agoric papers? In your own ethresear.ch thread you let users decide on the initial_bid. Using some kind of ambient price p (sort of like the basefee) this is one less parameter to specify (if we expect users to specify both feecap and time_preference). Of course it opens more question on how the dynamics of p affect the algorithm.

Segueing to a more formal model that could help compare the alternatives on hand. The presentation is more EIP 1559-specific but the representation of users and producers, metrics like social welfare etc. can be taken as is for a different mechanism – the only thing that changes would be strategies of users and producers.

In the last section I also give a result to show that under certain conditions, producer behaviour can be individually rational but not socially optimal. This is not unexpected however, these are the kind of things that were discussed on other threads. I haven’t necessarily seen it written up though.

EIP 1559 System dynamics

Given

b(0): the basefee at t=0,
c: a target gas per block,
G: the max gas limit per block, and
d: the basefee max change denominator d,

we observe two dynamical processes:

b(t) is the basefee at time t \in \mathbb{N}.
g(t) is the total gas used by the block at time t, g(t) \in [0, G].

This yields the following state dynamics:

b(t+1) = b(t) + b(t) \frac{g(t) - c}{cd} = b(t) \Big(1 + \frac{g(t) - c}{cd} \Big)

Users

Probably WLOG, we can assume that one user = one transaction[^1]. k runs over a countable (possibly infinite) set of users K, t denotes time steps, which we can assume discrete since “events” happen one block at a time. For some k, v_k: t \mapsto v_k(t) is the value function of the user, mapping time indices to the value. For all k, there exists t_k such that v_k(t) = 0, \, \forall t < t_k (t_k is k's wake-up time, when k starts caring for their transaction being included). After t_k, we assume v_k nonincreasing (the longer the transaction delay, the lower the utility for the user who submitted it). The value is assumed in the same unit as transaction fees, i.e., additive with respect to fees.
As an example, a simple time preference would have a single parameter \delta (discount rate) and an initial value v. When the user awakens, at t_k, and the transaction is included at t_k, the utility is v. If the transaction is included at t_k + 1, the utility is (1-\delta) v etc.
Another example is users who care for their transaction to be included immediately, or not at all. You could then have v_k(t_k) = v for some v > 0 and v_k(t_k + 1) = 0.
User k places their transaction a_k in the mempool at time t_k (i.e., earliest possible inclusion is in block at height t_k) and sets the transaction premium (\texttt{premium}(a_k)) and fee cap (\texttt{feecap}(a_k)).
Users observe the basefee b(t) at time t-1, i.e., know about b(t_k) once the block at height t_k - 1 is produced. The basefee is Markovian, i.e., only depends on its value at the previous block height. This makes it easier to reason about strategies for users and producers alike, as either can simply base their strategies on the value of b(t) alone (producers need to consider also the set of transactions in the mempool at t). The strategy space of user k is thus the set of mappings from the basefee and their utility function to their transaction attributes,

S_k = \Big\{ (v_k, b(t_k)) \mapsto (\texttt{premium}(a_k), \texttt{feecap}(a_k) \Big\}

Given some basefee b(t) at time t, the fee paid by user k whose transaction is included at time t is

\texttt{fee}(a_k, t) = \texttt{gasused}(a_k) \times \texttt{gasprice}(a_k, t)

where

\texttt{gasprice}(a_k, t) = \min(\texttt{feecap}(a_k), b(t) + \texttt{premium}(a_k))

Let i : K \times \mathbb{N} \to \{ 0, 1 \} be the inclusion function, with i(k, t) equal to 1 if and only if the transaction of user k was included at time t. Note that i(k, t) = 1 \Rightarrow b(t) \leq \texttt{feecap}(a_k).
The payoff function of user k is

\sum_{t \in \mathbb{N}} i(k, t) (v_k(t) - \texttt{fee}(a_k, t))

Producers

We have N block producers, commanding respectively fraction \alpha_n of the mining/staking power. The probability producer n is selected to create a block is \alpha_n.
Producers learn whether they will produce the block at height t right after the block at height t-1 is produced. The producer at time t selects from the mempool at time t a set of transactions respecting the block limit. We can get the state of the mempool at time t with:

M(t) = \{ a_k, k \in K: t_k \leq t; \; \forall s < t, \, i(k, s) = 0 \}

i.e., transactions from users who are awake and who weren’t previously included. Given M(t) and b(t), the producer for time t chooses a set of transactions A(t) \subseteq M(t) to include in their block.

The producer function is p : N \times \mathbb{N} \to \{ 0, 1 \}, with p(n, t) equal to 1 if and only if producer n produced the block at time t in the canonical version of the chain. The long-term payoff of block producer n is given by:

\sum_{t \in \mathbb{N}} (1-\delta)^t p(n, t) \Big( \sum_{k \in K} i(k, t) \cdot \texttt{gasused}(a_k) \times (\texttt{gasprice}(a_k) - b(t)) \Big)

with \delta giving a discount rate for payoff now vs. payoff later. We can assume

\frac{1}{T} \sum_{t = 1}^T p(n, t) \rightarrow_{T \to \infty} \alpha_n

Social welfare

The fee is paid from the user to the producer and is thus a simple transfer. The social welfare of the system is obtained by

SW(v, \alpha, b(0)) = \sum_{t \in \mathbb{N}} \sum_{k \in K} i(k,t) (v_k(t) - \texttt{gasused}(a_k) \cdot b(t))

All else being equal, the social welfare is optimised whenever transactions get in as early as possible and when basefee is lower.

The concern that producers can “manipulate” the fee has been expressed a few times, so we now give a simple example, showing that if a producer is chosen to produce two successive blocks, they can artificially delay inclusion to maximise their payoff. This is a prototype deviation, clearly a bit contrived.

A single producer

We have two time steps, 0 and 1. Let’s normalise the gas target to 1. The basefee is set at b for the first block and moves to b' for the second block. Transactions W(0) awaken at time t=0, with \mu(W(0)) = \sum_{a \in W(0)} \texttt{gasused}(a). Assume

All transactions are identical (this is a strong assumption, but the example works as long as there is money on the table).
\mu < 1 (all transactions fit in one block).
\texttt{feecap(a)} = f and \texttt{premium(a)} = \epsilon > f - b (the producer cannot get the whole premium at time step 0, since it is larger than the difference between the feecap and the basefee).
A single producer creates the blocks at time t=0 and t=1. For PoW chains, you could try to selfish mine, leaving the first block empty and stuffing the second one to reap higher fees. In eth2, at the start of a new epoch, validators can look up the slots in that epoch where they will be proposers.
Producer discount rate is \delta = 0 (also WLOG).

The payoff of the block producer who includes all transactions from W(0) at time step 0 is \mu \cdot (f - b).

If the producer does not include anything, the basefee drops to b' = b - \frac{1}{d}b = \frac{d-1}{d}b. Assume that b' + \epsilon < f, i.e., the basefee has dropped enough that the producer would get the whole premium instead of the difference between the feecap and the basefee. Including the transactions at time step 1 now yields payoff \mu \cdot \epsilon > \mu \cdot (f - b). In other words, it is more profitable for the producer to wait out another step. This is individually rational, but not socially optimal.

This holds true as long as the opportunity cost of not including transactions at t = 0 is lower than the profit from delaying them, and decreasing the basefee.

There is a cadCAD notebook on eth2 specs!