Introduction

BraidsMiner Incentives

Conclusions

Braiding the Blockchain
Bob McElrath, Ph.D.

Scaling Bitcoin
Hong Kong
Dec 7 2015
bmcelrath@sldx.com

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Save the Orphans!
Orphans are not a necessary component of the operation ofbitcoin!

Orphans occur when miners do not know about theexistence of another block (B) before generating theirs (C)Simultaneous block generation is unavoidable
It doesn’t require us to deprive a miner of profit
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Save the Orphans!
Orphans are not a necessary component of the operation ofbitcoin!

What if block C contains no conflicting transactions?
What if block C contains a duplicate transaction?
There is no conflict so let us call C a sibling.
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Save the Orphans!
Orphans are not a necessary component of the operation ofbitcoin!

A future block must be able to tie up B and C, indicatingthat there is no conflict.
To get rid of orphans, blocks must have multiple parents
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Save the Orphans!
Orphans are not a necessary component of the operation ofbitcoin!

If C contains a double-spend relative to B, then C forms a
new chain tip.

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Down the Rabbit HoleAllowing blocks to havemultiple parents creates adata structure called a
Directed Acyclic Graph.
What if I just throw out blocks
as fast as I desire, doalgorithms exist that could
make sense of the chaos anddefine a highest work “tip”?
The blockchain is anover-simplified data structure,with some unfortunate
consequences (orphans,selfish mining).
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Down the Rabbit HoleAllowing blocks to havemultiple parents creates adata structure called a
Directed Acyclic Graph.
What if I just throw out blocks
as fast as I desire, doalgorithms exist that could
make sense of the chaos anddefine a highest work “tip”?
The blockchain is anover-simplified data structure,with some unfortunate
consequences (orphans,selfish mining).
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Down the Rabbit HoleAllowing blocks to havemultiple parents creates adata structure called a
Directed Acyclic Graph.
What if I just throw out blocks
as fast as I desire, doalgorithms exist that could
make sense of the chaos anddefine a highest work “tip”?
The blockchain is anover-simplified data structure,with some unfortunate
consequences (orphans,selfish mining).
Braiding the BlockchainBob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

The Directed Acyclic Graph
Allowing blocks to have multiple parents creates a:
Directed Blocks have parents, parents cannot refer tochildren
Acyclic A cycle is cryptographically impossible
Graph Structure is non-linear (no “height”)
A DAG can be partial ordered in linear time.
We have to make a restriction relative to a more generaldag, so I’m going to name this data structure a braid.

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Braid Terminology
BEGDA(genesis)CFsiblings

timeH(braid tip)

Braid A Directed Acyclic Graph having no incest (no triangles)
Bead Analog of Bitcoin’s blocks (green circles)
Sibling A bead that cannot be partial ordered relative to myself:
the pairs (B,C) and (E,F)
Incest A parent that is simultaneously an ancestor of anotherparent (disallowed)
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Our Approach
Because of selfish mining1 we will incentivize miners toquickly transmit beads
Because GHOST2 worsens some attacks, we will requirethat parents must not contain conflicting transactions
Allow all of these to be decided per-node:
Bead time; Bead target difficulty; Bead size

Assume Braids will be a parallel, faster layer to Bitcoin
blocks:Beads will be constructed such that they are valid Bitcoin
blocks, if they meet bitcoin’s difficulty target.

Publish beads ex-post-facto because knowing who thecurrent leader is (Bitcoin-NG3 ) opens a new vulnerability
1

Eyal, Sirer, arXiv:1311.0243
Sompolinsky, Zohar, ia.cr/2013/881
3Eyal, Gencer, Sirer, Renesse, arXiv:1510.02037
2

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Braid Fork Example

A double-spend occurs in A and B⇒ We must evaluate which braid has the most work

Beads in each fork reference either A or B as a parent
The highest-work braid will be decided by evaluating thework in the combined work of all beads in the red and blue
subgraphs.
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

How to Incentivize Miners
Miner incentives must be aligned with correct operation of thenetwork
Consensus is created by on the profit-maximizing miners
Let the reward be proportional to a miner’s target difficulty⇒ Miners can individually choose target and block rate basedon other considerations (e.g. bandwidth)⇒ Bandwidth and CPU is now the only limiting factor for thenetwork!

The existence of siblings/orphans means we cannot decideminer coin allocation until all beads are seen by all nodes⇒ Coin allocation will be calculated 100 blocks later

