Transaction Fee Mining and Mechanism Design

Michael Tang ¹ Alex Zhang¹
¹Department of Computer Science, Princeton University
{mwtang, alzhang}@princeton.edu

Abstract

Transaction fees represent a major incentive in many blockchain systems as a way to incentivize processing transactions. Unfortunately, they also introduce an enormous amount of incentive asymmetry compared to alternatives like fixed block rewards. We analyze some of the incentive compatibility issues that arise from transaction fees, which relate to the bids that users submit, the allocation rules that miners use to choose which transactions to include, and where they choose to mine in the context of longest-chain consensus. We start by surveying a variety of mining attacks including undercutting, fee sniping, and fee-optimized selfish mining. Then, we move to analyzing mechanistic notions of user incentive compatibility, myopic miner incentive compatibility, and off-chain-agreement-proofness, as well as why they are provably incompatible in their full form. Then, we discuss weaker notions of nearly and $\gamma$ -weak incentive compatibility, and how all of these forms of incentive compatibility hold or fail in the trustless auctioneer setup of blockchains, examining classical mechanisms as well as more recent ones such as Ethereum’s EIP-1559 mechanism and [3]’s burning second-price auction. Throughout, we generalize and interrelate existing notions, provide new unifying perspectives and intuitions on analysis, and discuss both specific and overarching open problems for future work.

1 Introduction

The design choices surrounding decentralized cryptocurrencies have recently become a point of great interest both due to a menagerie of emerging challenges and their far-reaching consequences on real blockchain systems with billions of USD worth of transaction volume and tens of millions of users. The primary design of modern cryptocurrencies relies on a distributed ledger, which replaces trusted third parties with hashes, cryptography, and mechanism design. First introduced in [9], the basic idea is that participants in the network, known as miners, will try to solve a computationally-difficult hash puzzle¹¹1We motivate the problem using Proof of Work here, but almost everything we discuss also applies to alternate formulations such as Proof of Stake. If a miner is successful, they “win” the responsibility of adding the next block to the ledger, which includes adding the next set of transactions to the ledger. The miner is then rewarded with a fixed block reward and a set of transaction fees corresponding to the transactions they included in their block. In many real-world systems like Bitcoin, the long-term goal is to eventually phase out the block reward (for deflationary or other reasons), until eventually transaction fees become the primary incentive for miners to continue working on the network.

Transactions in the blockchain system are validated when they are put on a newly mined block and acknowledged by other participants. Transaction fees are paid by users making a transaction as a way of incentivizing miners to use their computational resources to keep the blockchain running; however, unlike fixed block rewards, transaction fees are not fixed, and users can offer variable transaction fee amounts, e.g. based on how urgently they want their transaction to be serialized on the blockchain. The simplest and most common mechanism is a first-price auction system where, users bid according to their personal value of having their transaction being added to the next block, and miner as the untrusted auctioneer is incentivized to include higher-paying transactions into their blocks. Unfortunately, it tunrs out that this formulation trades off simple or honest user bids in favor of honest transaction selection on the part of the miner, and the optimal bidding strategy for users is less than obvious. Similarly, having mined blocks representing different values due to the variability of transaction fees also incentivizes various deviations from the honest mining strategy, which are effectively undetectable due to the latency and other extenuating idiosyncracies of the distributed system. Sadly, mechanistic and mining deviations both decrease the predictability, capacity, and robustness of the ledger as a whole, among other implications.

In this paper, we survey major attacks under transaction fees that relate to mining, such as undercutting [2, 5] and fee sniping [12], and point out possible defenses and holes in their analysis that can be further investigated in future work. We also explore mechanism design questions surrounding incentive compatibility in the transaction-fee auction, proving a strong result by [3] regarding the impossibility of retaining classical incentive compatibility for all parties, and discussing the implications and alternative objectives to optimize in a not-fully-incentive-compatible world. We concretely survey several classical mechanisms 8 as well as state-of-the-art mechanisms 9.1 9.2 and analyze their behavior and that of potential variants. We conclude by giving some final intuitions on the design space and open questions for future work.

2 The Mining Game

2.1 Transaction-fee mining setup

We first formalize a general model setup to represent the mining game with a focus on transaction fees as the block reward. We assume a set of $n$ miners $m_{1},...,m_{n}$ , each of which has some proportional mining power $\chi(m_{i})$ such that $\sum_{i=1}^{n}\chi(m_{i})=1$ . Each miners $m_{i}$ is aware of a directed tree $G(m_{i})$ that represents their (private) knowledge of the blockchain, and they can choose any node/block on this tree to mine on. After a time interval that is exponentially distributed with mean $\chi(m_{i})^{-1}$ , the miner will find a new block $B$ and add a directed edge to the node they were mining on. They may then choose to broadcast this information to all other miners at any point. Our setup will be time-driven, so we observe and analyze the state of the system at some time $t$ .

2.2 Mining notation

We will analyze the decision-making processes of a set of miners at some time $t$ during the game. Each miner will have access to a directed tree $G$ representing the publicly known chain, and a directed tree $G(m_{i})$ representing their private chain. Let $T$ denote the total set of transaction fees. We let $\mathcal{T}(B)$ denote the transaction fees included in block $B$ , and $\mathcal{R}(B)$ denote the announced transactions fees not included in $B$ or any of its predecessors (i.e. the remaining transaction fees after block $B$ ). We also use $h(B)$ to denote the height of a block $B$ , or the length of the chain that ends at $B$ , and $\mathcal{H}$ denote the height of the highest announced block. For private chains, we use $\mathcal{H}_{m_{i}}$ to denote the highest block on $m_{i}$ ’s private chain. Because general rational strategies will not choose to mine two blocks at the same height, we let $b_{m_{i}}^{j}$ denote the unique block that miner $m_{i}$ mined at height $j$ if it exists or the block at height $j$ that the miner first heard about.

2.3 Honest Miner algorithm

All future decisions and strategies will be time-driven, in the sense that any algorithm will make decisions at every time-step about what blocks to mine on, what transaction fees to include, and whether or not to publicly announce these blocks. The canonical ”honest miner” algorithm is the ideal behavior for miners on the chain

Algorithm 2.1.

The HonestMiner strategy for miner $m_{i}$ will

1.

Mine on the end of the longest chain. If there are multiple, choose the one $m_{i}$ heard about first, which is $b_{m_{i}}^{\mathcal{H}}$ .
2.

Take all remaining available transaction fees $\mathcal{R}(b_{m_{i}}^{\mathcal{H}})$ upon discovering a new block $B$ .
3.

Publish the new block to the public chain immediately.

and can be formalized into the pseudocode below in Algorithm 1.

Algorithm 1 Honest Miner

1:procedure honestmine

G\leftarrow

publicly known blocks

G(m_{i})\leftarrow

publicly known blocks

\mathcal{H}\leftarrow

height of highest publicly known block

5: mine at

h^{\mathcal{H}}_{m_{i}}

6: while indefinitely do

\triangleright

primary loop

7: if found a block

B

then

8: Take transaction fees

\mathcal{R}(h^{\mathcal{H}}_{m_{i}})

9: add

B

h^{\mathcal{H}}_{m_{i}}

in both

G

and

G(m_{i})

and announce to the public chain

10: set

h^{\mathcal{H}+1}_{m_{i}}=B

, iterate

\mathcal{H}

1

11: mine at

h^{\mathcal{H}}_{m_{i}}

12: else if other miner found block

B

then

13: add

B

h^{\mathcal{H}}_{m_{i}}

in both

G

and

G(m_{i})

and announce to the public chain

14: set

h^{\mathcal{H}+1}_{m_{i}}=B

, iterate

\mathcal{H}

1

15: mine at

h^{\mathcal{H}}_{m_{i}}

16: end if

17: end while

18:end procedure

All other algorithms discussed in Section 3 can be fit into the pseudocode framework described in Algorithm 1 with minor modifications, so we will only write out the algorithm details for them.

Observation 2.1.

Under the transaction-fee regime, the HonestMiner strategy is not profitable for a time interval of length $t$ after some block is mined.

Dubbed the mining gap in [2], the point of Observation 2.1 is that for some time after a block is found, there is a non-trivial mining cost that outweighs the profit from transaction fees for discovering a new block. This observation may incentivize miners to use other non-honest strategies that make the blockchain more vulnerable to the attacks we will mention in the next section, and further motivate the design of new mechanisms in Section 4.

3 Transaction Fee Mining Attacks

3.1 Undercutting

First proposed in [2], the undercutting attack is performed when a miner forks the head of a chain and leaves a subset of the transaction fees unclaimed to encourage other miners to mine on top of the fork. They also introduce an simple alternative to the canonical ”honest mining” strategy, which they call the PettyCompliant strategy. The idea is to follow the same strategy as the ”honest mining” strategy, except if there is a tie in the longest chain, the PettyCompliant strategy will choose to mine on the block with the most available transaction fees rather than the oldest. More formally,

Algorithm 3.1.

The PettyCompliant strategy for miner $m_{i}$ will

1.

Mine on $b^{\mathcal{H}}_{*}=\operatorname*{arg\!\max}_{b^{\mathcal{H}}_{m_{i}}}\mathcal{R}(b_{m_{i}}^{\mathcal{H}})$ , which is the block at height $\mathcal{H}$ with the highest available transaction fees.
2.

Take all remaining available transaction fees $\mathcal{R}(b^{\mathcal{H}}_{*})$ upon discovering a new block $B$ .
3.

Publish the newly discovered block to the public chain immediately.

It is easy to observe that during the existence of a fork, PettyCompliant performs strictly better than the honest miner because it mines on a block with higher rewards without the risk of losing it. Undercutting strategies can exploit this fact by incentivizing PettyCompliant miners to extend their forked blocks, especially in the event of a tie for the highest block. A simple undercutting strategy proposed in [2] is called LazyFork which will fork the head of the chain if it is more valuable to take the transaction fees inside. More formally,

Algorithm 3.2.

The LazyFork strategy for miner $m_{i}$ will

1.
Consider $b^{\mathcal{H}}_{*}=\operatorname*{arg\!\max}_{b_{m_{i}}^{\mathcal{H}}}\mathcal{R}(b_{m_{i}}^{\mathcal{H}})$ , which is the block at height $\mathcal{H}$ with the highest available transaction fees and consider $b^{\mathcal{H}-1}_{*}=\operatorname*{arg\!\max}_{b_{m_{i}}^{\mathcal{H}-1}}\mathcal{R}(b_{m_{i}}^{\mathcal{H}-1})$ . Define $\Delta_{\mathcal{H}}=\mathcal{R}(b^{\mathcal{H}-1}_{*})-\mathcal{R}(b^{\mathcal{H}}_{*})$ , i.e. the maximum transaction fees you could get from forking on top of $b^{\mathcal{H}-1}_{*}$ .
1. (a)
  
  If $m_{i}$ owns $b^{\mathcal{H}}_{*}$ , $m_{i}$ will mine on top of $b^{\mathcal{H}}_{*}$ .
2. (b)
  
  Else if $\mathcal{R}(b^{\mathcal{H}}_{*})\geq\Delta_{\mathcal{H}}$ , $m_{i}$ will mine on top of $b^{\mathcal{H}}_{*}$ because it is not profitable enough to fork.
3. (c)
  
  Else $m_{i}$ will mine on $b^{\mathcal{H}-1}_{*}$ because it is profitable enough to fork.
2.

Take $\frac{1}{2}$ of the remaining available transaction fees upon discovering a new block $B$ .
3.

Publish the newly discovered block to the public chain immediately.

The existence of LazyFork miners is dangerous because it increases the probability of orphaned blocks existing, as well as the vulnerability of the blockchain to a double-spending attack. However, the LazyFork strategy itself is susceptible to more aggressive undercutting by other miners, and therefore a more aggressive modification called FunctionFork uses a function $f(\cdot)$ to determine the amount of transaction fees to leave open to other miners, and whether or not they should continue honestly mining on top of the head of $G$ , or perform an undercutting attack.

Remark 3.1.

While another option for an undercutting strategy is to choose to mine on top of blocks lower than $\mathcal{H}-1$ , for ease of analysis the proposed strategies only consider mining on $\mathcal{H}-1$ or $\mathcal{H}$ . While mining at a lower level on the chain is riskier, there is potentially interesting equilibrium behavior that may arise from opening up a wider set of options for an undercutting miner.

Algorithm 3.3.

The FunctionFork strategy for miner $m_{i}$ will

1.
Define the following variables
- •
  
  $b^{\mathcal{H}}_{*}=\operatorname*{arg\!\max}_{b_{m_{i}}^{\mathcal{H}}}\mathcal{R}(b_{m_{i}}^{\mathcal{H}})$ , which is the block at height $\mathcal{H}$ with the highest available transaction fees.
- •
  
  $b^{\mathcal{H}-1}_{*}=\operatorname*{arg\!\max}_{b_{m_{i}}^{\mathcal{H}-1}}\mathcal{R}(b_{m_{i}}^{\mathcal{H}-1})$ , which is the block at height $\mathcal{H}-1$ with the highest available transaction fees.
- •
  
  $\Delta_{\mathcal{H}}=\mathcal{R}(b^{\mathcal{H}-1}_{*})-\mathcal{R}(b^{\mathcal{H}}_{*})$ , i.e. the maximum transaction fees $m_{i}$ could get from forking on top of $b^{\mathcal{H}-1}_{*}$ .
- •
  
  $\mathcal{V}_{\text{CONT}}(f)=f(\mathcal{R}(b^{\mathcal{H}}_{*}))$ which is the value for continuing on the highest chain.
- •
  
  $\mathcal{V}_{\text{UND}}(f)=\min\{f(\mathcal{R}(b^{\mathcal{H}-1}_{*})),\Delta_{\mathcal{H}}\}$ which is the value for undercutting.
2.
Choose where to mine based on
1. (a)
  
  If you own $b^{\mathcal{H}}_{*}$ , mine on top of $b^{\mathcal{H}}_{*}$ .
2. (b)
  
  Else if $\mathcal{V}_{\text{CONT}}(f)\geq\mathcal{V}_{\text{UND}}(f)$ , mine on top of $b^{\mathcal{H}}_{*}$ because it is not profitable enough to fork.
3. (c)
  
  Else mine on $b^{\mathcal{H}-1}_{*}$ because it is profitable enough to fork.
3.

If you mined on top of $b^{\mathcal{H}}_{*}$ , take $\mathcal{V}_{\text{CONT}}(f)$ transaction fees, and $\mathcal{V}_{\text{UND}}(f)$ otherwise.
4.

Publish the newly discovered block to the public chain immediately.

Clearly, $f(\cdot)$ is supposed to be some mapping from the transaction fees you receive to the amount you give, and therefore any general strategy will make it a monotonically increasing function. [2] show that when considering the linear family of functions $f(x)=kx$ for $k\in[0,1]$ , if we assume that every miner is non-atomic, i.e. there are infinite miners with infinitesimally small hashing power, so they only locally consider how to maximize the block they just found because with zero probability they find another, then the equilibrium strategy is to undercut other players by slowly decreasing $k$ until it hits zero. They also show that under the assumption that every miner is atomic, the equilibrium behavior is unstable. They further prove that there exists a family of functions $\mathcal{F}$ in which it is an equilibrium for every miner to use FunctionFork $(f)$ for $f\in\mathcal{F}$ under strong conditions, which we state without proof:

Theorem 3.1.

Assume every miner is non-atomic, and that miners may only mine on top of $\mathcal{H}$ and $\mathcal{H}-1$ . Let $W_{0}$ be the upper branch of the Lambert function $W$ satisfying $W_{0}(xe^{x})=x$ for all $x\in[-\frac{1}{e},\infty)$ and $W_{0}(x)\in[-1,\infty)$ . Then, for any constant $\gamma\leq\frac{1}{2}$ such that $2\gamma-\ln(\gamma)\geq 2$ , define the monotonically-increasing function $f(x)$ as

\displaystyle f(x)=\begin{cases}f(x)=x&x\leq\gamma\\ f(x)=-W_{0}(-\gamma e^{x-2\gamma})&\gamma<x<2\gamma-\ln(\gamma)-1\\ f(x)=1&x\geq 2\gamma-\ln(\gamma)-1\end{cases}

Then it is an equilibrium for every miner to use the FunctionFork(f) strategy, i.e. it is a best response over all potential other strategies.

Finally, [2] conclude using Theorem 3.1 and a set of simulations that while it is intractible to prove that convergence to such equilibrium is guaranteed in practice, they are able to simulate scenarios where rational miners eventually change to undercutting eachother as the equilibrium, severely damaging the stability of the blockchain.

Remark 3.2.

An important caveat to the analysis above is that it ignores block size limits, which are the maximum claimable fees on any block. [5] finds that the undercutting scheme is significantly weakened than exactly what was proposed above under these more realistic conditions because it makes undercutting less profitable in expectation. This fact also somewhat implies that any defenses against undercutting should restrict the size of transaction fees that can be found on a block, or restrict what transaction fees can be put on a forked block in the first place. [12] was added to Bitcoin for this purpose, which ensures transactions cannot be put into a block unless it is of a certain height on the chain, preventing an attacker from putting all high-paying fees onto a single forked block.

3.2 Fee sniping

Fee sniping (as described in [12, 7]) is an attack where a miner will deliberately fork a block to take the high transaction fees found on the currently accepted block. Although it is unlikely that any miner will re-mine a previous block and find a new block before a new block is found by another miner, because transaction fees are not fixed, it is sometimes profitable in expectation to attempt a fee snipe. We define a simple fee sniping strategy below

Algorithm 3.4.

The BasicFeeSnipe strategy for miner $m_{i}$ will

1.
Consider $b^{\mathcal{H}}_{*}=\operatorname*{arg\!\max}_{b_{m_{i}}^{\mathcal{H}}}\mathcal{T}(b_{m_{i}}^{\mathcal{H}})$ , which is the block at height $\mathcal{H}$ with the highest available transaction fees and consider $b^{\mathcal{H}-1}_{*}=\operatorname*{arg\!\max}_{b_{m_{i}}^{\mathcal{H}-1}}\mathcal{T}(b_{m_{i}}^{\mathcal{H}-1})$ . Define $\Delta_{\mathcal{H}}=\mathcal{R}(b^{\mathcal{H}-1}_{*})-\mathcal{R}(b^{\mathcal{H}}_{*})$ , i.e. the maximum transaction fees you could get from forking on top of $b^{\mathcal{H}-1}_{*}$ .
1. (a)
  
  If $m_{i}$ owns $b^{\mathcal{H}}_{*}$ , $m_{i}$ will mine on top of $b^{\mathcal{H}}_{*}$ .
2. (b)
  
  Else if $\mathcal{R}(b^{\mathcal{H}}_{*})\geq\chi(m_{i})^{2}\cdot\mathcal{R}(b^{\mathcal{H}-1}_{*})$ , $m_{i}$ will mine on top of $b^{\mathcal{H}}_{*}$ because it gets a higher expected reward by being honest.
3. (c)
  
  Else $m_{i}$ will mine on $b^{\mathcal{H}-1}_{*}$ because it gets a higher expected reward by forking.
2.

Take all of the remaining available transaction fees upon discovering a new block $B$ .
3.

Publish the newly discovered block to the public chain immediately.

We can observe that BasicFeeSnipe is almost the same as LazyFork discussed in Section 3.1, except it decides where to mine based on the expected value of winning the next two blocks by forking and not on incentivizing other miners. We see that in the forking condition $\chi(m_{i})^{2}\cdot\mathcal{R}(b^{\mathcal{H}-1}_{*})>\mathcal{R}(b^{\mathcal{H}}_{*})$ , where the left side of the inequality is precisely the probability of winning the next two blocks $\chi(m_{i})^{2}$ multiplied by the current transaction-fee rewards for winning $\mathcal{R}(b^{\mathcal{H}-1}_{*})$ at the current timestep, which is actually a safe estimate of the expectation because during the mining process, more fees will come in.

Remark 3.3.

To combat fee sniping, [12] added an nLockTime variable on the Bitcoin blockchain to forcibly prevent miners from orphaning the current best block by forking an earlier block. They take advantage of block size limits to ensure one cannot push an absurdly large amount of transaction fees to a single block.

3.3 Whale transaction attacks

[7] analyzes a type of attack performed in which a miner $A$ makes a valid transaction with another miner $B$ on the main blockchain, then forks the chain to a point before the transaction was valid to nullify it. To incentivize other miners to work on this new chain, they offer an exorbitant transaction fee that can be claimed if the fork becomes the new main chain. They call this attack a whale transaction, and demonstrate that it also can lead to vulnerabilities in the blockchain like double spending.

Consider the following simplified setup for miner $A$ attempting to perform a whale transaction:

1.

Assumptions: Let $1$ be the normalized average block reward (fixed block reward + average transaction fee) and let $\delta$ be the (normalized) whale fee that miner $A$ offers. Assume hashing power $\chi(x_{i})$ is fixed for all miners, and relative mining power is known among all miners. Also assume miners will choose the most profitable strategies, and that they can either be honest or work on miner $A$ ’s fork. Finally, to allow for easier steady-state analysis, assume at any point that the relative mining power of miner $A$ ’s fork is fixed, i.e. they will offer more of a fee $\delta$ to keep the mining power constant.
2.

Pre-mining phase: Miner $A$ will make a transaction with miner $B$ , then attempt to undo it by forking at an earlier node in $G$ . Miner $A$ can then issue several illegimate transactions such as a double spending transaction in $G(A)$ until they are ready to announce their blocks. They will also ensure that they have hefty unclaimed transaction fees on their fork.
3.

Racing phase: Assume $\mathcal{H}_{A}<\mathcal{H}$ , so miner $A$ ’s fork has to catch up to the main blockchain. Let $\gamma_{i}=1$ if miner $m_{i}$ decides to mine on miner $A$ ’s fork, and $0$ otherwise. Then the relative mining power on miner $A$ ’s fork is $q=\chi(A)+\sum\gamma_{i}\chi(m_{i})$ and the relative mining power on the honest chain is $p=1-q$ . Let $z$ denote the lead that the main branch has over $A$ ’s fork. Then, the probability that the fork overtakes the main branch, i.e. $z=-1$ , can be computed by modeling this process as a biased random walk where $z$ decrements with probability $q$ and increments with probability $p$ . The probability that the fork eventually overtakes the main branch is therefore

$a_{z}=\min\{1,q/p\}^{z+1}$

Theorem 3.2.

Suppose miner $A$ has mining power $\chi(A)$ , and a miner $X$ has mining power $\chi(X)$ . Assume every other miner is honest. For notational sake, let $M=\sum_{m\neq A}\chi(m)$ be the total mining power of all miners except $A$ . Then under the setup defined above, miner $X$ is incentivized to mine on $A$ ’s fork when

\delta>\frac{(1-(\frac{\chi(A)}{M})^{z+1})}{M}\cdot\frac{\chi(A)+\chi(X)}{(\frac{\chi(A)+\chi(X)}{M+\chi(X)})^{z+1}}-1

