skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Transaction Fee Mechanism Design in a Post-MEV World
The incentive-compatibility properties of blockchain transaction fee mechanisms have been investigated with passive block producers that are motivated purely by the net rewards earned at the consensus layer. This paper introduces a model of active block producers that have their own private valuations for blocks (representing, for example, additional value derived from the application layer). The block producer surplus in our model can be interpreted as one of the more common colloquial meanings of the phrase "maximal extractable value (MEV)." We first prove that transaction fee mechanism design is fundamentally more difficult with active block producers than with passive ones: With active block producers, no non-trivial or approximately welfare-maximizing transaction fee mechanism can be incentive-compatible for both users and block producers. These results can be interpreted as a mathematical justification for augmenting transaction fee mechanisms with additional components such as order flow auctions, block producer competition, trusted hardware, or cryptographic techniques. We then consider a more fine-grained model of block production that more accurately reflects current practice, in which we distinguish the roles of "searchers" (who actively identify opportunities for value extraction from the application layer and compete for the right to take advantage of them) and "proposers" (who participate directly in the blockchain protocol and make the final choice of the published block). Searchers can effectively act as an "MEV oracle" for a transaction fee mechanism, thereby enlarging the design space. Here, we first consider a TFM that is inspired by how searchers have traditionally been incorporated into the block production process, with each transaction effectively sold off to a searcher through a first-price auction. We then explore the TFM design space with searchers more generally, and design a mechanism that circumvents our impossibility results for TFMs without searchers. Our mechanism (the "SAKA" mechanism) is incentive-compatible (for users, searchers, and the block producer), sybil-proof, and guarantees roughly 50% of the maximum-possible welfare when transaction sizes are small relative to block sizes. We conclude with a matching negative result: even when transaction sizes are small, no DSIC and sybil-proof deterministic TFM can guarantee more than 50% of the maximum-possible welfare.  more » « less
Award ID(s):
2212745
PAR ID:
10610629
Author(s) / Creator(s):
; ;
Editor(s):
Böhme, Rainer; Kiffer, Lucianna
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Volume:
316
ISSN:
1868-8969
ISBN:
978-3-95977-345-4
Page Range / eLocation ID:
29:1-29:24
Subject(s) / Keyword(s):
MEV Transaction Fee Mechanisms Auctions Theory of computation → Computational pricing and auctions Security and privacy → Distributed systems security
Format(s):
Medium: X Size: 24 pages; 786717 bytes Other: application/pdf
Size(s):
24 pages 786717 bytes
Right(s):
Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, ACM)
    We study incentive-compatible mechanisms that maximize the Nash Social Welfare. Since traditional incentive-compatible mechanisms cannot maximize the Nash Social Welfare even approximately, we propose changing the traditional model. Inspired by a widely used charging method (e.g., royalties, a lawyer that charges some percentage of possible future compensation), we suggest charging the players some percentage of their value of the outcome. We call this model the percentage fee model. We show that there is a mechanism that maximizes exactly the Nash Social Welfare in every setting with non-negative valuations. Moreover, we prove an analog of Roberts theorem that essentially says that if the valuations are non-negative, then the only implementable social choice functions are those that maximize weighted variants of the Nash Social Welfare. We develop polynomial time incentive compatible approximation algorithms for the Nash Social Welfare with subadditive valuations and prove some hardness results. 
    more » « less
  2. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Guruswami, Venkatesan (Ed.)
    Transaction fee mechanism design is a new decentralized mechanism design problem where users bid for space on the blockchain. Several recent works showed that the transaction fee mechanism design fundamentally departs from classical mechanism design. They then systematically explored the mathematical landscape of this new decentralized mechanism design problem in two settings: in the plain setting where no cryptography is employed, and in a cryptography-assisted setting where the rules of the mechanism are enforced by a multi-party computation protocol. Unfortunately, in both settings, prior works showed that if we want the mechanism to incentivize honest behavior for both users as well as miners (possibly colluding with users), then the miner revenue has to be zero. Although adopting a relaxed, approximate notion of incentive compatibility gets around this zero miner-revenue limitation, the scaling of the miner revenue is nonetheless poor. In this paper, we show that if we make a mild reasonable-world assumption that there are sufficiently many honest users, we can circumvent the known limitations on miner revenue, and design auctions that generate asymptotically optimal miner revenue. We also systematically explore the mathematical landscape of transaction fee mechanism design under the new reasonable-world assumptions, and demonstrate how such assumptions can alter the feasibility and infeasibility landscape. 
    more » « less
  3. ; ; (, ACM)
    Leyton-Brown, Kevin; Samuelson, Larry; Hartline, Jason D (Ed.)
    We study incentive-compatible mechanisms that maximize the Nash Social Welfare. Since traditional incentivecompatible mechanisms cannot maximize the Nash Social Welfare even approximately, we propose changing the traditional model. Inspired by a widely used charging method (e.g., royalties, a lawyer that charges some percentage of possible future compensation), we suggest charging the players some percentage of their value of the outcome. We call this model the percentage fee model. We show that there is a mechanism that maximizes exactly the Nash Social Welfare in every setting with non-negative valuations. Moreover, we prove an analog of Roberts theorem that essentially says that if the valuations are non-negative, then the only implementable social choice functions are those that maximize weighted variants of the Nash Social Welfare. We develop polynomial time incentive compatible approximation algorithms for the Nash Social Welfare with subadditive valuations and prove some hardness results. 
    more » « less
  4. ; ; ; (, IEEE INFOCOM)
    Crowdsensing leverages the rapid growth of sensor-embedded smartphones and human mobility for pervasive information collection. To incentivize smartphone users to participate in crowdsensing, many auction-based incentive mechanisms have been proposed for both offline and online scenarios. It has been demonstrated that the Sybil attack may undermine these mechanisms. In a Sybil attack, a user illegitimately pretends multiple identities to gain benefits. Sybil-proof incentive mechanisms have been proposed for the offline scenario. However, the problem of designing Sybil-proof online incentive mechanisms for crowdsensing is still open. Compared to the offline scenario, the online scenario provides users one more dimension of flexibility, i.e., active time, to conduct Sybil attacks, which makes this problem more challenging. In this paper, we design Sybil-proof online incentive mechanisms to deter the Sybil attack for crowdsensing. Depending on users’ flexibility on performing their tasks, we investigate both single-minded and multi-minded cases and propose SOS and SOM, respectively. SOS achieves computational efficiency, individual rationality, truthfulness, and Sybil-proofness. SOM achieves individual rationality, truthfulness, and Sybil-proofness. Through extensive simulations, we evaluate the performance of SOS and SOM. 
    more » « less
  5. ; ; (, IEEE Transactions on Computational Social Systems)
    Blockchain technology, recognized for its decentralized and privacy-preserving capabilities, holds potential for enhancing privacy in contact tracing applications. Existing blockchain-based contact tracing frameworks often overlook one or more critical design details, such as the blockchain data structure, a decentralized and lightweight consensus mechanism with integrated tracing data verification, and an incentive mechanism to encourage voluntary participation in bearing blockchain costs. Moreover, the absence of framework simulations raises questions about the efficacy of these existing models. To solve above issues, this article introduces a fully third-party independent blockchain-driven contact tracing (BDCT) framework, detailed in its design. The BDCT framework features an RivestShamir-Adleman (RSA) encryption-based transaction verification method (RSA-TVM), achieving over 96% accuracy in contact case recording, even with a 60% probability of individuals failing to verify contact information. Furthermore, we propose a lightweight reputation corrected delegated proof of stake (RCDPoS) consensus mechanism, coupled with an incentive model, to ensure timely reporting of contact cases while maintaining blockchain decentralization. Additionally, a novel simulation environment for contact tracing is developed, accounting for three distinct contact scenarios with varied population density. Our results and discussions validate the effectiveness, robustness of the RSA-TVM and RC-DPoS, and the low storage demand of the BDCT framework. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email