Transaction fee mechanism design

Author: Jagrut Kosti, R&D Team Lead.

In a blockchain protocol, miners or validators include transactions in a block. Some incentive compatibility rules exist, but get little 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 essential to align incentives. This prevents the system from favouring one actor too much. While this article discusses base layer incentives, the requirements can be extended to the application layer as well. In most protocols, there are primarily two 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 many research efforts have focused on defining the needs for a sustainable incentive structure.

We first define the transaction fee mechanism (TFM). Next, we explain the incentive compatibility requirements and state what a good TFM should include. The description and the conclusion are based on two papers mentioned in the reference section.

Transaction fee mechanism

A transaction \(t\) has a 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 up to \(s_t⋅b_t\). A block is an ordered sequence of transactions, and each block has a cap on the number of included transactions called the maximum block size, \(C\) (capacity). A Mempool is a list of outstanding transactions 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 the 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 for pending transactions

The allocation rule is a vector-valued function x from the onchain history \(H\) and mempool \(M\) to a 0-1 value \(x_t(H,M)\) for each pending transaction \(t∈M\).

A value of 1 for \(x_t(H,M)\) indicates that transaction \(t\) is included 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 an 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 for included transactions

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

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

Burning rule for transaction creators

Burning rule is a function \(q\), indicating the amount of money burned by the creator of transaction \(t∈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 currency holders via deflation. An alternative is to redirect a block's revenue to entities other than the block's miner, e.g., a foundation, future miners, etc.

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

Incentive compatibility

Dominant strategy incentive compatible

User's utility function: for a TFM \((x,p,q)\), onchain history \(H\) and mempool \(M\), the utility of the originator of the transaction \(t∈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 DSIC if the miner follows the intended allocation rule. Then, every user has a dominant strategy. This means each user has a bid that always gives the highest benefit, no matter what others bid.

E.g. First Price Auctions (FPA) are not DSIC. An FPA allocation rule, used in Bitcoin and Ethereum, includes a feasible set of transactions that maximizes the total 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)\), onchain 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 miner who cares only about 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 μ is the marginal cost per unit size for a miner. It's the same for all miners and common knowledge.

• The first term is the miner's revenue.
• The second term is the fee burn for miners' fake transactions. It does not include real transactions, as those are paid by the 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=∅\)

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

How offchain agreements coordinate transaction submission and mining

In OCA, each creator of transaction \(t\) agrees to submit \(t\) with an onchain bid \(b_t\). They also transfer \(τ \cdot s_t\) to the miner offchain. The miner agrees to mine a block with the agreed transactions of \(T\).

A TFM is OCA-proof if, for every on-chain history \(H\), there is a bidding strategy \(σ_H\) that is good for each user. For every set \(T\) of transactions and valuations \(v\), no OCA can make both the user's and miner's utility higher than in the outcome \(B)_k=x(H,M(σ_H(v)))\) with onchain bids \(σ_H(v)\) and no offchain transfers.¹

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

Evaluating TFM protocols for DSIC, MMIC, and OCA proofness

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 three properties?

Source 1 conjectures that no non-trivial TFM can satisfy all three properties, and source 2 proves this conjecture. When designing a TFM, it is useful to describe a mechanism that meets different parts and relaxations of these three properties. The goal should be to minimize the effects of a property that is not satisfied or partially satisfied.

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

References

• Roughgarden, Tim. "Transaction fee mechanism design." ACM SIGecom Exchanges 19.1 (2021): 52-55. (Paper)
• 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)