2021/06/02 by Tim Roughgarden, Roughgarden, Tim · 1 voice · 19 citations
Computer Science · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #FOS: Economics and business #Parallel #Theoretical Economics (econ.TH) #and Cluster Computing (cs.DC) #cs.CR #cs.DC #cs.DS #cs.GT #econ.TH
paper · pdf · doi:10.48550/arxiv.2106.01340
arxiv published 2021/06/02 · arxiv updated 2023/12/22
Demand for blockchains such as Bitcoin and Ethereum is far larger than supply, necessitating a mechanism that selects a subset of transactions to include "on-chain" from the pool of all pending transactions. This paper investigates the problem of designing a blockchain transaction fee mechanism through the lens of mechanism design. We introduce two new forms of incentive-compatibility that capture some of the idiosyncrasies of the blockchain setting, one (MMIC) that protects against deviations by profit-maximizing miners and one (OCA-proofness) that protects against off-chain collusion between miners and users. This study is immediately applicable to a recent (August 5, 2021) and major change to Ethereum's transaction fee mechanism, based on a proposal called "EIP-1559." Historically, Ethereum's transaction fee mechanism was a first-price (pay-as-bid) auction. EIP-1559 suggested making several tightly coupled changes, including the introduction of variable-size blocks, a history-dependent reserve price, and the burning of a significant portion of the transaction fees. We prove that this new mechanism earns an impressive report card: it satisfies the MMIC and OCA-proofness conditions, and is also dominant-strategy incentive compatible (DSIC) except when there is a sudden demand spike. We also introduce an alternative design, the "tipless mechanism," which offers an incomparable slate of incentive-compatibility guarantees -- it is MMIC and DSIC, and OCA-proof unless in the midst of a demand spike.