Barriers to Collusion-Resistant �Transaction Fee Mechanisms

​

​

EC’24

​

Yotam Gafni

Weizmann Institute

Aviv Yaish

Hebrew University, Israel

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], [Roughgarden ’21], [Chung & Shi ‘21], ...

​

Modeling assumptions we use:

• Blocksize B identical goods (we will mostly assume 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

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)

​

​

​

​

Understanding OCA-proof vs SCP

• 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.
• An auction is SCP if a coalition of the miner and bidders cannot increase their aggregated utility by deviating from the honest protocol.

​

​

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 Blockchainers, think about the

fixed-tip version of EIP-1559)

So how do OCA and SCP differ?

Intuition:

OCA is the miner and users colluding against the protocol

SCP is the miner playing the users against each other

​

We prove that SCP=>OCA, and it is a strictly weaker notion.

​

​

​

​

​

​

Example of OCA-proof but not SCP TFMs

• A second-price auction is OCA-proof but not SCP:
• The joint utility of the intended allocation is the full surplus. So any coalition with any off-chain agreement can not surpass that.
• The coalition of the miner and a losing bidder can increase its joint utility by the losing bidder bid higher to increase the second price.

​

• Maybe this example is a bit strange, because the miner colludes with a losing bidder, and they can use false-names instead…

​

​

Example of OCA-proof but not SCP TFMs II

Truthful

Miner+Bidder2 Collusion

Impossibility results in the “core TFM” model�[Chung & Shi ’22, (Shi, Chung & Wu ’22), Zhao et. al ’22]

Let’s start characterizing…

Deterministic DSIC + MMIC + OCA => 0-revenue

• In the single-bidder case, the bidder utility w.r.t. payment looks like the joint utility w.r.t. burn
• We know from Myerson that the allocation uniquely determines the payment, and thus, here, the burn

(For this we use DSIC + OCA, and it applies to the randomized case as well)

​

• The implications transfer to the multi-bidder case by using MMIC
• If there was revenue with many bidders, the miner would simulate it against a single bidder with shills.

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]

Single-item Deterministic OCA Mechanisms

• Any mechanism with a constant burn which is also a reserve (‘posted burn’)
• Allocate to the highest bidder (above the reserve)
• Freedom to set payments (that are individually rational and burn-balanced)

Adding DSIC, or MMIC to this characterization…

• With DSIC:
• The allocation rule uniquely determines the payment
• These are exactly second-price auctions with reserve that is burned.

​

• With MMIC:
• “Generalized first-price” auctions
• Let p(b) = f(max b) be a payment rule that only depends on the highest bid
• The function f needs to be monotone and always higher than the burn

And that’s it, these two classes don’t intersect.�

Randomized Barriers… or Impossibility?

• A key assumption that drives the randomized impossibility result of [Chung, Shi & Roughgarden ‘24] is that the inclusion rule is bounded
• While we similarly assume that the confirmation rule is bounded, we do not necessarily assume so for the inclusion rule.
• Reasons:
• More general
• Could be a reasonable pattern (mempool as part of the consensus, defered verification)

​

• Technical implications: Low transactions might still be confirmed

Randomized Scale-invariant Mechanisms: Impossible

Tension between Two-bidder and Single-bidder cases

Future Directions

• Revising collusion notions [Ganesh, Thomas & Weinberg ‘24], upcoming work [Ferreira, Gafni & Resnick ‘24]
• A non-trivial randomized mechanism for our setting?
• Understand the revenue benefits of the “non-constant burn difference” DSIC+OCA mechanisms we introduce

​

Thanks for listening!�

Contact: yotam.gafni@gmail.com