Paper 2024/237

Collusion-Resilience in Transaction Fee Mechanism Design

Hao Chung, Carnegie Mellon University
Tim Roughgarden, Columbia University
Elaine Shi, Carnegie Mellon University

Users bid in a transaction fee mechanism (TFM) to get their transactions included and confirmed by a blockchain protocol. Roughgarden (EC'21) initiated the formal treatment of TFMs and proposed three requirements: user incentive compatibility (UIC), miner incentive compatibility (MIC), and a form of collusion-resilience called OCA-proofness. Ethereum's EIP-1559 mechanism satisfies all three properties simultaneously when there is no contention between transactions, but loses the UIC property when there are too many eligible transactions to fit in a single block. Chung and Shi (SODA'23) considered an alternative notion of collusion-resilience, called c-side-constract-proofness (c-SCP), and showed that, when there is contention between transactions, no TFM can satisfy UIC, MIC, and c-SCP for any c at least 1. OCA-proofness asserts that the users and a miner should not be able to "steal from the protocol" and is intuitively weaker than the c-SCP condition, which stipulates that a coalition of a miner and a subset of users should not be able to profit through strategic deviations (whether at the expense of the protocol or of the users outside the coalition). Our main result is the first proof that, when there is contention between transactions, no (possibly randomized) direct-revelation TFM satisfies UIC, MIC, and OCA-proofness. This result resolves the main open question in Roughgarden(EC'21). We also suggest several relaxations of the basic model that allow our impossibility result to be circumvented.

Available format(s)
Publication info
Blockchaintransaction fee mechanismmechanism design
Contact author(s)
haochung @ andrew cmu edu
tim roughgarden @ gmail com
runting @ gmail com
2024-02-16: approved
2024-02-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hao Chung and Tim Roughgarden and Elaine Shi},
      title = {Collusion-Resilience in Transaction Fee Mechanism Design},
      howpublished = {Cryptology ePrint Archive, Paper 2024/237},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.