DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2024.98

Maximizing Miner Revenue in Transaction Fee Mechanism Design

Authors: Ke Wu, Elaine Shi, and Hao Chung

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract

Transaction fee mechanism design is a new decentralized mechanism design problem where users bid for space on the blockchain. Several recent works showed that the transaction fee mechanism design fundamentally departs from classical mechanism design. They then systematically explored the mathematical landscape of this new decentralized mechanism design problem in two settings: in the plain setting where no cryptography is employed, and in a cryptography-assisted setting where the rules of the mechanism are enforced by a multi-party computation protocol. Unfortunately, in both settings, prior works showed that if we want the mechanism to incentivize honest behavior for both users as well as miners (possibly colluding with users), then the miner revenue has to be zero. Although adopting a relaxed, approximate notion of incentive compatibility gets around this zero miner-revenue limitation, the scaling of the miner revenue is nonetheless poor. In this paper, we show that if we make a mild reasonable-world assumption that there are sufficiently many honest users, we can circumvent the known limitations on miner revenue, and design auctions that generate asymptotically optimal miner revenue. We also systematically explore the mathematical landscape of transaction fee mechanism design under the new reasonable-world assumptions, and demonstrate how such assumptions can alter the feasibility and infeasibility landscape.

Cite as

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 98:1-98:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wu_et_al:LIPIcs.ITCS.2024.98,
  author =	{Wu, Ke and Shi, Elaine and Chung, Hao},
  title =	{{Maximizing Miner Revenue in Transaction Fee Mechanism Design}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{98:1--98:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.98},
  URN =		{urn:nbn:de:0030-drops-196266},
  doi =		{10.4230/LIPIcs.ITCS.2024.98},
  annote =	{Keywords: Blockchain, Mechanism Design, Transaction Fee}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2023.97

What Can Cryptography Do for Decentralized Mechanism Design?

Authors: Elaine Shi, Hao Chung, and Ke Wu

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{shi_et_al:LIPIcs.ITCS.2023.97,
  author =	{Shi, Elaine and Chung, Hao and Wu, Ke},
  title =	{{What Can Cryptography Do for Decentralized Mechanism Design?}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{97:1--97:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.97},
  URN =		{urn:nbn:de:0030-drops-176005},
  doi =		{10.4230/LIPIcs.ITCS.2023.97},
  annote =	{Keywords: Transaction Fee Mechanism Design}
}

Search Results

Documents authored by Chung, Hao

Maximizing Miner Revenue in Transaction Fee Mechanism Design

Abstract

Cite as

What Can Cryptography Do for Decentralized Mechanism Design?

Abstract

Cite as

Thanks for your feedback!

Could not send message