Authors:
(1) Hao Chung∗, Carnegie Mellon University (haochung@andrew.cmu.edu);
(2) Tim Roughgarden†, Columbia University and a16z (crypto tim.roughgarden@gmail.com);
(3) Elaine Shi∗, Carnegie Mellon University (runting@cs.cmu.edu). Authors: Authors: (1) Hao Chung∗, Carnegie Mellon University (haochung@andrew.cmu.edu); (2) Tim Roughgarden†, Columbia University and a16z (crypto tim.roughgarden@gmail.com); (3) Elaine Shi∗, Carnegie Mellon University (runting@cs.cmu.edu). Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 1.1 Our Contributions 1.1 Our Contributions 1.2 TFM Incentive-Compatibility Notions: A Cheat Sheet 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 Definitions
2.1 Transaction Fee Mechanism
2.2 Incentive Compatibility Notions Definitions 2.1 Transaction Fee Mechanism 2.1 Transaction Fee Mechanism 2.2 Incentive Compatibility Notions 2.2 Incentive Compatibility Notions Preliminary: Myerson’s Lemma Preliminary: Myerson’s Lemma Preliminary: Myerson’s Lemma Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms 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 Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap 5.2 Formal Proofs 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 Feasibility and Impossibility of UIC + MIC + OCA-Proof Feasibility and Impossibility of UIC + MIC + OCA-Proof 6.1 A Non-Truthful Mechanism with 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 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 How to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate 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.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 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 Static Revelation Principle for Transaction Fee Mechanisms Static Revelation Principle for Transaction Fee Mechanisms 8.1 Static Revelation Principle: Bidding Rules That Output Single Bid 8.1 Static Revelation Principle: Bidding Rules That Output Single Bid 8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids 8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids A. Comparison of Collusion-Resilience Notions A. Comparison of Collusion-Resilience Notions References 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. user incentive compatibility miner incentive compatibility OCA-proofness 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. Two notions of miner-user collusion-resilience. • 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). • OCA-proofness: • 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]. • c-SCP: c 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. Discussion should not be able to steal from the protocol only the global coalition steal from other users or steal from the protocol This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv ∗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 make use of 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).

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Algorand

Ethereum

Google

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

Understanding the Problem of the Strategic Seller in Market Design

EScholar Technologies

Too Long; Didn't Read

CTA: Download the FREE AI Productivity Shift report

Why the Perfect Blockchain Fee Mechanism May Be Impossible

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

How HPPK DS Balances Security and Efficiency Across NIST Levels

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

Why No Transaction Fee Mechanism Can Truly Be Collusion-Proof

What Is a Transaction Fee Mechanism? Definitions, Incentives, and Strategies

No Blockchain Auction Can Satisfy UIC, MIC, and Global SCP at Once

How HPPK DS Balances Security and Efficiency Across NIST Levels

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

Why No Transaction Fee Mechanism Can Truly Be Collusion-Proof

What Is a Transaction Fee Mechanism? Definitions, Incentives, and Strategies

No Blockchain Auction Can Satisfy UIC, MIC, and Global SCP at Once

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps