EC'24 Tutorial on Transaction Fee Mechanism Design

Abstract

Blockchains are becoming increasingly important for the modern digital economy, with Ethereum alone holding assets valued at over $300 billion, and processing a daily transaction volume of more than $1 billion. A blockchain is a decentralized computer that users can interact with via transactions that modify the computer's state. The blockchain is operated by miners, who collect transactions into batches called blocks, and who are responsible for reaching a consensus on the computer's state. Due to the limits of the computer network (e.g., latency and bandwidth), block space is finite and scarce. Thus, users bid for block space in a transaction fee mechanism (TFM). The allocation of this mechanism determines the state transitions of the blockchain computer, with payments given to miners as an incentive to prioritize the allocation of transactions. A key challenge of the blockchain setting is that miners cannot be trusted: they may deviate from the protocol if profitable for them, possibly alone,[1] or as part of a user-miner collusion.[2] Alarmingly, recent results show that truthful TFMs that are resistant to miner malfeasance and user-miner collusion necessarily produce zero revenue.[3] [4] [5] This implies that the desiderata considered thus far is perhaps too strict for useful designs and should be relaxed,[6] [7] or that the TFM model should be extended to involve additional actors, thus introducing "healthy" competition.[8] [9]

In this tutorial, we present the basic TFM framework considered by the literature, discuss different aspects of TFM design, summarize previous major results, and highlight promising avenues for future work. Our goal is to introduce researchers to TFMs and equip them with the tools to conduct state-of-the-art research.

Keywords: Transaction Fee Mechanisms, Blockchains, Auctions, Mechanism Design.

Outline

Blockchains are complex multi-agent systems. The simplest model for a TFM assumes that (1) the miners are selling a single block and miners are myopic (i.e., miner incentives in future auctions are ignored), (2) all slots in a block are identical, and (3) there is a single blockchain. Our tutorial starts with this simple model and gradually challenges its assumptions by introducing more complex considerations that are also closer to reality, where, for each one, we present the corresponding major results. With this format, participants will appreciate the intricacies of a real-world TFM and learn about the great opportunity for future research.

Organization

Lecture 1: TFM for a single block (20 mins)

Lecture 2: Dynamic TFMs (20 mins)

Break (30 mins)

Lecture 3: Extensions to the TFM framework (20 mins)

Panel Discussion (30 mins)

Our panel's focus will be on the major mechanism design challenges currently open in the TFM domain. Our speakers are thought leaders involved in both academia and industry:

Goals & Audience

Our goal is to introduce interested researchers to TFMs and equip them with the tools to conduct state-of-the-art research in this domain. Our target audience encompasses researchers, graduate students, and advanced undergraduates in EconCS. Some familiarity with auctions, mechanism design, or blockchains is helpful but not required.

Importance

Blockchains are becoming increasingly important for the modern digital economy, with Ethereum alone holding assets valued at over $300 billion, and processing a daily transaction volume of more than $1 billion. TFMs govern the resource allocation process on blockchains and are therefore inherently important for the secure, efficient, and fair operation of blockchains. The proper design of TFMs becomes even more crucial when considering that miners are profit-maximizing agents who have been observed to manipulate blockchain mechanisms for profit.[31] However, recent results have shown that "good" TFMs necessarily result in 0 revenue for miners,[32] [33] [34] presenting another major risk: given that processing transactions is costly for miners, they would not perform their duty if it is unprofitable for them. Thus, the design of proper transaction fee mechanisms and the analysis of existing widely used mechanisms are both of immense real-world importance.

In recent years, TFMs have emerged as a distinct research area of particular interest to mechanism designers, yet so far no one has done a tutorial focusing on the topic. With respect to tutorials on related topics, a blockchain tutorial was given in EC'22 ("Economics of Distributed Systems", by Jacob Leshno and Matt Weinberg), and another in EC'18 ("Emerging Research Directions Regarding Incentives and Cryptocurrencies", by Jacob Leshno, Arvind Narayanan, Georgios Piliouras, Alex Psomas and Matt Weinberg). Although not a tutorial, Tim Roughgarden gave a keynote talk in EC'22 on "Economics and Computation in Blockchains/Web3", with a notable portion of the talk dedicated to TFMs.

Organizers

Hao Chung.