Proof: Assume miner $X$ decides to stay honest. Then their expected reward is the probability that the fork fails, $(1-a_{z})$ multiplied by the reward (which is normalized to $1$ ) for finding a new block, and the probability of finding a new block, $\frac{\chi(X)}{M}$ . So

\mathbf{E}[X\text{ mines honest reward}]=(1-a_{z})\frac{\chi(X)}{M}=\frac{(1-(\frac{\chi(A)}{M})^{z+1})\cdot\chi(X)}{M}

Now assume $X$ decides to work on $A$ ’s fork. Their expected reward is the probability that the fork succeeds, $a_{z}$ , multiplied by the reward $(1+\delta)$ for finding a new block, and the probability of finding a new block, $\frac{\chi(X)}{q}$ , where $q=\chi(A)+\chi(X)$ now. So,

\mathbf{E}[X\text{ mines whale reward}]=a_{z}\frac{\chi(X)}{q}(1+\delta)=\frac{(\frac{\chi(A)+\chi(X)}{M-\chi(X)})^{z+1})\cdot\chi(X)}{\chi(A)+\chi(X)}\cdot(1+\delta)

Now miner $X$ will be incentivized to mine on miner $A$ ’s fork if their expected reward is higher. This is precisely when

	$\displaystyle\frac{(\frac{\chi(A)+\chi(X)}{M-\chi(X)})^{z+1})\cdot\chi(X)}{\chi(A)+\chi(X)}\cdot(1+\delta)>\frac{(1-(\frac{\chi(A)}{M})^{z+1})\cdot\chi(X)}{M}$
	$\displaystyle\delta>\frac{(1-(\frac{\chi(A)}{M})^{z+1})}{M}\cdot\frac{\chi(A)+\chi(X)}{(\frac{\chi(A)+\chi(X)}{M+\chi(X)})^{z+1}}-1$
	$\displaystyle\square$

[7] use Theorem 3.2 and plug in values for $z$ and $\delta$ to find what relative values of $\delta$ are necessary to motivate a whale attack. It should be remarked that the values of $\delta$ are quite large, and therefore, a whale attack is only rational if miner $A$ is able to get a huge sum of rewards. However, as block rewards continue to diminish, it is also easily observable that the whale transaction can be smaller to promote the same effect.

Remark 3.4.

The analysis above makes strong assumptions about the honest behavior of other miners on the chain, and therefore it is entirely possible that lower values of $\delta$ will allow for a whale transaction attack to be profitable for any deviant miners. Additionally, under the transaction-fee regime, as we will see in the next section, miners can use blocks with low-value fees as a starting point to attempt low-risk attacks.

3.4 Fee-optimized selfish mining

[4] first proposed the selfish mining algorithm, which can yield a higher expected reward than the honest miner even with $<51\%$ of the total hashing power. The intuitive idea is to waste other miners’ hashing power by hiding the existence of their owned mined blocks, and only revealing them when the public chain reveals a new block. A transaction-fee regime version of this algorithm is defined below:

Algorithm 3.5.

The SelfishMiner strategy for a miner $m_{i}$ will

1.

Choose to mine on $\mathcal{H}_{m_{i}}$ , which is the highest block on their private chain.
2.

Take all remaining available transaction fees $\mathcal{R}(\mathcal{H}_{m_{i}})$ upon discovering a new block $B$ .
3.

If $h(B)=\mathcal{H}$ , publish the block immediately. Otherwise, if there exists two distinct blocks of height $\mathcal{H}$ where one is owned by $m_{i}$ , and $\mathcal{H}_{m_{i}}=\mathcal{H}+1$ , reveal $b_{m_{i}}^{\mathcal{H}}$ .

In [2], they observe that under the transaction-fee regime, the default selfish mining algorithm will have a slightly higher expected reward than in the standard fixed-block reward regime despite performing the same actions.

Theorem 3.3.

Let $\gamma\in[0,1]$ be the probability that if the selfish miner $m_{i}$ is in a race with the public chain, it is not orphaned. Then given $\chi(m_{i})=\alpha\in(0,0.5)$ , the expected reward of SelfishMiner is

\mathbf{E}(\text{reward})=\frac{5\alpha^{2}-12\alpha^{3}+9\alpha^{4}-2\alpha^{5}+\gamma(\alpha-4\alpha^{2}+6\alpha^{3}-5\alpha^{4}+2\alpha^{5})}{2\alpha^{3}-4\alpha^{2}+1}

Proof: Consider the following states, in which at any timestep in the game, a miner $m_{i}$ running SelfishMiner will be in:

•

State $0$ : The highest block in $G$ is also the highest block in $G(m_{i})$ , i.e. miner $m_{i}$ is not hiding any blocks.
•

State $j>0$ : Miner $m_{i}$ has a private chain of length $j$ , so $\mathcal{H}_{m_{i}}=\mathcal{H}+j$
•

$0^{\prime}$ : $\mathcal{H}_{m_{i}}=\mathcal{H}$ , but one is produced by $m_{i}$ , and the other is not, i.e. the selfish miner is racing with the public chain.

Let $f_{s}$ be the probability that a transaction is in the block found by a $m_{i}$ conditioned on being in state $s$ , and $p_{s}$ is the probability that miner $m_{i}$ is in state $s$ , then the expected reward for the miner is $\sum_{s}f_{s}\cdot p_{s}$ . Observe that the probability of being in any state $s$ is identical in both the fixed reward and transaction-fee regime, and [4] have already shown that

	$\displaystyle p_{0}=\frac{1-2\alpha}{2\alpha^{3}-4\alpha^{2}+1}$
	$\displaystyle p_{0}^{\prime}=\frac{(1-\alpha)(\alpha-2\alpha^{2})}{2\alpha^{3}-4\alpha^{2}+1}$
	$\displaystyle p_{j}=\biggr{(}\frac{\alpha}{1-\alpha}\biggr{)}^{j-1}\cdot\frac{\alpha(1-2\alpha)}{2\alpha^{3}-4\alpha^{2}+1}\quad\text{ for }j>0$

We now compute $f_{s}$ . Suppose a transaction arrives in state $0$ . If the selfish miner $m_{i}$ finds the block, which occurs with probability $\alpha$ , the transaction will be in the longest chain only if they mine the next block; this whole event occurs with probability $\alpha^{2}$ . Otherwise, an honest miner $m_{-i}$ might find the next block with probability $(1-\alpha)$ and cause a race where whoever wins gets the transaction fee. The selfish miner wins this race with probability $\alpha+\gamma(1-\alpha)$ , so in total,

f_{0}=\alpha^{2}+\alpha(1-\alpha)(\alpha+\gamma(1-\alpha))

For the $0^{\prime}$ state, we observe that the selfish miner will get the transaction only if they find the next block first, which occurs with probability $\alpha$ , so

f_{0^{\prime}}=\alpha

The remaining states can be recursively computed: $f_{1}$ is precisely the probability of the selfish miner gaining another block to guarantee that the transaction will belong to $m_{i}$ plus the probability of returning to state $0^{\prime}$ and winning. Formally,

f_{1}=\alpha+(1-\alpha)f_{0^{\prime}}=\alpha+(1-\alpha)\alpha

To compute $f_{j}$ for $j>1$ , observe that the transaction will not belong to $m_{i}$ only if the honest miner wins the next $j-1$ blocks, returning $m_{i}$ to state $0$ , then winning the block in state $0$ . This is precisely

f_{j}=1-\biggr{(}(1-\alpha)^{j-1}(1-f_{0})\biggr{)}\quad\text{ for }j>1

Finally, we compute $\sum_{s}p_{s}f_{s}$ and condense some of the simple but tedious computations:

\mathbf{E}(\text{reward})=p_{0}f_{0}+p_{0^{\prime}}f_{0^{\prime}}+p_{1}f_{1}+\sum_{j>1}p_{j}f_{j}

$p_{0}f_{0}+p_{0^{\prime}}f_{0^{\prime}}+p_{1}f_{1}$ can be computed by multiplying the individual expressions and summing, so we will state their results without explicitly writing out the intermediate steps. The more interesting computation is

\sum_{j>1}p_{j}f_{j}=\sum^{\infty}_{j=2}\biggr{[}\biggr{(}\frac{\alpha}{1-\alpha}\biggr{)}^{j-1}\frac{\alpha-2\alpha^{2}}{2\alpha^{3}-4\alpha^{2}+1}-\alpha^{j-1}(1-f_{0})\frac{\alpha-2\alpha^{2}}{2\alpha^{3}-4\alpha^{2}+1}\biggr{]}

(1)

By the properties of a geometric series, $\sum^{\infty}_{j=2}(\frac{\alpha}{1-\alpha})^{j-1}=\frac{\alpha}{1-2\alpha}$ and $\sum^{\infty}_{j=2}\alpha^{j-1}=\frac{\alpha}{1-\alpha}$ , so we can simplify (1) to get

	$\displaystyle\sum_{j>1}p_{j}f_{j}=\biggr{[}\biggr{(}\frac{\alpha}{1-2\alpha}\cdot\frac{\alpha-2\alpha^{2}}{2\alpha^{3}-4\alpha^{2}+1}-\frac{\alpha}{1-\alpha}\cdot(1-f_{0})\frac{\alpha-2\alpha^{2}}{2\alpha^{3}-4\alpha^{2}+1}\biggr{]}$
	$\displaystyle=\frac{\alpha^{2}-\alpha(1+\alpha(1-\alpha)(1-\gamma))(\alpha-2\alpha^{3})}{2\alpha^{3}-4\alpha^{2}+1}$

and finally, we get our result by summing all the terms

	$\displaystyle\mathbf{E}(\text{reward})=\frac{2\alpha^{2}-5\alpha^{3}+2\alpha^{4}+\alpha\gamma-4\alpha^{2}\gamma+5\alpha^{3}\gamma-2\alpha^{4}\gamma}{2\alpha^{3}-4\alpha^{2}+1}+\frac{\alpha^{2}-3\alpha^{3}+2\alpha^{4}}{2\alpha^{3}-4\alpha^{2}+1}$
	$\displaystyle+\frac{2\alpha^{2}-5\alpha^{3}+2\alpha^{4}}{2\alpha^{3}-4\alpha^{2}+1}+\frac{\alpha^{2}-\alpha(1+\alpha(1-\alpha)(1-\gamma))(\alpha-2\alpha^{3})}{2\alpha^{3}-4\alpha^{2}+1}$
	$\displaystyle=\frac{5\alpha^{2}-12\alpha^{3}+9\alpha^{4}-2\alpha^{5}+\gamma(\alpha-4\alpha^{2}+6\alpha^{3}-5\alpha^{4}+2\alpha^{5})}{2\alpha^{3}-4\alpha^{2}+1}$
	$\displaystyle\square$

It is interesting to observe that for $\gamma\in[0,0.55]$ , the expected reward found in Theorem 3.3 is strictly greater than the expected reward under the block regime found in [4], which is $\frac{\alpha(1-\alpha)^{2}(4\alpha+\gamma(1-2\alpha))-\alpha^{3})}{1-\alpha(1+(2-\alpha)\alpha)}$ . [2] reasons that this is because in high-number states, the selfish miner will gain a disproportionately large number of transaction fees while in the fixed-reward model, the rewards gained for mining a new block are always fixed. While interesting, the reward gain in the transaction-fee regime is minimal compared to the fixed-reward regime. A more interesting analysis comes from the fact that selfish miners can look at the value of a block when deciding whether or not to hide it. Consider the following fee-optimized selfish miner proposed in [2], which has a threshold parameter $\beta$ :

