Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms

Our work contributes to the rapidly-expanding literature on transaction fee mechanism design and more broadly, on game-theoretic applications to decentralized platforms. While Lavi, Sattath and Zohar [28], Basu et al. [6] and Yao [35] were amongst the first to view inclusion of transactions in a block as a mechanism design problem, a research agenda around TFMs started building after Roughgarden [31, 32] established basic desiderata that a “good” TFM must satisfy, and analyzed EIP-1559, the TFM adopted by Ethereum, through the lens of these desiderata. However, Chunag and Shi [10] argue that simultaneously satisfying the three properties proposed by Roughgarden [31] – truthfulness for users and the miner and collusion-resistance – is impossible for any non-trivial mechanism that ever allocates some user with a positive probability. Various notions of collusion-resistance have been considered [10, 15] while Gafni and Yaish [19] and Chung, Roughgarden and Shi [9] investigate the relationship between these collusion-resistance desiderata. Further work has also considered relaxing the concept of truthfulness for users from DSIC to BIC [18, 7]. Shi, Chung and Wu [33, 34] consider expanding the space of TFMs by arming the mechanism with cryptography. While all the aforementioned works treat TFMs as single-shot mechanisms, [16, 4, 1] investigate the long-term dynamics of the repeated game that arises from running the TFM in every block. Bahrani, Garimidi and Roughgarden [5] are the first to revisit the desiderata for TFMs in blockchains with MEV.

Beyond TFMs, a wide body of literature has been growing around economic design in blockchains, starting with Babaioff et al. [3] and Eyal and Sirer [14]. More recent works range from designing credible auctions via cryptography [17, 13, 8, 22, 11] and persuasion mediated via blockchains [12]. There has also been growing literature on cryptographic and consensus protocols in the presence of rational agents [23], [26], [2], [25], [24], [27].

Our paper is a follow-up to Ganesh, Thomas and Weinberg [21], which define off-chain influence-proofness (OffC-IP). They construct a cryptographic OffC-IP and on-chain simple (OnC-S) TFM based on a second price auction, and prove that OffC-IP and OnC-S are incompatible with strong notions of collusion-proofness considered in previous papers. Besides fully characterizing the allocation and burn rules of any OffC-IP mechanism, the present paper advances beyond the results of Ganesh, Thomas and Weinberg [21] by (1) uncovering plaintext OffC-IP and OnC-S TFMs, thus removing the strong use of cryptography, and (2) providing formal impossibility results regarding OffC-IP and OnC-S TFMs (regardless of whether the TFM is collusion-proof).

After giving preliminaries, our paper proceeds along the lines of our two main contributions as follows:

1. 1.

   First, we characterize the allocation and burn rule of any OffC-IP TFM: they are exactly those satisfying the burn identity we define in Theorem 11.

   • $\mathrm{■}$

     Section 3 first provides a much-simpler warm-up by characterizing the burn rule of OffC-IP posted-price TFMs.

   • $\mathrm{■}$

     Section 4 presents the burn identity for general mechanisms.

2. 2.

   Second, we examine settings under which OffC-IP and OnC-S TFMs exist, and show that posted-price mechanisms are the only deterministic plaintext OffC-IP and OnC-S TFMs.

   • $\mathrm{■}$

     In Section 5, we consider prior-independent TFMs, and show that in order to be OffC-IP and OnC-S, such TFMs require both cryptography and miner-advice (as leveraged by Ganesh, Thomas and Weinberg [21] to construct such a TFM).

   • $\mathrm{■}$

     Motivated by the above, in Section 6 we consider prior-dependent mechanisms. We prove our second main result in Theorem 17: that deterministic OffC-IP and OnC-S TFMs must necessarily be the posted-price mechanisms of Section 3. Then we examine various implications and limitations of this result.

     • –

       In particular, Corollary 21 observes that deterministic OffC-IP and OnC-S TFMs thus require infinite supply, i.e., they do not exist with finite capacity.

     • –

       In contrast, Subsection 6.3 shows that there exist randomized OffC-IP and OnC-S TFMs with finite supply, so long as the prior distribution of values is bounded.

