Skip to main content

One post tagged with "incentive-mechanism"

View All Tags

Jagrut Kosti

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 tt has publicly visible and immutable size sts_t. The creator of the transaction is responsible for specifying a bid btb_t per unit size, publicly indicating to pay upto stbts_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, CC (capacity). A Mempool is a list of outstanding transaction waiting to be included in the block. MM is miner's current mempool.

Valuation vtv_t is the maximum per size value the transaction inclusion in a block for a creator is (vtv_t is private to the creator) whereas btb_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=B1,B2,...,Bk1H = B_1, B_2, ..., B_{k-1} (History) is the sequence of blocks in the current longest chain. B1B_1 being the genesis block and Bk1B_{k-1} the most recent block.

Allocation Rule

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

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

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

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

tMstxt(H,M)C\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 pp from the creator of the included transactions to the miner for each included transaction tBkt \in B_k.

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

Burning Rule

Burning rule is a function qq, indicating the amount of money burned by the creator of transaction tBkt \in B_k.

qt(H,Bk)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)(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)(x, p, q), on-chain history HH and mempool MM, the utility of the originator of the transaction tMt \notin M with valuation vtv_t and bid btb_t is:

ut(bt):=(vtpt(H,Bk)qt(H,Bk))stu_t(b_t) := ( v_t - p_t(H, B_k) - q_t(H, B_k)) \cdot s_t

if tt is included in Bk=x(H,M(bt))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)(x, p, q), on-chain history HH, mempool MM, fake transactions FF, and choice BkMFB_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,Bk):=tBkMpt(H,Bk)sttBkFqt(H,Bk)stμtBkstu(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. settingF=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 tt agrees to submit tt with on-chain bid btb_t while transferring τst\tau \cdot s_t to the miner off-chain; the miner in turn agrees to mine a block comprising the agreed upon transactions of TT.

A TFM is OCA-proof if, for every on-chain history HH, there exists an individually rational bidding strategy σH\sigma_H such that, for every possible set TT of outstanding transactions and valuations vv, 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 Bk=x(H,M(σH(v)))B_k = x(H,M(\sigma_H(v))) with on-chain bids σH(v)\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)