Algorithm 3.6.

The FeeSelfishMiner strategy for a miner $m_{i}$ will

1.

Choose to mine on $\mathcal{H}_{m_{i}}$ , which is the highest block on their private chain.
2.

Take all remaining available transaction fees $\mathcal{R}(\mathcal{H}_{m_{i}})$ upon discovering a new block $B$ .
3.

If $h(B)=\mathcal{H}$ or if $\mathcal{T}(B)>\beta$ , publish the block immediately. Otherwise, if there exists two distinct blocks of height $\mathcal{H}$ where one is owned by $m_{i}$ , and $\mathcal{H}_{m_{i}}=\mathcal{H}+1$ , reveal $b_{m_{i}}^{\mathcal{H}}$ .

The intuitive idea is as follows. If a selfish miner comes across a nearly worthless block with $\mathcal{T}(B)<\beta$ , there is little risk in using it in a fork to potentially overtake the main chain. [2] recompute both $p_{s}$ and $f_{s}$ and an additional state $0^{\prime\prime}$ , which is where the FeeSelfishMiner will choose to honestly mine, and conclude with the following theorem, which we state without proof because the analysis is very similar to Theorem 3.3:

Theorem 3.4.

Let $\gamma\in[0,1]$ be the probability that if the selfish miner $m_{i}$ is in a race with the public chain, it is not orphaned. For a FeeSelfishMiner miner $m_{i}$ using threshold $\beta$ , given $\chi(m_{i})=\alpha\in(0,0.5)$ , the expected reward is

\mathbf{E}(\text{reward})=\biggr{(}\frac{1+\beta(1-\alpha)^{2}(1-\gamma)}{e^{\beta}-1}+5\alpha+(1-\alpha)^{2}\gamma+\frac{2\alpha^{2}}{1-2\alpha}-2\alpha^{2}\biggr{)}\cdot\biggr{(}\frac{\alpha(1-2\alpha)(1-e^{-\beta})}{1-2e^{-\beta}\alpha-3(1-e^{-\beta})\alpha^{2}}\biggr{)}

Plugging in values into Theorem 3.4, it is observable that for $\alpha=\frac{1}{3}$ , the SelfishMiner and HonestMiner schemes both achieve an expected reward of approximately $\frac{1}{3}$ , but the FeeSelfishMiner with an optimal $\beta$ performs $13.6\%$ better with an expected reward of $\approx 0.38$ .

Remark 3.5.

A key part of this analysis is the fact that blocks containing low-transaction fees are a useful way to start a forking attack because they are not very valuable to the attacker even if they are on the eventual chain. However, selfish mining itself offers no incentives for other miners to help, making it relatively weak unless a single miner owns a large percentage of the mining power. We believe that there is a lot of future work in analyzing attacks that take advantage of low transaction-fee blocks while also incentivizing other miners to mine on their fork to greatly increase the probability of a successful attack.

4 Transaction Fee Mechanism Design

Besides preventing selfish-mining attacks, there are other desiderata to consider in the design of a transaction fee system. Here, we are specifically interested in the transaction fee mechanism (TFM), and our goal is to modify or relax the first price auction setup in order to obtain or trade off against desired properties. To start, let us define the framework of a TFM.

4.1 TFM definitions

We consider a single auction instance corresponding to the next mined block:

1.

$m$ users with values $\mathbf{v}$ for having their transaction included in the block, submit bids ²²2When discussing TFMs, we will use the terms “bid” and “transaction” interchangeably $\mathbf{b}$
2.

the miner picks a subset of $k$ bids $B_{I}\subseteq\mathbf{b}$ ³³3For concision, throughout this paper we will abuse notation to treat vectors $\mathbf{b},\mathbf{v}$ as sets to include in the block
3.

the blockchain then confirms a further subset $B_{C}\subseteq B_{I}$ and enforces payments $\mathbf{p}$ for each user whose transaction was confirmed, and revenue $r$ for the miner

where the blockchain always executes the mechanism honestly, but the users and miner are strategic, acting to maximize their respective utility ( $r$ for miner and $v_{i}-p_{i}$ for user $i$ , with users with unconfirmed bids getting utility 0).

Note that all of this operates under the continuing assumption that the blockchain is effectively permissionless and anonymous.

Remark 4.1 (Iterated analysis is hard).

Ideally, we would prefer our analysis, including notions such as incentive compatibility and miner and user utility, to extend to an iterated game over multiple rounds of block proposals into account. Unfortunately, conditioning on large numbers of unpredictable future transactions makes such analysis becomes significantly more difficult, so the literature generally focuses on the mechanism applying to a single auction instance. This may be a rich area of further study, e.g. [3] points out that unconfirmed bids from fake bids added by miners are not easy to retract in blockchains like Ethereum and thus would have a chance of incurring the full cost of the bid in future rounds, which may serve as a penalty for encouraging honest miner behavior. We use this intuition in 6.

Following the notation in [3], which distinguishes between inclusion and confirmation, a TFM then corresponds to a tuple $(\mathbf{I},\mathbf{C},\mathbf{P},\mathbf{M})$ where: ( $\mathbb{R}_{+}\coloneqq[0,\infty)\subseteq\mathbb{R}$ )

1.

$\mathbf{I}:\mathbb{R}_{+}^{m}\to\mathbb{R}_{+}^{m}\times\{0,1\}^{m}$ is the miner’s inclusion rule: given bids, output the bids and whether each bid is included
2.

$\mathbf{C}:\mathbb{R}_{+}^{m}\times\{0,1\}^{m}\to\{0,1\}^{m}$ is the blockchain’s confirmation rule: given bids and an inclusion vector, output whether each bid is confirmed
3.

$\mathbf{P}:\mathbb{R}_{+}^{m}\times\{0,1\}^{m}\to\{\mathbb{R}_{+}\}^{m}$ is the blockchain’s payment rule: given bids and a confirmation vector, output payments
4.

$\mathbf{M}:\mathbb{R}_{+}^{m}\times\{0,1\}^{m}\to\mathbb{R}_{+}$ is the blockchain’s miner revenue rule: given bids and a confirmation vector, output miner revenue

Since the blockchain always implements its rules honestly, in analysis we can simplify this to a tuple $(\mathbf{x},\mathbf{p},\mu)$ where

1.

$\mathbf{x}\coloneqq\mathbf{C}\circ\mathbf{I}:\mathbb{R}_{+}^{m}\to\{0,1\}^{m}$ is the allocation rule: given bids, output whether each bid is confirmed
2.

$\mathbf{p}\coloneqq\mathbf{P}\circ\mathbf{I}:\mathbb{R}_{+}^{m}\to\mathbb{R}_{+}^{m}$ is the payment rule: given bids, output payments
3.

$\mu\coloneqq\mathbf{M}\circ\mathbf{I}:\mathbb{R}_{+}^{m}\to\mathbb{R}_{+}$ is the miner revenue rule: given bids, output miner revenue

When the mechanism is random, we relax whether a bid is included/confirmed into the probability of inclusion/confirmation $[0,1]^{m}$ , and output expected payments and revenue.

Note that the strategy space includes deviations from honest behavior such as:

1.

Users can bid dishonestly, which is sometimes known as bid shading, possibly after examining some or all other bids (note that as long as user payments are non-negative, i.e. the mechanism does not pay users for bidding, this implies underbidding)
2.

Users can submit additional fake bids (for which they have zero value), possibly after examining all real bids
3.

Miners can submit fake bids, possibly after examining all real bids
4.

Miners can select bids dishonestly with respect to the inclusion rule
5.

Cartels (i.e. sets) of users and the miner can collude to deviate in ways that maximize their joint utility (sum of individual utilities), including overbidding, underbidding, submitting additional fake bids, and selecting dishonestly

Remark 4.2 (Joint utility is all you need).

A simple offchain payment suffices to ensure that whenever joint utility is strictly increased, payoff can be distributed among colluders such that each receives strictly greater utility.

Due to idiosyncratic properties of blockchains (i.e. costless account creation, permissionlessness, pseudonymity), all of the above deviations can be conducted undetectably, which prevent explicit penalization for deviations.

4.2 Incentive compatibility

From a mechanism design perspective, a TFM is effectively an auction where the auctioneer may or may not be truthful. Further, the majority of previous mechanism design literature assumes a trusted auctioneer who honestly executes the mechanism. As such, attempts to design TFM usually focus on the following incentive compatibility properties:

1.

a TFM is user incentive compatible (UIC) if truthful bidding is dominant for users.
2.

a TFM is myopic miner incentive compatible (MMIC) if truthful implementation of the mechanism is dominant for miners where only single-round utility is considered (recall 4.1)
3.

a TFM is off-chain-agreement-proof (OCA-proof) if no off-chain agreement (OCA) ⁴⁴4Note that throughout this paper we assume off-chain agreements have fulfillment guarantees, as is implied by the literature between the miner and any number of users can improve joint utility over the outcome from bidding and implementing the mechanism honestly, respectively. We can relax this by denoting TFMs robust against OCAs of the miner and up to $c$ users as $c$ -OCA-proof.

Remark 4.3 (UIC, MMIC, OCA-proof are incomparable).

No pair of notions yields entailment, which motivates thinking independently about all three, e.g. instead of some unifying property. For most directions this quickly follows from considering first-price, second-price, or posted-price auctions. We will present the proof of one subtle direction to give intuition on the relationships between the notions:

Proposition 4.1.

OCA-proof does not imply MMIC

Proof.

Consider an auction where only the highest bid is confirmed, and they simply pay their bid which the miner receives as revenue, except when they are the only bid, in which case they pay nothing and the miner gets nothing. This is OCA-proof since there is no nonzero joint utility for the miner to collude with any unconfirmed user, and the joint utility for the cartel consisting of the miner and the single confirmed user cannot exceed the value $v_{i}$ of the user. However, this is not MMIC, since in cases where there is only one bid, the miner can inject a fake bid to get revenue nonzero. ∎

Remark 4.4.

(Incentive compatibility properties are naturally motivated) We see that these canonical properties are also naturally motivated by a view of the TFM as a user-centric transaction-processing service. Possible such desiderata include:

1.

Simplify user bidding, which reduces overpayment, user-side computational costs, and overall user experience
2.

Increase network capacity and reduce delays for users
3.

Increase network robustness and decentralization properties
4.

Allow users to pay for priority inclusion in a block
5.

Allow users to pay for other properties of blocks (e.g. transaction ordering or bid escalators ⁵⁵5this refers to a user specifying a more detailed curricula of how much they are willing to pay for their transaction to be included within the $k$ next blocks for each $k$ )

Among these, (1) motivates UIC and OCA-proofness as a simple bid should intuitively just be a function of the user’s personal utility $v_{t}$ and not competing bids or off-chain miner offers (e.g. (1) bidding $v_{t}$ or either bidding a posted price $p$ if $v_{t}<p$ or abstaining otherwise). Similarly, (2) motivates MMIC, as effective network capacity decreases if miners submit fake bids to manipulate revenue, which is a common way by which miners deviate from the honest protocol. (3) is closely related to mitigations against selfish mining, and additionally can be viewed as a motivation for OCA-proofness, as collusion is a centralizing vector. (4) is a property found in first-price auctions 8.1 and later “tipping” in the EIC-1559 mechanism 9.1. (5) is left open and mentioned among other open challenges in the conclusion.

5 Three-Way Incentive Compatibility is Impossible

Sadly, a major result by [3] implies that getting this combination of incentive compability notions as written is impossible. Specifically:

Theorem 5.1.

