Recent Developments in �Transaction Fee Mechanisms

​

​

Mathematical Foundations of the Internet and Blockchain Economics Workshop,

TSIMF, Sanya

January 2024

​

Yotam Gafni

Weizmann Institute

Aviv Yaish

Yale University

Matheus V. X. Ferreira

University of Virginia

Max Resnick

Special Mechanisms Group

Transaction Fees

• Blockchain throughput is limited
• Demand > supply in popular blockchains
• Goal 1: allocate block-space efficiently

Block

TX

TX

TX

Max size:

2 TXs

Pending TXs

Date

Transaction Fee Mechanisms

• Formalized in [Lavi, Sattath & Zohar ‘19], [Yao ‘18], [Roughgarden ’21], [Chung & Shi ‘21], ...

​

Modeling assumptions we use:

• Blocksize B identical goods
• Users have `unit demand’ (want to get one transaction in)
• Static setting (one block)

​

A big driving force: Ethereum’s EIP-1559, redesigning Bitcoin’s pay-as-bid

Robust Auction Design

“The most important features of an auction are its robustness against collusion and its attractiveness to potential bidders. Failure to attend to these issues can lead to disaster.“

[Paul Klemperer, “What Really Matters in Auction Design” 2002]

​

”The FCC and others conducting similar auctions should think carefully about the tradeoff between more informed price discovery and the risk of collusive bidding.”

[Cramton & Schwarz,

“Collusive Bidding: Lessons from the FCC Spectrum Auctions” 2000]

​

TFMs ~= Robust Auction Design

• 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, and by the centrality of the miner in e.g. Ethereum Proof of Stake

Popular Notions:

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

​

(on top of the DSIC requirements for truthful user bids)

​

​

​

​

OCA-proof definition [Roughgarden ‘21]

• An auction is OCA-proof if a coalition of the miner and bidders cannot increase its aggregate utility to be higher than the joint utility of the intended allocation.

​

Miner

Bidder1

Bidder2

Bidder3

Allocated

Example of OCA:�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

(For Blockchain-oriented folks,

think about the tipless version of

EIP-1559, if there was no burn)

A caveat before we start - Impossibility results for TFMs�[Chung & Shi ’22, Shi, Chung & Wu ’22, Zhao et. al ’22]

A brief history of collusion notions

• Focus on user-user collusion (Green & Laffont ‘79, Chen & Micali ‘11, Leyton-Brown, Shoham & Tennenholtz ‘00, Goldberg & Hartline ‘05)
• Core-selecting Auctions (Ausubel & Milgrom ‘02, Day & Milgrom ’08, Goeree & Lien ‘16)
• Many works consider a Bayesian / Stackelberg model, where colluders can signal each other, or punish non-colluders (Che & Kim ‘09, Rachmilevitz ‘14)
• Bargaining among the colluders (McAfee & McMillan ‘92)
• Trust between the colluders? (Stigler ‘64) More on that later…

​

• OCA is a miner-user collusion notion, that assumes trust, takes an axomiatic form, and is agnostic of bargaining

​

​

​

​

​

​

​

​

​

​

How do Deterministic OCA Mechanisms Look?�[Gafni & Yaish MARBLE’24]

0

1

2

3

…

b1

b2

b3

b4

# of allocated transactions

Good Revenue with Deterministic DSIC+OCA?�[Gafni & Yaish MARBLE’24]

Deterministic DSIC+OCA Mechanisms�[Gafni & Yaish, in Revision, extending EC’24 version]

Definition of MMIC (Miner-incentive compatibility)�[Lavi, Sattath & Zohar ‘17]

• The miner can not gain by removing bidders
• The miner can not gain by adding fake bidders

​

• For example, the second-price auction is not MMIC

Deterministic MMIC+OCA Mechanisms�[Gafni & Yaish, in Revision, extending EC’24 version]

• Consider the class of OCA mechanisms
• Unlike the DSIC case, any burn rule is implementable
• The payment is MMIC if and only if all the conditions hold:
• Miner utility is agnostic to losing bids,
• Miner utility is weakly monotone decreasing w.r.t. removing a winning bid
• Payment of all winning bidders but one, does not exceed the counterfactual sum of payments if we remove that bidder, by too much... (full details in text)

​

All these conditions hold for pay-as-bid payments, and many other variations of it.

“Bitcoin’s TFM is not that bad”

​

​

As for [Roughgarden ‘21] conjecture,

Randomized Barriers… or Impossibility?

Part 2: Rethinking Collusion-Resistence

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?

An “incentive-compatible” collusion�[Ferreira, Gafni & Resnick ‘24], also mentioned in [Ganesh, Thomas & Weinberg ‘24]

• For example, if the collusion allows a bidder b1 = 1 to bid and pay 1.5 and be refunded 1, but does not allow the same for bidder b1 = 1.25, it is not IC.
• IC-collusion is a ‘completeness’ requirement
• We will also require that the collusion is individually rational.

Single seller, single buyer, single item. �What are the DSIC & IC+IR-OCA mechanisms?�

​

​

​

​

​

​

​

​

​

Characterization: Regular vs. Non-regular Distributions

Takeaways

​

• We may want collusion notions to be incentive-compatible themselves

(somewhat like the ‘semi-strong eq’ notion, e.g., [Geffner & Tennenholtz ‘23])

• This naturally leads us to posted-prices, like the tipless EIP-1559
• Collusion can mitigate inefficiency due to high prices
• It can not help with low prices, at least if it is by willing participants (IR)
• Maybe it’s good to aim to higher prices, and facilitate miner-user coordination?
• Non-constant burning based on block utilization (within a single block) is a valuable design pattern

​

​

​

​

​

​

​

Thanks for listening!���

Please feel free to reach out:

yotam.gafni@gmail.com

Some resources for follow up:

EC’24 paper (#1 part of the talk): https://dl.acm.org/doi/10.1145/3670865.3673469

Recent draft (#2 part of the talk):

https://arxiv.org/abs/2412.20853

EC’24 tutorial on TFMs:

https://aviv.yai.sh/ec24tutorialtfms/

Beyond the single-buyer case [WIP]

• You may want to set different prices based on the amount of bidders
• This is important for welfare
• The price for a single-bidder must be from the single-bidder collusion-free range, two bidders from the two-bidder collusion-free range, and so on…
• Moreover, the way this function is structured must not incentivize the miner to introduce fake bidders.

​

​

​

​

​

​

​

​

​

Value quantile v

Schematics of pricing schemes for single item, no burn, and up to two bidders