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). Unfortunately, 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, even if the block size is infinite. Second, assuming a finite block size, no non-trivial TFM can simultaneously provide incentive compatibility for any individual user and for any miner-user coalition.

This thesis explores potential relaxations and the theoretical landscape of transaction fee mechanisms under these relaxations. We delve into four key directions:

1. MPC-assisted model. We introduce a new MPC-assisted model, where the TFM is implemented through a joint multi-party computation (MPC) protocol among miners. While this model does not get rid of the zero-miner revenue limitation, it indeed allows us to overcome some impossibility results pertaining to the original model (henceforth called the plain model), leading to non-trivial mechanisms with useful guarantees that are otherwise impossible in the plain model.

2. Approximate Incentive Compatibility. Allowing strategic players to gain no more than ε-additional utility compared to honest behavior, we design mechanisms with positive miner revenues in both the plain and MPC-assisted models. Despite achieving optimality with respect to the miner revenue, these mechanisms have poorly scalable miner revenue, as we proved with certain impossibility results.

3. Reasonable-world assumption. We show that if we make a mildly stronger assumption assuming that we know a lower bound h on the number of honest users and an upper bound d on the number of bids controlled by the coalition, we can circumvent the previous limitations on miner revenue, and design mechanisms that generate optimal miner revenue linear in h.

4. Miner-user coalition proof. Here, we consider another flavor of notion capturing incentives of the miner-user coalitions: miner-user coalition proof, which requires that any miner-user coalition is unstable. We show that, under this new notion, we are able to design interesting transaction fee mechanisms for finite block sizes that satisfy incentive compatibility for any individual user and any miner coalition, as well as miner-user coalition proofness.

131 pages

Thesis Committee:
Elaine Shi(Chair)
Ryan O'donnell
AAyush Jain
Tim Roughgarden (Columbia University/A16Z)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu