Document Open Access Logo

What Can Cryptography Do for Decentralized Mechanism Design?

Authors Elaine Shi, Hao Chung, Ke Wu

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.97.pdf
  • Filesize: 0.84 MB
  • 22 pages

Document Identifiers

Author Details

Elaine Shi
  • ECE and CSD Department, Carnegie Mellon University, Pittsburgh, PA, USA
Hao Chung
  • ECE Department, Carnegie Mellon University, Pittsburgh, PA, USA
Ke Wu
  • CSD Department, Carnegie Mellon University, Pittsburgh, PA, USA

Funding

Research supported by NSF awards 2212746, 2044679, 1704788, a Packard Fellowship, a generous gift from the late Nikolai Mushegian, a gift from Google, and an ACE center grant from Algorand Foundation.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 97:1-97:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.97

Abstract

Recent works of Roughgarden (EC'21) and Chung and Shi (SODA'23) initiate the study of a new decentralized mechanism design problem called transaction fee mechanism design (TFM). Unlike the classical mechanism design literature, in the decentralized environment, even the auctioneer (i.e., the miner) can be a strategic player, and it can even collude with a subset of the users facilitated by binding side contracts. Chung and Shi showed two main impossibility results that rule out the existence of a dream TFM. First, any TFM that provides incentive compatibility for individual users and miner-user coalitions must always have zero miner revenue, no matter whether the block size is finite or infinite. Second, assuming finite block size, no non-trivial TFM can simultaneously provide incentive compatibility for any individual user and for any miner-user coalition. In this work, we explore what new models and meaningful relaxations can allow us to circumvent the impossibility results of Chung and Shi. Besides today’s model that does not employ cryptography, we introduce a new MPC-assisted model where the TFM is implemented by a joint multi-party computation (MPC) protocol among the miners. We prove several feasibility and infeasibility results for achieving strict and approximate incentive compatibility, respectively, in the plain model as well as the MPC-assisted model. We show that while cryptography is not a panacea, it indeed allows us to overcome some impossibility results pertaining to the plain model, leading to non-trivial mechanisms with useful guarantees that are otherwise impossible in the plain model. Our work is also the first to characterize the mathematical landscape of transaction fee mechanism design under approximate incentive compatibility, as well as in a cryptography-assisted model.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
Keywords
  • Transaction Fee Mechanism Design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ittai Abraham, Danny Dolev, Rica Gonen, and Joseph Halpern. Distributed computing meets game theory: Robust mechanisms for rational secret sharing and multiparty computation. In PODC, 2006. Google Scholar
  2. Gilad Asharov, Ran Canetti, and Carmit Hazay. Towards a game theoretic view of secure computation. In Eurocrypt, 2011. Google Scholar
  3. Gilad Asharov and Yehuda Lindell. Utility dependence in correct and fair rational secret sharing. Journal of Cryptology, 24(1), 2011. Google Scholar
  4. Soumya Basu, David A. Easley, Maureen O'Hara, and Emin Gün Sirer. Towards a functional fee market for cryptocurrencies. CoRR, abs/1901.06830, 2019. URL: http://arxiv.org/abs/1901.06830.
  5. Vitalik Buterin, Eric Conner, Rick Dudley, Matthew Slipper, and Ian Norden. Ethereum improvement proposal 1559: Fee market change for eth 1.0 chain. URL: https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1559.md.
  6. Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 2000. Google Scholar
  7. Hao Chung and Elaine Shi. Foundations of transaction fee mechanism design. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.03151.
  8. Kai-Min Chung, T-H. Hubert Chan, Ting Wen, and Elaine Shi. Game-theoretic fairness meets multi-party protocols: The case of leader election. In CRYPTO. Springer-Verlag, 2021. Google Scholar
  9. Kai-Min Chung, Yue Guo, Wei-Kai Lin, Rafael Pass, and Elaine Shi. Game theoretic notions of fairness in multi-party coin toss. In TCC, volume 11239, pages 563-596, 2018. Google Scholar
  10. Yevgeniy Dodis and Tal Rabin. Cryptography and game theory. In AGT, 2007. Google Scholar
  11. Meryem Essaidi, Matheus V. X. Ferreira, and S. Matthew Weinberg. Credible, strategyproof, optimal, and bounded expected-round single-item auctions for all distributions. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 66:1-66:19, 2022. Google Scholar
  12. Matheus V. X. Ferreira, Daniel J. Moroz, David C. Parkes, and Mitchell Stern. Dynamic posted-price mechanisms for the blockchain transaction-fee market. CoRR, abs/2103.14144, 2021. URL: http://arxiv.org/abs/2103.14144.
  13. Matheus V. X. Ferreira and S. Matthew Weinberg. Credible, truthful, and two-round (optimal) auctions via cryptographic commitments. In Péter Biró, Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020, pages 683-712. ACM, 2020. Google Scholar
  14. Juan Garay, Jonathan Katz, Björn Tackmann, and Vassilis Zikas. How fair is your protocol? a utility-based approach to protocol optimality. In PODC, 2015. Google Scholar
  15. Juan A. Garay, Jonathan Katz, Ueli Maurer, Björn Tackmann, and Vassilis Zikas. Rational protocol design: Cryptography against incentive-driven adversaries. In FOCS, 2013. Google Scholar
  16. Juan A. Garay, Björn Tackmann, and Vassilis Zikas. Fair distributed computation of reactive functions. In DISC, volume 9363, pages 497-512, 2015. Google Scholar
  17. Andrew V. Goldberg and Jason D. Hartline. Collusion-resistant mechanisms for single-parameter agents. In SODA 2005, pages 620-629, 2005. Google Scholar
  18. Ronen Gradwohl, Noam Livne, and Alon Rosen. Sequential rationality in cryptographic protocols. In FOCS, 2010. Google Scholar
  19. Joseph Halpern and Vanessa Teague. Rational secret sharing and multiparty computation. In STOC, 2004. Google Scholar
  20. Sergei Izmalkov, Silvio Micali, and Matt Lepinski. Rational secure computation and ideal mechanism design. In FOCS, 2005. Google Scholar
  21. Jonathan Katz. Bridging game theory and cryptography: Recent results and future directions. In TCC, 2008. Google Scholar
  22. Gillat Kol and Moni Naor. Cryptography and game theory: Designing protocols for exchanging information. In TCC, 2008. Google Scholar
  23. Ilan Komargodski, Shin’ichiro Matsuo, Elaine Shi, and Ke Wu. log*-round game-theoretically-fair leader election. In CRYPTO, 2022. Google Scholar
  24. Ron Lavi, Or Sattath, and Aviv Zohar. Redesigning bitcoin’s fee market. In The World Wide Web Conference, WWW 2019, pages 2950-2956, 2019. Google Scholar
  25. Roger B. Myerson. Optimal auction design. Math. Oper. Res., 6(1), 1981. Google Scholar
  26. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, USA, 2007. Google Scholar
  27. Shien Jin Ong, David C. Parkes, Alon Rosen, and Salil P. Vadhan. Fairness with an honest minority and a rational majority. In TCC, 2009. Google Scholar
  28. Rafael Pass and Elaine Shi. Fruitchains: A fair blockchain. In PODC, 2017. Google Scholar
  29. Tim Roughgarden. Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559. Manuscript, https://timroughgarden.org/papers/eip1559.pdf, 2020.
  30. Tim Roughgarden. Transaction fee mechanism design. In EC, 2021. Google Scholar
  31. Ke Wu, Gilad Asharov, and Elaine Shi. A complete characterization of game-theoretically fair, multi-party coin toss. In Eurocrypt, 2022. Google Scholar
  32. Andrew Chi-Chih Yao. An Incentive Analysis of Some Bitcoin Fee Designs (Invited Talk). In ICALP 2020, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact