Designing Transaction Fee Mechanisms

​

​

Talk for Collider Ventures, April 2024

​

Aviv Yaish

Final year Phd Student @ Hebrew University

Twitter: @yaish_aviv

Yotam Gafni

Postdoc @ Weizmann

Twitter: @Suflaky

Blockchains

• A decentralized financial transaction system
• Different solutions (PoW, PoS), all involve some form of blocks issued by miners
• Each miner has a probability of winning relative to its share (of compute, stake)
• Users incentivize miners to be included by offering fees (an auction is born)

Transaction Fee Mechanisms

• Formalized in a series of works [Lavi, Sattath & Zohar ‘19], [Roughgarden ’21], [Chung & Shi ‘21], …

​

Modeling assumptions we use:

• Blocksize B of identical goods (and let’s just have B=1…)
• Users have `unit demand’ (want to get one transaction in)

So… it’s just another auction, right?

• Wrong ☺
• Other than the standard IC condition for users, the blockchain settings have special characteristics:
• Possible/desirable to ’burn’ payments
• Anyone can be a miner: Need IC requirements from the miner side
• Miner-user collusion is made easier by committing to side payments

Notions:

• MMIC (Myopic Miner Incentive Compatibility)
• OCA-proof (Off-chain-agreement-proof)
• SCP (Side-channel proof)

​

(on top of the DSIC requirements for user bids)

​

​

​

​

We will spend the first half of the talk on the Myopic case, then move to discuss the Non-Myopic case

Reminder: 1^st and 2^nd price auctions

1st-price auction

2nd-price auction

Highest bidder wins

Pays its own bid

Highest bidder wins

Pays second highest bid

Game Over, Mech Designers?

Posted Prices for the win?

Posted Price

DSIC ✅

MMIC ✅

Arbitrary winner above a set price

Pays set price

​

But…

​

1. How do you set the price?

​

• Collusion?

​

Collusion vs. a Posted Price

Posted Price

DSIC ✅

MMIC ✅

Arbitrary winner above a set price

Pays set price

Let the price be 1.5

Ok, bidder 1, just say you’re willing to pay 1.5, and I’ll cash you back 1

Impossibility results�[Chung & Shi ’22, (Shi, Chung & Wu ’22), Zhao et. al ’22, Gafni & Yaish ‘24, (Chung, Roughgarden & Shi ’24)]

Possibility result [Gafni & Yaish ’22]

• OCA-proof + MMIC + BIC is possible
• It’s the first-price auction! (a.k.a. Bitcoin’s TFM)

​

• Welfare optimal
• Some good revenue guarantees

​

​

​

​

​

​

​

​

​

Possibility result II [WIP Gafni, Ferreira & Resnick]

• Rethink collusion notions
• Posted-prices are actually good?

​

​

​

​

​

​

​

​

Collusion vs. a Posted Price??

Posted Price

DSIC ✅

MMIC ✅

Arbitrary winner above a set price

Pays set price

Let the price be 1.5

Ok, bidder 1, just say you’re willing to pay 1.5, and I’ll cash you back 1

Hold on Mr. Miner:

Wouldn’t everyone ask for a cashback in this case?

Posted-prices – how is the price set?

In words: At each round the current price reacts multiplicatively correlated with previous block size

​

If the block size was larger than target, the price increases, and vice versa

EIP-1559 price mechanism points of interest

• The mechanism only uses block size, not the value of the bids
• Using bid values leads to better convergence and optimal welfare [Ferreira et. Al ‘21]
• But, if it used value data, much more sensitive to manipulation?

​

• Annoying predetermined constants 😒
• What if there is a demand spike or sharp downturn?
• Could lead to chaotic behavior if step-size constants are too large [Leonardos et. Al ‘21]
• But… would still remain close to the target size [Leonardos et. Al ‘22]

​

• Non-myopic Miner attacks with >=20% mining rate [Azouvi et. al ‘23]
• The miner creates fake scarcity to later benefit

​

• [Deng et. Al ‘20] suggest a mix of 2^nd-price and 2^nd -price with reserve instead?

​

​

���- [Leshno, Huberman & Moallemi ‘17] Free entrance of miners creates perfect competition in the market of transaction assignment, where in equilibrium users accurately express their urgency.��- [Nisan ‘23] Monopoly pricing is chaotic even with fixed demand. But user strategic behavior actually helps.��- [Gafni & Yaish ‘22] Prioritizing urgent transactions performs better than greedy assignment under competitive analysis. �� ��

Beyond EIP-1559