EC’24 Tutorial on Transaction Fee Mechanism Design

Organizers: Hao Chung, Matheus V. X. Ferreira, Yotam Gafni, Aviv Yaish

Abstract

Blockchains are becoming increasingly important to 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 (Lavi, Sattath, & Zohar, 2019), or as part of a user-miner collusion (Roughgarden, 2021). Alarmingly, recent results show that truthful TFMs that are resistant to miner malfeasance and user-miner collusion necessarily produce zero revenue (Chung, Roughgarden, & Shi, 2024; Chung & Shi, 2023; Gafni & Yaish, 2024a). This implies that the desiderata considered thus far is perhaps too strict for useful designs and should be relaxed (Gafni & Yaish, 2022; Yao, 2018), or that the TFM model should be extended to involve additional actors thereby introducing “healthy” competition (Bahrani, Garimidi, & Roughgarden, 2024b; Huberman, Leshno, & Moallemi, 2021).

In this tutorial, we present the basic TFM framework considered by the literature, we discuss different aspects of TFM design, we 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 a simple model and gradually challenges these assumptions by introducing more complex models that are also closer to reality, where for each model, we present the corresponding major results. With this format, participants will appreciate the intricacies of a real-world TFM and learn about the wide 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)

We are planning to have a tentative panel of thought leaders from both academia and industry, on the major mechanism design challenges in the TFM domain. In case the panel fails to materialize, we will dedicate more time to the talks.

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 to 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 (Yaish, Stern, & Zohar, 2023). On the other hand, recent results have shown that “good” TFMs necessarily result in 0 revenue for miners (Chung et al., 2024; Chung & Shi, 2023; Gafni & Yaish, 2024a), 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.

Related Tutorials

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 a Ph.D. candidate at The Hebrew University, a research consultant at Matter Labs, and a visiting researcher at the University of Innsbruck.
Email: aviv.yaish@mail.huji.ac.il

Reading

- Bahrani, M., Garimidi, P., & Roughgarden, T. (2024a). Centralization in block building and proposer-builder separation. arXiv. https://doi.org/10.48550/arXiv.2401.12120
- Bahrani, M., Garimidi, P., & Roughgarden, T. (2024b). Transaction fee mechanism design in a post-MEV world. Cryptology ePrint Archive. Retrieved from https://ia.cr/2024/331
- Bar-On, Y., & Mansour, Y. (2023, December). Optimal publishing strategies on a base layer. arXiv. https://doi.org/10.48550/arXiv.2312.06448
- Chung, H., Roughgarden, T., & Shi, E. (2024). Collusion-resilience in transaction fee mechanism design. Retrieved from https://arxiv.org/abs/2402.09321
- Chung, H., & Shi, E. (2023). Foundations of transaction fee mechanism design. In Proceedings of the 2023 annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 3856–3899). Society for Industrial; Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch150
- Ferreira, M. V. X., Moroz, D. J., Parkes, D. C., & Stern, M. (2021). Dynamic posted-price mechanisms for the blockchain transaction-fee market. In Proceedings of the 3rd ACM conference on advances in financial technologies (pp. 86–99). New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/3479722.3480991
- Gafni, Y., & Yaish, A. (2022). Greedy transaction fee mechanisms for (non-)myopic miners. Retrieved from https://arxiv.org/abs/2210.07793
- Gafni, Y., & Yaish, A. (2024a, February). Barriers to collusion-resistant transaction fee mechanisms. https://doi.org/10.48550/arXiv.2402.08564
- Gafni, Y., & Yaish, A. (2024b, February). Competitive revenue extraction from time-discounted transactions in the semi-myopic regime. https://doi.org/10.48550/arXiv.2402.08549
- Huberman, G., Leshno, J. D., & Moallemi, C. (2021). Monopoly without a Monopolist: An Economic Analysis of the Bitcoin Payment System. The Review of Economic Studies, 88(6), 3011–3040. https://doi.org/10.1093/restud/rdab014
- Lavi, R., Sattath, O., & Zohar, A. (2019). Redesigning bitcoin’s fee market. In The world wide web conference (pp. 2950–2956). New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/3308558.3313454
- Leonardos, S., Monnot, B., Reijsbergen, D., Skoulakis, E., & Piliouras, G. (2021). Dynamical analysis of the EIP-1559 ethereum fee market. In Proceedings of the 3rd ACM conference on advances in financial technologies (pp. 114–126). New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/3479722.3480993
- Leonardos, S., Reijsbergen, D., Monnot, B., & Piliouras, G. (2023). Optimality despite chaos in fee markets. In Lecture notes in computer science (pp. 346–362). Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-47751-5_20
- Mamageishvili, A., & Felten, E. W. (2023). Efficient rollup batch posting strategy on base layer. In Lecture notes in computer science (pp. 355–366). Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-48806-1_23
- Mamageishvili, A., Kelkar, M., Schlegel, J. C., & Felten, E. W. (2023). Buying Time: Latency Racing vs. Bidding for Transaction Ordering. In J. Bonneau & S. M. Weinberg (Eds.), 5th conference on advances in financial technologies (AFT 2023) (Vol. 282, pp. 23:1–23:22). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2023.23
- Nisan, N. (2023). Serial monopoly on blockchains. Retrieved from https://www.cs.huji.ac.il/~noam/publications/ser-mon.pdf
- Pai, M., & Resnick, M. (2024). Dynamic transaction fee mechanism design.
- Roughgarden, T. (2020). Transaction fee mechanism design for the ethereum blockchain: An economic analysis of EIP-1559. CoRR, abs/2012.00854. Retrieved from https://arxiv.org/abs/2012.00854
- Roughgarden, T. (2021). Transaction fee mechanism design. ACM SIGecom Exchanges, 19(1), 52–55.
- Shi, E., Chung, H., & Wu, K. (2023). What can cryptography do for decentralized mechanism design? In Y. T. Kalai (Ed.), 14th innovations in theoretical computer science conference, ITCS 2023, january 10-13, 2023, MIT, cambridge, massachusetts, USA (Vol. 251, pp. 97:1–97:22). Saarbrücken/Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2023.97
- Wu, K., Shi, E., & Chung, H. (2024). Maximizing Miner Revenue in Transaction Fee Mechanism Design. In V. Guruswami (Ed.), 15th innovations in theoretical computer science conference (ITCS 2024) (Vol. 287, pp. 98:1–98:23). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2024.98
- Xavier Ferreira, M. V., & Parkes, D. C. (2023). Credible decentralized exchange design via verifiable sequencing rules. In Proceedings of the 55th annual ACM symposium on theory of computing (pp. 723–736). New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/3564246.3585233
- Yaish, A., Qin, K., Zhou, L., Zohar, A., & Gervais, A. (2024). Speculative denial-of-service attacks in ethereum. In 33rd USENIX security symposium (USENIX security 24). Philadelphia, PA: USENIX Association. Retrieved from https://ia.cr/2023/956
- Yaish, A., Stern, G., & Zohar, A. (2023). Uncle maker: (Time)stamping out the competition in ethereum. In Proceedings of the 2023 ACM SIGSAC conference on computerand communications security (CCS ’23). New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/3576915.3616674
- Yao, A. C.-C. (2018). An incentive analysis of some bitcoin fee designs. arXiv. https://doi.org/10.48550/arXiv.1811.02351