Transaction Fee Mechanism Design - Intro

Given a blockchain protocol, where the transactions are included in a block by a miner or validators, there are a few incentive compatibility requirements that do not get much attention. These are:

• Dominant Strategy Incentive Compatible (DSIC)
• Incentive Compatibility for Myopic Miner (MMIC)
• Off-Chain Agreements (OCA)

For a sustainable decentralized ecosystem, it is important to align the incentives so that system isn't biased towards a particular actor at scale. While this article discusses base layer incentives, the requirements can be extended in application layer as well. In most protocols, there are primarily 2 different actors: the ones that maintain the protocol and the ones that use it. They can be further divided based on the architecture, but the collective flow of revenue is between these actors. Not much research efforts have gone into formalizing the requirements for a susitainable incentive structure.

We first formalize transaction fee mechanism (TFM), then define the incentive compatibility requirements and conclude by stating what does a good TFM should consist of. The description and the conclusion are based on 2 papers mentioned in the reference section.

Transaction Fee Mechanism

A transaction $t$ has publicly visible and immutable size $s_t$. The creator of the transaction is responsible for specifying a bid $b_t$ per unit size, publicly indicating to pay upto $s_t \cdot b_t$. A block is an ordered sequence of transactions and each block has a cap on the number of included transactions called maximum block size, $C$ (capacity). A Mempool is a list of outstanding transaction waiting to be included in the block. $M$ is miner's current mempool.

Valuation $v_t$ is the maximum per size value the transaction inclusion in a block for a creator is ($v_t$ is private to the creator) whereas $b_t$ is what they actually pay. Valuation can also be thought of as maximum price for the utility of a transaction to be included in the block.

$H = B_1, B_2, ..., B_{k-1}$ (History) is the sequence of blocks in the current longest chain. $B_1$ being the genesis block and $B_{k-1}$ the most recent block.

Allocation Rule

Allocation rule is a vector-valued function $x$ from the on-chain history $H$ and mempool $M$ to a 0-1 value $x_t(H,M)$ for each pending transaction $t \in M$.

A value of 1 for $x_t(H,M)$ indicates transaction $t$’s inclusion in the current block $B_k$; a value of 0 indicates its exclusion.

$B_k = x(H,M)$ is the set of transactions for which $x_t(H,M) = 1$.

A feasible allocation rule is a set of transactions $T$ such that:

$$\sum_{t \in M} s_t \cdot x_t(H, M) \le C$$

While a allocation rule is defined with some criteria in mind, it is important to note that the miner (block proposer) has the ultimate say over the block it creates.

Payment Rule

Payment rule is a function $p$ from the creator of the included transactions to the miner for each included transaction $t \in B_k$.

$p_t(H, B_k)$ is a non-negative number for each unit size.

Burning Rule

Burning rule is a function $q$, indicating the amount of money burned by the creator of transaction $t \in B_k$.

$q_t(H, B_k)$ is a non-negative number for each unit size.

Burning rule can also be thought of as a refund to the holders of the currency via deflation. An alternative is to redirect a block's revenue to entities other than block's miner e.g. foundation, future miners, etc.

A TFM is a triple $(x, p, q)$ where x is a feasible allocation rule, p is payment rule and q is burning rule.

Incentive Compatibility

Dominant Strategy Incentive Compatible

User's Utility Function

For a TFM $(x, p, q)$, on-chain history $H$ and mempool $M$, the utility of the originator of the transaction $t \notin M$ with valuation $v_t$ and bid $b_t$ is:

$$u_t(b_t) := ( v_t - p_t(H, B_k) - q_t(H, B_k)) \cdot s_t$$

if $t$ is included in $B_k = x(H, M(b_t))$, 0 otherwise.

We assume that a transaction creator bids to maximize the utility function above. A TFM is then DSIC if, assuming that the miner carries out the intended allocation rule, every user (no matter what their value) has a dominant strategy — a bid that always maximizes the user’s utility, no matter what the bids of the other users.

E.g. First Price Auctions (FPA) are not DSIC. An FPA allocation rule (historically Bitcoin, Ethereum) is to include a feasible subset of outstanding transactions that maximizes the sum of the size-weighted bids. A winner then pays the bid if the transaction is included and nothing is burned and all revenue goes to the miner.

Incentive Compatibility for Myopic Miner

Myopic Miner Utility Function

For a TFM $(x, p, q)$, on-chain history $H$, mempool $M$, fake transactions $F$, and choice $B_k \subseteq M \cup F$ of included transactions (real and fake), the utility of a myopic miner (a miner concerned only with the current block) is:

$$u(F, B_k) := \sum_{t \in B_k \cap M} p_t(H, B_k) \cdot s_t - \sum_{t \in B_k \cap F} q_t(H, B_k) \cdot s_t - \mu \sum_{t \in B_k} s_t$$

where $\mu$ is the marginal cost per unit size for a miner. Its the same for all miners and a common knowledge.

• The first term is the miner's revenue
• The second term is the fee burn for miner's fake transactions. It does not include real transactions as that is paid by transaction's creators.
• The third term is the total marginal cost

A TFM is then MMIC, if a myopic miner maximizes its utility by creating no fake transactions i.e. setting$F = \emptyset$

E.g. FPAs are MMIC as the miner's best choice is to include all max bid transactions and including fake transactions does not increase any utility. Second-price type auctions, on the other hand, are not MMIC since a miner can include fake transactions to boost the max bid.

Off-chain Agreements

In OCA, each creator of transaction $t$ agrees to submit $t$ with on-chain bid $b_t$ while transferring $\tau \cdot s_t$ to the miner off-chain; the miner in turn agrees to mine a block comprising the agreed upon transactions of $T$.

A TFM is OCA-proof if, for every on-chain history $H$, there exists an individually rational bidding strategy $\sigma_H$ such that, for every possible set $T$ of outstanding transactions and valuations $v$, there is no OCA under which the user's utility of every transaction and the miner's utility is strictly higher than in the outcome $B_k = x(H,M(\sigma_H(v)))$ with on-chain bids $\sigma_H(v)$ and no off-chain transfers.

E.g. FPAs are OCA-proof whereas the TFMs where any amount of revenue is burned are not.

Conclusion

The article gives a brief overview of the formalization in TFM design. For a sustainable protocol, it is important that the TFM is DSIC, MMIC and OCA-proof. Based on this, the obvious question is: Is there any TFM that satisfies all 3 properties?

[1] conjectures that no non-trivial TFM can satisfy all 3 properties and [2] proves this conjecture. For designing a TFM, we can generally say that it would be interesting to characterize a mechanism that satisfy various subsets and relaxations of these 3 properties. The goal should be to minimize the effects of a property that is not satisfied or partially satisfied.

I highly recommend interested users to read [1] & [2].

References

1. Roughgarden, Tim. "Transaction fee mechanism design." ACM SIGecom Exchanges 19.1 (2021): 52-55. (Paper)
2. Chung, Hao, and Elaine Shi. "Foundations of transaction fee mechanism design." Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023. (Paper)