Hao Chung is a Ph.D. student at Carnegie Mellon University, where he is advised by Elaine Shi. He is broadly interested in cryptography and mechanism design, especially in the intersection between two topics.
Email: haochung@andrew.cmu.edu

Matheus V. X. Ferreira.

Matheus is a Postdoctoral Fellow in Computer Science at Harvard University and an incoming Assistant Professor of Computer Science at the University of Virginia. He holds a Ph.D. in Computer Science from Princeton University. Matheus's research interests include security, applied cryptography, optimization, and their applications to blockchain systems. He is particularly interested in translating research into practice.
Email: matheus@seas.harvard.edu

Yotam Gafni.

Yotam Gafni is a postdoc student at Weizmann Institute, where he is hosted by Uri Feige. Yotam was a research member at SLMath Berkeley for the 2023 Fall semester, and has recently completed his Ph.D. at Technion, where he was advised by Ron Lavi and Moshe Tennenholtz. He is broadly interested in auctions, mechanism design, and the fairness and security of collaborative voting / machine-learning.
Email: yotam.gafni@gmail.com

Aviv Yaish.

Aviv researches the intricate relationship between the economics and security of cryptocurrencies, with a special interest in breaking cryptocurrency mechanisms. He is an incoming postdoc at Yale, currently finishing his Ph.D. at The Hebrew University, a research consultant at Matter Labs, and a visiting researcher at the University of Innsbruck.
Email: a@yai.sh