We will define several quantities that we will use in a new miner
incentive formula (a.k.a. How many bitcoins do I get?)Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Siblings
A sibling S is an analog to Bitcoin orphans. It is defined as
A bead that cannot be ordered to come before
or after mine using only the DAGs partial order
Siblings are defined per braid tip
Siblings must not contain conflicting transactions
Siblings may contain duplicate transactions
If siblings share the same transaction, each sibling will beallocated a work-weighted fraction of the tx fee. (e.g. 2 siblingsat the same target difficulty will each recieve 1/2 of the tx fee)

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Cohort Difficulty
The cohort difficulty D is the work of other miners during thetime window in which I was mining. It is defined as:
The combined work of all beads between
my youngest parent and my oldest child.
A miner with large cohort difficulty relative to his own isplaying games or following a perverse incentive
Trying to steal fees by becoming everyone’s sibling
Withholding blocks (children are late)⇒ Incentivizing small cohort difficulty incentivizes fast blocktransmission

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Cohorts and Siblings
siblings
cohortGEDA

FCH (tip)time

B
The cohort of bead B is (D,E,G) while its siblings are (D,E)
Quiz:
Siblings of G? Cohort of G?
Siblings of D? Cohort of D?
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Miner Incentive Formula
The miner of block i receives a reward Ri :  TiXdi 1
di 1
Ri =ft+C;
Di NtDi N
ti, j bead indicest transaction index
di difficulty = 1/target
Di the parallel enclosed difficulty
Ti number of transactions in bead i
C block reward = 25 BTC

Braiding the Blockchain

Nt =StX
dss

Ds;

N=NcX
djj

Dj

ft Transaction fee for tx t
St number of siblings containing
tx t (St = 1 if no siblings)
Nt Sum of weighted difficulty oversiblings contining tx t
N Sum of weighted difficulty overall beads (normalization)
Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Miner Incentive Formula
The miner of block i receives a reward Ri :  TiXdi 1
di 1
Ri =ft+C;
Di Nt
Di Nt

Nt =StX
dssDs;

N=NcX
djj

Dj

This miner incentive formula is constructed such that it is:linear in miner difficulty di (miners set their own target)
For Ddii  N miner income is independent of target
Smaller di means smoother income distribution over time

Fair (difficulty-weighted) split of fees ft among siblings

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Miner Incentive Formula
The miner of block i receives a reward Ri :  TiXdi 1di 1
Ri =ft+C;
Di Nt
Di Nt

Nt =StXdss

Ds;

N=NcX
djj

Dj

Consequences of this incentive structure:
We’re incentivized to optimize the p2p topology to quickly
propagate blocks
Use of cohort difficulty Di incentivizes fast transmission ofblocks
Small miners can mine without joining pools: coinbase has
many outputs (like p2pool)

Braiding the Blockchain

Bob McElrath, Ph.D.

IntroductionBraids

Miner Incentives

Conclusions

Evaluating the Best Braid
The sub-braid containing the most work can be determined byestimating the hash rate
H=minersXHi

i

The best way to do this is using a likelihood function:{xi }Wα ({Hi }) = − log L = − log

YPxi (Hi t, ki )iwhere Px (h, k) is the Poisson distribution
Miners are incentivized to include all chain tips as parents
because it gives the sub-dag they’re mining on more work.
Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Confirmation Times
How do I know when a transaction is “confirmed”?
Satoshi’s analysis still applies, and we must keep Bitcoin’s
payout schedule⇒ Counting six bitcoin blocks is still resonable

Much better analyses are possible
Do there exist other braid-tips with similar work?
What’s the ratio of work in my braid tip and the next closest?
Has the hash power recently changed?

We have much more data: I’d like to see a whole class of risk
evaluation methods added for different users and use cases.

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

ConclusionsConfirmation Times
How do I know when a transaction is “confirmed”?
Satoshi’s analysis still applies, and we must keep Bitcoin’s
payout schedule⇒ Counting six bitcoin blocks is still resonable

Much better analyses are possible
Do there exist other braid-tips with similar work?
What’s the ratio of work in my braid tip and the next closest?
Has the hash power recently changed?

We have much more data: I’d like to see a whole class of risk
evaluation methods added for different users and use cases.

Braiding the Blockchain

Bob McElrath, Ph.D.

Introduction

BraidsMiner Incentives

Conclusions

Conclusions
Gettting rid of orphans forces us to the Braid structure.
Transaction volume is limited only by bandwidth and CPU!
Confirmation times can be much faster, limited only by thepropagation time to reach the entire network (e.g. the sizeof the Earth).
Algorithms are more complex, but seem to all be O(N): We
don’t have to solve the Travelling Salesman Problem.
Miner income becomes much smoother and morepredictable
Many ways to put this into bitcoin many incentive models:simulation and testing is necessary.
Smaller miners do not have to use pools⇒ mining decentralization!
Braiding the Blockchain

Bob McElrath, Ph.D.