As a first step towards deriving the burn identity, we re-interpret the revenue optimization problem faced by the miner in the off-chain game in terms of the equilibrium burn and the virtual values of the allocated users.

For a revenue optimal equilibrium ${\sigma }^{𝒟}$ and a corresponding mechanism ${ℳ}_{\mathrm{𝗈𝖿𝖿}}$ in the off-chain game, we can apply the revelation principle to ${\sigma }^{𝒟}$ to unpack the underlying truth-telling mechanism. We say that the truth-telling mechanism $(\overline{X},\overline{P},\overline{B})$ corresponding to a revenue optimal equilibrium ${\sigma }^{𝒟}$ is Myerson-in-Range.

It immediately follows from the definition that an off-chain equilibrium ${\sigma }^{𝒟}$ with a trivial off-chain component is off-chain influence proof if and only if the corresponding direct-revelation mechanism is Myerson-in-Range.

It is notationally cumbersome to keep mentioning that the mechanism and the corresponding equilibrium satisfies some property (for eg. off-chain influence proofness). We abuse notation to instead say that the corresponding direct-revelation mechanism $(\overline{X},\overline{P},\overline{B})$ satisfies the same property.

In the remainder of this section, we characterize all Myerson-in-Range mechanisms for a given block-building process $ℬ$. We argue that the direct-revelation mechanism $(\overline{X},\overline{P},\overline{B})$ is Myerson-in-Range if and only if it optimizes the miner’s expected virtual utility – the difference between her expected virtual surplus ${𝔼}_{\overrightarrow{v}\sim {𝒯}^n}\left[{\sum }_{i=1}^n\phi (v_i)\overline{X}(\overrightarrow{v})\right]$ and the burn ${𝔼}_{\overrightarrow{v}\sim {𝒯}^n}\left[\overline{B}(\overrightarrow{v})\right]$ – for all $n\in \mathbb{N}$. In detail, for an equilibrium ${\sigma }^{𝒟}$ in the off-chain game with a corresponding direct-revelation mechanism $(\overline{X},\overline{P},\overline{B})$, the miner’s net expected revenue equals ${𝔼}_{\overrightarrow{v}\sim {𝒯}^n}\left[{\sum }_{i=1}^n{\overline{P}}_i(\overrightarrow{v})-\overline{B}(\overrightarrow{v})\right].$ Since $\overline{P}$ is the value payment rule of a BNE, we can apply Myerson’s lemma [29] to replace the expected payments by the expected virtual surplus in the expected net revenue. In other words, we can pretend that the miner receives a surplus equal to ${\sum }_{i=1}^n\phi (v_i){\overline{X}}_i(\overrightarrow{v})$ upon allocating users with values $\overrightarrow{v}$, but is charged $\overline{B}(\overrightarrow{v})$ via burns. Therefore, the miner optimizes her expected virtual utility ${𝔼}_{\overrightarrow{v}\sim {𝒯}^n}\left[{\sum }_{i=1}^n\phi (v_i)\overline{X}(\overrightarrow{v})-\overline{B}(\overrightarrow{v})\right]$ over all possible BNE ${\sigma }^{𝒟}$ in the off-chain game.

In fact, for a regular distribution $𝒯$, the miner can pointwise optimize her virtual utility for $\overrightarrow{v}\sim {𝒯}^n$. The value allocation and burn rules $(\overline{X},\overline{B})$ can take any value from the set of all feasible outcomes ${ℱ}_{ℬ}$ of $ℬ=(X,P,\mathrm{𝖡𝗎𝗋𝗇})$, i.e,

