What can cryptography do for decentralized mechanism design?

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.

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. While we show that cryptography 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, it is not a panacea. We still have a zero-miner revenue limitation. To overcome this impossibility, we introduce a mildly stronger reasonable-world assumption, under which we can design mechanisms that achieve optimal miner revenue. We also systematically explore the mathematical landscape of transaction fee mechanism design under the new MPC-assisted model and demonstrate how the reasonable-world assumptions can alter the feasibility and infeasibility landscape.

Based on joint work with Elaine Shi and Hao Chung.