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 3 Preliminary: Myerson’s Lemma Conceptually, user i must pay the minimal price which makes its bid confirmed. i 4 Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms As a warmup, we first show a finite-block impossibility for UIC + MIC + global SCP for deterministic mechanisms. Recall that a TFM is said to be trivial if everyone’s confirmation probability is zero for any bid vector assuming the miner follows the inclusion rule. In this case, everyone’s utility is always zero in an honest execution. We will show that no non-trivial mechanism can satisfy all three properties simultaneously. Later in Section 5, we extend the impossibility to randomized mechanisms. Due to the revelation principle that we prove in Section 8, if we can prove the impossibility for truthful mechanisms, the impossibility immediately extends to non-truthful mechanisms as well. Therefore, in this section, we shall assume truthful mechanisms. deterministic Lemma 4.1. For any global SCP mechanism, the confirmed bids must correspond to the highest bids. Lemma 4.1. For any global SCP mechanism, the confirmed bids must correspond to the highest bids. Proof. Suppose in some scenario, Alice bids her true value b and Bob bids his true value b ′ < b; however, Bob’s bid is confirmed, and Alice’s is not. Now, we can have Alice and Bob swap their bids. The miner creates the same block as before in which the position originally corresponding to Bob now has Alice’s bid of b′. Since the mechanism is weakly symmetric (Definition 1), Alice’s bid is confirmed. This way, the social welfare increases by b − b′ in comparison with the honest case, and this violates global SCP. Proof Lemma 4.2. For any global SCP mechanism, the amount of burnt coins depends only on the number of confirmed bids. Lemma 4.2. For any global SCP mechanism, the amount of burnt coins depends only on the number of confirmed bids. Proof. Suppose in two different scenarios, when everyone acts honestly, the blocks made are B and B′ respectively, the confirmed bids are b ⊆ B and b′ ⊆ B′ respectively where b and b′ are of the same length, and the burnt amount in the two scenarios are q and q′ respectively, where q < q′. Now, suppose we are actually in the second scenario. A global coalition can adopt the following strategy: create a block identical to B in which the confirmed bids correspond to the users with the highest true values and the rest can be fake bids. Observe that the social welfare is the sum of the true values of all confirmed bids (where fake bids have a true value of 0) minus the total coins burnt. Therefore, the above strategy achieves strictly higher social welfare than the honest case. Proof B B b B b B b b q q′ q q′ B Theorem 4.3. No non-trivial deterministic TFM can simultaneously satisfy UIC, MIC, and global SCP when the block size is finite. Theorem 4.3. No non-trivial deterministic TFM can simultaneously satisfy UIC, MIC, and global SCP when the block size is finite. 5 Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms In this section, we extend the finite-block impossibility of UIC + MIC + global SCP to even randomized mechanisms. Recall that a TFM consists of five rules as defined in Section 2.1, and a randomized TFM may use randomness in any of the five rules. Since the confirmation, the payment, and the miner revenue rules are executed by the blockchain, the strategic players can only bias the randomness in and deviate from the bidding rule and the inclusion rule. Again, due to the revelation principle proven in Section 8, it suffices to consider truthful mechanisms. 5.1 Proof Roadmap 5.2 Formal Proofs In the rest of this section, we present the formal proofs. Proof. We first prove that expected miner utility is the same in both scenarios. Suppose this is not true, and without loss of generality, suppose expected miner utility is higher in scenario 1. Then, the miner can ignore the bids b, inject the fake bids b′, pretend that the bid vector is (a, b′), and run the honest mechanism. Since the confirmation probability of b′ is 0, the miner need not pay any cost for the fake bids. Therefore, the miner gets higher expected utility by taking the above strategy which violates MIC. Proof b b a b b The proof of total social welfare is similar. Suppose without loss of generality, that the expected total social welfare in scenario 1 is higher. Then, the global coalition can inject fake bids b′ and pretend that the bid vector is (a, b′), thus allowing it to increase its expected social welfare. This violates global SCP. b a b The equivalence in total user utility follows directly from the above, since total user utility is the difference between the social welfare and the miner utility. Lemma 5.5. Suppose the mechanism satisfies UIC, MIC, and global SCP, and the block size is k. Let a be any positive real number. Consider a scenario with only one bid a. Then, the only user’s utility is zero assuming it bids its true value. Lemma 5.5. Suppose the mechanism satisfies UIC, MIC, and global SCP, and the block size is k. Let a be any positive real number. Consider a scenario with only one bid a. Then, the only user’s utility is zero assuming it bids its true value. Theorem 5.6. No non-trivial, possibly randomized TFM can simultaneously satisfy UIC, MIC, and global SCP when the block size is finite. Theorem 5.6. No non-trivial, possibly randomized TFM can simultaneously satisfy UIC, MIC, and global SCP when the block size is finite. Proof. We will show that under any sufficiently large a, the confirmation probability under a single bid a is non-zero. If we can show this, then we can show a contradiction to UIC. Specifically, consider b > a and both sufficiently large. By Lemma 5.5, if there is only one user with true value b, its utility is zero when it bids truthfully. However, the user can underbid a. Since the confirmation probability is non-zero and the payment is at most a, the user enjoys positive utility, which violates UIC. Proof 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

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

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 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

5 Ways to Measure Privacy Risks in Text Data

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

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

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps