Multidimensional Blockchain Fees Are (Essentially) Optimal

In the specific case of blockchain resource pricing, these papers can be roughly broken down into three buckets, which we describe next. The first set analyzes past or current fee mechanisms or variations thereof. These papers include some of the original economic analyses of EIP-1559 [33], empirical studies [12, 27], simulation studies [31], and clean theoretical models [25, 26]. All of these papers focus on the single-dimensional resource case, usually under some simplifying assumptions such as, e.g., certain stochastic limits in the case of [26]. The second set of papers proposes simple extensions or characterizations of mechanisms for pricing single resources in a variety of settings [20, 8, 9], including some impossibility results [16]. The final set proposes multidimensional fee mechanisms for a variety of settings [13, 19, 18]. The multidimensional fees work closest in spirit to ours is [18], which proposes a stochastic demand model of resources with stochastic observations. They apply linear-quadratic control theory to set prices that minimize a composite loss function that seeks to balance matching the target block size, while smoothly changing prices.

This work, on the other hand, shows that, even in an adversarial setting, a very simple update rule suffices and has low regret relative to optimally setting the prices. We also show that, in the “easier” stochastic setting, we recover a market-clearing price and provide a rate of convergence. One important case where we differ from many previous analyses is that we do not consider only incentive compatibility, but, indeed, consider worst-case adversarial behavior against the pricing mechanism and provide optimality bounds even in this particularly difficult setting.

The design of transaction fee mechanisms via gradient descent on an appropriately-chosen dual problem is also related to the literature on tatonnement processes [36, 17]. Many works (e.g., [11] and [32]) use gradient descent-like algorithms to develop dynamic pricing strategies for various types of markets. These algorithms use a dynamic step size to ensure convergence to optimal prices. More similar to our work, [5] uses a fixed step size, and their algorithm, as a result, does not necessarily converge to any single price.

First, let $t=1,\mathrm{\dots },T$ denote the current blockheight. At blockheight $t-1$, we assume that there are $n_t$ transactions from which we may pick a subset to be included in block $t$. (This list of transactions that we are allowed to choose from is often called the mempool.) Each of these $j=1,\mathrm{\dots },n_t$ transactions has some associated utility ${(q_t)}_j\in {\text{R}}_{+}$ which is gained if it is included in the block. Additionally, transaction $j$, if included in the block, will consume some amount of the $m$ available resources, which we denote as an $m$-vector $a_j\in {\text{R}}^m$. (The $i$th entry of this vector, ${(a_j)}_i$, denotes how much of resource $i$ is consumed by transaction $j$.) Finally, the vector $x_t\in {\{0,1\}}^{n_t}$ will denote the transactions that were included in block $t$: the $j$th entry ${(x_t)}_j=1$ if transaction $j$ is included in block $t$ and is 0, otherwise.

This set up lets us write the total resource consumption of all transactions included in block $t$ in a convenient way. Define the $m$-vector

where the matrix $A_t\in {\text{R}}_{+}^{m\times n_t}$ has $j$th column $a_j$ denoting the resources consumed by transaction $j$ in the mempool. We then have that ${(y_t)}_i$ denotes the total amount of resource $i$ is consumed by the transactions included in block $t$.

We denote the set of allowable transactions in a block by $S_t\subseteq {\{0,1\}}^{n_t}$, which may include resource limits (e.g., if $x\in S_t$, then $Ax\le b$), and interactions among transactions. Examples may include complementarity constraints such as, if $x\in S_t$, then $x_j=1$ implies that $x_{j^{\prime }}=0$ for some $j^{\prime }\ne j$, among many other, potentially very complicated, constraints.

Finally, we denote the network’s “unhappiness” with the resource usage at block $t$ as the loss function ${\mathrm{\ell }}_t:{\text{R}}_{+}^m\to \text{R}\cup \{\mathrm{\infty }\}$. This function maps the resource usage at block $t$, which is always a nonnegative vector, to some number ${\mathrm{\ell }}_t(y_t)$. Higher values denote less desirable resource usage. We assume this function, which is chosen by the blockchain designer, is convex and lower semicontinuous for the remainder of the paper.

