Table of LinksAbstract and 1. Introduction1.1 Our Contributions1.2 TFM Incentive-Compatibility Notions: A Cheat SheetDefinitions2.1 Transaction Fee Mechanism2.2 Incentive Compatibility NotionsPreliminary: Myerson’s LemmaWarmup: Impossibility of UIC + MIC + Global SCP for Deterministic MechanismsImpossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap5.2 Formal ProofsFeasibility and Impossibility of UIC + MIC + OCA-Proof6.1 A Non-Truthful Mechanism with UIC + MIC + OCA-Proof6.2 Impossibility of UIC + MIC + OCA-Proof for Truthful MechanismsHow to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate7.2 Allowing the Globally Optimal Strategy to Output Multiple Bids7.3 Inclusion-Rule-Respecting and 7.4 Discussions and Open Questions Regarding the Use of CryptographyStatic Revelation Principle for Transaction Fee Mechanisms8.1 Static Revelation Principle: Bidding Rules That Output Single Bid8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple BidsA. Comparison of Collusion-Resilience NotionsReferences2 Definitions2.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 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.\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.\:::infoAuthors:(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).::::::infoThis paper is available on arxiv under CC BY 4.0 DEED license.:::[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.