The Game Theory Behind Blockchain Fee Models

Table of Links

Abstract and 1. Introduction

2. Related Work

3. Preliminaries

   3.1 TFMs: Desirable Properties

   3.2 Groves’ Redistribution Mechanism (RM)

4. IDEAL-TFRM: Impossibility of Achieving Strictly Positive Redistribution Index

5. Transaction Fee Redistribution Mechanism (TFRM)

6. R-TFRM: A TFRM Robust to Miner Manipulation

   6.1 R-TFRM: Analyzing Impact of Miner Manipulation on Rebate and Miner Revenue

7. R2-TFRM: Robust and Rational TFRM

8. Conclusion and References

A. Proofs for Results from Section 4 and 5

B. Proofs for Results from Section 6

C. Proofs for Results from Section 7

2 RELATED WORK

The role of transaction fees in decentralized cryptocurrencies such as Bitcoin and Ethereum has been studied in relation to (i) transaction latency [22, 23, 30], (ii) fairness [2, 34] and most recently, as decentralized auction-based mechanisms [8, 14, 33, 40].

Transaction Fee Mechanism (TFM). Roughgarden [33] formulated the transaction issuer and miner interaction as an auction setting. More concretely, the author expresses popular mechanisms in the TFM framework, including first-price, second-price, and EIP1559. Roughgarden [33] introduces user incentive compatibility (UIC), miner incentive compatibility (MIC), and off-chain agreement (OCA) proof as desirable incentive properties for TFMs. E.g., EIP1559 satisfies UIC, MIC, and OCA-proof – under specific constraints on the base fee. Ferreira et al. [14] present a dynamic posted-price TFM which is UIC (if the network is not congested) and MIC. The authors also provide an equilibrium posted price based on the demand. Chung and Shi [8] show it is impossible to construct a TFM that simultaneously satisfies UIC, MIC, and OCA-proof (even when only a single user and the miner collude). To address the impossibility, they introduce a penalty to the creator of a fake transaction, discounted by a parameter “𝛾." The authors present a randomized (based on trusted on-chain randomness) second-price auction that satisfies the three properties. Lastly, the authors in [40] relax UIC to Bayesian UIC (BUIC) to construct another second-price-based auction, satisfying BUIC, MIC, and OCA-proof.

Redistribution Mechanism (RM). Popular auction-based mechanisms like VCG and Groves [9, 15, 37] satisfy AE and UIC but do not satisfy SBB. Faltings [13] and Guo and Conitzer [19] achieve SBB by compromising on AE. Hartline and Roughgarden [21] propose a mechanism that maximizes the sum of the agents’ utility in expectation. de Clippel et al. [11] “destroy" some items to maximize the agents’ utilities, leading to approximate AE and SBB. Parkes et al. [31] propose an alternate approach by proposing an optimization problem which is approximately AE, SBB.

Maskin et al. [25] first propose the idea of redistribution of the surplus as far as possible after preserving UIC and AE. Bailey [1], Cavallo [6], [27], and Guo and Conitzer [18] consider a setting of allocating 𝑘 homogeneous objects among 𝑛 competing agents with unit demand. Guo and Conitzer [20] generalize their work in [18] to multi-unit demand to obtain worst-case optimal (WCO) RM.

In summary, the relatively recent TFM literature only focuses on the satisfiability of desirable incentive properties and not on reducing the user cost. Given that a decentralized cryptocurrency (e.g., Bitcoin or Ethereum) is a public resource, re-imaging a TFM as an RM will (i) continue to guarantee these properties but, crucially, (ii) minimize the cost paid by the user.

3 PRELIMINARIES

We now (i) formally introduce TFMs, (ii) relevant game-theoretic definitions, and (iii) summarize redistribution mechanisms. Table 1 tabulates the notations used in this paper.

Transaction Fee Mechanism (TFM) Model. We have a strategic but myopic[2] miner building a block 𝐵 (with finite capacity) for the underlying blockchain. There are 𝑚 transactions available to be confirmed in a mempool 𝑀. However, the block can hold only up to 𝑛 < 𝑚 transactions. We assume that all transactions are of the same size. Among the 𝑛 transactions included in the block, the miner confirms 𝑘 ≤ 𝑛 transactions[3].

In TFMs, the included (but not confirmed) bids are often used as ‘price-setting’ bids [8]. We use the example of a second-price TFM to explain Definition 1 better.

In order to define the desirable properties of a TFM, we first define user and miner utilities.

That is, the miner’s utility only depends on the set of transactions 𝐵 ∩ 𝑀 since for transactions in 𝐹 , it is paying to itself.