We now define the block building problem as the problem of optimizing the utility of the included transactions, minus the loss incurred by the network, subject to the transactions being in the allowable transaction set:

Here, the variables are the included transactions $x_t\in {\text{R}}^{n_t}$ and the total resource consumption of the included transactions, $y_t\in {\text{R}}^m$. Additionally, $𝐜𝐨𝐧𝐯(S_t)$ denotes the convex hull of the set $S_t$. Replacing $S_t$ with its convex hull allows “fractional” transactions, such as $x_j=1/3$. These values of $x_j\in (0,1)$ can be interpreted as “spreading out” transaction $j$ over the next $1/x_j$ blocks. We denote the optimal value of problem (1) by $s^{\star }$.

In general, it is a good idea to have maximum per-block resource consumption bounds, which we write as $b\in {\text{R}}_{+}^m$, so we will assume that

so any allowable choice of transactions $x_t\in S_t$ will satisfy

as both $A_t$ and $x_t$ are nonnegative. In other words, we assume that the maximum amount of resource $i$ that any set of acceptable transactions may consume is no more than $b_i$. Note that this also implies

for any $y_t$ feasible for (1) since $y_t=A_t{x}_t$. (For why such limits are necessary, see the discussion in [19, §1].) Since $0\le y_t\le b$ for any feasible points, we assume, without loss of generality, that ${\mathrm{\ell }}_t(y)=\mathrm{\infty }$ whenever $y\nleqq b$ or $y\ngeqq 0$ for convenience.

We may view this block building problem as the following “idealized” scenario: if we, as the network, knew the welfare generated by each transaction, along with all possible constraints for all transactions then solving problem (1) would give us a way to include transactions as to maximize welfare minus the loss incurred by the network. Of course, in general, almost all of these things are not known (or, potentially even knowable) to the network, so we will show how to approximately solve this problem by, instead, correctly setting the price of the consumed resources for each block.

We also note that the number of resources $n$ here is left to the blockchain designer. A valid question might be: what is a reasonable number of resources and just how granular should these resources be in order to ensure that the system behaves as intended? While it may be tempting to have as many different resources as possible in order to have the most granular possible price discovery, we will see later that this may result in a very weak bound, which we show can be matched by an adversary. On the other hand, if many resources are correlated in their usage, it may be good to run some dimensionality reduction technique (such as PCA) on the historical resource utilization and only explicitly price a few “meta” resources.

One possible relaxation of (1), for each block $t=1,\mathrm{\dots },T$, can be constructed by relaxing the equality constraint in (1) to a penalty, parametrized by a vector $p_t\in {\text{R}}^m$, which we will call the prices:

where the variables are the same as those of problem (1). If we denote the optimal value of this problem, which is parametrized by the vector $p_t$, as $f_t(p_t)$, then, since the objective is separable over $x_t$ and $y_t$, we can write the optimal value of this problem as

We note that this function $f_t$, which we will call the dual function, is convex since it is the pointwise supremum of a family of functions linear in $p_t$.

The first term of (2) can be recognized as the Fenchel conjugate of $\mathrm{\ell }$ [10, §3.3] evaluated at $p_t$, which we write as ${\mathrm{\ell }}_t^{\ast }(p_t)$. This function can be interpreted as choosing the resource allocation $y$ that maximizes the network’s profit minus the loss as a result of resource consumption $y$. We note that the Fenchel conjugate has a closed-form expression for many commonly used loss functions.

The second term in (2) is the optimal value of the following problem:

