Greedy Transaction Fee Mechanisms�for (Non-)myopic Miners

​

​

HUJI Crypto seminar, December 2022

Kindly supported by ERC grant 740435 and the ministry of science & technology

​

Aviv Yaish

Hebrew University, Israel

Yotam Gafni

Technion, Israel

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 were formalized in a series of works [Lavi, Sattath & Zohar ‘19], [Roughgarden ’21], [Chung & Shi ‘21]

​

Modeling assumptions we use:

• Blocksize B of identical goods
• Users have unit demand (come once and served)

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

OCA and SCP definitions

Are OCA and SCP the same?

Truthful

Miner+Bidder2 Collusion

Are OCA and SCP the same? II

A note about collusion implementation

• Unlike the MMIC + DSIC conditions, it is not clear how the SCP/OCA threats are implemented
• How does this non-trivial multi-party bargaining happen, within the race situation of issuing a block?

​

​

​

​

​

​

​

Impossibility result(s) for TFMs�[Chung & Shi ’22, (Shi, Chung & Wu ’22), Zhao et. al ’22]

Is a Bayesian setting realistic?

Do users know what other transactions they compete against?

• No knowledge of future transactions
• Existing transactions: What you see is what you get? What about side payments?
• Cryptographic implementations for mempool [Shi, Chung & Wu ‘22]

Possibility result

• OCA-proof + MMIC + BIC is possible
• It is the direct revelation implementation of Bitcoin’s pay-as-bid auction
• We call it the shading auction

​

• Welfare optimal
• Revenue optimal?

​

​

​

​

​

​

​

​

​

3 Approximate revenue optimality benchmarks

Compare the shading auction to:

• The optimal auction (without OCA-proof + MMIC restrictions)
• The value surplus (for uniform and exponential distributions)
• The class of all auctions with reserve-based allocations

​

​

​

​

​

​

​

​

​

Revenue

Value surplus

​

Optimal auction

​

Optimal TFM

​

Optimal reserve-based TFM

The class of auctions with reserve-based allocations

• Consider a uniform price auction with reserve price r
• Let an allocation rule x that relates to some such r
• Any BIC auction that implements this allocation rule and is:
• EPIR (Ex-post individually rational)
• EPBB (Ex-post burn balanced)

Belongs to the class.

​

​

​

​

​

​

​

​

Theorem: ��The optimal revenue OCA-proof and MMIC auction in the class is the shading auction (with reserve r=0)

Proof idea��- If a user enters block a with reserve price r, at least r must be burned (due to OCA)������ ��

Block

Reserve price r

b < r

A bid with b < r is left out of the block

Block

Reserve price r

b’ > r

Proof idea II�- shading bid with no reserve is revenue-equivalent to uniform price with no reserve��Now take a conditional expectation over revenue of some auction A’ (w.l.o.g. assume A’ is uniform with reserve r):�- If the block is over-full, uniform price with no reserve performs the same as A’ in terms of payments, and at least as well w.r.t burning��- If the block is not over-full, A’ makes 0 in expectation ��

���- So far we considered that the miner only cares for the next block�- This is reasonable in an ideal blockchain where each miner is negligible�- In reality, there are large mining pools and the market resembles an oligopoly [Arnosti & Weinberg ‘22]��

The non-myopic case

A non-myopic competitive ratio model

- An adversary chooses transactions for infinite rounds�- The transactions are revealed to the miner at each round. Older transactions are carried over with reduced TTL. Transactions with zero TTL expire.�- We wish to compare the online and offline performance of different allocation rules�

Greedy (w.r.t fees)��

Fee: 1, TTL: 1

Adversary:

Round 0

Round 1

Round 2

…

Greedy choice:

OPT choice:

Fee: 1, TTL: 1

Lower bound proof

Adversary:

Greedy choice:

OPT choice:

Later rounds

Lower bound proof II

Adversary:

Greedy choice:

OPT choice:

…

…

Later rounds

Lower bound proof III

Adversary:

Greedy choice:

OPT choice:

…

…

Later rounds

Adversary:

Greedy choice:

Round 0

Round 1

Round 2

Fee: 1, TTL: 1

Round 3

Fee: 1, TTL: 1

Later rounds

Adversary:

Round i

Both transactions available to Greedy

OPT choice:

Adversary:

OPT choice:

…

…

Later rounds

Adversary:

OPT choice:

…

…

…

Later rounds

Adversary:

OPT choice:

…

…

Case 3: impossible

Later rounds

Going back to user incentives...

​

- In the myopic case, the BNE maintained the allocation behavior

• Both for the pay-as-bid auction, and for uniform-price (in dominant strategies)
• Is it still so in the non-myopic case?

​

Intuition: No, users shade differently based on their patience.

​

​

​

​

​

​

Is uniform-price ex-post IC?

​

​

​

​

​

The first bidder in Round 0 prefers to bid (Fee: 7, TTL: 2) instead

​

We obtain a similar result for the pay-as-bid greedy auction under Bayesian IC

Fee: 10, TTL: 2

Fee: 8, TTL: 1

Bidders:

Round 0

Round 1

Fee: 5, TTL: 1

Fee: 5, TTL: 1

How should we model users beyond a single block?

​

​

​

​

​

​

Expected fee minimizers

Counter-evidence: Super-high transaction fees outliers (we found a 2.5m$ fee paid), daily patterns to fees

​

Single-minded Urgency

Counter-evidence (?):

Mempools are significantly larger than block sizes (x20 Bitcoin, x500 Ethereum),

People using low priority in fee recommendation engines

​

Hassle minimizers

Counter-evidence: People using low priority in fee recommendation engines

​

​

​

​

Thanks for listening!

​

​

​

​

​

Email me at - yotam.gafni@campus.technion.ac.il

Arxiv paper: https://arxiv.org/abs/2210.07793

Mechanism Design for Data Science group - https://mdds.net.technion.ac.il/