# Designing Multi-Dimensional Blockchain Fee Markets

**Published by:** [f(crypto)](https://paragraph.com/@0xemperor/)
**Published on:** 2023-09-18
**URL:** https://paragraph.com/@0xemperor/designing-multi-dimensional-blockchain-fee-markets

## Content

Upgrading our Fee Markets to the final form. In this blog, I explore “Dynamic Pricing For Non-fungible Resource: Designing Multidimensional Blockchain Fee Markets.” https://twitter.com/buffalu__/status/1630589018688884737?s=20 A natural thing to wonder while viewing this tweet is wondering about the waste of resources and compute. A subsequent question is, what makes it possible? Is it because the resources are being priced too cheap? We’ll come to this problem again in a bit. Blockchains are public ledgers that allow users to submit transactions that modify the shared state. Full nodes with finite computational resources verify these transactions. How does a transaction try to secure a spot in this block? Many blockchains today enable smart contract development. Smart contracts are basically just programs that run on-chain. Users interact with these programs in the form of transactions, and these are executed by full nodes and added to a “block.” Interacting with these programs in the form of transactions requires some fees the network charges, which can be considered compensation for transaction processing. What unit of account do these blockchains charge for this? In the case of EVM (Ethereum virtual machine), this unit of account is gas. Each operation in the EVM requires a hardcoded amount of gas. Earlier, we mentioned that blockchains limit the resources consumed in a unit of time. In this case, the unit of time is done on a per-block basis, and the limit is called the block limit, which enforces a “limit” on the total amount of gas consumed. Since there’s only a fixed supply and the demand for this fluctuates, so does the price of “gas” (as demand-supply theory would dictate).Gas Charge - From Doug Colkitt's Talk on EVM optimizationsBlockchains face the fundamental challenge of balancing limited computational resources with fluctuating user demands. Transactions compete for block inclusion, consuming network bandwidth, storage, and computation. However, blockchains like Ethereum rely on a fungible unit like gas to price these resources. This makes it hard to reflect each underlying resource's actual marginal cost and scarcity. In the paper “Broken Metre: Attacking Resource Metering in EVM,” Perez et al. show a way of a new DoS (Denial of Service) attack on ethereum exploiting this one-dimensional “metering” of resources and propose the Resource Exhaustion attack. The essence of the attack is exploiting the fact that there were EVM instructions for which the gas fees were too low compared to the resources they consumed. This also led to an EIP-2929, which increased the gas requirement for these opcodes for some of the EVM instructions mentioned in the paper. There were also similar attacks like this on the SUICIDE opcode in 2016. Let’s do a thought experiment: Imagine you live in an apartment building where all utilities - electricity, water, heating, etc. - are bundled into a single bill that all residents split evenly. This means you pay the same monthly amount as your neighbor even if you barely use electricity or water, and they crank up the heat and AC all day. In this scenario, you have no incentive to conserve scarce resources others depend on. You end up overconsuming cheap resources like electricity while underutilizing resources like heat that you don't personally value as much (or need). The same issues crop up when blockchains price computation, storage, and bandwidth using one fungible token. You may want to store a large file on-chain while someone else is running complex smart contracts. But you pay gas proportionally to the total resources used, not based on your specific demands. This leads to mispricing and misallocation of scarce non-fungible resources. Computation may be overutilized, while storage is underutilized. There is no way for the market to express the actual marginal cost and demand for each resource. Ideally, we want the price for each resource to reflect its real-time scarcity so the blockchain charges higher fees when bandwidth is constrained versus when computation is plentiful. This would enable more efficient allocation and usage based on actual supply and demand dynamics. In their paper "Dynamic Pricing for Non-Fungible Resources," Diamandis et al. propose a systematic way to define and update dynamic prices for blockchain resources like computation, bandwidth, and storage. This is done by formulating an optimization problem from the network designer's perspective to maximize transaction utility minus resource loss. The problem decomposes into two parts - minimizing network loss and maximizing transaction producer welfare - joined by resource prices. Note: This article will be pretty convex optimization heavy, and the reader is suggested to have some familiarity. However, I’ll try to motivate what the equations mean and signify at every step.Exploration of Fee MarketsRollups and Data marketsRollups are a scaling technique that separates transaction execution from data availability. Transactions are executed off-chain in a rollup, with only transaction data posted to the base layer. The roll-up occasionally submits proof of valid state to the base layer. This naturally creates two separate fee markets - one for including transaction data on the base layer and one for execution in the rollup. Some "lazy" blockchains exclusively are optimized for data availability, leaving the execution to rollups that have also popped up. This also creates separate markets for data inclusion and execution. Ethereum has proposed allowing notable "blob" transactions containing arbitrary rollup data in EIP-2242 and then expanded upon in EIP-4484. Blobs can be priced separately from base layer gas, creating a two-dimensional fee market. Decoupling execution from data availability unlocks scalability and thus no longer constrains the base chain.In a proto-danksharding (EIP-4484) implementation, all validators and users still have to directly validate the availability of the full data. The main feature introduced by proto-danksharding is new transaction type, which we call a blob-carrying transaction. A blob-carrying transaction is like a regular transaction, except it also carries an extra piece of data called a blob. Blobs are extremely large (~125 kB), and can be much cheaper than similar amounts of calldata. However, blob data is not accessible to EVM execution; the EVM can only view a commitment to the blob. - From Proto-Danksharding FAQIndependent fee markets for data and execution enable more precise price discovery based on actual supply and demand. Overuse of one resource won't congest the other. Adding a blob/data market alongside base layer gas avoids competition between rollups and base layer transactions. Rollup data has a dedicated channel. Overall, separate fee markets for data availability and execution are a natural fit for rollup architectures. This prevents congestion across purposes and improves efficiency through targeted pricing. The multidimensional fee model proposed in the paper formalizes how to implement such markets. Proto-dank sharding introduces a two-dimensional EIP-1559 fee market with separate floating gas prices and limits for regular gas and blobs. There are two resources: gas and blobs. Each has a target per block (15M gas, eight blobs), a max per block (30M gas, 16 blobs), and a variable basefee. The blob fee is charged in gas but adjusts based on blob usage to target eight blobs per block on average. Block builders face a more challenging optimization problem balancing gas and blob limits and maximizing revenue. Heuristics can get close to optimal. The exponential EIP-1559 adjustment mechanism for blobs fixes issues with the current EIP-1559 formula, making adjustments depend only on total usage. The fake_exponential function approximates the exponential adjustment while being simple and efficient to compute. In summary, proto-dank sharding creates a two-dimensional fee market to utilize block space better and avoid worst-case usage scenarios. The new exponential blob fee adjustment provides better targeting.ParallelizationThere are two main approaches to enabling parallel execution in blockchains:Minimal VM changes and the responsibility is shifted to full nodes to identify parallelization opportunities.Using access lists - Transactions specify which accounts they access so that Non-conflicting transactions can be executed in parallel. This is used in Solana Sealevel to unlock parallel processing for thousands of transactions.The issue with the access list approach is that contention for popular accounts limits parallelization gains. Many transactions want to access the same accounts (NFT mints, popular protocols, or presales), forcing sequential execution. We also saw Easy Parallelizability being discussed for Ethereum, and this was discussed as a way to speed up the EVM in a blog by flashbots. In the end, we will see a formalization of fee markets for threaded VM resource pricing.Exploration by Ethereum and SolanaIn ethereum, a multidimensional fee market was proposed by Vitalik in the form of Multidimensional EIP1559. Ethereum has resources with different bursts (short-term) and sustained (long-term) capacity limits. For example, the EVM can handle occasional slow blocks but not sustained ones. The current gas model doesn't handle these burst vs. sustained differences well. It makes worst-case and average-case ratios similar, leading to inefficient gas costs, but the resources used in these cases are vastly different. For example, on average, transaction data plus call data consumes ~3% of the gas in a block. Hence, a worst-case block contains ~67x (including the 2x slack from EIP 1559) more data than an average-case block. The post proposes a multidimensional EIP 1559 - separate EIP 1559 controllers for each resource. Base fees for each resource are adjusted separately based on usage. This allows much higher slack parameters as the entire burst/sustained gap is represented. Limits would rarely be hit except in edge cases. Resources could include EVM execution, call data, witness data, and storage. The benefits noted from this were lower fees from more efficient pricing, better DoS protection, and reduced need for dynamic basefee algorithms. We will not cover a thorough analysis of EIP 1559 and transaction fee mechanism in this blog and refer the reader to Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559 and Transaction Fee Mechanism Design by Tim Roughgarden et al. (We will cover these works in a later blog). One thing to note about EIP-1559 is that although it is close to the problem that this paper considers, it makes the fee estimation problem easier in a way that disincentivizes manipulation and collusion. This paper aims to price resources dynamically to achieve set objectives. Multidimensional Fee markets are also being considered in a different form. Anatoly Yakovenko proposed it for Solana in “Consider increasing fees for writable accounts.” The issue proposes increasing fees exponentially for unused writable accounts to disincentivize bots flooding the network with invalid transactions based on stale state. The fee design is meant to help build congestion control, capture fees, punish misbehaving senders, and refund well-behaved senders. An alternate proposal suggested increasing fees for used accounts and rebating a portion of the program, giving developers more control while still limiting contention.Defining the ProblemTransactions A transaction in ethereum is defined as any action taken by an externally owned account (i.e., not a smart contract). Suppose A sends B 1 eth. This must be debited from A’s account and credited into B. A transaction changes the state of the EVM. The data (arbitrary in nature) is sent over the p2p (peer-to-peer) network to be added to the chain. They are first broadcasted and collected by nodes in the mempool. The mempools act as a staging/holding area for pending transactions waiting to be included in the block. Transactions in the mempool are prioritized by various factors, primarily the gas price offered. This is why gas immediately goes up during high volume transaction times because users keep spamming transactions with higher gas fees, so their transaction gets included and is prioritized. A miner/validator gets to choose which transactions from the mempool go into a block. Miners may also outsource this to “block builders.” Nodes Nodes execute and validate transactions to maintain the latest state. Most blockchains try to have minimum computational requirements for these nodes in a blockchain. They have finite resources, so blockchains limit total resources per unit of time to prevent overload. If transactions are included in a blockchain faster than nodes can execute them, these nodes won’t be able to reconstruct the latest state and, therefore, assert validity. This is also called Resource Exhaustion Attack. Resource Targets and Limits One way to avoid Resource Exhaustion would be to enforce a fixed upper bound of resources/combination of resources in a unit amount of time (or blocks). Another way would be to ensure miners do not constantly include high-resource transactions to blocks and better manage resource distribution/loading. This would suggest that we should have a “Resource Target” - a minimum target for consumption of resources every block to avoid waste of resources and a “Resource Limit” - so we make sure nodes catch up after a while.Resources $$i = 1, …, m.$$ In Ethereum's EVM, the fee unit is gas. Each operation consumes a hardcoded gas amount. As seen below, they all consume resources. We will henceforth only consider resource consumption rather than these granular opcodes (although you could use them if you wanted to).Opcodes and their Gas Cost$$j = 1,….n$$$$x$$$$R_1$$$$x = [ R_1, R_2, R_1R_2] $$$$b^*$$ To understand this as a simple example, let’s say we have five transactions being considered, and the 1st, 2nd, 4th, and 5th are being included in the block. The boolean vector looks like $$x = [1, 1, 0, 1, 1]^T$$$$A\in \mathbb{R}^{m*n}$$$$ A = \begin{bmatrix}12 & 32 & 34 & 43 & 54 \1 & 2 & 3 & 4 & 5\10 & 20 & 30 & 40 & 50\end{bmatrix}$$$$y = Ax$$ In our example $$y = Ax$$$$ y = \begin{bmatrix}12 & 32 & 34 & 43 & 54 \ 1 & 2 & 3 & 4 & 5 \ 10 & 20 & 30 & 40 & 50\end{bmatrix} * \begin{bmatrix}1 \ 1 \ 0 \ 1 \ 1 \end{bmatrix} $$$$ y = [141, 12, 120]$$$$ith$$$$Ax$$$$Ax-b^*$$$$ith$$$$b$$$$Ax \leq b$$ There we have it. We have represented how to measure the various resources, calculate deviation, and represent the resource limit.Network Fees $$j$$ Note: In Ethereum, the network fee is implemented by burning some amount of gas (post EIP 1559). $$p$$ One Example we should note is the transaction spam attack, which is called the EXTCODESIZE opcode repeatedly, an attack that happened in 2016. This exploited mispriced resources since EXTCODESIZE was too cheap and caused the network to slow down a lot. When you attempt a full node today, you can see a dramatic slowdown and processing from block 2283416 to 2463000. This immediately led to a subsequent EIP-150, which fixed the issue with the hardfork. This incident makes us realize the importance of resource pricing appropriately and not neglecting this problem since it can directly affect the performance of the underlying chain.A simple Idea $$p$$$$Ax =b^*$$$$(Ax)_i >g b^*_i$$$$(Ax)_i < g b^*_i$$How do you update p in the next block, though? This equation can be given byEquation for updating p - network resource feeswhere,$$p^k$$$$η$$$$Ax$$$$b^*$$In words, it is: New prices = Current prices - Learning rate * (Observed usage - Target usage) $$Ax-b^*$$ This type of iterative price update rule based on supply and demand motions (a different motivation in other spaces) appears in many contexts. Still, it is especially prevalent in machine learning for optimization and multi-agent learning. The goal is always to gradually steer behavior toward an optimal point, just like tuning the prices in a blockchain fee market.Resource Allocation ProblemThe ultimate goal of this system is to maximize the utility of the underlying blockchain. Since we are not omniscient, we do not know what the inclusion of a transaction in a block means to a user or miner (i.e., the utility) or what they want to add to a block. So, most of our optimization/design is around the desire to modify the fees so that resource usage is always near the resource target. $$\ell$$$$Ax$$Loss - Equation 1Loss - Equation 2While there are other losses we can consider, one important one is calculating the per-resource utilization.Loss - Per resource utilization$$p$$$$S$$Hard limits on resource consumption like Ax ≤ bContention for popular accounts or contractsInterdependencies between transactions $$S$$ Convex hull of Resource Constraints The convex hull conv(S) contains all convex combinations of points in S. This allows the network designer to "average" transactions over multiple blocks. Specifically, components of x can vary continuously between 0 and 1, interpreted as the probability or fraction of including a transaction over many blocks. Taking the convex hull conv(S) relaxes the binary constraints, allowing "partial" transactions. This relaxation allows the designer to reason about long-term resource utilization rather than allocation in a single block. This does not mean users or miners will create partial transactions. It's a convenience for the designer. Users/miners can only include transactions fully or not at all. The convex hull allows the designer to model allocation in an idealized way. This will allow the problem to decompose nicely into two coupled subproblems: one solved on-chain and one off-chain with integral solutions. $$q \in \mathbb{R}^n$$The problemThe Resource Constraint ProblemWhere,$$q^Tx - \ell(y)$$$$y = Ax$$$$x \in conv(S)$$The interpretation is that this is the "ideal but unrealistic" problem the network designer would solve. The paper shows that this decomposes into two problems: on-chain and implicitly by users and miners. The combination is called transaction producers. This combination exists because it’s inevitable that a user-miner colludes. This possibility was also mentioned in the paper “Transaction Fee Mechanism Design” by Roughgarden et al.The Dual functionOkay, we defined a problem we couldn’t solve and now need to convert it into a form, so we will. When dealing with a complex optimization problem, the concept of duality is a powerful tool. The dual problem is a natural counterpart to your original, or "primal," optimization problem. The dual problem is always the opposite of the primal. If the primal is minimization, the dual problem is maximization and vice versa. The dual is appealing because, more often than not, original problems in convex optimization seem to be very difficult but become very solvable in the dual form. What also makes the dual so compelling is that it provides a lower bound for the solution of the primal problem. This is invaluable because it gives you a benchmark for how good your solutions can be. They offer you alternative perspectives for understanding your problem, simplify complex equations, and can even lead to more efficient algorithms. In the primal problem above, we were optimizing a constrained optimization problem. $$x \in conv(S)$$$$x \in conv(S)$$ We add the constraints to the objective function to form the Lagrangian using dual variables (Lagrange multipliers). The dual for this problem is defined by$$p^T(y-Ax)$$ Rearranging, we finally find the dual function,Where,$$p$$ is the Lagrangian dual variable (also called the price) that relaxes the equality constraint $$y = Ax$$We aim to maximize the Lagrangian L(x,y,p) over x and y. $$p$$$$ f(x)$$$$f^*(y) = sup_x ( y^T x - f(x) )$$ Where "sup" refers to the supremum or least upper bound. $$ f^*(y)$$ Some key properties of the Fenchel conjugate:$$f^*(y)$$$$f^*(y)$$The second term defines the transaction producers' problem, and it optimizes the following problemTransaction Producer ProblemWhere,$$q$$$$A$$$$p$$$$x$$ $$(q - A^Tp)^Tx$$$$x ∈ conv(S)$$$$f(p)$$ We write the dual function as$$g(p)$$The dual problem$$g$$$$\ell^*$$$$∇l^(p) = y^*$$$$∇f(p) = -Ax^*$$$$y^*$$ Therefore, the gradient of the overall dual function is:$$p^*$$ In essence, the optimal fees align the incentives of the network (to minimize its loss l(y)) and the transaction producers (to maximize their utility) by properly internalizing the costs. The optimal fee that should be charged is the exact marginal cost the network faces. Now, we provide conditions under which the optimal resource prices/fees p* will be non-zero. $$X^*$$The condition we then have is$$AX^* $$ This motivates the need for multidimensional pricing. With separate prices for each resource, over-utilization of one resource can be discouraged by increasing its fee, while under-utilization of another can be encouraged by decreasing its fee. $$p$$First, the optimal price p* must be non-negative.Second, it defines a condition on the loss function called superlinearity, which implies that the domain where the dual function g(p) is finite is precisely the nonnegative orthant. This means the optimal prices are restricted to be non-negative. Superlinear losses prevent unbounded subsidies.Third, it characterizes the maximum prices beyond which transactions that consume resources will not be included by users/miners. This helps bound the range of reasonable fee values.Overall, the properties guide setting resource prices and characterizing their behavior. The nonnegativity constraints reflect the increasing costs of higher network usage. And the maximum prices bound subsidies and prevent exclusion of all resource-using transactions. The takeaway is that despite its generality, the structure of the network loss function $l(y)$ and dual function $g(p)$ enable valuable insights into the optimal pricing of blockchain resources.The SolutionWe can iteratively converge to the optimal prices. In a less constrained environment, L-BGFS could work. But since on-chain environments are compute-constrained (like that on ethereum), the paper suggests a modified version of gradient descent that is easy to compute and does not require storage beyond the fees. In gradient descent, we haveGradient descent update$$\eta$$ To ensure p stays in the domain of g, the paper suggests using projected gradient descent:$$z$$$$g$$$$y^*$$ We can then use an updated form.We see that this equation increases the network fee for a resource being overutilized and decreases the network fee for a resource being underutilized. As you would expect, this pricing mechanism is designed to disincentivize future users and miners from including transactions that consume currently overutilized resources in future blocks. This is not the only algorithm that works for this. The paper gives a few examples of loss functions and the update rules we get from them. Consider our earliest loss function,The conjugate function we get is$$y$$Consider another loss function: linearly separable lossesThe loss comes out to beWhile the papers use the gradient descent rule for this, other modifications can be considered, like adding momentum and adaptive steps.Extensions of the Fee MarketParallel Transaction Execution $$k$$ The allocation problem is given by:where,$$x_k$$$$y_k = Ax_k$$Resource allocation problem is to maximize utility minus loss.This can be solved using the same duality approach by combining all resources into one vector.It enables pricing threads and shared resources separately.Different Price Update SpeedsThe premise is that some resources can sustain burst capacities for much shorter periods of time compared to other resources. Therefore, Some resources may need faster price adjustments than others.$$η_i$$Update rule becomes$$D = diag(η_1,...,η_m)$$ We can also define this problem on a per-contract utilization basis instead of per resource.ConclusionWe explored multi-dimensional fee markets in this blog. In future blogs, I will explore transaction fee mechanism design.

## Publication Information

- [f(crypto)](https://paragraph.com/@0xemperor/): Publication homepage
- [All Posts](https://paragraph.com/@0xemperor/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@0xemperor): Subscribe to updates

## Optional

- [Collect as NFT](https://paragraph.com/@0xemperor/designing-multi-dimensional-blockchain-fee-markets): Support the author by collecting this post
- [View Collectors](https://paragraph.com/@0xemperor/designing-multi-dimensional-blockchain-fee-markets/collectors): See who has collected this post