with variable $x\in {\text{R}}^n$. We can interpret this problem as the transaction producers’ problem of creating and choosing transactions to be included in a block in order to maximize the utility of the included transactions ($q_t^{T}x$), after netting the fees paid to the network (${(A_t^T{p}_t)}^{T}x$). (This problem is sometimes called the block building problem or packing problem that is solved by block producers. These “block producers” include both users and validators.) Since the objective of this problem is linear, it has the same optimal value as the nonconvex problem

with variable $x\in {\text{R}}^n$. Note that the packing problem problem depends on the problem data associated with block $t$: the utilities $q_t$, the resources required by the submitted transactions, $A_t$, and the associated constraints $S_t$ for a particular block at time $t$. We will denote the optimal value of the packing problem as $h_t(p)$, where the index $t$ indicates that the problem data is associated with block $t$.

With this notation, the dual function can be written as

We note, for future use, that, when $f_t$ is differentiable at $p$,

where $y_t^{\star }(p)$ denotes the maximizer for the Fenchel conjugate of ${\mathrm{\ell }}_t$, at price $p$, while $x_t^{\star }(p)$ denotes the optimal transactions to be included for the block building problem (3) at price $p$. If $f_t$ is not differentiable at $p$, then any solution to each subproblem suffices. Note that both of these quantities are easy to compute if price $p$ is set at blockheight $t-1$ and block $t$ is submitted with these resource prices $p$: the former term, $y^{\star }(p)$, is the solution to a basic problem that often has a closed form, while the latter term, $A{x}^{\star }(p)$, is exactly the total resource consumption of the transactions included in block $t$.

From the discussion in §2.1, we have that the allowable transactions in $S_t$ can only consume up to some resource limit $b$, which means that:

from problem (3). Additionally, since ${\mathrm{\ell }}_t(y)=\mathrm{\infty }$ unless $0\le y\le b$, as noted in §2.1, then, it is not hard to show that

so we receive the simple bound on the gradient of $f_t$ at $p$:

This implies the gradient bound

for any $s$-norm. Note that, in the case where , the norm of $b$ is nondecreasing in the number of elements in $b$; in other words, the more resources with nonzero limits that we wish to price, the worse this resulting bound is.

As blockchain designers, we would like to set prices that, at least on average, render the supply and demand of resources (approximately) equal. That is, we would like to find a set of prices that solves the problem:

over $p\in {\text{R}}^m$. Finding a price $p^{\star }$ that minimizes this objective means that, using (1), over the $T$ blocks, we have

i.e., that the demand and supply for resources over the $T$ blocks are both equal. Or, in other words, that the market, over all $T$ blocks, clears on aggregate when the prices $p$ are correctly set. (The case where the objective is not differentiable over $p^{\star }$, but is subdifferentiable, means that there is at least one solution to each subproblem, at optimal prices $p^{\star }$, for which supply and demand are both equal.)

Since the prices $p$ for the blockchain must be set before the blocks are observed, it would be hard to solve (5) without oracular knowledge of the functions $f_t$. A simple heuristic is then the following: start with some prices $p_t$, set at blockheight $t-1$, observe what happens at block $t$ with these prices, and update the prices slightly (by, say $\eta >0$) according to the gradient information:

(If $f_t$ is not differentiable at $p_t$, then replace the gradient with a subgradient.) From before, we know that the gradient at block $t$ is observable at the prices set in the previous block, $p_t$. This heuristic has roughly the “right behavior”: if our prices are too low for a certain resource, say $i$, then the demand at these prices exceeds the expected supply, so

From the update step, this would increase the price ${(p_t)}_i$ of resource $i$ proportional to this amount. (The opposite is true if the prices at time $t-1$ were set too high.) See [19] for additional discussion.

Of course, we can also imagine any number of other update rules. For example, we may use a multiplicative update:

where $\circ$ denotes the elementwise (Hadamard) product. This update ensures that the prices are always nonnegative; though the previous update (6) can be modified slightly to accommodate this as well. We note that this update rule, when there is one resource, corresponds exactly to the EIP-4844 update found in Ethereum today.

Of course, the next natural question is: just how well do these heuristics perform? We will show in the remainder of the paper that the average gap between the objective values provided by this heuristic and those given by setting the optimal prices $p^{\star }$ (which clear the market on average; i.e., those that solve problem (5)) tends to zero as the number of blocks in question, $T$, grows:

for any (reasonable) choice of $p$. Perhaps the most surprising part is that we will show that this is true even when the allowable transactions $S_t$, resource utilizations $A_t$, and the welfare $q_t$ are controlled by an adversary. We will also show that these algorithms are essentially optimal: no better rate, in terms of $T$, is possible for any algorithm with such an adversary. The fact that this is possible, along with the original bounds for such problems, come from a long line of work in online convex optimization [35], which we present (and adapt to our specific scenario) in the next section.

Given some choice function $F:{\text{R}}^m\to \text{R}\cup \{\mathrm{\infty }\}$, we choose the new prices $p_{t+1}$ given the previous gradients $g_1,\mathrm{\dots },g_t$ by setting

where $\eta >0$ will be some specific step size to be chosen later. (The gradient can be replaced with any subgradient whenever the function is not differentiable, but is convex.) The one requirement we will have of this function $F$ is that it is “smooth”; in particular that the Hessian of $F$ (if twice-differentiable) is bounded from above by $\sigma I$, where $\sigma >0$, in some suitable domain $D\subseteq {\text{R}}^n$.

One choice of functions we will use is the norm-squared,

Since $\nabla F(z)=p_0+z$, then

which corresponds exactly to the gradient descent rule proposed in (6). This particular choice function is smooth with $\sigma =1$ for any domain $D$.

The second choice function is

which leads to the multiplicative update rule found in (7),

Here $\exp (\cdot )$ is taken elementwise, while $\circ$ denotes the elementwise (Hadamard) product. For the domain $D=\{z\mid {\Vert z\Vert }_{\mathrm{\infty }}\le \log (M)\}$, this choice function is smooth with $\sigma ={\Vert p_0\Vert }_{\mathrm{\infty }}M$. (We use $\log (M)$ since a bound on the prices of order $M$ would imply a bound on the domain size of order around $\log (M)$ – this is a somewhat technical condition that can be avoided by a slightly more careful choice of $F$; cf., appendix A.) We provide an alternate interpretation of this rule as both follow-the-regularized-leader and online mirror descent in appendix C. More specifically, these multiplicative update rules emerge from regularization by the nonnegative entropy function. This fact might explain some empirical observations of EIP-1559’s behavior.

Using (13), we can now give a bound on the regret $R$ using the inequality of (10). More specifically, if we know that the optimal aggregate clearing price $p^{\star }$ lies in some set $P$, then, using (13), we have

or, alternatively, that the average regret over that time horizon, $R/T$, is

For the gradient-descent-like rule (6), we have the choice function $F(z)=\frac{1}{2}{\Vert p_0+z\Vert }_2^2$. Applying the bound (13) gives, since $F(0)={\Vert p_0\Vert }_2^2$ and $\sigma =1$ for this choice function (from §3.1):

It is not hard to show that $F^{\ast }(\tilde{p})=\frac{1}{2}{\Vert \tilde{p}\Vert }_2^2$, and, assuming that we have a bound ${\Vert p^{\star }\Vert }_2\le M$ (and similarly for $p_0$), then the average regret is bounded by (14),

In the multiplicative update rule (7), the exponential choice function is given by $F(z)={\sum }_{i=1}^m{(p_0)}_i\exp (z_i)$ has $F(0)={\Vert p_0\Vert }_1$ and $\sigma =M$ such that, again, using bound (13),

It is also not hard to show that the conjugate of $F$ is

and, if we have a bound that $0\le \tilde{p}\le M\mathrm{𝟏}$ and $\epsilon \mathrm{𝟏}\le p_0\le M\mathrm{𝟏}$ for $\epsilon \le 1$, then

