Table of Links
Abstract and 1. Introduction
1.1 Our Contributions
1.2 TFM Incentive-Compatibility Notions: A Cheat Sheet
-
Definitions
2.1 Transaction Fee Mechanism
2.2 Incentive Compatibility Notions
-
Preliminary: Myerson’s Lemma
-
Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms
-
Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap
5.2 Formal Proofs
-
Feasibility and Impossibility of UIC + MIC + OCA-Proof
6.1 A Non-Truthful Mechanism with UIC + MIC + OCA-Proof
6.2 Impossibility of UIC + MIC + OCA-Proof for Truthful Mechanisms
-
How to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate
7.2 Allowing the Globally Optimal Strategy to Output Multiple Bids
7.3 Inclusion-Rule-Respecting and 7.4 Discussions and Open Questions Regarding the Use of Cryptography
-
Static Revelation Principle for Transaction Fee Mechanisms
8.1 Static Revelation Principle: Bidding Rules That Output Single Bid
8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids
A. Comparison of Collusion-Resilience Notions
References
Abstract
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 EIP1559 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-contract-proofness (c-SCP), and showed that, when there is contention between transactions, no TFM can satisfy UIC, MIC, and c-SCP for any c ≥ 1. OCA-proofness asserts that the users and a miner should not be able to “steal from the protocol.” On the other hand, the c-SCP condition requires 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) TFM in which users are expected to bid truthfully 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.
1 Introduction
Real estate on the blockchain is scarce, and blockchain users bid in an auction called the transaction fee mechanism (TFM) to have their transactions included and confirmed on the blockchain. The original Bitcoin protocol adopted a simple first-price auction, where the top k bids win and they each pay their bid. However, such first-price auctions are known to incentivize untruthful bidding. Therefore, a line of subsequent works [LSZ19, Yao, BEOS19, BCD+, Rou20, Rou21, FMPS21, CS23, SCW23, WSC24, GY22, ZCZ22, BGR23, TY23, KKLP23, XFP23, CMW23, LRMP23, Ndi23] explored what is the “dream TFM” for blockchains. Most works [Rou20, Rou21, CS23, SCW23, WSC24, GY22, GY22, ZCZ22, BGR23, TY23] agree on roughly the same set of desiderata, that is, a dream TFM should provide incentive compatibility not just for an individual user, but also for the miner of the block. Further, a dream TFM should provide resilience against miner-user collusion.
Roughgarden [Rou21] was the first to formally define the aforementioned requirements for a TFM, which he referred to as user incentive compatibility[1], (myopic) miner incentive compatibility, and OCA-proofness, where OCA stands for “off-chain agreement” and refers to colluding strategies between the miner and a set of users that allow off-chain transfers. Roughgarden [Rou21] also showed that the simple “posted price auction with all fees burnt” mechanism, which corresponds to the behavior of Ethereum’s EIP-1559 TFM [BCD+] when there is no congestion, satisfies all three properties. However, the posted price auction with all fees burnt does not satisfy all three properties when there is congestion. In practice, congestion does occur when there are major events such as an NFT mint or price fluctuations — for example, in Ethereum, roughly 2.3% of the blocks experience congestion.[2] When congestion arises, approximately speaking, Ethereum’s EIP-1559 mechanism falls back to the first-price auction, violating user incentive compatibility. Therefore, an interesting question is whether we can design a dream TFM satisfying all three properties for finite block sizes.
Chung and Shi [CS23] considered an alternative notion of collusion-resilience, called sidecontract-proofness. Unfortunately, they proved that no (even randomized) TFM can simultaneously satisfy user incentive compatibility and side-contract-proofness. Because side-contract-proofness is a more demanding property than OCA-proofness, the question raised by Roughgarden [Rou21], of whether there is a dream TFM satisfying all three properties under his collusion-resilience notion, had remained open.
Two notions of miner-user collusion-resilience. Multiple natural notions of collusion-resilience can and have been studied in the context of TFM design. Here we clarify informally the key differences between the notions proposed by Roughgarden [Rou21] and Chung and Shi [CS23]. These notions are defined formally in Definitions 4–6 (see Section 2) and compared further via examples in Appendix A.
• OCA-proofness: Roughgarden’s notion, henceforth referred to as OCA-proofness, asserts that there should exist a “reference strategy” for a miner and all users that is guaranteed to maximize their joint surplus. In this reference strategy, the miner is expected to follow the inclusion rule intended by the TFM. For users, the definition requires only that users follow some fixed bidding trategy σ (i.e., a mapping from a private user valuation to a user bid) that is individually rational (i.e., σ(v) ≤ v for all v ≥ 0). In particular, in the reference strategy, users are expected to bid independently (with a user’s bid independent of other users’ valuations and bids), and expected to submit a single bid (with no additional fake bids injected). One example of such a bidding strategy is the truth-telling strategy (with σ(v) = v). Because Roughgarden [Rou21] wished to discuss the OCA-proofness properties of non-UIC TFMs like first-price auctions, the definition also allows the reference strategy to be defined by a non-truthful bidding strategy (e.g., σ(v) = v/2). As a consequence, to prove that a TFM is both UIC and OCA-proof, it is sufficient to prove that it is UIC under one bidding strategy and OCA-proof under a possibly different bidding strategy (as in the example in Section 6.1).
• c-SCP: Chung and Shi’s notion [CS23], henceforth called c-SCP (where SCP stands for sidecontract-proofness), requires that the honest strategy (i.e., all users follow the honest bidding rule and the miner honestly implements the inclusion rule) is the profit-maximizing strategy for any coalition consisting of the miner of the present block and at most c users. For truthful mechanisms, the honest bidding rule is the truthful one, while for non-truthful mechanisms, the bidding rule can be more general (see Section 2.1 for the formal definition). Chung and Shi’s notion aligns with standard notions used in a line of work at the intersection of game theory and cryptography [HT04, KN08, ADGH06, OPRV09, AL11, ACH11, GKM+13, GKTZ15, GTZ15, Kat08, DR07, GLR10, CGL+18, WAS22, CCWS21, PS17, KMSW22, FW20, EFW22].
Discussion. The two notions of collusion-resilience address different issues. OCA-proofness captures the intuitive requirement that the users and miners should not be able to steal from the protocol through strategic deviations — for this reason, it considers only the global coalition consisting of the miner and all users. By contrast, the c-SCP notion captures the intuitive idea that a miner-user coalition’s best response is to act honestly, and that no strategic deviations can allow the coalition to steal from other users or steal from the protocol. For further discussion, see the end of this section and Appendix A.
∗Supported by NSF awards 2212746, 2044679, 1704788, a Packard Fellowship, a generous gift from the late Nikolai Mushegian, a gift from Google, and an ACE center grant from Algorand Foundation.
†Author’s research at Columbia University supported in part by NSF awards CCF-2006737 and CNS-2212745, and research awards from the Briger Family Digital Finance Lab and the Center for Digital Finance and Technologies.
[1] User incentive compatibility (UIC) is usually called dominant-strategy incentive compatible (DSIC) in the mechanism design literature. In general, we allow UIC TFMs to non-truthful (but dominant) bidding strategies (see Definition 2).
[2] From Jan 1, 2024 to Feb 5, 2024, 256595 blocks have been produced on Ethereum, and 5840 blocks among them were full (meaning more than 99.9% of the gas limit (30M) was used).
