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 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 Π′. 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.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. Lemma 8.4. The following statements hold. • If Π is UIC, then Π′ is UIC. If is UIC, then is UIC. • If Π is MIC, then Π′ is MIC. If is MIC, then is MIC. • For all c, if Π is c-SCP, then Π′ is c-SCP. For all c, if is c-SCP, then is c-SCP. Proof. We will prove three properties individually. Proof The proof of Theorem 8.2 directly follows from Lemma 8.3 and Lemma 8.4. 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 [11] We assume the metadata do not occupy the block space. See Remark 3 for more discussion.

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

How Bidding Rule Metadata Could Reinvent Blockchain Incentives

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