For any allocation rule $\overline{X}$ supported on ${ℱ}_{ℬ}$, by Myerson’s payment identity, $\overline{X}$ is the value allocation rule of some BNE ${\sigma }^{𝒟}$ if and only if ${\overline{X}}_i$ is monotone non-decreasing in $v_i$ for all $1\le i\le n$ (${\overline{X}}_i$ is the allocation rule for user $i$). For a regular distribution $𝒯$, it is fairly straightforward to see that there exists

that is monotone non-decreasing in user values. For that matter, any variant of $(\overline{X},\overline{B})$ that is monotone, and pointwise optimizes for the virtual utility except with probability zero constitutes a Myerson-in-Range mechanism $(\overline{X},\overline{P},\overline{B})$ for a suitably chosen value payment rule $\overline{P}$. The miner’s expected virtual utility is maximized even if there exists a set of value profiles with a probability measure zero for which the virtual utility optimal outcome is not implemented on-chain.

We summarize our discussion in the theorem below.

In our second step towards obtaining the burn identity, we will identify three intuitive properties satisfied by Myerson-in-Range mechanisms.

The first property (labeled optimal for $n$ users) is an immediate special case of our characterization of Myerson-in-Range mechanisms. While Theorem 5 suggests that $\overline{X}(\overrightarrow{v})$ pointwise optimizes ${\sum }_{i=1}^n\phi (v_i)X-B$ almost everywhere for $(X,B)\in {ℱ}_{ℬ}$, the first condition specifically observes that $\phi (\overrightarrow{v})\overline{X}(\overrightarrow{v})-\overline{B}(\overrightarrow{v})\ge \phi (\overrightarrow{v})\overline{X}(\overrightarrow{w})-\overline{B}(\overrightarrow{w})$ with probability $1$ for $\overrightarrow{v}\sim {𝒯}^n$ and all $\overrightarrow{w}\in \mathrm{𝗌𝗎𝗉𝗉}({𝒯}^n)$.

The second property (labeled Negative $\phi$’s are suboptimal) observes that including users with value below the monopoly reserve is suboptimal for a virtual utility maximizing miner. Suppose an allocation rule includes users with a negative virtual value with probability greater than zero. Then, the miner can increase her virtual utility by first censoring such a user’s bid and fabricating an identical bid of her own. Since the same set of bids are submitted to the anonymous TFM, except for un-allocating the user with the negative virtual value, all other users are allocated the same and the burn remains unchanged too, thereby increasing the miner’s expected virtual utility.

Finally, the third property (labeled No censoring or fabricating) connects the allocation rule for $n$ users with the allocation rule for $\widehat{n}$ users. It suggests that the miner’s virtual utility should remain invariant to censoring or fabricating bids with a non-positive virtual value.

We defer the proof of Theorem 6 to the full version. For the remainder of our discussions, we solely focus on the class of regular distributions $𝒯$ meeting the requirements of Theorem 6, i.e., having a continuous virtual value function and a positive probability of a random draw having a non-positive virtual value. Most natural distributions such as the uniform distribution, the normal distribution and the exponential distribution satisfy this condition. We say that a distribution is smooth if it satisfies the requirements from Theorem 6.

In this section, we derive a closed-form expression for the burn rule of a Myerson-in-Range mechanism. At a high level, we will reduce calculating the burn rule of a Myerson-in-Range mechanism to computing equilibrium payments in multi-item single-buyer environments.

We show that the virtual utility maximization problem faced by the miner is similar to the utility maximization problem faced by a monopsonist in multi-item settings. In Theorem 5, we argued that a Bayesian miner chooses an outcome from the menu of user allocation probabilities and burns specified by ${ℱ}_{ℬ}$ in the off-chain game to optimize her virtual utility. In other words, the miner “buys” an outcome supported by ${ℱ}_{ℬ}$ by making a “payment” equal to the burn corresponding to the outcome. In return, she derives a “surplus” equal to the virtual surplus of the allocation. Concretely, the items in the multi-item single-buyer environment are analogous to users in the TFM environment and the monopsonist’s values for the items correspond to the virtual values of the users and are drawn iid from ${𝒯}^{\phi }$, the distribution of virtual values when the value is drawn from $𝒯$.