Assuming finite block size, no nontrivial single-parameter, possibly randomized TFM can be both UIC and 1-OCA-proof.

To prove this, we will assume the following well known result by Myerson [8]:

Lemma 5.1.

Consider a single-parameter TFM $(\mathbf{x},\mathbf{p},\mu)$ that is UIC. Then the following properties must hold:

1.

We define monotone as follows: Consider some $\mathbf{b}:=(b_{1},...,b_{m})$ . An allocation rule $x$ is monotone if for any $\mathbf{b}$ , and any $b^{\prime}_{i}>b_{i}$ , $x_{i}(\textbf{b}_{-i},b^{\prime}_{i})\geq x_{i}(\mathbf{b_{-i}},b_{i})$ . The allocation rule $\mathbf{x}$ is monotone.

For any user $i$ , bid $b_{i}$ , and other bids $\mathbf{b}_{-i}$ , the payment rule is defined as

(a)

If the mechanism is non-deterministic

$p_{i}(\mathbf{b}_{-i},b_{i})=b_{i}\cdot x_{i}(\mathbf{b}_{-i},b_{i})-\int_{0}^{b_{i}}x_{i}(\mathbf{b}_{-i},t)dt$

(b)

Otherwise,

\displaystyle p_{i}(\mathbf{b}_{-i},b_{i})=\begin{cases}\min\{z\in[0,b_{i}]:x_{i}(\mathbf{b}_{-i},z)=1\}&\text{ if }x_{i}(\mathbf{b}_{-i},b_{i})=1\\ 0&\text{ if }x_{i}(\mathbf{b}_{-i},b_{i})=1\end{cases}

A user $i$ ’s payment must satisfy the ”payment sandwich” inequality

v\cdot(x_{i}(\mathbf{b}_{-i},v^{\prime})-x_{i}(\mathbf{b}_{-i},v))\leq p(\mathbf{b}_{-i},v^{\prime})-p(\mathbf{b}_{-i},v)\leq v^{\prime}\cdot(x_{i}(\mathbf{b}_{-i},v^{\prime})-x_{i}(\mathbf{b}_{-i},v))

Furthermore, for a non-decreasing function $x_{i}(\mathbf{b}_{-i},\cdot)$ and $p(\mathbf{b}_{-i},0)=0$ , the payment rule is of the unique form presented in (2).

4.

Let $f(z)$ be a monotonically decreasing function. If for any $z^{\prime}\geq z\geq 0$ , $z\cdot(f(z^{\prime})-f(z))\leq g(z^{\prime})-g(z)\leq z^{\prime}\cdot(f(z^{\prime})-f(z))$ and $g(0)=0$ , then

$g(z)=z\cdot f(z)-\int_{0}^{z}f(t)dt$

The idea here is that each user $i$ should only pay the minimum price that confirms their bid. It should be remarked that points (3) and (4) are actually direct corollaries of [8]’s original Myerson lemma. We also opt out of directly proving the deterministic case because it is similar but simpler than the general randomized case and uses the same overarching proof steps. We first prove the following lemma. For notational convenience, we define

\pi_{\mathbf{b}_{-i}}(r)=p_{i}(\mathbf{b}_{-i},r)-\mu(\mathbf{b}_{-i},r)

where $\mu(\mathbf{b})$ is the expected miner revenue and $p_{i}(\mathbf{b})$ is the expected payment of user $i$ .

Lemma 5.2.

Consider a single-parameter TFM $(\mathbf{x},\mathbf{p},\mu)$ that is 1-OCA-proof. Then for any bid vector $\mathbf{b}$ , user $i$ , and $r,r^{\prime}$ such that $r<r^{\prime}$ ,

r\cdot(x_{i}(\mathbf{b}_{-i},r^{\prime})-x_{i}(\mathbf{b}_{-i},r))\leq\pi_{\mathbf{b}_{-i}}(r^{\prime})-\pi_{\mathbf{b}_{-i}}(r)\leq r^{\prime}\cdot(x_{i}(\mathbf{b}_{-i},r^{\prime})-x_{i}(\mathbf{b}_{-i},r))

Proof 0.

We first prove the left inequality. Assume for the sake of contradiction that there exists a vector $\mathbf{b}$ , a user $i$ , and $r<r^{\prime}$ such that

r\cdot(x_{i}(\mathbf{b}_{-i},r^{\prime})-x_{i}(\mathbf{b}_{-i},r))>\pi_{\mathbf{b}_{-i}}(r^{\prime})-\pi_{\mathbf{b}_{-i}}(r)

Suppose the real bid vector is $(\mathbf{b}_{-i},r)$ and user $i$ ’s true value is $r$ . Then either

1.

They do not have a side contract, so the miner’s expected utility is $\mu(\mathbf{b}_{-i},r)$ and user $i$ ’s expected utility is $r\cdot(x_{i}(\mathbf{b}_{-i},r)-p_{i}(\mathbf{b}_{-i},r))$ .
2.

They have a side contract, and the miner asks user $i$ to bid $r^{\prime}$ . Then the miner’s expected utility is $\mu(\mathbf{b}_{-i},r^{\prime})$ and user $i$ ’s expected utility is $r\cdot(x_{i}(\mathbf{b}_{-i},r^{\prime})-p_{i}(\mathbf{b}_{-i},r^{\prime}))$ . This implies that their joint expected utility increases by $r\cdot(x_{i}(\mathbf{b}_{-i},r^{\prime})-x_{i}(\mathbf{b}_{-i},r))-(\pi_{\mathbf{b}_{-i}}(r^{\prime})-\pi_{\mathbf{b}_{-i}}(r))$ , which is $>0$ by our assumption. However, this now violates the TFM being 1-OCA-proof, so we have a contradiction.

We now prove the right inequality, which is the same argument. Assume for the sake of contradiction that there exists a vector $\mathbf{b}$ , a user $i$ , and $r<r^{\prime}$ such that

\pi_{\mathbf{b}_{-i}}(r^{\prime})-\pi_{\mathbf{b}_{-i}}(r)>r^{\prime}\cdot(x_{i}(\mathbf{b}_{-i},r^{\prime})-x_{i}(\mathbf{b}_{-i},r))

Suppose the real bid vector is $(\mathbf{b}_{-i},r^{\prime})$ and user $i$ ’s true value is $r^{\prime}$ . Then we get the same scenario as before, where the joint expected utility increases by a positive amount when the miner asks the user $i$ to bid $r$ instead through a contract, thus violating the TFM being 1-OCA-proof.

We will use the above lemma and Myerson’s lemma to prove the following key lemma:

Lemma 5.3.

For any single-parameter TFM, UIC and 1-OCA-proof imply zero miner revenue.

Proof 0.

Consider the following quantity, which only differs from $\pi_{\mathbf{b}_{-i}}(r)$ by a constant amount:

\tilde{\pi}_{\mathbf{b}_{-i}}(r)=p_{i}(\mathbf{b}_{-i},r)-\mu(\mathbf{b}_{-i},r)-(p_{i}(\mathbf{b}_{-i},0)-\mu(\mathbf{b}_{-i},0))

This is precisely the currency lost by a contract between user $i$ and the miner by fixing $\mathbf{b}_{-i}$ and changing from $0$ to $b_{i}$ value. Applying Lemma 5.2, we see that

r\cdot(x_{i}(\mathbf{b}_{-i},r^{\prime})-x_{i}(\mathbf{b}_{-i},r))\leq\tilde{\pi}_{\mathbf{b}_{-i}}(r^{\prime})-\tilde{\pi}_{\mathbf{b}_{-i}}(r)\leq r^{\prime}\cdot(x_{i}(\mathbf{b}_{-i},r^{\prime})-x_{i}(\mathbf{b}_{-i},r))

By definition, $\tilde{\pi}_{\mathbf{b}_{-i}}(0)=0$ and because the TFM is UIC and the above expression satisfies the ”payment sandwich” in Lemma 5.1(c), it follows that it must obey Lemma 5.1(d), that is that

\tilde{\pi}_{\mathbf{b}_{-i}}(r)-b_{i}\cdot x_{i}(\mathbf{b}_{-i},b_{i})-\int_{0}^{b_{i}}x_{i}(\mathbf{b}_{-i},t)dt

and because the TFM is UIC, its payment rule must also satisfy

p_{\mathbf{b}_{-i}}(r)-b_{i}\cdot x_{i}(\mathbf{b}_{-i},b_{i})-\int_{0}^{b_{i}}x_{i}(\mathbf{b}_{-i},t)dt

and therefore,

\tilde{\pi}_{\mathbf{b}_{-i}}(r)=p_{i}(\mathbf{b}_{-i},r)-\mu(\mathbf{b}_{-i},r)-(p_{i}(\mathbf{b}_{-i},0)-\mu(\mathbf{b}_{-i},0))=p_{i}(\mathbf{b}_{-i},r)

which further implies that $\mu(\mathbf{b}_{-i},r)=\mu(\mathbf{b}_{-i},0)-p_{i}(\mathbf{b}_{-i},0)$ is a constant when $\mathbf{b}_{-i}$ is held fixed.

To finish off the proof, suppose for the sake of contradiction that there exists a single-paramter TFM that is UIC and 1-OCA-proof and has non-zero miner revenue. Then there exists a bid vector $\mathbf{b}^{(0)}=(b_{1},...,b_{m})$ such that $\mu(\mathbf{b}^{(0)})>0$ . If we consider the sequence of bid vectors constructed such that for $i\in[m]$ , $\mathbf{b}^{(i)}=(0,...,0,b_{i+1},...,b_{m})$ and $\mathbf{b}^{(m)}=0$ . Recall that for a fixed $\mathbf{b}_{-i}$ , we showed that under the current assumptions, $\mu(\mathbf{b}_{-i},\cdot)$ is independent of user $i$ ’s bid. So in our sequence of bid vectors, $\mathbf{b}^{(i)}=\mathbf{b}^{(i-1)}$ and therefore $\mathbf{b}^{(0)}=\mathbf{b}^{(m)}$ . But because user $i$ can only pay at most their bid, $\mu(\mathbf{b}_{i})\leq|\mathbf{b}_{i}^{(m)}|_{1}=0$ , which contradicts our assumption that $\mu(\mathbf{b}^{(0)})>0$ . Thus, by contradiction, a single-parameter TFM that is UIC and 1-OCA-proof and has zero miner revenue.

Now we restrict ourselves to finite block sizes, and use Lemma 5.3 to show our impossibility theorem.

Lemma 5.4.

For randomized single-parameter TFMs with finite block size, 1-OCA-proof and zero miner revenue, the TFM is the trivial mechanism that always pays the miner nothing and never confirms any transactions.

Proof 0.

Let $B$ denote the finite block size. Suppose for the sake of contradiction that there exists a non-trivial TFM $(\mathbf{x},\mathbf{p},\mu)$ that satisfies both UIC and 1-OCA-proof. So there exists a bid vector $\mathbf{b}=(b_{1},...,b_{m})$ and a user $i$ such that $x_{i}(\mathbf{b})>0$ . Now for some positive value $p>0$ , let $N>\frac{B\cdot(b_{i}+p)}{x_{i}(\mathbf{b})\cdot p}$ be some large integer, and consider another bid vector $\mathbf{b}^{\prime}=(b_{1},...,b_{m},b_{m+1},...,b_{m+N})$ where $b_{j}=b_{i}+p$ for all $j\in[m+1,m+N]$ . If this is the real bid vector and each user bids truthfully, then there exists a user $j\in[m+1,m+N]$ who bids $b_{j}$ and is included with probability $\leq\frac{B}{N}<\frac{x_{i}(\mathbf{b})\cdot p}{b_{i}+p}$ .

