Does Your Blockchain Need Multidimensional Transaction Fees?
Nir Lavee, Noam Nisan, Mallesh Pai, Max Resnick · 2025
Read Does Your Blockchain Need Multidimensional Transaction Fees? by Nir Lavee, Noam Nisan, Mallesh Pai, Max Resnick (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15438.txt.
Introduction
Nir Lavee and three co-authors ask whether blockchains should charge fees in many dimensions in a 2025 paper. A block can hold only so much work, and a single fee meter wastes room when trades strain distinct resources, like storage versus raw compute. Pricing each resource apart could pack blocks fuller.
To size the prize, they define how well one rule set can mimic another once budgets are scaled. The best single meter turns out to equal the value of a two-player zero-sum game. With several meters, the search for the best set is provably hard in the strong sense. The frame gives chains a way to price the gain.
Catalog record
| CREATOR | Nir Lavee, Noam Nisan, Mallesh Pai, Max Resnick |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15438
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Does Your Blockchain Need Multidimensional Transaction Fees? Nir Lavee, Noam Nisan, Mallesh Pai, Max Resnick Abstract Blockchains have block‑size limits to ensure the entire cluster can keep up with the tip of the chain. These block-size limits are usually single-dimensional, but richer multi‑dimensional constraints allow for greater throughput. The potential for performance improvements from multi-dimensional resource pricing has been discussed in the literature, but exactly how big those performance improvements are remains unclear. In order to identify the magnitude of additional throughput that can be unlocked by multi-dimensional transaction fees, we introduce the concept of an α \alpha ‑approximation. A constraint set C 1 C_{1} is α \alpha ‑approximated by C 2 C_{2} if every block feasible under C 1 C_{1} is also feasible under C 2 C_{2} once all resource capacities are scaled by a factor of α \alpha (e.g., α = 2 \alpha=2 corresponds to doubling all available resources). We show that the α \alpha -approximation of the optimal single-dimensional gas measure corresponds to the value of a specific zero sum game. However, the more general problem of finding the optimal k k -dimensional approximation is NP-complete. Quantifying the additional throughput that multi-dimensional fees can provide allows blockchain designers to make informed decisions about whether the additional capacity unlocked by multi-dimensional constraints is worth the additional complexity they add to the protocol. 1 Introduction and Motivation Any new block added to the blockchain has to be replayed by the entire network. If the block is too large and takes too long to replay, then slower replicas may fall behind the tip of the chain, leading to degraded performance or even a pause in block production until the slow replicas can catch up. To ensure that all replicas can keep up, blockchain designers place constraints on which transactions can be packed into a valid block. If the leader proposes a block that violates these constraints, the rest of the cluster realizes that the block is invalid and rejects it. The original Bitcoin implementation [ Nak09 ] defined size as the number of bytes and limited a block to 1 Megabyte. 1 1 1 The later “SegWit” upgrade of Bitcoin took into account that not all bytes impose the same burden on the implementation, defined different “weights” for different components of a transaction, giving a measure of “virtual byte”, and limited blocks to 4 Mega Virtual Byte. This typically allowed 60%-70% more transactions in a block relative to raw bytesize measurements. Most blockchains in production today are only slightly more sophisticated than this. Nearly all use a single-dimensional measure of block size: for example, until recently, Ethereum sized all transactions according to a measure it calls gas, and Solana measures transactions according to Computational Units (CUs). But blockchains have more than a single constraint on new block production. Not only do blockchains inherit all of the intricacies of the computers that run their client software (e.g. storage, computation, memory bandwidth) but they also have to grapple with communication between the replicas (networking). Therefore, a blockchain protocol designer may wish to meter and price each of these resources separately---for example, certain transactions may be computationally trivial but require large amounts of networking or storage. This is not merely a theoretical concern---as of the Dencun upgrade in Spring 2024, Ethereum now defines two types of resources ‘‘gas’’ and ‘‘blobs’’. At the time of writing of this paper, Ethereum allows blocks to use, at a maximum, 36M gas and 6 blobs. 2 2 2 Ethereum also has a targeted size of 18M gas and 3 blobs, and the size of the block relative to the target affects the prices charged in the next block. We will ignore the target and focus solely on the maximum as the target is orthogonal to this paper. While there has been some recent work dealing with multi-dimensional constraints in blockchain systems [ DECA23 , CMW23 , ADM24 ] , handling multi-dimensional constraints remains difficult. Not only does the optimal assembly of blocks become complex algorithmically, but the pricing of transactions and the bidding process — the transaction fee mechanism — must also take into account multiple resources, which further complicates the strategic analysis. Avoiding this complexity is very desirable. This paper asks the question of whether and to what extent the complexity of multiple dimensions is worth the cost: how much do we lose by sticking to a single resource dimension? Take, for example, a blockchain that has two resources, gas and blobs, similar to Ethereum. Any given transaction can use some amount of gas and blobs. Can we replace the two restrictions of \texttt{gas}\leq 36\text{M} and \texttt{{blobs}}\leq 6 by some single restriction (\alpha\cdot\texttt{gas}+\beta\cdot\texttt{blobs}\leq B) ? It is not difficult to see that the two constraints cannot be replaced by a single linear one without incurring a loss. Figure 1 depicts the two “true” constraints as well as a single linear inequality that implies both of them ( \texttt{gas}+6\cdot\texttt{blobs}\leq 36 . However, note that this unavoidably rules out much of the space of actual block capacities in the worst case: a block which uses 18M gas and 3 blobs is considered as full by the linear measure, whereas it is clearly half-full on each dimension. Gas used Blobs used y\leq 6 x\leq 36 x+6y\leq 30 6 36 Figure 1: Two Ethereum-like constraints: the quantity x of one resource (gas) limited by x\leq 30 and the quantity y of another resource (fractional blobs) limited by y\leq 6 . The best single-dimensional gas measure that captures both constraints is x+5y\leq 30 , losing a factor of 2 in capacity in the worst case. It is easy to verify that, in the worst case, a single linear constraint may lose a factor of k in a setting with k distinct resources. But this is without any further modeling of how various resources are used by basic operations available in the protocol. How much would actually lose given a specific instruction set? We suggest a way to quantify the loss incurred based on the specific instruction set and its associated costs, allowing a more nuanced decision of whether or not the complexity of multi-dimensional fees is required. The hope is that in cases where a single gas measure will incur only a small loss of capacity, blockchain designers will choose simplicity. Conversely, in other cases, the loss may be too large, and the system would be better off with a multi-dimensional fee market. 2 Model Operations Resources Block B=(B_{j}) W=(w_{ij}) \cdot \leq Figure 2: Each row of the Operations-Resource Matrix represents an operation, each column represents a resource, and each entry w_{ij} represents the amount of resource j consumed by operation i . The basic property of the system that we will consider is the set of primitive operations that the system provides (e.g. Ethereum opcodes or Solana Instructions), where each transaction is composed of a sequence of primitive operations. Each of these primitive operations i\in I is associated with the amount w_{ij} that it uses of each resource j\in J . The actual constraints of the system allow a block to contain at most B_{j} quantity of each resource j . The parameters of the system are thus the operation-resource