Computer Science Thesis Oral
— 2:00pm
Location:
In Person
-
Reddy Conference Room, Gates Hillman 4405
Speaker:
KE WU
,
Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://kewucs.com/
What Can Cryptography Do For Transaction Fee 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). Unfortunately, Chung and Shi showed two impossibility results that rule out the existence of dream TFMs. First, any TFM that provides incentive compatibility for individual users and miner-user coalitions must always have zero miner revenue, even for infinite block size. 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 in four key directions:
- MPC-assisted model: We introduce a new model, where the TFM is implemented through a joint multi-party computation (MPC) protocol among miners. While this model does not eliminate the zero-miner revenue limitation, it helps to overcome some impossibility results in the original model (henceforth called the plain model), leading to non-trivial mechanisms with incentive compatible guarantees.
- 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.
- 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.
- 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 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.
Thesis Committee:
Elaine Shi (Chair)
Ryan O'Donnell
Aayush Jain
Tim Roughgarden (Columbia University / A16Z)