Now consider some user $j$ . Under the honest mechanism, their joint utility with the miner (who gets 0 revenue by Lemma 5.3) is

\leq b_{j}\frac{B}{N}<b_{j}\frac{x_{i}(\mathbf{b})\cdot p}{b_{i}+p}=x_{i}(\mathbf{b})\cdot p

But if the miner and user $j$ form a contract where user $j$ changes their bid from $b_{j}$ to $b_{i}$ and the miner pretends the real bid vector is $\mathbf{b}$ where $b_{i}$ actually comes from user $j$ , their joint utility is

(v_{j}-b_{i})\cdot x_{i}(\mathbf{b})=p\cdot x_{i}(\mathbf{b})

and therefore 1-OCA-proof is violated. Thus, by contradiction, the TFM must be the trivial mechanism.

The proof of Theorem 5.1 directly follows from Lemma 5.3 and Lemma 5.4. $\square$

6 Weaker Forms of Incentive Compatibility

Perhaps this incompatibility suggests that UIC and 1-OCA-proof are too strong. Short of ensuring zero payoff for users and miners being dishonest, where payoff is the utility increase from deviating compared to being honest, we can aim for the following:

1.

Bound the (worst-case or average) payoff from deviating
2.

Exploit the fact that fake or overbid transactions that are included but not confirmed cannot be retracted in many blockchains and thus run the risk of being confirmed at a later time and thus impose expected cost onto the miner, user, or cartel that proposed them (4.1). Thus, we can try to incorporate this cost into utilities and prove weaker forms of incentive compatibility on these utilities

6.1 Nearly incentive compatible

Towards (1), we extend [6]’s notion of nearly incentive compatible for users to nearly-IC, nearly-MMIC, nearly- $c$ -OCA-proof.

Definition 6.1.

(discount ratio) A user $i$ ’s payoff from deviating can be modeled as their percent savings on payment or discount ratio

\displaystyle\delta_{i}^{discount}(v_{i},\mathbf{b}_{-i})\coloneqq\begin{cases}\frac{p^{t}-p^{*}}{p^{t}}&\text{if }v_{i}\geq p^{*}(\mathbf{b}_{-i})\\ 0&\text{else}\end{cases}

where $p^{*}$ is the minimal price a user can pay to have their bid confirmed and $p^{t}$ is the price a user pays if they bid truthfully. Note that the 0 branch of the function simply formalizes the intuition that payoff can only be nonzero in cases where the user has any chance of getting positive utility. This also aligns with the fact that $0\leq\delta_{i}\leq 1$ .

[6]

Definition 6.2.

(average and max discount ratio) Suppose true values are drawn iid from a distribution $F$ on $\mathbb{R}_{+}$ . Then, the expected payoff for a user deviating assuming all other users are honest can be modeled the average discount ratio

\displaystyle\Delta_{n}^{discount,avg}\coloneqq\mathbf{E}_{\mathbf{v}\sim F}\delta_{1}^{discount}(v_{1},\mathbf{v}_{-1})

where WLOG by symmetry the choice of bidder 1 is arbitrary.

We can also reason about the max discount ratio

\displaystyle\Delta_{n}^{discount,max}\coloneqq\mathbf{E}_{\mathbf{v}\sim F}\max_{j}\delta_{j}^{discount}(v_{j},\mathbf{v}_{-j})

[6] We can adapt these to a generalized notion regarding additive payoff instead of percentage discount on payments that can also be applied to MMIC and OCA-proof and is a bit more natural to interpret being directly in terms of utility.

Definition 6.3.

(strategic payoff) For a user, miner, or cartel with up to $c$ users, their strategic payoff is

\displaystyle\delta(V,\mathbf{b}_{-i})\coloneqq\max\left(u^{*}-u^{t},0\right)

where, $V\subseteq\mathbf{v}$ consists of the values, if any, of the users in the colluding group. (i.e. $\{v_{i}\},\emptyset,\{v_{i_{1}},...,v_{i_{c}}\}$ for a user, a miner, and a cartel of $c$ users, respectively), and utility refers to joint utility, e.g. a sum of possibly $\sum_{v_{j}\in V}v_{j}-p_{j}$ for any users and $r$ for a miner.

Definition 6.4.

(average and max strategic payoff) (ours) With the same assumptions on $F$ and other users as in discount ratio, let the average strategic payoff for a user, miner, or cartel with up to $c$ users be

\displaystyle\Delta_{n}^{avg}\coloneqq\mathbf{E}_{\mathbf{v}\sim F}\delta(V,\mathbf{v}\setminus V),V\coloneqq\{v_{1},...,v_{c}\}

where WLOG by symmetry the choice of set V (up to size for cartels) is arbitrary.

We can also reason about the max strategic payoff

\displaystyle\Delta_{n}^{max}\coloneqq\mathbf{E}_{\mathbf{v}\sim F}\max_{V^{\prime}}\delta(V^{\prime},\mathbf{v}\setminus V^{\prime})

For clarity, we can further superscript these by users, miners, and cartels with up to $c$ users (e.g. $\Delta_{n}^{av,users}$ ,
$\Delta_{n}^{max,\leq c\text{ }cartels}$ ).

Note that as [6] implicitly does, we will assume $p^{t}\geq p^{*}>0$ for all confirmed users.

Generalizing [6] [13]’s analysis on near incentive compatibility for monopolistic auctions (theorem and scenario presented and discussed below 8.3), we can define:

Definition 6.5.

A TFM is nearly UIC if for any $F$ , the average payoff ratio for users satisfies $\Delta_{n}^{avg,users}\to 0$ with $\Delta_{n}^{avg,users}=O(1/n^{\beta})$ for some constant $\beta>0$ independent of $F$ .

The respective expressions using $\Delta_{n}^{avg,users},\Delta_{n}^{avg,\leq c\text{ }cartels}$ give the definitions of nearly MMIC and nearly c-OCA-proof, respectively.

It is also worth noting that this is not the only formulation of approximate incentive compatibility via bounded payoffs (e.g. additive vs. multiplicative). The choice of $O(1/n^{\beta})$ is also somewhat arbitrary, and our notion may be regarded as $1/n^{\beta}$ -near incentive compatibility as a special case of $f(n)$ -near incentive compatibility.

6.2 Weak incentive compatible

Towards (2), following the proof of the above impossibility theorem, [3] introduces the notion of weak incentive compatibility, where unconfirmed transactions are penalized with discount rate $\gamma$ ⁶⁶6One natural perspective on this is that $\gamma$ is the probability of the unconfirmed transaction being confirmed in a future block. We adapt an equivalent version of their definition:

Definition 6.6.

( $\gamma$ -strict utility) Let a player, miner, or cartel’s utility under a strategy be $u$ , which does not include unconfirmed bids. For each unconfirmed bid $i$ let $u_{i}$ be the utility resulting from that bid being confirmed. Note that this may include miner revenue coming from the bid. Then, their $\gamma$ -strict utility is $u+\gamma\sum_{i}\min(u_{i},0)$ for $\gamma\in(0,1]$ .

Definition 6.7.

( $\gamma$ -weak incentive compatibility) For $\gamma\in(0,1]$ , let $\gamma$ -weak UIC be UIC under $\gamma$ -strict utility. Define $\gamma$ -weak MIC, $\gamma$ -weak $c$ -OCA-proof respectively for MIC, $c$ -OCA-proof.

Remark 6.1.

Note that since each additional term is non-positive, $\gamma$ -strict utility $u_{\gamma}$ must satisfy $u^{\prime}\leq u$ , so trivially each incentive compatibility notion implies its $\gamma$ -weak counterpart for all $\gamma\in(0,1]$ . Similarly, $u_{\gamma}$ is monotonically decreasing in $\gamma$ , so in particular the weakest notion of 1-weak utility can be used as a sufficient condition to prove that a TFM is not $\gamma$ -weak incentive compatible for any $\gamma\in(0,1]$ .

6.3 Properties of weak incentive compatible TFMs

It turns out that weak TFM is still rather strong; as a start, satisfying all three notions of weak incentive compatibility already prescribes randomness and unconfirmed transactions as mandatory.

The following notion turns out to be a useful and natural assumption:

Definition 6.8.

A TFM is 2-user-friendly if there exists a bid vector such that it confirms at least two bids [3]

Theorem 6.1.

(Necessity of randomness for weak UIC and 2-weak-OCA-proof) [3] A deterministic and 2-user-friendly TFM with finite block size cannot be both weak UIC and 2-weak-OCA-proof.

Theorem 6.2.

(Necessity of unconfirmed transactions for weak UIC and 1-weak-OCA-proof) [3] A nontrivial (possibly randomized) TFM that always confirms all transactions cannot be both weak UIC and 1-weak-OCA-proof.

We will omit the extensive proofs, but they can be found in [3].

7 Beyond Incentive Compatibility

Beyond incompatibility, we may still be interested in other notions that help us characterize the tradeoffs of a TFM: we give one example here.

In the spirit of 4.4, it is possible that the benefits of reducing fake transactions via MMIC far outweigh those of simple user fees via UIC ⁷⁷7a concrete example might be if we can simpify bidding by providing access to a first-price-auction bidding oracle, but storage space for total transactions is limited, and in particular we want to impose a significant penalty on the miner for any fake transaction included. Since incentive compatibility applies for zero utility, even MMIC and UIC cannot give any guarantees on the magnitude of a protection against fake transactions, and at best imply that a miner or user is not encouraged to do so (but e.g. may very well be able to flood the network with fake transactions without any penalty).

Towards this end, we adapt an equivalent version of Roughgarden’s [11][10] notion of $\gamma$ -costly for punishing fake transactions:

Definition 7.1.

( $\alpha$ -costly) A TFM is $\alpha$ -costly if each confirmed fake transaction decreases its bidder’s utility by at least $\alpha$ .

We usually define this in relation to a $\epsilon$ -costly baseline, e.g. any UIC and MMIC TFM. In doing so, we assume a marginal cost $\epsilon>0$ incurred for all fake transactions, even those leading to no utility penalty. In real-world scenarios, this can be seen as added orphan risk to the miner due to blocks with more data taking longer to propagate. Thus, this notion is usually invoked when a given TFM achieves $\alpha$ -costly with $\alpha\gg\epsilon$ , as we will see with 9.1.

Remark 7.1.

Note that this is thematically distinct from $\gamma$ -strict utility from [3], which concerns quantifying the total utility impact of unconfirmed transactions to relax MMIC. This notion instead quantifies the per-transaction of confirmed (fake) transactions to strengthen MMIC.

8 Classical TFMs

We will use the above incentive compatibility notions and their weaker forms to analyze why classical mechanisms fall short of being good TFMs.

8.1 First-price auction

Algorithm 8.1.

The First-Price Auction mechanism parameterized by the block size $B$ behaves as follows:

1.

I: Include the $B$ highest bids $b_{1}\geq...\geq b_{B}$ , breaking ties arbitrarily. If the block is not full, we treat empty slots as bids of 0.
2.

C: Confirm all bids.
3.

P, R: The $i$ th confirmed bid pays $b_{i}$ to the miner, and unconfirmed bids pay nothing.

Proposition 8.1.

The first-price auction is not UIC, or even 1-weak UIC

Proof 0.

Suppose $v_{1}=10,b_{2}=2,b_{3}=1$ . The first bidder can save at least 7 by bidding e.g. $3$ and still having their bid confirmed. Note that no fake transactions are necessary here so 1-strict utility is the same as regular utility.

Proposition 8.2.

The first-price auction is MMIC

Proof 0.

