PaperlayerView exact revision on arXiv

Source-linked AI summary

Transaction Fee Mechanism Design

Tim Roughgarden

arXiv:2106.01340v3cs.CRcs.DCcs.DScs.GTecon.TH

TL;DR

Blockchains must choose which pending transactions fit into scarce block capacity, and fee mechanisms must account for strategic behavior by users and miners. The paper formalizes incentive guarantees and applies them to EIP-1559 and a tipless alternative, finding that their guarantees are incomparable.

  • Problem

    Blockchains face demand far exceeding transaction capacity, while fee mechanisms must address user bidding, miner deviations, and miner-user collusion.

    Source: §1 · p. 1, §3.3 · p. 15

  • Method

    The paper formalizes transaction fee mechanisms and evaluates EIP-1559 and a tipless variant against DSIC, MMIC, and OCA-proofness.

    Source: §1 · p. 2, Paper Structure · p. 4

  • Results

    The 1559 mechanism and the tipless mechanism are incomparable when assessed by MMIC, DSIC, and OCA-proofness.

    Source: §5 · p. 20

  • Takeaways & Limitations

    The tipless mechanism simplifies bidding to a fee cap and makes setting it to the user’s valuation optimal for every block and competing-bid profile.

    Source: §6 · p. 28

    The tipless mechanism is not OCA-proof when the base fee is excessively low.

    Source: §5.3 · p. 26

Abstract

from arXiv · show

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

Blockchains must allocate scarce block capacity among far more pending transactions, raising the question of whether transaction fee mechanisms can improve incentive compatibility over first-price auctions. The paper develops blockchain-specific incentive guarantees and applies them to EIP-1559 and a tipless alternative.

1 Introduction

  • The paper asks whether a transaction fee mechanism can meet blockchain-specific constraints while reducing strategic complexity relative to first-price auctions.Demand exceeds capacity, and the question accounts for miners’ control and the possibility of off-chain collusion.Source: §1 · p. 2

EIP-1559

  • EIP-1559 combines variable-size blocks, a history-dependent reserve price, and burning fees; the paper formalizes the proposal and analyzes its stated design goals.The analysis responds to concerns about the proposal’s lack of a formal specification or proof for independent evaluation.Source: EIP-1559 · p. 3

Paper Structure

  • The authors introduce MMIC for miner deviations and fake transactions, and OCA-proofness for off-chain collusion between miners and users, alongside DSIC.These guarantees address distinct forms of strategic behavior in the blockchain setting.Source: Paper Structure · p. 4

Related Work

  • Prior work includes alternative fee designs with approximate DSIC or MMIC guarantees, while the paper frames its analysis around three incentive properties.For example, the monopolistic-price mechanism is MMIC but not OCA-proof, and the pay-forward design is not OCA-proof.Source: Paper Structure · p. 4, Related Work · pp. 6–7

2 Preliminaries

The preliminaries model a block as a capacity-constrained allocation of pending transactions and define the transaction-fee mechanism components that govern inclusion and revenue. Blockchain-specific rules restrict payment and burning calculations to on-chain information and allow revenue to be burned or redirected.

2.1 Blockchain Transactions

  • A block has a maximum transaction size, and miners choose which pending transactions to include from their mempools.The miner has dictatorial control over inclusion and ordering.Source: §2.1 · p. 9

2.2 The Basic Model

  • The model represents supply by block capacity C and demand by the mempool M, with each transaction characterized by its size, valuation, and bid.Valuation is private, while the confirmed transaction’s size and bid are recorded on-chain.Source: §2.2 · pp. 9–10

2.3 The Design Space: Allocation, Payment, and Burning Rules

  • A transaction fee mechanism consists of an allocation rule, a payment rule, and a burning rule, with payment and burning restricted to on-chain information.Revenue may be burned or directed away from the miner.Source: §2.3 · p. 10, §2.3.2 · p. 12

2.3.1 Allocation Rules

  • An allocation rule maps history and the mempool to transaction inclusion decisions, subject to the block-size capacity constraint.An inclusion value of 1 means the transaction is placed in the current block; 0 means exclusion.Source: §2.3.1 · p. 10

2.3.2 Payment and Burning Rules

  • Payment and burning rules assign included transactions’ transfers to the miner and amounts burned, respectively, based on history and the current block.In the historical first-price auction, winners pay their bids to the miner and no fees are burned.Source: §2.3.2 · p. 11

3 Miners, Users, and Incentive Compatibility

The paper distinguishes user bidding incentives from miner deviations and off-chain collusion, defining incentive guarantees for each. These concepts capture the strategic risks created by miner control of block contents and the availability of side channels.

3.1 Users

  • DSIC requires that truthful or otherwise dominant bidding maximize each user’s utility regardless of other users’ bids, assuming the miner follows the allocation rule.The model evaluates user utility as the value of inclusion minus its cost.Source: §3.1 · pp. 12–13

Definition 3.4 (Incentive-Compatibility for Myopic Miners (MMIC))

  • MMIC requires a profit-maximizing myopic miner to follow the intended allocation and create no fake transactions.Miners can otherwise deviate from the allocation or add fake transactions; first-price auctions are MMIC, but second-price-type auctions are not.Source: Definition 3.4… · p. 14, §3.2 · p. 14
  • A second-price-type auction can reward fake bids: with bids 10, 8, and 3, the miner’s revenue rises from 9 to 16 after adding a fake bid of 8.The miner includes the top two real transactions and the fake transaction.Source: Definition 3.4… · p. 15

3.3 Off-Chain Agreements

  • OCA-proofness rules out off-chain agreements that make both the miner and all participating transaction creators strictly better off than a canonical on-chain outcome.Off-chain agreements can coordinate bids, allocations, and transfers, creating a risk where side channels are readily available.Source: §3.3 · pp. 15–16
  • Burning any portion of first-price-auction revenue makes that auction non-OCA-proof, because colluding parties can coordinate to evade the burn.When all proceeds go to the miner, the first-price auction is OCA-proof.Source: §3.3 · p. 16

4 The 1559 and Tipless Mechanisms

The section formalizes EIP-1559’s 1559 mechanism and an alternative tipless mechanism, comparing designs built around a history-dependent base fee and burned base-fee revenue. Variable-size blocks provide an on-chain demand signal, while the tipless design replaces user-specified tips with a hard-coded tip.

Burning a history-dependent base fee

  • Inferring demand from past blocks is underspecified because the chain records confirmed transactions but not transactions priced out by the base fee.The section frames this as a challenge when a sequence of maximum-size blocks could reflect either a base fee that is too low or one that is exactly right.Source: §4 · p. 16

Variable-size blocks

  • Variable-size blocks use sizes above or below target as on-chain signals of positive or negative excess demand, with maximum size set to twice the target.The mechanism adjusts the base fee upward or downward when the latest block is larger or smaller than target, respectively.Source: §4 · p. 17

Tips

  • EIP-1559 tips reward miners for inclusion: small tips can suffice when demand is stable, while large tips can seek priority during a sudden demand spike.The fee cap also limits the transaction’s effective bid relative to the base fee.Source: §4 · p. 17

Scope of the analysis

  • The analysis considers a single-block timescale with a fixed, public base fee, leaving the rules governing its evolution across blocks outside the analysis.The cited scope note says the “usually” incentive guarantees implicitly assume a rule that prevents the base fee from becoming excessively low relative to demand under normal conditions.Source: §4 · pp. 17–18

The 1559 mechanism

  • The 1559 mechanism uses a history-dependent base fee, requires a fee cap at least as high as that fee, and burns base-fee revenue.A transaction pays size times the lesser of base fee plus tip or fee cap; any remainder above the base fee goes to the miner.Source: §4 · pp. 16–18

The tipless mechanism

  • The tipless mechanism replaces user-specified tips with a hard-coded tip, while retaining a history-dependent base fee that is burned.Only transactions with bids of r+δ are eligible; when δ is at least the marginal cost, the intended allocation includes a largest-possible subset of eligible transactions.Source: §4 · pp. 16, 18, 19

5 Main Results: Which TFMs Are MMIC, DSIC, or OCA-Proof?

This section develops criteria for MMIC, DSIC, and OCA-proofness and applies them to transaction fee mechanisms. It also establishes OCA-proofness limitations for β-burn FPAs and β-burn 1559 mechanisms.

5 Main Results: Which TFMs Are MMIC, DSIC, or OCA-Proof?

  • By these three guarantees, FPAs dominate β-burn FPAs with β > 0, 1559 dominates those and β-burn 1559 with β < 1, while 1559 and tipless are incomparable.Table 1 summarizes the results for the six designs.Source: §5 · p. 20, Table 1 · p. 20

5.1 MMIC and Non-MMIC TFMs

5.2 DSIC and Non-DSIC TFMs

  • The tipless mechanism is DSIC, while 1559 is DSIC when its base fee is not excessively low and creators cannot overbid; FPAs and β-burn FPAs are not DSIC.In those DSIC cases, the dominant bid is min{r + µ, vt}; excessively low base fees may occur transiently while the fee catches up to a sudden demand spike, and the 1559 result carries over to β-burn 1559.Source: §5.2 · pp. 22–24

5.3 OCA-Proof and Non-OCA-Proof TFMs

  • OCA-proofness is equivalent to an individually rational bidding strategy whose induced outcome maximizes joint miner-user utility; FPAs and 1559 satisfy this condition.The section notes that posted pricing and fee burning matter together for OCA-proofness, rather than either change in isolation.Source: §5.3 · pp. 24, 25, 27
  • The defined SPA is almost OCA-proof: its greedy allocation may yield slightly less social welfare than the maximum, permitting a small Pareto improvement.With a welfare-maximizing allocation rule, an SPA would be OCA-proof under truthful bidding.Source: §5.3 · p. 25
  • With δ = µ, tipless is OCA-proof when the base fee is not excessively low, but not generally when it is excessively low or when δ > µ.If δ − µ is small, the possible joint-surplus improvement from an OCA is negligible.Source: §5.3 · pp. 26–27
  • For every β ∈ (0, 1], a β-burn FPA is not OCA-proof.Source: §5.3 · p. 27
  • For every β ∈ [0, 1), the β-burn 1559 mechanism is not OCA-proof.Source: §5.3 · p. 27

6 Discussion

The discussion compares the 1559 and tipless mechanisms, outlines trade-offs in burning versus redirecting base-fee revenue, and flags long-term miner collusion as a question beyond the paper’s single-block focus.

The 1559 mechanism vs. the tipless mechanism, and beyond

  • The 1559 and tipless mechanisms are the clear winners: each provides two of three incentive guarantees always and all three when the base fee is reasonably tuned.With an excessively low base fee, 1559 may lose DSIC and tipless may lose OCA-proofness; the authors conjecture no mechanism always satisfies all three properties.Source: §6 · pp. 27–28
  • Tipless is simpler for users and miners, but its fixed tip may need protocol upgrades and low-base-fee tie-breaking can enable coordination across transactions.When the base fee is not excessively low, both designs act as unlimited-supply posted-price mechanisms, with optimal bidding extending to additive multi-transaction users and user cartels.Source: §6 · p. 28

Alternatives to burning

  • Burning base fees favors currency holders, while paying them forward among the next ℓ miners favors miners without changing the incentive-compatibility properties.Burning makes inflation variable while miner revenue stays relatively constant; paying forward makes inflation essentially deterministic but miner rewards unpredictable.Source: §6 · pp. 28–29

Multi-block time scales

  • A smaller-than-target 1559 block can lower the next base fee and raise the next miner’s revenue, creating cross-block incentives and a repeated-game collusion problem.Miners may benefit collectively from keeping blocks small, yet each has a myopic incentive to fill its own block and maximize immediate tips.Source: §6 · p. 29
  • Persistent harmful miner collusion has not been definitively observed on Bitcoin or Ethereum, and the paper does not identify one of its three main mechanisms as obviously more vulnerable.The authors identify a significant miner or validator share, around 30% for example, as a regime where non-myopic strategies might plausibly pay off.Source: §6 · p. 29

Related papers

Loading 2106.01340v3…