References

  1. Ron Lavi, Or Sattath, and Aviv Zohar, "Redesigning Bitcoin's Fee Market," in The World Wide Web Conference, WWW '19 (New York, NY, USA: Association for Computing Machinery, 2019), 2950--56, https://doi.org/10.1145/3308558.3313454. ↩

  2. Tim Roughgarden, "Transaction Fee Mechanism Design," ACM SIGecom Exchanges 19, no. 1 (2021): 52--55. ↩

  3. Hao Chung and Elaine Shi, "Foundations of Transaction Fee Mechanism Design," in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (Society for Industrial; Applied Mathematics, 2023), 3856--99, https://doi.org/10.1137/1.9781611977554.ch150. ↩

  4. Hao Chung, Tim Roughgarden, and Elaine Shi, "Collusion-Resilience in Transaction Fee Mechanism Design," 2024, https://arxiv.org/abs/2402.09321. ↩

  5. Yotam Gafni and Aviv Yaish, "Barriers to Collusion-Resistant Transaction Fee Mechanisms," February 2024, https://doi.org/10.48550/arXiv.2402.08564. ↩

  6. Andrew Chi-Chih Yao, "An Incentive Analysis of Some Bitcoin Fee Designs" (arXiv, 2018), https://doi.org/10.48550/arXiv.1811.02351. ↩

  7. Yotam Gafni and Aviv Yaish, "Greedy Transaction Fee Mechanisms for (Non-)myopic Miners," 2022, https://arxiv.org/abs/2210.07793. ↩

  8. Gur Huberman, Jacob D Leshno, and Ciamac Moallemi, "Monopoly Without a Monopolist: An Economic Analysis of the Bitcoin Payment System," The Review of Economic Studies 88, no. 6 (March 2021): 3011--40, https://doi.org/10.1093/restud/rdab014. ↩

  9. Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden, "Transaction Fee Mechanism Design in a Post-MEV World," Cryptology ePrint Archive, 2024, https://ia.cr/2024/331. ↩

  10. Roughgarden, "Transaction Fee Mechanism Design." ↩

  11. Chung and Shi, "Foundations of Transaction Fee Mechanism Design." ↩

  12. Chung, Roughgarden, and Shi, "Collusion-Resilience in Transaction Fee Mechanism Design." ↩

  13. Gafni and Yaish, "Barriers to Collusion-Resistant Transaction Fee Mechanisms." ↩

  14. Elaine Shi, Hao Chung, and Ke Wu, "What Can Cryptography Do for Decentralized Mechanism Design?" in 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, ed. Yael Tauman Kalai, vol. 251, LIPIcs (Saarbrücken/Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023), 97:1--22, https://doi.org/10.4230/LIPIcs.ITCS.2023.97. ↩

  15. Ke Wu, Elaine Shi, and Hao Chung, "Maximizing Miner Revenue in Transaction Fee Mechanism Design," in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), ed. Venkatesan Guruswami, vol. 287, Leibniz International Proceedings in Informatics (LIPIcs) (Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2024), 98:1--23, https://doi.org/10.4230/LIPIcs.ITCS.2024.98. ↩

  16. Stefanos Leonardos et al., "Dynamical Analysis of the EIP-1559 Ethereum Fee Market," in Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, AFT '21 (New York, NY, USA: Association for Computing Machinery, 2021), 114--26, https://doi.org/10.1145/3479722.3480993. ↩

  17. Yotam Gafni and Aviv Yaish, "Scheduling with Time Discounts," 2024, https://doi.org/10.48550/arXiv.2402.08549. ↩

  18. Noam Nisan, "Serial Monopoly on Blockchains," 2023, https://www.cs.huji.ac.il/~noam/publications/ser-mon.pdf. ↩

  19. Tim Roughgarden, "Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559," CoRR abs/2012.00854 (2020), https://arxiv.org/abs/2012.00854. ↩

  20. Matheus V. X. Ferreira et al., "Dynamic Posted-Price Mechanisms for the Blockchain Transaction-Fee Market," in Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, AFT '21 (New York, NY, USA: Association for Computing Machinery, 2021), 86--99, https://doi.org/10.1145/3479722.3480991. ↩

  21. Leonardos et al., "Dynamical Analysis of the EIP-1559 Ethereum Fee Market." ↩

  22. Stefanos Leonardos et al., "Optimality Despite Chaos in Fee Markets," in Lecture Notes in Computer Science (Springer Nature Switzerland, 2023), 346--62, https://doi.org/10.1007/978-3-031-47751-5_20. ↩

  23. Mallesh Pai and Max Resnick, "Dynamic Transaction Fee Mechanism Design," 2024. ↩

  24. Akaki Mamageishvili et al., "Buying Time: Latency Racing Vs. Bidding for Transaction Ordering," in 5th Conference on Advances in Financial Technologies (AFT 2023), ed. Joseph Bonneau and S. Matthew Weinberg, vol. 282, Leibniz International Proceedings in Informatics (LIPIcs) (Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2023), 23:1--22, https://doi.org/10.4230/LIPIcs.AFT.2023.23. ↩

  25. Bahrani, Garimidi, and Roughgarden, "Transaction Fee Mechanism Design in a Post-MEV World." ↩

  26. Aviv Yaish et al., "Speculative Denial-of-Service Attacks in Ethereum," in 33rd USENIX Security Symposium (USENIX Security 24), USENIXSEC '24 (Philadelphia, PA: USENIX Association, 2024), https://ia.cr/2023/956. ↩

  27. Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden, "Centralization in Block Building and Proposer-Builder Separation" (arXiv, 2024), https://doi.org/10.48550/arXiv.2401.12120. ↩

  28. Matheus Venturyne Xavier Ferreira and David C. Parkes, "Credible Decentralized Exchange Design via Verifiable Sequencing Rules," in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023 (New York, NY, USA: Association for Computing Machinery, 2023), 723--36, https://doi.org/10.1145/3564246.3585233. ↩

  29. Akaki Mamageishvili and Edward W. Felten, "Efficient Rollup Batch Posting Strategy on Base Layer," in Lecture Notes in Computer Science (Springer Nature Switzerland, 2023), 355--66, https://doi.org/10.1007/978-3-031-48806-1_23. ↩

  30. Yogev Bar-On and Yishay Mansour, "Optimal Publishing Strategies on a Base Layer" (arXiv, December 2023), https://doi.org/10.48550/arXiv.2312.06448. ↩

  31. Aviv Yaish, Gilad Stern, and Aviv Zohar, "Uncle Maker: (Time)stamping Out the Competition in Ethereum," in Proceedings of the 2023 ACM SIGSAC Conference on Computerand Communications Security (CCS '23), CCS '23 (New York, NY, USA: Association for Computing Machinery, 2023), https://doi.org/10.1145/3576915.3616674. ↩

  32. Chung and Shi, "Foundations of Transaction Fee Mechanism Design." ↩

  33. Chung, Roughgarden, and Shi, "Collusion-Resilience in Transaction Fee Mechanism Design." ↩

  34. Gafni and Yaish, "Barriers to Collusion-Resistant Transaction Fee Mechanisms." ↩