Paper 2022/1294

What Can Cryptography Do For Decentralized Mechanism Design?

Elaine Shi, Carnegie Mellon University
Hao Chung, Carnegie Mellon University
Ke Wu, Carnegie Mellon University

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 simultaenously 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.

Available format(s)
Publication info
Published elsewhere. ITCS 2023
blockchainmechanism designmulti-party computation
Contact author(s)
runting @ gmail com
haochung @ andrew cmu edu
kew2 @ andrew cmu edu
2023-02-19: last of 5 revisions
2022-09-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elaine Shi and Hao Chung and Ke Wu},
      title = {What Can Cryptography Do For Decentralized Mechanism Design?},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1294},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.