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
3 Preliminary: Myerson’s Lemma
Conceptually, user i must pay the minimal price which makes its bid confirmed.
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. 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.
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.
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.
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.
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.
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.
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.