From the reduction discussed above, computing the equilibrium allocation and burn of a Myerson-in-Range mechanism corresponds to computing the equilibrium allocation and payments in the analogous multi-item single-buyer environment. Since we apply the revelation principle in the TFM environment, the value allocation and burn rules $(\overline{X},\overline{B})$ will correspond to DSIC mechanisms for the monopsonist. However, there are some subtle differences between the two settings. In the multi-item single-buyer environment, the monopsonist should be disincentivized to deviate from truth-telling for all value profiles over the items. However, in the TFM environment, an off-chain equilibrium and the corresponding direct-revelation mechanism is Myerson-in-Range even if the miner would like to deviate from the equilibrium behaviour with probability zero. We will address the discrepancy in the definitions between the two environments by arguing that the allocation and the burn rules of a Myerson-in-Range mechanism can be smoothened over some measure zero collection of value profiles so that the miner pointwise optimizes her virtual utility for all value profiles $\overrightarrow{v}$ in the smoothened mechanism.¹¹¹¹11Note that the smoothened mechanism might not necessarily be feasible, i.e, be supported over ${ℱ}_{ℬ}$. However, we will use the smoothened mechanism to derive a burn identity which holds almost surely for the original mechanism.

We will say that such a pair $(\tilde{X},\tilde{B})$ is a monopsonist smoothening of $(\overline{X},\overline{B})$.

We defer the proof of Theorem 7 to the full version.

The monopsonist smoothening enables the application of results from existing literature on multi-item auctions to transaction fee mechanism design. For instance, for a given utility function $U(\overrightarrow{v})$ mapping the buyer’s value profile to her utility¹²¹²12Such a utility function can be derived even for non-truth-telling equilibria via the revelation principle (see Rochet , [30], for example)., Rochet [30] argues that the allocation rule and payment rule of the DSIC mechanism that induces the utility function $U$ is essentially unique.

Note that when $U$ is convex, $\nabla U$ is defined almost everywhere, and the allocation and payment rules $\overline{X}$ and $\overline{P}$ are uniquely defined at all such points with a well-defined gradient. At values where $\nabla U$ is not well-defined, setting $\overline{X}$ to be any sub-derivative of $U$ satisfies dominant-strategy incentive compatibility.

Applying Theorem 7 in conjunction with Theorem 9 for a virtual utility optimizing miner yields the following.

We say that the function $U$ is the smoothened virtual utility function of the mechanism $(\overline{X},\overline{P},\overline{B})$.

Corollary 10 expresses condition A from Theorem 6 in terms of the smoothened virtual utility. We can also similarly rewrite conditions B and C. Condition B states that the mechanism should almost never allocate a user with a virtual value smaller than zero. Thus, the gradient ${\nabla }_i^{\phi }U(\phi (\overrightarrow{v}))={\overline{X}}_i(\overrightarrow{v})=0$ almost surely whenever . Since $U$ is convex in $\phi (\overrightarrow{v})$, ${\nabla }_i^{\phi }U(\phi (\overrightarrow{v}))$ is increasing in $\phi (\overrightarrow{v})$ and thus, ${\nabla }_i^{\phi }U(\phi (\overrightarrow{v}))=0$ for all $v_i$ with a strictly negative virtual value.

Condition C suggests that fabricating or censoring a bid with a non-positive virtual value should almost never change the miner’s virtual utility. Thus, for value profiles $\overrightarrow{v}=(v_1,\mathrm{\dots },v_n,v_{n+1},\mathrm{\dots },v_{n+t})$ and $\overrightarrow{w}=(v_1,\mathrm{\dots },v_n)$ such that $\phi (v_{n+i})\le 0$ for all $1\le i\le t$, the smoothened virtual utility function at $\overrightarrow{v}$ and $\overrightarrow{w}$ must satisfy $U(\overrightarrow{v})=U(\overrightarrow{w})$.

We summarize the discussions above to state the burn identity.

Finally, we will combine the burn identity with Myerson’s payment identity to derive a DSIC payment rule in terms of the smoothened virtual utility function. From the payment identity,

The smoothened virtual utility function determines the allocation rule everywhere except at a measure zero set of points. Further, since the distribution $𝒯$ is regular, all points between the infimum and supremum of $\mathrm{𝗌𝗎𝗉𝗉}(𝒯)$ have a positive probability density and as a consequence, even when $\overline{X}$ differs from ${\nabla }^{\phi }U$ at a measure zero set of points, ${\int }_0^{v_i}{\overline{X}}_i(\upsilon ,{\overrightarrow{v}}_{-i})𝑑\upsilon ={\int }_0^{v_i}{\nabla }_i^{\phi }U(\phi (\upsilon ),\phi ({\overrightarrow{v}}_{-i}))𝑑\upsilon$, almost everywhere. Thus, the payment rule of a Myerson-in-Range mechanism with a smoothened utility function $U$ equals

with probability $1$.

To conclude our discussion on Myerson-in-Range mechanisms, by Lemma 4, observe that a direct-revelation mechanism is off-chain influence proof only if it has a trivial off-chain component and its burn rule satisfies the burn identity.

The reduction from TFMs to multi-item auctions characterizing off-chain influence proof mechanisms can be extended to also characterize global strong collusion proof mechanisms. In the full version, we use our characterization to design a mechanism that is on-chain simple and global strong collusion proof which yields a positive revenue to the miner.¹³¹³13[9, 19] show that no such deterministic mechanism exists that yields positive miner revenue. We construct a randomized mechanism with positive miner revenue. Our mechanism applies for both infinite and bounded block size, although for a finite block, our mechanism requires the prior distribution to have a known upper bound (and it remains an open question whether such mechanisms exist without a known upper bound).

Before constructing simple-to-participate mechanisms, it would be useful to have a sufficient condition that ensures that a candidate mechanism $(\overline{X},\overline{P},\overline{B})$ is indeed on-chain user simple and off-chain influence proof. We will begin with such a sufficient condition very similar to the three properties in Theorem 6.

The three properties in Theorem 6 do not characterize Myerson-in-Range mechanisms due to the following reason – the three conditions do not automatically guarantee that, for some block-building process $ℬ=(X,P,\mathrm{𝖡𝗎𝗋𝗇})$, $\phi (\overrightarrow{v})\overline{X}(\overrightarrow{v})-\overline{B}(\overrightarrow{v})\ge \phi (\overrightarrow{v})X-B$ for all $(X,B)\in {ℱ}_{ℬ}$. It only ensures that $\phi (\overrightarrow{v})\overline{X}(\overrightarrow{v})-\overline{B}(\overrightarrow{v})\ge \phi (\overrightarrow{v})X-B$ for $(X,B)=(\overline{X}(\overrightarrow{w}),\overline{B}(\overrightarrow{w}))$ for some value profile $\overrightarrow{w}$. However, suppose that the mechanism is on-chain user simple and $(\overline{X}(\overrightarrow{v}),\overline{P}(\overrightarrow{v}),\overline{B}(\overrightarrow{v}))=(X(\overrightarrow{v}),P(\overrightarrow{v}),\mathrm{𝖡𝗎𝗋𝗇}(\overrightarrow{v}))$ for all $\overrightarrow{v}$.¹⁶¹⁶16Remember that the mechanism is prior-dependent and we are assuming that the miner does not submit any advice to the block-building process $(X,P,\mathrm{𝖡𝗎𝗋𝗇})$. Thus, $X$, $P$ and $\mathrm{𝖡𝗎𝗋𝗇}$ take as input a profile of bids and output the allocations, payments and the burn respectively. Then, $\phi (\overrightarrow{v})\overline{X}(\overrightarrow{v})-\overline{B}(\overrightarrow{v})\ge \phi (\overrightarrow{v})X-B$ for all $(X,B)\in {ℱ}_{ℬ}$. In this section, we argue ensuring that the direct-revelation mechanism realizes all feasible outcomes in ${ℱ}_{ℬ}$, along with the three conditions from Theorem 6, is sufficient for the mechanism to be Myerson-in-Range.

We defer the proof to the full version.

Note that the direct-revelation mechanism $(\overline{X},\overline{P},\overline{B})$ satisfying the requirements in Lemma 15 is on-chain user simple and off-chain influence proof. For on-chain user simplicity, observe that the block-building process takes in bids and already implements the payment rule corresponding to the DSIC direct-revelation mechanism. For off-chain influence proofness, once again, equilibrium payments are charged from the users by the payment rule $P=\overline{P}$ on-chain, and thus, the miner will not have to make any extraneous off-chain transfers to steer users towards the underlying BNE. Thus, the Myerson-in-Range mechanism $(\overline{X},\overline{P},\overline{B})$ has a trivial off-chain component and by Lemma 4, the mechanism is off-chain influence proof.

Remember that the payment identity in the multi-item environment (Theorem 9) is both necessary and sufficient for a mechanism to be DSIC for a monopsonist. Applying Theorem 9 for a virtual utility maximizing miner, we get a partial converse to Theorem 11.

In this section, we argue that the only deterministic plain-text mechanism that is simple to participate is the class of all uniform posted-price mechanisms.¹⁷¹⁷17Remember that, by definition, we require our TFMs to be anonymous. Strictly speaking, a deterministic, anonymous, virtual utility maximizing mechanism is not possible for a block with a finite capacity. For example, for a block of capacity $1$, if there are two users with equal values, both larger than the monopoly reserve, the mechanism either has to randomize or has to break ties in the favour of one bidder. However, we will consider mechanisms that are deterministic and anonymous up to tie-breaking. Our impossibility results are agnostic to how ties are broken, and do not rely on the edge-cases requiring tie-breaking.

As a first step towards proving Theorem 17, we will show that a deterministic off-chain influence proof mechanism has a simple burn rule parametrized only by the number of users included in the block. Concretely, we will argue that there exists a sequence of burns ${\left({\mathrm{\Phi }}_t\right)}_{t\in \mathbb{N}}$ such that ${\mathrm{\Phi }}_t$ is burnt whenever the miner builds a block containing $t$ users. As a sanity check, note that the block reward equals the net revenue from building an empty block, which in turn equals $-{\mathrm{\Phi }}_0$.

We defer the proof to the full version.

For the remainder of the section, we will show that ${\mathrm{\Phi }}_t=t({\mathrm{\Phi }}_1-{\mathrm{\Phi }}_0)+\mathrm{\Phi }$ for simple-to-participate deterministic mechanisms. In other words, the marginal burn $\mathrm{\Delta }{\mathrm{\Phi }}_t:={\mathrm{\Phi }}_t-{\mathrm{\Phi }}_{t-1}$, i.e, the burn for including the $t$^th user conditioned on including $t-1$ users, must be a constant $\mathrm{\Delta }\mathrm{\Phi }$. Proving a constant marginal burn will conclude the proof of Theorem 17 for $\phi (p)=\mathrm{\Delta }\mathrm{\Phi }$ and $p={\phi }^{-1}(\mathrm{\Delta }\mathrm{\Phi })$.

To show that the marginal burn $\mathrm{\Delta }{\mathrm{\Phi }}_t$ is a constant, we will first argue that the marginal burn is non-increasing in $t$ (Lemma 19), and then, for a non-increasing sequence ${\left(\mathrm{\Delta }{\mathrm{\Phi }}_t\right)}_{t\in \mathbb{N}}$, we will show that they cannot decrease either (Lemma 20).