  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.