Since miner revenue is the sum of the bids, it is best response is to truthfully pick the highest ones.

Proposition 8.3.

The first-price auction is OCA

Proof 0.

Consider a cartel of any number of users and the miner. The bids of the users in the cartel do not affect joint utility as their payments go to the miner, so we can arbitrarily set their bids to be their values (i.e. honest). Then, it remains to pick the $B$ bids to include: including a cartel user increases the joint utility by their value and including a non-cartel user increases the joint utility by their bid. Thus, to maximize joint utility the miner should honestly include the top $B$ bids to be confirmed.

8.2 Second-price auction

Algorithm 8.2.

The Second-Price Auction mechanism is parameterized by the block size $B$ . It behaves as follows: (differences from first-price bolded)

1.

I: Include the $B$ highest bids $b_{1}\geq...\geq b_{B}$ , breaking ties arbitrarily. If the block is not full, we treat empty slots as bids of 0.
2.

C: Confirm all bids.
3.

P, R: All confirmed bids pay $\mathbf{b_{B+1}}$ to the miner, and unconfirmed bids pay nothing.

Second-price auctions are famously UIC, but when the auctioneer is untrusted, fall to MMIC and OCA-proof:

Proposition 8.4.

Second-price auctions are not even 1-weak MMIC or 1-weak 1-OCA-proof.

Proof 0.

Suppose $\mathbf{b}=(10,9,8,3),k=3,B=4$ . The miner gets revenue $3(3)=9$ honestly but by injecting a fake bid of $7$ can raise this to $3(7)=21$ . ⁸⁸8Generally, injecting a fake bid between $b_{k},b_{k+1}$ is the dominant strategy Even under 1-strict utility we have $21-7\geq 9$ , so second-price auctions are not 1-weak MMIC.

Similarly, the miner can form a cartel with the fourth bidder to increase their bid to 7, raising their joint utility from $3(3)+0=9$ to $3(7)+0=21$ , and even under 1-strict utility this yields (depending on $v_{4}$ ) $21+\min(7+v_{4}-7,0)\geq 21\geq 9$ , so second-price auctions are not 1-weak 1-OCA-proof.

8.3 Monopolistic auction

Second-price auctions quickly motivate:

Algorithm 8.3.

The Monopolistic Auction mechanism is parameterized by the block size $B$ . It behaves as follows: (differences from second-price bolded)

1.

I: Include the $\mathbf{k^{*}\coloneqq\max_{k}kb_{k}}$ highest bids $b_{1}\geq...\geq b_{k^{*}}$ , breaking ties arbitrarily. If the block is not full, we treat empty slots as bids of 0.
2.

C: Confirm all bids.
3.

P, R: All confirmed bids pay $b_{k^{*}}$ to the miner, and unconfirmed bids pay nothing.

Proposition 8.5.

Monopolistic auctions are not 1-OCA-proof

Proof 0.

Suppose $\mathbf{b}=(10,9,7,3),k=3,B=4$ . The miner gets revenue $3(7)=21$ honestly but by forming a cartel with the third bidder to increase their bid to 8, they can raise their joint utility from $3(7)+v_{3}-7=14+v_{3}$ to $3(8)+v_{3}-8=16+v_{3}$ , which does not change under 1-strict utility.

Although, a result from [13] [6] does give (here stated using their original discount-ratio-based definition) that

Proposition 8.6.

Monopolistic auctions are nearly UIC, satisfying:

1.

For $F$ with bounded support, $\Delta^{discount,max}_{n}\to 0$ and in particular $\Delta^{discount,max}_{n}=O(1/\sqrt{n})$ .
2.

For any $F$ , $\Delta^{discount,avg}_{n}\to 0$ and in particular $\Delta^{discount,avg}_{n}=O(1/\sqrt{n})$ .

When discussing asymptotic bounds, we will allow the constant in $O(\cdot)$ to depend on $F$ .

Proof.

We omit the proof of (1), which can be found in [13], but will prove (2) given (1) to give some intuition on the probabilistic nature of the definition.

Fix a $0<\epsilon<1$ and a distribution $F$ .

First, pick a $D>0$ where $F(D)>1-\epsilon/3$ . Suppose we are sampling $n$ iid $v_{1},...,v_{n}\sim F$ . Let $X_{n}$ be a random variable denoting the number of $v_{i}$ ’s that fall in $[0,D]$ . By the Law of Large numbers, there exists $N_{1}$ where $n\geq N_{1}$ ensures that $\mathbf{P}(X_{n}\leq(1-\epsilon/2)n)<\epsilon/6$ .

Then, let $G$ be $F$ restricted to $[0,D]$ , and we will crucially apply (1) to get $N_{2}$ where $m\geq N_{2}$ ensures $\Delta_{m}^{discount,avg}(G)\leq\Delta_{m}^{max}<\epsilon/3$ .

Now we are ready to prove the result. Pick $n\geq\max(N_{1},N_{2})$ and fix $v_{1},...,v_{n}\sim F$ . It suffices to show that $\Delta_{n}^{discount,avg}(F)\leq\epsilon$ . Recall that $\Delta_{n}^{discount,avg}\in[0,1]$ . Then, we can write

	$\displaystyle\Delta_{n}^{discount,avg}(F)$	$\displaystyle=\mathbf{P}(X_{n}\leq(1-\epsilon/2)n)\Delta_{n}^{discount,avg}(F)+\mathbf{P}(X_{n}>(1-\epsilon/2)n)\Delta_{n}^{discount,avg}(F)$
		$\displaystyle\leq(\epsilon/6)(1)+\sum_{m>(1-\epsilon/2)n}\mathbf{P}(X_{n}=m)[\Delta_{n}^{discount,avg}(F)]$
		$\displaystyle\leq\epsilon/6+\sum_{m>(1-\epsilon/2)n}\mathbf{P}(X_{n}=m)[\frac{m}{n}\Delta_{n}^{discount,avg}(G)+\frac{n-m}{m}(1)]$
		$\displaystyle\leq\epsilon/6+\sum_{m>(1-\epsilon/2)n}\mathbf{P}(X_{n}=m)[(1)(\epsilon/3)+(\epsilon/2)(1)]$
		$\displaystyle\leq\epsilon/6+\epsilon/3+\epsilon/2=\epsilon$

where in step 3 we apply the definition of $\Delta_{n}^{discount,avg}$ , and in step 4 we use the facts that $\frac{m}{n}\leq 1,\frac{n-m}{m}\leq\epsilon/2$ ∎

8.4 Posted-price auction

Algorithm 8.4.

The Posted-Price Auction mechanism is parameterized by the block size $B$ and a posted price $p$ . It behaves as follows:

1.

I: Include any $B$ bids (that equal $p$ ). If the block is not full, we treat empty slots as bids of 0.
2.

C: Confirm all bids (that equal $p$ ).
3.

P, R: All confirmed bids pay $p$ to the miner and unconfirmed bids pay nothing.

Proposition 8.7.

Posted-price auctions are not 1-weak-OCA-proof

Proof 0.

Suppose $p=10,\mathbf{b}=(0,0,0,0),\mathbf{v}=(5,0,0,0)$ . The miner can form a cartel with user 1 and have them bid the posted $10$ , which increases their joint utility from $0$ to $5-10+10=5$ , which does not change under 1-strict utility.

9 Towards Incentive Compatible TFMs

9.1 EIP-1559 mechanism

Now we will examine our first arguably robust mechanism, a combination of posted-price and first-price, which was proposed in [1] and later implemented in the Ethereum mainnet as the successor to the first-price auction, where it now runs.

Algorithm 9.1.

The EIP-1559 Mechanism is parameterized by the block size $B$ and a posted price $p$ . It behaves as follows: (differences from second-price bolded)

1.

I: Include highest $B$ bids $b_{1}\geq...\geq b_{B}\mathbf{\geq p}$ , breaking ties arbitrarily. If the block is not full, we treat empty slots as bids of 0.
2.

C: Confirm all bids. Bids must be $\geq p$ .
3.

P: The $i$ th confirmed bid pays $b_{i}$ , and unconfirmed bids pay nothing.
4.

R: For the $i$ th confirmed bid, the miner gets $\mathbf{b_{i}-p}$ and the remaining $p$ is burned.

Intuitively, $p$ is usually denoted the base fee and the remaining payment $b_{i}-p$ the tip.

Proposition 9.1.

EIP-1559 is MMIC

Proof 0.

The miner’s revenue is exactly the sum of the bids they include, minus a constant $Bp$ , so optimizing revenue is always equivalent to picking the highest bids honestly, and fake transactions are a strict loss of $p$ and never increase utility.

In fact, it explicitly punishes fake transactions:

Proposition 9.2.

EIP-1559 is $(p+\epsilon)$ -costly

Proof 0.

This is easy to see, as any fake transaction incurs at least the posted price $p$ along with $\epsilon$ .

Proposition 9.3.

EIP-1559 is OCA-proof

Proof 0.

Consider a cartel of any number of users and the miner. The bids of the users in the cartel should be below $p$ if their values are below $p$ (as confirming a bid by such a user would contribute negative joint utility) and at least $p$ if their values are at least $p$ so as to be an inclusion candidate. Beyond this, the tips do not matter as they go to the miner, so we can arbitrarily set their bids to be their values (i.e. honest). Then, it remains to pick the $B$ bids to include. Ignoring users with bids below $p$ , including a cartel user $i$ increases the joint utility by $v_{i}-p\geq 0$ , and including a non-cartel user $i$ identically increases the joint utility by their tip $v_{i}-p\geq 0$ . Thus, to maximize joint utility the miner should honestly include the top $B$ bids to be confirmed (for all at least $p$ ).

But in accordance with incompatibility, incentive compatibility must fail somewhere. Here, it fails rather elegantly, not being UIC but lending itself to an obvious bid (as desired under 4.4) except under a specific regime of high demand:

Proposition 9.4.

EIP-1559 is typically UIC-like in the sense that there is a Nash of paying the base fee whenever at most $B$ users have value strictly greater than $p$ . ⁹⁹9Note that [11] actually gives an alternate definition of UIC as there exists a symmetric ex post Nash equilibrium that is best response for users, which does not necessarily have to be honest wrt their value. Under that definition, EIP-1559 is explicitly UIC outside the high demand regime. However, we remark that in the spirit of simplifying fees for users, an honest Nash is in practice very similar to what is usually just a slightly underbid Nash, and further [3] and [11] point out that one can always convert between mechanisms satisfying these two definitions of UIC easily through what is known as the revelation principle.

Proof 0.

We claim that for user $i$ , bidding $min(p,v_{i})$ is a Nash. To see this, under the assumptions and all other users using the same strategy, we can bid the absolute minimum $p$ and be confirmed with the utility $v_{i}-p>0$ since there are not enough users to fill up the block, so this is best response, as bidding more leads to monotonically greater payment and bidding less leads to 0 utility.

Of course, on that regime it completely fails to be UIC.

Proposition 9.5.

EIP-1559 is not 1-weak UIC

Proof 0.

Suppose $p=5,B=3,\mathbf{v}=(16,10,10,10),b_{2}=b_{3}=5$ . The first bidder can save at least 5 by bidding e.g. $11$ and still having their bid confirmed as one of the top three, rather than bidding truthfully ( $b_{1}=16$ ). Note that no fake transactions are necessary here so 1-strict utility is the same as regular utility.

Intuitively, if more than $B$ users have value strictly greater than $p$ , then for all users it is preferable to bid at least $p$ (but less than their value $v_{i}$ ) to have a chance at getting confirmed and achieving nonzero utility. Thus, the situation is closer to a first-price auction where all confirmed users are penalized a flat amount $p$ .

