Authors:
(1) Yotam Gafni, Weizmann Institute (yotam.gafni@gmail.com);
(2) Aviv Yaish, The Hebrew University, Jerusalem (aviv.yaish@mail.huji.ac.il). Authors: Authors: (1) Yotam Gafni, Weizmann Institute (yotam.gafni@gmail.com); (2) Aviv Yaish, The Hebrew University, Jerusalem (aviv.yaish@mail.huji.ac.il). Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 1.1 Technical Overview 1.1 Technical Overview 1.2 Related Work 1.2 Related Work Model and Preliminaries and 2.1 Transaction Fee Mechanisms
2.2 The TFM Desiderata


Understanding OCA
3.1 The Difference Between SCP and OCA
3.2 Useful Preliminary Results for OCA-proof TFMs


Deterministic OCA-proof Mechanisms


Randomized OCA-proof Mechanisms


Discussion and References Model and Preliminaries and 2.1 Transaction Fee Mechanisms
2.2 The TFM Desiderata Model and Preliminaries and 2.1 Transaction Fee Mechanisms Model and Preliminaries and 2.1 Transaction Fee Mechanisms 2.2 The TFM Desiderata 2.2 The TFM Desiderata Understanding OCA
3.1 The Difference Between SCP and OCA
3.2 Useful Preliminary Results for OCA-proof TFMs Understanding OCA 3.1 The Difference Between SCP and OCA 3.1 The Difference Between SCP and OCA 3.2 Useful Preliminary Results for OCA-proof TFMs 3.2 Useful Preliminary Results for OCA-proof TFMs Deterministic OCA-proof Mechanisms Deterministic OCA-proof Mechanisms Deterministic OCA-proof Mechanisms Randomized OCA-proof Mechanisms Randomized OCA-proof Mechanisms Randomized OCA-proof Mechanisms Discussion and References Discussion and References Discussion and References A. Missing Proofs A. Missing Proofs B. Non-anonymous Deterministic Mechanisms 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. blocks collusion-resistant 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? 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 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 [1] Notice that we introduce a c quantifier for the OCA collusion notion, similarly to the quantifier for SCP.

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

When Every Mechanism Burns: The Theoretical Boundaries of DSIC, MMIC, and OCA-Proof Design

Why Education Beats Universal Basic Income in the Age of Automation

EScholar Technologies

Too Long; Didn't Read

Download free Tech Leaders Productivity Report!

The Limits of Incentive-Compatible and OCA-Proof Transaction Fee Mechanisms in Cryptocurrencies

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

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

When Every Mechanism Burns: The Theoretical Boundaries of DSIC, MMIC, and OCA-Proof Design

The Research Roots of Collusion‑Resistant Crypto Auctions

The Psychology of Incentives on Blockchains

The Success of Incentive-Centered Blockchain Markets

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

When Every Mechanism Burns: The Theoretical Boundaries of DSIC, MMIC, and OCA-Proof Design

The Research Roots of Collusion‑Resistant Crypto Auctions

The Psychology of Incentives on Blockchains

The Success of Incentive-Centered Blockchain Markets

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps