How Bidding Rule Metadata Could Reinvent Blockchain Incentives

Table of Links

Abstract and 1. Introduction

1.1 Our Contributions

1.2 TFM Incentive-Compatibility Notions: A Cheat Sheet

2. Definitions

   2.1 Transaction Fee Mechanism

   2.2 Incentive Compatibility Notions

3. Preliminary: Myerson’s Lemma

4. Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms

5. Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap

   5.2 Formal Proofs

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

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

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

8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids

To handle this difficulty, we need to relax the syntax of the inclusion rule. Earlier in our definitions (Section 2.1), we require that the inclusion rule outputs a subset of the input bid vector. In this section, we slightly relax this syntax requirement, and allow the honest inclusion rule to append some metadata for each bid.[11] The purpose of the metadata in the honest execution is to encode the auxiliary information for the blockchain’s confirmation/payment rules. This relaxation in the syntax is non-essential for the impossibility results in this paper, since all the proofs for our impossibility results (Sections 4, 5 and 6.2) still hold even if the honest inclusion rule can append the metadata. Now, we are ready to present the revelation principle.

Theorem 8.2. Let c be any natural number. Given any non-truthful TFM Π for block size k that is UIC, MIC, and c-SCP with an individually rational bidding rule, there exists a truthful TFM Π′ for block size k that is UIC, MIC, and c-SCP such that 1) the honest bidding rule is truth-telling, and 2) given any vector of true values, the outcome under an honest execution of Π is identically distributed as the outcome under an honest execution of Π′.

Lemma 8.3. Assume the miner follows the mechanism honestly. Then, the outcome when all users follow the bidding rule β under the mechanism Π is identically distributed as the outcome when all users bid truthfully under the mechanism Π′.

Lemma 8.4. The following statements hold.

• If Π is UIC, then Π′ is UIC.

• If Π is MIC, then Π′ is MIC.

• For all c, if Π is c-SCP, then Π′ is c-SCP.

Proof. We will prove three properties individually.

The proof of Theorem 8.2 directly follows from Lemma 8.3 and Lemma 8.4.

---

[11] We assume the metadata do not occupy the block space. See Remark 3 for more discussion.