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 2 Definitions 2.1 Transaction Fee Mechanism A transaction fee mechanism (TFM) consists of the following possibly randomized algorithms: We say a TFM is trivial if the confirmation probability of all transactions is zero for any bid vector assuming the miner honestly follows the inclusion rule; otherwise, it is called non-trivial. non-trivial. A strategic miner or miner-user coalition may deviate from the honest inclusion rule. On the other hand, since the confirmation, payment, and miner revenue rules are executed by the blockchain, they are always implemented honestly. We focus on mechanisms that are weakly symmetric, i.e., mechanisms that do not make use of the bidders’ identities or other auxiliary information (e.g., timestamp, transaction metadata), except for tie-breaking among equal bids. More formally, we define weak symmetry as below. weakly symmetric Definition 1 (Weak symmetry). A mechanism is called weakly symmetric if the mechanism can always be equivalently described in the following manner: given a bid vector b where each bid may carry some extra information such as identity or timestamp, the honest mechanism always sorts the vector b by the bid amount first. During the sorting step, if multiple bids have the same amount, then arbitrary tie-breaking rules may be applied, and the tie-breaking can depend on extra information such as timestamp, identity, or random coins. After this sorting step, the inclusion rule and the confirmation rules should depend only on the amount of the bids and their relative position in the sorted bid vector. Definition 1 b b Strategy space. A strategic user can deviate from the honest bidding rule and post an arbitrary bid vector with zero to multiple bids. Without loss of generality, we may assume that in the strategic bid vector, at most one bid can correspond to the user’s actual transaction which has a non-zero true value; all other bids must be fake bids with zero true value. A strategic miner can deviate from the honest inclusion rule, and instead create an arbitrary block (subject to the block size limit) that includes any subset of the bid vector as well as any number of fake bids that it chooses to inject. A strategic miner-user coalition can adopt a combination of the above strategies. Strategy space. Utility and social welfare. For a user with true value v, let x ∈ {0, 1} be the indicator of whether its primary bid is confirmed or not, let p denote its total payment, then the user’s utility is x · v − p. The miner’s utility is simply its revenue. The social welfare is defined to be the sum of the utilities of all users and the miner (i.e., the total value of the confirmed transactions, less any burned payments). Utility and social welfare Notice that we allow the miner revenue to be smaller than the sum of users’ payment, since the coins can be burnt. When calculating the social welfare, the payments among the users and the miner are canceled out, so the social welfare is independent of the payment; however, the amount of burnt coins decreases the social welfare. For example, suppose there is only one user, and let p be the user’s payment and q be the amount of burnt coins. In this case, the user’s utility is x·v −p, the miner revenue is p − q, and the social welfare is (x · v − p) + (p − q) = x · v − q. 2.2 Incentive Compatibility Notions Definition 3 (Miner incentive compatible (MIC)). A TFM is said to be miner incentive compatible (MIC), iff given any bid vector b, the miner’s expected utility is maximized when the miner does not inject any fake bid and creates a block indicated by the honest inclusion rule. Definition 3 miner incentive compatible b Definition 5 (Global side-contract-proof (global SCP)). A TFM is said to be global side-contract-proof (global SCP), iff given any vector of true values v, the expected social welfare is maximized when all the users bid according to the honest bidding rule, and the miner follows the honest inclusion rule, where the maximization is taken over all the coordinated strategies that the coalition consisting of the miner and all users can adopt. Definition 5 global side-contract-proof (global SCP) v In the definitions above, the expectation is taken over the randomness of the TFM. More explicitly, in Definition 2, the expectation is taken over the randomness of the inclusion/confirmation/payment rules; in Definitions 3 to 6, the expectation is taken over the randomness of the inclusion/confirmation/ payment/miner revenue rules. Note that in the OCA-proofness definition, σ is required to output a single real-valued bid. A canonical example of σ is scaling; that is, σ(v) = γv for some γ ∈ [0, 1] (cf., Corollary 5.12 and 5.14 in [Rou21]). A detailed comparison between c-SCP, global SCP, and OCA-proofness is given in Appendix A. 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). 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 [5] The finite block size regime in this work and [CS23] corresponds to the case in [Rou21] where the base fee in the EIP-1559 or tipless mechanisms is excessively low, i.e. the number of transactions willing to pay the base fee exceeds the maximum block size (cf., Definition 5.6 in [Rou21]). [6] The blockchain protocol can always suppress conflicting or double-spending transactions. [7] Throughout the paper except Section 8, we only focus on bidding rules that output a single bid. In Section 8, we consider general bidding rules that may output multiple bids. [8] Roughgarden [Rou21] assumes that all included transactions are confirmed. However, Chung and Shi [CS23] show that allowing unconfirmed transactions in a block enlarges the design space. For example, some mechanisms require a block to contain some unconfirmed transactions (see Section 7 in [CS23]). [9] We can also relax the requirement such that individual rationality holds in expectation. Both the impossibility results (Sections 4, 5 and 6.2) and the revelation principle result (Section 8) continue to hold.

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

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

Why No Transaction Fee Mechanism Can Truly Be Collusion-Proof

EScholar Technologies

Too Long; Didn't Read

CTA: Download the FREE AI Productivity Shift report

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Why Ethics Fail in Open Source Communities

Why the Perfect Blockchain Fee Mechanism May Be Impossible

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

Why No Transaction Fee Mechanism Can Truly Be Collusion-Proof

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

Why Ethics Fail in Open Source Communities

Why the Perfect Blockchain Fee Mechanism May Be Impossible

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

Why No Transaction Fee Mechanism Can Truly Be Collusion-Proof

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

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps