Incentives and Trade-offs in Transaction Selectionin DAG-based Protocols

Yonatan Sompolinsky and Yoad Lewenberg

Scaling Bitcoin, Stanford

Background● Directed Acyclic Graph of blocks (blockDAG)● Inclusive Blockchain Protocols, Financial Crypto ‘15,Lewenberg, Sompolinsky, and Zohar● Modification and scaling up of Layer 1● Orthogonal to Layer 2 solutions

Genesisblock

recentblockBlockchain vs BlockDAG
Chain paradigm:
1. maintain single chain
2. ignore the rest
3. forks rare

Genesisblock

recentblock

DAG paradigm:
1. maintain entire graph
2. consider all blocks
3. forks common

Genesisblock

recentblockThe BlockDAG paradigm
Chain paradigm:
1. maintain single chain
2. ignore the rest
3. forks rare

Genesisblock

recentblock

DAG paradigm:
1. maintain entire graph
2. consider all blocks
3. forks common

Genesisblock

recentblockRoad to scaling up Layer 1
speed up block
rate (or size)

genesisblock

reference all
blocksextract
consistency

Road to scaling up Layer 1
speed up block
rate (or size)reference all
blocksextract
consistency

SPECTRE
genesisblockBlockDAG is (only) a paradigm● DAG merely a framework, not a solution● Not all blockDAGs are created equal● DAG vs chain like highway vs one-lane road…

BlockDAG is (only) a paradigm● DAG merely a framework, not a solution● Not all blockDAGs are created equal● DAG vs chain like highway vs one-lane road…

BlockDAG is (only) a paradigm● DAG merely a framework, not a solution● Not all blockDAGs are created equal● DAG vs chain like highway vs one-lane road…

BlockDAG is (only) a paradigm● DAG merely a framework, not a solution● Not all blockDAGs are created equal● DAG vs chain like highway vs one-lane road…

Scaling up Layer 1 -- challenges

throughput &confirmation times

bandwidth utilization

Two scenarios for DAG throughput
mempool: tx1<tx2<tx3<tx4<… (non-conflicting)tx1,tx2

new blockminer 1tx1,tx2

new blockminer 1tx1,tx2

new blockminer 2

tx3,tx4

new blockminer 2

tx1,tx2 selected & approved
tx3,tx4 still in mempool

tx1,tx2,tx3,tx4 selected & approved(mempool cleared faster)under utilization

full utilization

Proposition 1: under naïve/greedy mining,
DAG throughput ≈ chain throughput
Throughput
1000

OptimalGreedy

Chain

800
600
400
200
001020304050

λ60

7080

90100

Key observation / good news
Miners are incentivized to be avoid selecting the same txns,
and to contribute to throughput increase.
Indeed, “collisions” result in loss of fees…

The Inclusive Game
mempool: tx1>tx2
players: miner1, miner2

miner2 chose tx1

miner2 chose tx2

miner1 chose tx1 (0.5*tx1, 0.5*tx1)(tx1, tx2)

miner1 chose tx2 (tx2, tx1)

(0.5*tx2, 0.5*tx2)

collision on tx1

collision on tx2

The Inclusive Game
pure strategy: select a txn
mixed strategy: select a txn using randomness

miner2 chose tx1

miner2 chose tx2

miner1 chose tx1 (0.5*tx1, 0.5*tx1)(tx1, tx2)

miner1 chose tx2 (tx2, tx1)

(0.5*tx2, 0.5*tx2)

collision on tx1

collision on tx2

How to “solve” the gamelevel of cooperation

adversarial

selfishselfish +coordination

altruistic

solution:solution:solution:solution:

Safety Level

Nash Equ.

Correlated Equ.

Max SocialWelfareMax Social Welfare● Solution: select txns uniformly [above capacity threshold]● No collisions, full utilization● But there’s a catch…
probability

100thresh

fee amount

High throughput is not enough
1. Strategically unstable
2. Forces egalitarian waiting times, no QoS levels andpreferential treatment
waiting time

constant servicetime00

fee amount

High throughput is not enough
1. Strategically unstable
2. Forces egalitarian waiting times, no QoS levels andpreferential treatment
waiting time

constant servicetime
diffQoS00

fee amountTrade-off: high utilization vs fast conf. times
shorter waiting times  more collisions lower utilization
4# of collisions# of collisions

4
3.5
3
2.5
2
1.5
1
0.5

3.5
3
2.5
2
1.5
1
0.5
000

10

20

30

waiting time

40

50

0200

400
600
waiting time

800

1000

round #1

Nash Equilibriumminer1\miner2

tx1

tx2

tx1

(0.5*tx1,0.5*tx1)(tx1, tx2)

tx2

(tx2, tx1)

(0.5*tx2,0.5*tx2)● Finding Nash usually hard
● Tit-for-tat strategies● Greedy pools/miners will suffer
retaliation (?)

round #2
miner1\miner2

tx1

tx2

tx1

(0.5*tx1,0.5*tx1)(tx1, tx2)

tx2

(tx2, tx1)

(0.5*tx2,0.5*tx2)

round #3
miner1\miner2

tx1

tx2

tx1

(0.5*tx1,0.5*tx1)(tx1, tx2)

tx2

(tx2, tx1)

(0.5*tx2,0.5*tx2)

Nash Equilibrium (myopic)● Assigns high probability to high paying txns
● Not too greedy: top txns not necessarily selected

probability

100fee amountThroughput under Nash
Throughput of: DAG + greedy mining (green)
DAG + Nash Equ. (blue)
DAG + optimal utilization (red)Throughput

Utilization

1000

1OptimalTopKTopK

Nash

800

0.8

600

0.6

400

0.4

200

0.2

0Nash

0020

4060

λ80

100

020

4060

λ80

100

0
0.2
0.4
0.599
0.799
0.999
1.2
1.4
1.6
1.8
2
2.2
2.4
2.6
2.8
3
3.2
3.4
3.6
3.8
4
4.2
4.4
4.6
4.8
4.999
5.199
5.399
5.599
5.799

waiting time

QoS levels

500
450
400
350
300
250
200
150
100
50
0Nashfee amount
TopKUCO
Exponent

Correlated Equilibrium / asymmetric Nash
● Can we do better by somehow coordinating between miners?

● Preliminary results: yes, higher throughput● Coordination mechanism: using prvs blocks’ randomness● Future work

Scaling and incentives● Strategic mining in Bitcoin -- sophisticated, risky
in DAG -- easy (but also marginal)● Decisions more granular: which txns to select?

how fast to release blocks?
● “Lazy” selfish mining -- miner is lazy in information
sharing, does not contribute reasonable bandwidthWhen implementing
BlockDAG protocols -incentives really matter“Bitcoiners of the world, unite!
You have nothing to lose but your chains!“