Rougharden 1559

Demand for blockchains such as Bitcoin and Ethereum is far larger than supply, necessitating a mechanism that selects a subset of transactions to include “on-chain” from the pool of all pending transactions. This paper investigates the problem of designing a blockchain transaction fee mechanism through the lens of mechanism design. We introduce two new forms of incentive-compatibility that capture some of the idiosyncrasies of the blockchain setting, one (MMIC) that protects against deviations by profit-maximizing miners and one (OCA-proofness) that protects against off-chain collusion between miners and users. This study is immediately applicable to a recent (August 5, 2021) and major change to Ethereum’s transaction fee mechanism, based on a proposal called “EIP-1559.” Historically, Ethereum’s transaction fee mechanism was a first-price (pay-as-bid) auction. EIP-1559 suggested making several tightly coupled changes, including the introduction of variable-size blocks, a history-dependent reserve price, and the burning of a significant portion of the transaction fees. We prove that this new mechanism earns an impressive report card: it satisfies the MMIC and OCA-proofness conditions, and is also dominant-strategy incentive compatible (DSIC) except when there is a sudden demand spike. We also introduce an alternative design, the “tipless mechanism,” which offers an incomparable slate of incentive-compatibility guarantees—it is MMIC and DSIC, and OCA-proof unless in the midst of a demand spike. 1 Introduction Real estate on a major blockchain is a scarce resource. For example, Bitcoin [24] and Ethereum [7], the two biggest blockchains by market cap1 , process roughly 5 and 15 transactions per second on average, respectively. Demand for these blockchains is far larger, necessitating a mechanism that selects a subset of transactions to include “on-chain” from the pool of all submitted transactions. Historically, most blockchain protocols have employed a pay-as-bid transaction fee mechanism. Every transaction is submitted with a bid (in the blockchain’s native currency), the miner of a block decides which transactions should be included in it, and upon publication of that block, the bid of each included transaction is transferred from its creator to the miner. We follow blockchain convention and refer to this mechanism as a first-price auction (FPA). FPAs are natural enough and are currently the dominant paradigm in blockchain protocols, but are they really the best we can do? Could a different transaction fee mechanism offer more compelling incentive-compatibility properties? The primary goal of this paper is to investigate these questions through the lens of mechanism design, while taking into account the many idiosyncrasies of the blockchain setting relative to more traditional applications of the field. For example: (1) The miner of a block has dictatorial control over its contents, and in particular may deviate from the allocation rule intended by the protocol designer. (2) The miner of a block can costlessly include fake transactions that are indistinguishable from real transactions. (3) Payments should be computable from “on-chain” data, which typically discloses no information about losing bids. (4) Miners and users can easily collude off-chain to manipulate a transaction fee mechanism. The sequential and repeated nature of the blockchain setting also offers some potential advantages to the mechanism designer (which are not exploited by FPAs). For example: (5) The choice of mechanism (such as a reserve price) for a given block could be informed by the (publicly visible) outcomes for previous blocks. (6) Revenue from a block need not be transferred directly to the block’s miner and could instead be redirected, for example to a foundation or to the miners of future blocks. The key question is then: is there a transaction fee mechanism, possibly taking advantage of points (5) and (6), that meets the constraints imposed by (1)–(4) while also decreasing the strategic complexity relative to FPAs? EIP-1559 In addition to its basic scientific interest, the analysis of transaction fee mechanisms is immediately applicable to scrutinizing what is arguably the biggest change made to-date to the Ethereum blockchain. As background, a blockchain can change its own specification through a “hard fork,” meaning a coordinated switch by the nodes in its network to a new and backwards-incompatible version of the protocol software. At the time of this writing, the Ethereum blockchain has had roughly a dozen hard forks since its genesis in May 2015, most recently the “London fork” that began with block number 12865000, mined on August 5, 2021. Each hard fork implements a collection of Ethereum improvement protocols or “EIPs” that have been vetted by the community and approved for inclusion. One of the EIPs implemented in the London fork is EIP-1559, a proposal by Vitalik Buterin (Ethereum’s founder) [8, 10] that suggested several tightly coupled changes to Ethereum’s transaction fee mechanism (which was previously an FPA), including the introduction of variable-size blocks, a history-dependent reserve price, and the burning of a significant portion of the transaction fees.2 While Buterin did not provide a formal economic analysis of his proposed design, in [9] he outlined the motivation behind the proposal: Our goal is to discourage the development of complex miner strategies and complex transaction sender strategies in general, including both complex client-side calculations and economic modeling as well as various forms of collusion. Community discussion of EIP-1559 began in earnest in early 20183 and over time the proposal garnered a number of advocates and critics. The polarization around this EIP was evident in the community survey conducted by Tim Beiko.4 “Difficulties analyzing the EIP” ranked among the chief risks pointed out by the survey respondents, citing “the lack of a formal specification or proof for the mechanism that people can independently evaluate and critique.” As part of the course of our work, we formalize the transaction fee mechanism proposed in EIP-1559 and rigorously interrogate to what extent it meets its stated design goals. Anecdotal evidence suggests that a preliminary report based on this work [26] contributed to the understanding of and broader support for EIP-1559.5 We stress that while EIP-1559 provides important and timely motivation for the present work, the discussion and results in this paper apply equally well to many other blockchains, including Bitcoin. The Bitcoin community is famously hostile to any major changes to the Bitcoin protocol, however, so its transaction fee mechanism is likely to remain an FPA for the foreseeable future. Some smaller blockchains have deployed variations of the mechanism proposed in EIP-1559, including Filecoin6 and NEAR7 . Paper Structure Section 2 of this paper describes our basic model, a mechanism design setting in which the mechanism participants (creators of transactions) compete for transaction inclusion in a block with limited capacity. The formalism follows in the mechanism design tradition of allocation rules and payment rules, but with two twists. First, to take into account point (6) above, the payment rule (describing transfers to a block’s miner) is supplemented with a burning rule (Definition 2.5) which indicates how much of the block’s revenue is burned (or otherwise redirected away from the block’s miner). Second, in light of point (3), payment and burning rules are restricted to depend only on the bids of the winning transactions. Transaction fee mechanisms have been an integral part of blockchain design since Nakamoto’s original white paper introducing the Bitcoin protocol [24]. Since its genesis, Bitcoin has used an FPA as its transaction fee mechanism. The going price for Bitcoin transactions has been discussed much more thoroughly than the transaction fee mechanism itself. For example, the “blocksize wars” refers to a bitter dispute within the Blockchain community over whether to increase the maximum allowable size of a block (ultimately leading in 2017 to a split between Bitcoin and a new fork called Bitcoin Cash) [5], and one of the primary arguments put forth by proponents of larger blocks was that it would prevent (or at least delay) high transaction fees that would be prohibitive for all but the more cost-insensitive participants. Another much-discussed issue, for example in [11] and [16], is whether Bitcoin becomes more vulnerable to various attacks as the fixed block reward decreases (it programmatically halves every 4 years) and the transaction fees per block increase (as one would expect if the demand for Bitcoin transactions continues to increase). Section 3 spells out three forms of incentive-compatibility, each guaranteeing robustness to a particular type of deviation from the intended behavior. Robustness to deviations from straightforward bidding by transaction creators is captured by the familiar notion of dominant-strategy incentive-compatibility (DSIC). The other two guarantees are specifically motivated by the blockchain setting and are new to this paper. First, we define incentivecompatibility for myopic miners (Definition 3.4), or MMIC, a condition stating that a transaction fee mechanism should be robust to deviations by profit-maximizing miners from the intended allocation rule (see point (1)) and also the injection of fake transactions (point (2)). Second, we define OCA-proofness (Definition 3.6), which states that the mechanism should be robust to cartels of transaction creators and miners colluding off-chain; more precisely, no off-chain arrangement among members of such a cartel should be capable of Pareto improving over a canonical on-chain outcome. The rest of the paper investigates to what extent different transaction fee mechanisms enjoy these three strategic robustness properties. Section 4 provides a formal description of the transaction fee mechanism proposed in EIP1559, which we call the 1559 mechanism. This mechanism makes use of a reserve price that is adjusted over time in response to excess demand, and variable-size blocks to provide an onchain signal of excess demand. All revenue generated by the reserve price is burned. Finally, there is effectively an FPA sprinkled on top: Transaction creators also have the option of supplementing the reserve price by an additional “tip” that is transferred to the block’s miner. Small tips should be sufficient to incentivize a miner to include a transaction during a period of stable demand, when there is room in the current block for all the outstanding transactions that are willing to pay the reserve price. Large tips can be used to encourage special treatment of a transaction, such as immediate inclusion in a block in the midst of a sudden demand spike. Section 4 also introduces the tipless mechanism, a variant of the 1559 mechanism in which the tips are hard-coded rather than user-specified. Relative to the 1559 mechanism, the tipless mechanism provides more robustness to non-straightforward bidding while sacrificing some resistance to off-chain collusion. Section 5 contains the main results of this paper, and considers in turn the MMIC, DSIC, and OCA-proofness properties. Section 5.1 provides a sufficient condition for establishing the MMIC property (Theorem 5.2): the payment of a transaction should be independent of the other included transactions and their bids, and the allocation rule should maximize miner profit. This condition implies that FPAs, the 1559 mechanism, and the tipless mechanism are MMIC (Corollary 5.3). Second-price-type auctions are notable examples of non-MMIC mechanisms (Example 3.5). Section 5.2 studies the extent to which different transaction fee mechanisms meet the DSIC condition. Theorem 5.5 shows that the tipless mechanism acts as a posted-price mechanism (with price equal to the reserve price plus the hard-coded tip) and, as such, is DSIC. The 1559 mechanism reverts to an FPA in the special case of a zero reserve price, but Theorem 5.7 identifies two conditions that together are sufficient for the optimality of straightforward bidding: the base fee should not be excessively low for the current demand curve (Definition 5.6), and transaction creators should use individually rational bidding strategies. Under these conditions, the 1559 mechanism acts as a posted-price mechanism, Another line of work analyzes Bitcoin transaction fees as a market equilibrium. Houy [17] and Rizun [25] formalized the intuitive idea that equilibrium transaction fees should be determined by the matching of supply with demand. Richer models of demand, with waiting costs and pending transactions persisting until inclusion, are considered by Easley et al. [14] and Huberman et al. [18]. Among other results, these papers show that, as the fixed block reward decreases, the Bitcoin network can remain economically viable only if there is suf sufficient congestion (and consequent delays) to prop up the market-clearing transaction fees. Similar models of demand are investigated (in the context of EIP-1559) through simulations by Monnot et al. [22]. Three previous works focus squarely on the design of alternative transaction fee mechanisms. Lavi et al. [19] and Yao [27], motivated by the aforementioned need to keep Bitcoin miner revenues high even as the block reward goes to zero, proposed the “monopolistic price” transaction fee mechanism. In this mechanism, all transactions included in a block pay the same amount (per unit size), which is the lowest bid by any included transaction. (See also Example 3.5.) Miners are then expected to maximize their revenue (price times quantity), which may involve restricting the supply (i.e., producing an underfull block) to prop up the price. Lavi et al. [19] and Yao [27] proved that this mechanism is “approximately DSIC,” in the sense that truthful bidding is an approximately dominant strategy for users as the number of users grows large [19, 27]. With respect to the two new notions of incentivecompatibility introduced in this paper, the mechanism is MMIC but, on account of choosing revenue-maximization over joint utility-maximization, is not OCA-proof. Basu et al. [4] also proposed an alternative transaction fee mechanism to FPAs, with an eye toward stronger incentive-compatibility guarantees; we summarize a slightly simplified version of it here. With the monopolistic price mechanism as a starting point, the mechanism in [4] adds two additional ideas. The first is to automatically charge only a nominal transaction fee to all transactions in any block that is not full. This rule is intended to prevent miners from boosting their revenue through the production of underfull blocks, though by itself the rule is toothless and leads to a mechanism equivalent to the monopolistic price mechanism (a miner can costlessly extend its favorite underfull block with minimum bid b to a full block with minimum bid b using fake transactions, all with bid b). The second new addition is that transaction fees are partially paid forward, with the transaction fee revenue from a block B split evenly between B’s miner and the miners of the ℓ − 1 subsequent blocks (here ℓ is a tunable parameter). Thus, the miner of a block gets a 1/ℓ fraction of the transaction fee revenue in that block, along with a 1/ℓ fraction of the combined revenue of the preceding ℓ − 1 blocks. As a result, for ℓ ≥ 2, fake transactions now carry a cost: the miner pays their full transaction fees but recoups only a 1/ℓ fraction of them as revenue. In our terminology, Besu et al. [4] prove that their mechanism is approximately MMIC and approximately DSIC provided the range of possible valuations is bounded and the number of transactions involved is sufficiently large. Perhaps the biggest vulnerability of this mechanism is its failure to satisfy OCA-proofness (for every ℓ ≥ 2): a miner and transaction creators could collude to move all transaction fees off-chain (paid to the miner), leaving no on-chain fees to pay forward to future miners (cf., Corollary 5.17). Our notion of incentive-compatibility for myopic miners (Definition 3.4) concerns an untrusted auctioneer (the miner), and as such is related to credible mechanisms [2]. Intuitively, a mechanism is credible if the agent tasked with carrying it out has no plausibly deniable utility-improving deviation. Interestingly, because miners can manipulate allocations but not prices (Remark 2.7), there is no need to restrict to “plausibly deniable” deviations in Definition 3.4. Another difference is that the current theory of credible mechanisms, and in particular the characterizations in [2], is largely restricted to single-item auctions (though see [12] for approximate revenue-optimality results in more general settings). Blockchain transaction fee mechanisms must work in the more general setting of (multi-item) knapsack auctions [1]. Discussion The 1559 and tipless mechanisms are the two clear winners in our study of MMIC, DSIC, and OCA-proof transaction fee mechanisms—both provide two of these three incentivecompatibility guarantees in all circumstances, and all three in what is plausibly the common case of a base fee that is reasonably well tuned to the current demand. In a block with an excessively low base fee (presumably due to rapidly increasing demand), one might expect bidding wars in the 1559 mechanism (on account of the failure of DSIC) and off-chain coordination in the tipless mechanism (due to the breakdown of OCA-proofness). We conjecture that there is no transaction fee mechanism that always satisfies all three properties. More generally, it would be interesting to characterize the mechanisms that satisfy various subsets and relaxations of these three properties. Perhaps the strongest argument in favor of the tipless mechanism over the 1559 mechanism is its simplicity. On the user side, there are several simplifications. The creator of a transaction t must specify only one parameter (a fee cap ct) rather than two (a fee cap ct and a tip δt). The “obvious optimal bid” in the tipless mechanism (setting ct = vt) is optimal for every block and no matter what the bids of the competing transactions. The “obvious optimal bid” in the 1559 mechanism (setting ct = vt and δt = µ) is optimal only in blocks with neither an excessively low base fee nor overbidding. On the miner side, assuming that δ ≥ µ, the revenue-maximizing strategy simplifies to maximizing the block size while using only eligible transactions (i.e., with bid at least r +δ). On the negative side, the hard-coded tip δ in the tipless mechanism would likely need to be adjusted over time via protocol upgrades. Also, the tipless mechanism’s apparent DSIC advantage over the 1559 mechanism in blocks with excessively low base fees breaks down in the presence of cartels of colluding users or even a single user who creates multiple transactions. The reason is that, in a block with an excessively low base fee, such a cartel or user could coordinate bids across transactions to manipulate the (arbitrary but consistent) tie-breaking rule of the mechanism. When the base fee is not excessively low, the 1559 and tipless mechanisms are effectively unlimited-supply posted-price mechanisms; as such, the bidding strategies in Theorems 5.5 and 5.7 remain optimal for users that control multiple transactions (assuming an additive valuation over them) and for cartels of colluding users. Corollary 5.17 shows that, for a block’s base fee to be economically meaningful, no revenue from it can be passed on to the block’s miner. The simplest solution is to burn all the base fee revenues. One appealing alternative implementation, with the same incentive-compatibility properties, is to instead split the base fee revenues of a block equally among the miners of the next ℓ blocks. (Here ℓ is a tunable parameter; the 1559 mechanism can be thought of as the special case in which ℓ = 0.) Thus, a miner of a block receives a 1/ℓ fraction of the sum of the base fee revenues from the previous ℓ blocks, along with all of the tips from the current block. While burning the base fee revenue favors holders of the native currency (through deflation), this “pay-it-forward” implementation favors miners (through more transaction fee revenue). A second trade-off between the two implementations concerns whether variability in demand (and hence transaction fee revenue) translates to variability in blockchain security or in the issuance of new currency. With money-burning, every block changes the money supply in two ways: minting new coins for the block reward (e.g., 2 ETH in Ethereum), and burning the coins used to pay the base fee. Thus the blockchain’s inflation rate would be variable and unpredictable from block to block, but miner revenue (which effectively pays for the blockchain’s security [3, 6]) would stay relatively constant (modulo fluctuations in the market price of the native currency). With the pay-it-forward implementation, the inflation rate would be essentially deterministic but the miner rewards (and, hence, blockchain security) would be unpredictable (though never less than that with money-burning). This paper focuses on incentive issues in transaction fee mechanisms at the time scale of a single block. Many candidate deviations by miners and users manifest already at this time scale. The 1559 mechanism and its variants entangle the transaction fee mechanisms for different blocks through a history-dependent base fee. Dependencies between blocks open up the possibility of miner deviations that unfold over longer time scales. For example, publishing a smaller-than-target block decreases the base fee for the next block, potentially increasing the revenue of that block’s miner. Every miner would happily free ride on previous miners who have sacrificed some eligible transactions to keep block sizes and hence the base fee down, but no miner has an incentive to actually make such a sacrifice. Long-term manipulation by a cartel of miners thus boils down to sustaining collusion in a repeated multi-player Prisoner’s Dilemma game: If all players cooperate (e.g., keep block sizes small to keep the base fee low in the 1559 mechanism or the bids high in an FPA) they all earn more revenue, but each player has an incentive to unilaterally deviate from this strategy (e.g., when it mines a block, to pack that block full to maximize its immediate tip revenue, thereby decreasing the revenue earned by miners of future blocks). Persistent and harmful miner collusion has not yet been observed in a major blockchain such as Bitcoin or Ethereum. None of the primary transaction fee mechanisms discussed in this paper (FPAs, the 1559 mechanism, and the tipless mechanism) are obviously more vulnerable than the others to such long-term collusion. It would be interesting to develop a more nuanced understanding of this issue.