Alternate characterizations of the regime where UIC fails are “low $p$ ” or “high demand,” depending on assumptions on the dynamics of user values and posted prices. Notably, [1] [11] motivate this design in economic terms, where the setting and updating of $p$ attempts to capture current demand, so UIC is seen as mostly valid up to a good setting of $p$ . This leads to various open problems such as (1) optimal ways to set and update $p$ to capture demand based on incoming bids, towards minimizing the failure regime and (2) optimal ways to alleviate the lack of UIC during the failure regime, possibly trading off against other properties.

Related to (2), we note some variations of the EIP-1559 mechanism and results explored by [11] [10], which give us a better sense of the design space and relevant tradeoffs:

Suppose we wanted to capture the value of the burned payments by passing them to the miner as revenue. Unfortunately:

Proposition 9.6.

Passing the burned values to the miner is equivalent to a first-price auction, and is not 1-weak-UIC ever

Proof 0.

The miner and users can essentially take the auction off-chain, where the users communicate their bids off-chain to the miner, and then each user $i$ bids $p$ on-chain and then transfers $b_{i}-p$ off-chain to the miner, resulting in an effective bid of $b_{i}$ paid to the miner. This is the same formulation as the first-price auction above 8.1, and by our previous result is not 1-weak-UIC.

In fact, passing any amount of the payments is meaningless, as this informal note from [11] [10] shows.

Remark 9.1.

Burning a $\alpha$ fraction of the base fee is economically equivalent to having no base fee at all, since in a scenario where originally the base fee would converge to $p*$ , burning a $0<\alpha<1$ fraction of it and passing the rest to the miner as revenue would lead to the base fee converging to $2p^{*}$ , with the unburnt fees redistributed between the mienr and colluding users through an OCA.

Having conceded that full fee burning is needed, we can also motivate the existence of a base fee. Suppose we ran EIP-1559 with $p=0$ , and simply burned all payments in an attempt to preserve incentive-compatibility for the miner. Denote this setup by a fee-burning first-price auction, citing our earlier result that EIP-1559 behaves like a first-price auction on tips, and noting its similarity to the canonical first-price auction 8.1. Sadly:

Proposition 9.7.

Fee-burning first-price auctions are not 1-weak OCA-proof [11] [10]

Proof 0.

The obvious OCA is to move all payments off-chain and conduct a first-price auction with no fee burning. For example, if $v_{1}=10$ the miner can form a cartel with user 1, have them bid and burn 0 and include their transaction, which yields a payoff of 10, e.g. in exchange for an off-chain payment of 5. There is no need for fake transactions so the 1-strict utility is the same as regular utility.

Interestingly, we can trade off UIC in the failure regime:

Algorithm 9.2.

The Tipless EIP-1559 Mechanism is parameterized by the block size $B$ and a posted price $p$ . It behaves as follows: (differences from standard EIP-1559 mechanism in bold)

1.

I: Include highest $B$ bids $b_{1}\geq...\geq b_{B}\mathbf{\geq p}$ , breaking ties arbitrarily. If the block is not full, we treat empty slots as bids of 0.
2.

C: Confirm all bids. Bids must be $\geq p$ .
3.

P: The $i$ th confirmed bid pays $b_{i}$ , and unconfirmed bids pay nothing.
4.

R: For the $i$ th confirmed bid, the miner gets $b_{i}-p$ and the remaining $p$ is burned.

[11][10] shows that analogously to the standard EIP-1559 mechanism:

Proposition 9.8.

Tipless EIP-1559 is MMIC and UIC, but not 1-weak OCA-proof

which effectively allows to trade off UIC against OCA-proofness in the failure regime, depending on what we prioritize in the 4.4 sense. (e.g. simple fees vs. removing centralization vectors).

9.2 Burning second-price auction

We conclude by briefly mentioning a mechanism proposed by [3] specifically to show that three-way $\gamma$ -weak incentive compatibility for any $\gamma\in(0,1]$ is possible. Following their necessity theorems, it indeed uses burning and randomness to achieve this result.

Algorithm 9.3.

The Burning Second-Price Auction mechanism is parametrized by the block size $B$ , a max cartel size $c$ , a discount factor $\gamma\in(0,1]$ , and a number of included bids $k\leq B$ and number of included but unconfirmed bids $k^{\prime}$ satisfying $k^{\prime}=B-k,1\leq k\leq\lfloor\gamma k/c\rfloor$ . It behaves as follows:

1.

I: Include the $B$ highest bids $b_{1}\geq...\geq b_{B}$ , breaking ties arbitrarily. If the block is not full, we treat empty slots as bids of 0.
2.

C: Confirm a random subset of $\lfloor\gamma k/c\rfloor$ included bids with on-chain randomness.
3.

P: All confirmed bids pay $b_{k+1}$ , and unconfirmed bids pay nothing.
4.

R: The miner gets $\gamma(b_{k+1}+...+b_{B})$ , and all remaining payment is burned.

Proposition 9.9.

For any $\gamma\in(0,1]$ , the burning second-price auction is $\gamma$ -weak UIC, $\gamma$ -weak MMIC, and $\gamma$ -weak OCA-proof.

9.3 Summary

We summarize the above results in the following table:

	UIC	MMIC	OCA-proof
First-price		✓	✓
Second-price	✓
Monopolistic	nearly	✓
Posted-price	✓	$\checkmark^{*}$
EIP-1559 (low demand)	$\checkmark^{**}$	$\checkmark^{*}$	✓
EIP-1559 (high demand)		$\checkmark^{*}$	✓
Tipless EIP-1559 (low demand)	$\checkmark^{**}$	$\checkmark^{*}$	✓
Tipless EIP-1559 (high demand)	✓	$\checkmark^{*}$
Burning second-price	weak	weak	weak

Table 1: Comparison of properties of TFMs

* $(\epsilon+\alpha)$ -costly for a constant parameter $\alpha$

** UIC-like, i.e. the paying the base price is a Nash

10 Conclusion and Future Work

The transaction mechanism design problem aims to replace trusted third parties with a coordination game involving incentives. The tasks of coordinating a distributed system, setting prices to match demand and transaction utility, and ultimately allocating assymetrically-valued transactions into vaguely-equal-effort-to-verify blocks thus fall to the users and miners, and by proxy, the mining and mechanism designer who writes those canonical roles for the users and miners to figure out. All of these essentially boil down to figuring out which users’ transactions go where in the ledger and which miner is responsible for verifying each transaction, which motivates the separation of fields that have converged to the mining game and the transaction fee auction respectively.

In analyzing these two sets of problems, we have discovered a menagerie of attacks and misalignments, some of which are provably intractable 5.1. But even under intractability, it is clear that we can make significant progress 9.1 9.2 if we carefully define 6 feasible objectives and analyze 6.3 design elements that can get us there. At the very least, it is clear that intuitive notions of transaction fees mining and mechanism design 2.1 8.1 fall far short of what we can achieve, so formal analysis is both necessary and urgent.

We leave the reader with a few open questions to guide future research, collected broadly from ideas in the literature:

1.

Are the currently investigated undercutting and fee sniping attacks resolved completely by the nLockTime protocol, and if not, what new types of equilibrium behavior arise?
2.

Is $\gamma$ -weak the strongest notion of incentive compatibility under which we can simultaneously achieve some version of UIC, MMIC, and OCA-proofness?
3.

Where is the provable limit for incentive-compatibility exactly: can we prove tighter impossibility bounds (e.g. with properties beyond zero miner revenue) or show examples of TFMs with stronger guarantees?
4.

Can we more precisely characterize the intuition of unconfirmed fake transaction risk as exploited in $\gamma$ -strict utility? Are there more expressive notions of this expectation than a linear sum, e.g. discounted utility horizon, superlinear risk with respect to the size of the transaction?
5.

To what extent is distance-from-equilibrium analysis à la nearly incentive compatible productive? Are the assumptions (fixed distributions, iid values) reasonable under real-world conditions, and if not, is there a better model of weak UIC that provides fee simplicity without requiring honesty? If it is productive, how does this notion compare to weak incentive compatibility under $\gamma$ -strict utility or other corrected utility metrics?
6.

What is the best update rule for the demand proxy (e.g. base fee) in a demand-modeling mechanism such as EIP-1559?
7.

What is the optimal tradeoff surrounding the failure regime of EIP-1559, and how do we mitigate deviations in those conditions? Alternatively, are there ways of minimizing that regime altogether? (this may just mean a better update rule)
8.

How can we tractably reason about mechanisms in their full iterated extent?
9.

Towards (5) in 4.4, can we design mechanisms that allow users more expressivity with respect to their preferences than just a linear sense of value related to being confirmed in this block or not? E.g. can we design a TFM that allows MEV-seeking players to directly pay for transaction ordering without being in the mining role?
10.

Given that burning is provably required for some incentive compatibility notions, are there robust ways of paying value forward to miners without encouraging fake transactions and OCAs?

References

[1] V. Buterin et al. “EIP-1559 specification”, 2021 URL: https://github.com/ethereum/EIPs/blob/master/EIPS/eip-1559.md
[2] Miles Carlsten, Harry Kalodner, S. Weinberg and Arvind Narayanan “On the Instability of Bitcoin Without the Block Reward” In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16 Vienna, Austria: Association for Computing Machinery, 2016, pp. 154–167 DOI: 10.1145/2976749.2978408
[3] Hao Chung and Elaine Shi “Foundations of Transaction Fee Mechanism Design” In CoRR abs/2111.03151, 2021 arXiv: https://arxiv.org/abs/2111.03151
[4] Ittay Eyal and Emin Gün Sirer “Majority is not Enough: Bitcoin Mining is Vulnerable” In CoRR abs/1311.0243, 2013 arXiv: http://arxiv.org/abs/1311.0243
[5] Tiantian Gong, Mohsen Minaei, Wenhai Sun and Aniket Kate “Towards Overcoming the Undercutting Problem” In Financial Cryptography and Data Security Cham: Springer International Publishing, 2022, pp. 444–463
[6] Ron Lavi, Or Sattath and Aviv Zohar “Redesigning Bitcoin’s Fee Market” In ACM Trans. Econ. Comput. 10.1 New York, NY, USA: Association for Computing Machinery, 2022 DOI: 10.1145/3530799
[7] Kevin Liao and Jonathan Katz “Incentivizing Blockchain Forks via Whale Transactions” In Financial Cryptography and Data Security Cham: Springer International Publishing, 2017, pp. 264–279
[8] Roger B. Myerson “Optimal Auction Design” In Mathematics of Operations Research 6.1 INFORMS, 1981, pp. 58–73 URL: http://www.jstor.org/stable/3689266
[9] Satoshi Nakamoto “Bitcoin: A Peer-to-Peer Electronic Cash System” Accessed: 2015-07-01, 2008 URL: https://bitcoin.org/bitcoin.pdf
[10] Tim Roughgarden “Transaction Fee Mechanism Design” In CoRR abs/2106.01340, 2021 arXiv: https://arxiv.org/abs/2106.01340
[11] Tim Roughgarden “Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559” In CoRR abs/2012.00854, 2020 arXiv: https://arxiv.org/abs/2012.00854
[12] Peter Todd “Discourage Fee Sniping with nLockTime” In GitHub repository GitHub, https://github.com/bitcoin/bitcoin/pull/2340, 2013
[13] Andrew Chi-Chih Yao “An Incentive Analysis of some Bitcoin Fee Designs” In CoRR abs/1811.02351, 2018 arXiv: http://arxiv.org/abs/1811.02351