which follows from the fact that $F^{\ast }$ is separable and convex so is maximized at the boundary of the domain. For simplicity, we will assume that $M\ge e$, in which case the first term in the max is nonnegative. Putting it all together, we know that

Plugging these values into (15) gives

where, from before, $M$ is the maximum price allowed for any one resource, $m$ is the number of resources, and $\epsilon$ is the minimum starting price. The latter condition cannot be dropped since, if $p_0=0$, no update would ever be able to increase the price, while on the order of $\sim \log (1/\epsilon )$ updates are needed to scale the price $p_0$ to any constant. A sufficient condition to ensure that $p_0\ge \epsilon \mathrm{𝟏}$ is that there is always some minimal demand for blockspace at a small enough price, as in, e.g., [19, §3.2].

A standard result in stochastic gradient descent from, say [21, Thm. 9.5], is that,

Here, $B={\Vert b\Vert }_2$ and ${\Vert {\tilde{p}}^{\star }\Vert }_2\le M$ is a bound on the optimal price ${\tilde{p}}^{\star }$ that minimizes the expected utility $f$ given in (16). (We also assume that the initial price ${\Vert p_0\Vert }_2\le M$.) Finally, the time-averaged price $\overline{p}$ is defined

Setting $\eta =2M/B^2\sqrt{T}$ then gives the bound:

There is an immediate extension to this result. The first is to note that, by assumption, this result relies on i.i.d. draws of the sample ${\omega }_t$, but this can be generalized considerably. If we define ${ϵ}_t$ to be the noise in the gradient estimate at block $t$, i.e.,

then the above result requires that $\{{ϵ}_t\}$ be zero mean and i.i.d. Under suitable conditions, this can be relaxed to the $\{{ϵ}_t\}$ being a martingale difference sequence [22, §5.2].

In this model, we assumed that the step size $\eta$ is fixed and can depend on the total length of observed time period, $T$. Indeed, the step size trades off the ability of the prices $p$ to “react” to observed gradients $g_t$ with the average regret. (In particular, as $T$ becomes large, the average regret becomes small, but $\eta$ must be similarly small and must remain so for the time period in observation.) It is not hard to show that the regret bound in both the adversarial (§3.3) and stochastic case (§3.4) above for the gradient descent rule (6) (i.e., the one derived from the norm-square choice function) also carries through in the case where the step sizes $\eta$ are decreasing with respect to time, to get an update rule of the form

Here, ${\eta }_t=C/\sqrt{t}$ and $C>0$ is some appropriately chosen constant that, importantly, does not depend on the observation window $T$, but only on the known bounds for the price ${\Vert p\Vert }_2\le M$ and the maximum resource utilizations ${\Vert b\Vert }_2\le B$. The regret for this algorithm, under the same assumptions as §3.3 for the norm-squared choice function, is no more than $\sqrt{2}BM\sqrt{T}$ in the adversarial case; see [23, §3.1] for a proof. (The bound for the stochastic case is more refined, but see, e.g., [21, Thm. 5.3] for the statement.) More generally, any sequence $\{{\alpha }_t\}$ which asymptotically satisfies

and $1/{\alpha }_T=O(\sqrt{T})$ has a similar guarantee, up to a potentially different constant.

Indeed, if the step sizes of the algorithm are allowed to vary with respect to time, we can get much stronger regret guarantees in the case that the conjugate of the loss ${\mathrm{\ell }}_t^{\star }$ is strongly convex, using the same update rule (17). More specifically, if ${\mathrm{\ell }}_t^{\star }$ is $\mu$-strongly convex, then we can achieve logarithmic regret that, additionally, does not depend on there being any bound on the optimal price $p^{\star }$. (One case where ${\mathrm{\ell }}_t^{\ast }$ is strongly convex is, e.g., when ${\mathrm{\ell }}_t(y)=(1/2){\Vert {(y-b^{\star })}_{+}\Vert }_2^2$ for some target utilizations $b^{\star }\in {\text{R}}_{+}^m$ and $y$ is bounded by the maximum resource utilizations $y\le b$.) In this particular case, we have that for the update rule (17), where the step sizes are ${\eta }_t=\mu /t$, the regret is no larger than $B^2\log (T)/\mu$, making the average regret quite small: no more than $B^2\log (T)/(\mu T)$. (For a proof of this, see [23, §3.3.1].)

