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 7 How to Circumvent the Impossibilities In this section, we discuss possible ways to circumvent the impossibilities. Recall that in the definition of OCA-proofness, we require all users act independently in the globally optimal strategy σ, and σ should only output a single bid. If we remove either of the two requirements, we can have mechanisms that satisfies UIC, MIC and OCA-proofness, where we present in Sections 7.1 and 7.2. These mechanisms are somewhat contrived and not obviously relevant for real-world blockchain protocols; the primary point of these mechanisms is to “stress-test” the definitions, and these examples highlight the subtlety of the modeling and help us to have a better understanding of the trade-offs between various notions of collusion-resilience. In Section 7.3, we consider an even weaker definition, called inclusion-rule-respecting, which might be the weakest but still meaningful definition that captures the notion of “no way to steal from the protocol.” Finally, in Section 7.4, we discuss the use of cryptography in the TFM literature, and point out a future direction by using cryptography and Bayesian incentive compatibility. 7.1 Allowing the Globally Optimal Strategy to Coordinate OCA-proofness requires that all users act independently in the globally optimal strategy σ. However, if we remove this restriction, then the following auction would simultaneously satisfy UIC, MIC, and OCA-proof (with the aforementioned relaxation). Posted price auction with random selection and total burning. The mechanism is parametrized with some reserve price r > 0 and block size k. Any bid that is at least r is considered eligible. Randomly select up to k bids to include in the block. All included bids are confirmed and they each pay r. All payment is burnt and the miner receives nothing. It is not hard to see that the above mechanism satisfies UIC and MIC. It also satisfies OCA-proofness with the aforementioned relaxation since the global coalition can just have the users with the top k values bid more than r, while everyone else bids 0. Posted price auction with random selection and total burning. Note that allowing all users to coordinate bids does not trivialize the definition, as this relaxed OCA-proofness definition still requires that the miner follow the TFM’s inclusion rule honestly. For example, in the auction above, the miner has to select k bids uniformly at random among all eligible bids. 7.2 Allowing the Globally Optimal Strategy to Output Multiple Bids We next show that when we allow the globally optimal strategy σ to output multiple bids, then we can actually construct a truthful mechanism that satisfies UIC, MIC, and OCA-proofness. Similar to Section 6.1, we try to signal to the mechanism when everyone is adopting the globally optimal strategy σ. In this mechanism, since σ can output multiple bids, users can signal through fake bids. We assume the miner and the mechanism can distinguish whether a set of bids come from the same user. In practice, this can be implemented by checking whether these bids are signed by the same public key. Specifically, consider the following mechanism parametrized by a reserve price r > 1. • Globally optimal strategy σ(v): If the user’s true value v ≥ r, σ(v) outputs (r, r/v) where r/v ∈ (0, 1] is a uniquely decodable encoding of the user’s true value v. Otherwise, if v < r, σ(v) simply outputs ∅, i.e., the user drops its bid. Globally optimal strategy σ • Inclusion rule. Inclusion rule. • Confirmation, payment, and miner revenue rules: All included bids that are at least r are confirmed. Each confirmed bid pays r, and the miner gets nothing. • Confirmation, payment, and miner revenue rules: Claim 7.1. The above mechanism satisfies UIC, MIC, and a relaxed notion of OCA-proofness in which σ is allowed to output multiple bids. Claim 7.1. The above mechanism satisfies UIC, MIC, and a relaxed notion of OCA-proofness in which σ is allowed to output multiple bids. Proving UIC is the most complicated part. Fix any user i. Notice that each confirmed bid pays r, so if user i’s true value is at most r, it cannot get positive utility regardless its bid. Thus, bidding truthfully is a dominant strategy. Henceforth, we assume user i’s true value is strictly larger than r. There are two possibilities. i r r r First, before user i submits its bid, the bid vector contains exactly n bids at r and n bids lie in the range (0, 1] for some n. Then, bidding truthfully will lead to Case 3, where user i’s bid is guaranteed to be included and confirmed, and thus maximizes the utility.


Second, before user i submits its bid, the bid vector does not contain exactly n bids at r and n bids lie in the range (0, 1] for some n. Suppose there is no bid strictly larger than r in the bid vector before user i submits its bid. Then, if user i bids truthfully, its bid will be the only bid larger than r, and the inclusion rule goes to Case 4. Since k ≥ 1, user i’s bid is guaranteed to be included and confirmed, and thus maximizes the utility. On the other hand, suppose there are t ≥ 1 bids strictly larger than r in the bid vector before user i submits its bid. Then, the inclusion can never go to Case 1 or Case 2. If user i bids truthfully, the inclusion rule must go to Case 4, and user i’s bid is included with probability min(k, t + 1)/(t + 1). However, if the strategic bidding leads to Case 3, it must be t = 1. Then, user i’s inclusion probability has dropped from 1/2 to 0 if k = 1, or from 1 to at most 1 if k ≥ 2. On the other hand, if the strategic bidding leads to Case 4, any untruthful bidding > r leads to the same inclusion probability and the same payment, so the utility does not change, while any untruthful bidding ≤ r leads to the zero inclusion probability which leads to zero utility. Finally, notice that injecting fake bids never helps in Case 4. Thus, in all cases, the utility is better than bidding truthfully. First, before user i submits its bid, the bid vector contains exactly n bids at r and n bids lie in the range (0, 1] for some n. Then, bidding truthfully will lead to Case 3, where user i’s bid is guaranteed to be included and confirmed, and thus maximizes the utility. First, before user i submits its bid, the bid vector contains exactly n bids at r and n bids lie in the range (0, 1] for some n. Then, bidding truthfully will lead to Case 3, where user i’s bid is guaranteed to be included and confirmed, and thus maximizes the utility. Second, before user i submits its bid, the bid vector does not contain exactly n bids at r and n bids lie in the range (0, 1] for some n. Suppose there is no bid strictly larger than r in the bid vector before user i submits its bid. Then, if user i bids truthfully, its bid will be the only bid larger than r, and the inclusion rule goes to Case 4. Since k ≥ 1, user i’s bid is guaranteed to be included and confirmed, and thus maximizes the utility. On the other hand, suppose there are t ≥ 1 bids strictly larger than r in the bid vector before user i submits its bid. Then, the inclusion can never go to Case 1 or Case 2. If user i bids truthfully, the inclusion rule must go to Case 4, and user i’s bid is included with probability min(k, t + 1)/(t + 1). However, if the strategic bidding leads to Case 3, it must be t = 1. Then, user i’s inclusion probability has dropped from 1/2 to 0 if k = 1, or from 1 to at most 1 if k ≥ 2. On the other hand, if the strategic bidding leads to Case 4, any untruthful bidding > r leads to the same inclusion probability and the same payment, so the utility does not change, while any untruthful bidding ≤ r leads to the zero inclusion probability which leads to zero utility. Finally, notice that injecting fake bids never helps in Case 4. Thus, in all cases, the utility is better than bidding truthfully. Second, before user i submits its bid, the bid vector does not contain exactly n bids at r and n bids lie in the range (0, 1] for some n. Suppose there is no bid strictly larger than r in the bid vector before user i submits its bid. Then, if user i bids truthfully, its bid will be the only bid larger than r, and the inclusion rule goes to Case 4. Since k ≥ 1, user i’s bid is guaranteed to be included and confirmed, and thus maximizes the utility. On the other hand, suppose there are t ≥ 1 bids strictly larger than r in the bid vector before user i submits its bid. Then, the inclusion can never go to Case 1 or Case 2. If user i bids truthfully, the inclusion rule must go to Case 4, and user i’s bid is included with probability min(k, t + 1)/(t + 1). However, if the strategic bidding leads to Case 3, it must be t = 1. Then, user i’s inclusion probability has dropped from 1/2 to 0 if k = 1, or from 1 to at most 1 if k ≥ 2. On the other hand, if the strategic bidding leads to Case 4, any untruthful bidding > r leads to the same inclusion probability and the same payment, so the utility does not change, while any untruthful bidding ≤ r leads to the zero inclusion probability which leads to zero utility. Finally, notice that injecting fake bids never helps in Case 4. Thus, in all cases, the utility is better than bidding truthfully. i Recall that weakly symmetric mechanisms do not make use of the bidders’ identities or other auxiliary information except for tie-breaking among equal bids. Because the mechanism above relies on the fact that the inclusion rule can distinguish whether a set of bids come from the same user, it may not be obvious that the mechanism satisfies weak symmetry. The next claim proves this formally. Claim 7.2. The above mechanism satisfies weak symmetry. Claim 7.2. The above mechanism satisfies weak symmetry. Proof. To show weak symmetry, we give an equivalent description as follows. Given a bid vector b, the sorting algorithm checks whether b satisfies the condition of Case 1. If so, the sorting algorithm places the multiple r bids corresponding to the true value vector (v1, . . . , vn) (defined in Case 1 above) from high to low, and sorts the rest in the descending order. Otherwise, if b does not satisfy the condition of Case 1, the sorting algorithm sorts b in the descending order and breaks tie arbitrarily. Proof In the original mechanism, the only case that depends on the extra information (identity, in this case) is Case 1. By applying the sorting algorithm described above, the inclusion rule can implement Case 1 by only depending on the amount of the bids and their relative position in the sorted bid vector. 7.3 Inclusion-Rule-Respecting It is also natural to consider a further relaxation of OCA-proofness henceforth called “inclusionrule-respecting”. In comparison with OCA-proofness, inclusion-rule-respecting only requires that the globally optimal strategy σ not involve altering the inclusion rule, and all other constraints on σ are removed. Inclusion-rule-respecting is strictly weaker than the notions in Section 7.1 and Section 7.2. Therefore, the mechanisms mentioned in Section 7.1 and Section 7.2 simultaneously satisfy UIC, MIC, and inclusion-rule-respecting too. The “inclusion-rule-respecting” notion has an intuitive interpretation: it discourages miners from altering the intended protocol implementation; in other words, all profiting strategies can be implemented as bidding strategies above the protocol layer. In this sense, “inclusion-rulerespecting” also captures the intuition of “no way to steal from the protocol”. One can also view it as follows: global SCP captures “not stealing from the protocol” where the protocol is the union of the miner’s inclusion rule as well as users’ honest bidding strategies; and inclusion-rule-respecting captures the same notion but where the protocol is only the underlying blockchain protocol. OCA-proofness is somewhere in between. 7.4 Discussions and Open Questions Regarding the Use of Cryptography Another interesting question is whether we can overcome the impossibilities using cryptography. Shi et al. [SCW23] showed that if the rules of the TFM are enforced through a multi-party computation protocol (henceforth called the MPC-assisted model), then we can design a finite-block TFM that simultaneously satisfies UIC, MIC, and 1-SCP (in the ex-post sense). On the other hand, Shi et al. also showed that simultaneously achieving UIC, MIC, and c-SCP for c ≥ 2 is impossible in the MPC-assisted model, even for Bayesian notions of equilibrium. Partly this is because even with an MPC protocol enforcing the inclusion rule, a strategic miner or user can still inject fake bids, and the mechanism does not know the number of bids ahead of time (i.e., the mechanism is “permissionless”). It is an interesting open question whether using cryptography and Bayesian notions of equilibrium can help us overcome the impossibilities in this paper. Specifically, Shi et al. [SCW23] suggested that the MPC-assisted model also justifies the relaxed notion of Bayesian equilibrium, since players cannot see others’ bids before posting their own. 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.

How to Circumvent Impossibility Theorems in Blockchain Mechanism Design

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

15 Common Types of Unethical Behavior Found in Open-Source Projects

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

No Blockchain Auction Can Satisfy UIC, MIC, and Global SCP at Once

15 Common Types of Unethical Behavior Found in Open-Source Projects

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

No Blockchain Auction Can Satisfy UIC, MIC, and Global SCP at Once

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps