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 1.1 Our Contributions As explained above, both Roughgarden’s and Chung and Shi’s collusion-resilience notions capture meaningful incentive compatibility considerations. Recognizing their differences, one natural question is: does Chung and Shi’s finite-block impossibility result still hold if we adopt the original OCA-proofness notion of Roughgarden in lieu of c-SCP? Notably, no existing TFM construction [LSZ19, Yao, BEOS19, BCD+, Rou20, Rou21, FMPS21, CS23, SCW23, WSC24, GY22, ZCZ22, BGR23, TY23, KKLP23, XFP23, CMW23, LRMP23, Ndi23] simultaneously satisfies user incentive compatibility, miner incentive compatibility, and OCA-proofness under finite block size. Main impossibility result. In our work, we give an affirmative answer to the above question. We show that, indeed, an analog of Chung and Shi’s finite-block impossibility result still holds when we replace the c-SCP requirement with OCA-proofness. Specifically, we prove the following theorem. Main impossibility result. Theorem 1.1. Suppose the block size is finite. Then, no possibly randomized, truthful TFM can simultaneously satisfy user incentive compatibility (UIC), miner incentive compatibility (MIC), and OCA-proofness. Further, this impossibility holds even when the globally optimal strategy σ need not be individually rational. Theorem 1.1 Suppose the block size is finite. Then, no possibly randomized, truthful TFM can simultaneously satisfy user incentive compatibility (UIC), miner incentive compatibility (MIC), and OCA-proofness. Further, this impossibility holds even when the globally optimal strategy σ need not be individually rational. In a truthful TFM, a user is expected to bid truthfully, so if the mechanism satisfies UIC, a user’s utility is maximized when it just reports its true value. However, OCA-proofness allows the global coalition to adopt a non-truthful bidding strategy σ even for truthful mechanisms. Our Theorem 1.1 is intuitively stronger but technically incomparable in comparison with Chung and Shi’s impossibility, which shows that no TFM can simultaneously satisfy UIC and 1-SCP for finite block sizes. The reason is that Chung and Shi’s impossibility does not rely on MIC; however, MIC is necessary for our Theorem 1.1 to hold. Specifically, a simple second-price auction with no burning (see Remark 2) satisfies both UIC and OCA-proofness, but does not satisfy MIC since the miner may benefit by injecting a fake (t + 1)-th bid where t is the number of confirmed bids, since the (t + 1)-th bid sets the price for confirmed bids. Global SCP. We suggest a simpler version of OCA-proofness that we call global SCP, which also intuitively captures the requirement that strategic users and miners cannot steal from the protocol, and is perhaps more appropriate when focusing on UIC TFMs (as we do in this paper). In our work, global SCP is not only a technical stepping stone towards proving Theorem 1.1, but also of independent interest as we explain below. Specifically, global SCP is almost the same as OCAproofness, except for requiring σ to be the honest bidding strategy indicated by the mechanism (i.e., the same bidding strategy used to establish UIC). In other words, a mechanism satisfies global SCP if and only if the honest strategy is surplus-maximizing for the global coalition. It is easy to see that for a truthful mechanism, c-SCP for any c implies global SCP, which in turn implies OCA-proofness. To prove Theorem 1.1, we first prove the following theorem: Global SCP. stepping stone independent interest Theorem 1.2. Suppose that the block size is finite. Then no possibly randomized TFM can simultaneously satisfy user incentive compatibility (UIC), miner incentive compatibility (MIC), and global SCP. Further, the impossibility holds even for non-truthful mechanisms. Theorem 1.2. Suppose that the block size is finite. Then no possibly randomized TFM can simultaneously satisfy user incentive compatibility (UIC), miner incentive compatibility (MIC), and global SCP. Further, the impossibility holds even for non-truthful mechanisms. We now explain why the global SCP notion is of independent interest. One advantage of global SCP is that the revelation principle holds for any TFM that satisfies UIC, MIC, and global SCP, which we formally prove in Section 8. In other words, given any TFM that is UIC, MIC, and global SCP, there is an equivalent truthful mechanism that simulates it. For this reason, Theorem 1.2 rules out even non-truthful TFMs that simultaneously satisfy UIC, MIC, and global SCP.[3] revelation principle By contrast, Theorem 1.1 holds only for truthful mechanisms. In particular, in Section 6.1, we show a non-truthful mechanism that simultaneously satisfies UIC, MIC, and OCA-proof. The mechanism is contrived, but it demonstrates the subtlety and the technical challenges when modeling the notion of collusion-resilience. This also suggests that the revelation principle does not hold for mechanisms that satisfy UIC, MIC, and OCA-proofness, partly because in such a mechanism, the bidding strategies used to establish UIC and OCA-proofness may be different. Ways to circumvent the impossibilities. We show in Section 7 that the impossibility of Theorem 1.1 can be circumvented by allowing non-truthful mechanisms or by allowing users to coordinate in bidding in the globally optimal strategy σ. In the same section, we raise an open question regarding whether it is possible to use cryptography (e.g., the MPC-assisted model of Shi et al. [SCW23]) and Bayesian notions of incentive compatibility to circumvent the impossibilities. Ways to circumvent the impossibilities. 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 [3] Simultaneously with and independently of this paper, Gafni and Yaish [GY24] proved, among other results, a version of Theorem 1.2 for the special case of deterministic mechanisms and a block size of 1.

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

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

5 Ways to Measure Privacy Risks in Text Data

Why the Perfect Blockchain Fee Mechanism May Be Impossible

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

5 Ways to Measure Privacy Risks in Text Data

Why the Perfect Blockchain Fee Mechanism May Be Impossible

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