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
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.
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 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.
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.
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.
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).
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 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.
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.
[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.
