Authors:
(1) Yotam Gafni, Weizmann Institute ([email protected]);
(2) Aviv Yaish, The Hebrew University, Jerusalem ([email protected]).
Table of Links
-
Understanding OCA
B. Non-anonymous Deterministic Mechanisms
Abstract
To allocate transactions to blocks, cryptocurrencies use an auction-like transaction fee mechanism (TFM). A conjecture of Roughgarden [Rou21] asks whether there is a TFM that is incentive compatible for both the users and the miner, and is also resistant to off-chain agreements (OCAs) between these parties, a collusion notion that captures the ability of users and the miner to jointly deviate for profit. The work of Chung and Shi [CS23] tackles the problem using the different collusion resistance notion of side-channel proofness (SCP), and shows an impossibility given this notion. We show that OCA-proofness and SCP are different, with SCP being strictly stronger. We then fully characterize the intersection of deterministic dominant strategy incentive-compatible (DSIC) and OCA-proof mechanisms, as well as deterministic MMIC and OCA-proof ones, and use this characterization to show that only the trivial mechanism is DSIC, myopic miner incentive-compatible (MMIC) and OCA-proof. We also show that a randomized mechanism can be at most 0.842-efficient in the worst case, and that the impossibility of a non-trivial DSIC, MMIC and OCA-proof extends to a couple of natural classes of randomized mechanisms.
1 Introduction
Cryptocurrencies such as Bitcoin utilize a decentralized mechanism wherein entities called miners process user transactions in batches called blocks. In times of congestion, the prompt processing of a transaction may be incentivized by attaching a fee to it, which can collected by miners upon including the transaction in a block. A cryptocurrency’s TFM determines how much fees are charged from transactions and transferred to miners as revenue, with TFMs commonly modeled as auctions. A key difference between TFMs and traditional auctions is the ease with which miners and users may collude via smart contracts to increase their profits. The possibility of designing such collusion-resistant TFMs is the main focus of our work.
The seminal work of Roughgarden [Rou21] includes collusion resistance, referred to as off-chain-agreement (OCA)-proofness, as the centerpiece of “good” TFMs, alongside other properties such as being incentive compatible for both users and miners (DSIC and MMIC, respectively). Given this desiderata, Roughgarden poses an important open question: can we design good TFMs that satisfy all desired properties?
This was followed by Chung & Shi [CS23], who discuss a collusion resistance notion they call c-side-contract-proof (SCP), which means that no coalition of the miner and c users can benefit from colluding. They show that satisfying DSIC and 1-SCP is only possible for the trivial mechanism that never allocates any item, implying that good TFMs produce 0 miner revenue. This is exacerbated by similar results for TFMs that are allowed to use strong cryptographic primitives, even when considering relaxed Bayesian and approximate versions of the TFM deisderata [SCW23; CSZZ23; WSC23].
As we show, Roughgarden’s [Rou21] open question is not directly answered by the results for SCP [CS23], as OCA-proofness and SCP are not equivalent. To answer the question about OCA-proofness, we offer the following results:
• We show the existence of OCA-proof mechanisms that are not SCP in Claim 3.1, and then show in Claim 3.3 that SCP is strictly stronger as it implies OCA-proofness.
• In Lemma 3.5, we show that any DSIC+MMIC+OCA-proof mechanism must have 0 miner revenue in the single bidder case.
• For the general case, we answer Roughgarden’s [Rou21] open question in Theorem 4.7 by showing that the trivial TFM is the only possible determinstic mechanism satisfying DSIC, MMIC, and 1-OCA-proofness[1]. We do so by precisely characterizing all DSIC+1-OCA mechanisms, and all MMIC+1-OCA-proof mechanisms, which is of independent interest.
• For randomized mechanisms, we show that the trivial mechanism is the only DSIC + MMIC + OCA-proof, scale-invariant mechanism (Corollary 5.6). Scale invariance is a natural property, defined by requiring that scaling all bids by the same factor leaves the allocation unchanged. It holds for notable mechanisms such as the first-price, second-price, and the all-pay auctions. It does not hold, for example, for the second-price auction with reserve price r > 0.
• We show that no randomized DSIC+MMIC+OCA-proof mechanism is efficient in Theorem 5.8, and we bound away the efficiency approximation in Theorem 5.13 and Corollary 5.15, showing that it can achieve at most 0.842 in the worst case.
This paper is
[1] Notice that we introduce a c quantifier for the OCA collusion notion, similarly to the quantifier for SCP.