We construct a lower bound for any algorithm which attempts to minimize the dual problem corresponding to the commonly-used loss

where $b^{\star }\in {\text{R}}_{+}^m$ is the resource utilization target. Using this definition, it is not hard to show that the Fenchel conjugate of $\mathrm{\ell }$ is

where ${({(p)}_{+})}_i=\max \{p_i,0\}$ denotes the “positive part” of $p$, applied elementwise. The set $S_t\subseteq {\{0,1\}}^{n_t}$ we assume satisfies

for some matrix $A_t\in {\text{R}}^{m\times n_t}$ and max resource utilization $b\in {\text{R}}_{+}^m$. (We note that this set up reduces exactly to the resource metering of EIP-1559 when the number of resources $m=1$, where $n_t$ is the number of transactions in the mempool of the block builder and $b$ is the block limit.)

Consider a (stochastic) adversary who is able to control the amount of resources used by the network. The adversary picks the welfare to be $q_t=0$ and picks transactions $A_t$ such that the welfare maximization problem (3) satisfies, at price $p_t$,

where ${\epsilon }_t\sim {\{\pm 1\}}^m$ is uniformly randomly chosen (independently, for each $t=1,\mathrm{\dots },T$) and

for $i=1,\mathrm{\dots },m$. (The adversary can achieve this by constructing, say, exactly one transaction that is always included with zero welfare and utilizations equal to exactly $b^{\star }-{\epsilon }_t\circ \tilde{b}$; we assume this in what follows.) This gives

It suffices to show that, in expectation, the regret is $\mathrm{\Omega }(\sqrt{T})$, which means that there is at least one choice of resource consumption trajectories (gradients $\{g_t\}$) that leads to large regret, for any possible choices of prices $p_t$ by an algorithm. First note that the linear bound (13),

is met at exact equality for any nonnegative $p_t$ and $p^{\star }$ using our construction. To see this, note that the transactions were chosen to have zero welfare, $q_t=0$. Using the definition of $\mathrm{\ell }$ (18) means that, for any $p,p_t\ge 0$:

for every $t=1,\mathrm{\dots },T$. It will then suffice to show that the linear sum

is “large” in expectation, for $p^{\star }$ chosen with knowledge of $g_t$.

The first term of the loss (20) is zero since

as $p_t$ can depend only on the observed gradients, $g_1,\mathrm{\dots },g_{t-1}$. The expected regret then reduces to

Since $p^{\star }$ is chosen after observing the gradients $g_t$, and we are free to choose any $p^{\star }$ with ${\Vert p^{\star }\Vert }_{\mathrm{\infty }}\le M$ and $p^{\star }\ge 0$, we then this term is maximized by choosing $p_i^{\star }=M$ if

and $0$ otherwise, for $i=1,\mathrm{\dots },m$. This means that

where ${({(z)}_{+})}_i=\max \{z_i,0\}$ is the “positive part” of $z_i$. Using the definition of $g_t$ above (19), we can bound the latter term

where ${\epsilon }_t^{\prime }\sim \{\pm 1\}$ for $t=1,\mathrm{\dots },T$ is uniformly and independently drawn and $C\ge 1/24$. The inequality follows from a mechanical (if involved) counting argument, or any number of lower bounds on the expected value of the positive side of a random walk. We reproduce a simple, noncounting proof of this in appendix B. We note that, compared to either of the bounds of §3.3, this is tight up to a twiddle factor of $M$ and a square root factor of $m$.