Scaling Nakamoto

Consensus to Thousands of

Transactions per Second

The Conflux Foundation

Blockchains and Cryptocurrencies

• Value storage and transfer

• Smart contract

• Anonymous transactions

• Combined Market Cap: 0.3-0.4 trillion USD

Performance Problem

Transactions per

Second: (TPS)

~30

~200

~7

~3000

Undesirable user experience, long processing delay,

and skyrocketing transaction fees!

Why standard blockchain

systems have very low

throughput?

Nakamoto Consensus in Bitcoin

Block_{n-3 }

Block_{n-2 }

Block_{n-1 }

Block_{n }

Block_{n+1 }

…

Tx1

…

Tx99

• Transactions are packed into blocks

• A chain of blocks as the transaction history

• Everyone can append a valid block at the end

Standard Nakamoto Consensus

• Proof-of-work: participants perform computation

tasks to generate blocks

• Longest-chain: all participants agree on the longest

chain as the valid transaction history

• Slow/small block generation

▪ Bitcoin: 1MB block per 10 minutes

▪ Ethereum: ~100k block per 15 seconds

What if we run Nakamoto

Consensus with large/fast

blocks generation?

Forks in Nakamoto Consensus

fork

Longest chain

fork

fork

Blockn

Blockn-1

Block0

Block1

Block2

…

…

fork

fork

fork

• Forks waste network/processing resources

• Downgrade safety

▪ Attacker needs less resource to beat the longest chain

Conflux

One Observation

• Bitcoin enforces a very restrictive transaction total

order at the generation time of each block:

Block1: My transactions need to follow Block0!

Block0

Block1

…

Block2: My transactions need to follow Block0!

Block2

One Observation

• Bitcoin enforces a restrictive transaction total order

at the generation time of each block:

Block0

Block1

Block3

Block4

Block5

…

Block2

Case1: Block1 survives and its order becomes the final

transaction history, Block2 is discarded!

One Observation

• Bitcoin enforces a restrictive transaction total order

at the generation time of each block:

Block0

…

Block2

Block3

Block4

Block5

Case2: Block2 survives and its order becomes the final

transaction history, Block1 is discarded!

One Observation

• Bitcoin enforces a restrictive transaction total order

at the generation time of each block:

Block0

Block1

…

Block2

• Blockchain transactions rarely conflict with each

other and they can be serialized in any order

• Why not process non-conflicting transactions in all

concurrent blocks?

Conflux Main Ideas

• Optimistically process concurrent blocks

• Organize blocks into a direct acyclic graphs (DAG)

• First agree on a total order of all blocks

▪ Assume transactions would not conflict each other

• Then derives the transaction order from the agreed

block order

▪ Resolve transaction conflicts lazily

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

D

F

G

Tx4

Genesis

A

Tx2

C

E

H

Tx0

Tx1

B

J

I

K

Tx3

Tx4

Each block has one outgoing parent edge to its parent block

Parent edges form a tree

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

E admits that D is generated before E

D

G

Tx4

Genesis

A

C

E

H

Tx0

Tx1

Tx2

B

F

J

I

K

Tx3

Tx4

Each block may have multiple ref. edges

Ref. edges simply denote happens-before relationships

How to Agree on a Block Order?

• Key Idea: deterministically define a block total

order of a DAG based on a chain

• First agrees on a pivot chain of blocks

• Then extend the agreed pivot chain into a total

order of all blocks in the DAG

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

Subtree A has 6 nodes

D

G

Tx4

Genesis

A

C

E

H

Tx0

Tx1

Tx2

Subtree B has 5 nodes

B

F

J

I

K

Tx3

Tx4

Select the pivot chain with the GHOST Rule

[Sompolinsky et. al., ICFCDS’15]:

1. Start from the Genesis block

2. Iteratively advance to the child block with the largest subtree

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

D

F

G

Tx4

Genesis

A

Tx2

C

E

H

New Block

K

Tx0

Tx1

B

J

I

Tx3

Tx4

Rules for generating a new block:

1. Select the last block in the pivot chain as the parent

2. Create reference edges to all other blocks without incoming edges

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

D

F

G

Tx4

Genesis

A

Tx2

C

E

H

New Block

K

Tx0

Tx1

B

J

I

Tx3

Tx4

Why not the longest one as the pivot chain?

Because blocks in forks are counted in each selection step,

it guarantees that the attacker always needs 50% power to

revert the pivot chain!

How to extend the agreement to

a total order of all blocks?

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

D belongs to the epoch of E, because D happens

before E but does not happen before C

D

G

Tx4

Genesis

A

C

E

H

Tx0

Tx1

Tx2

B

F

J

I

K

Tx3

Tx4

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

1. Each pivot chain block forms one epoch

2. An off-chain block belongs to the first epoch whose

corresponding pivot chain block happens after it.

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

1. Order based on epoch first

2. Topologically sort blocks in each epoch

3. Break ties based on block id

D

G

Tx4

Genesis

A

C

E

H

Tx0

Tx1

Tx2

B

F

J

I

K

Tx3

Tx4

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

Block Total Order: Genesis, A, B, C, D, F, E, G, J, I, H, K

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

D

F

G

Tx4

Genesis

A

Tx2

C

E

H

Tx0

Tx1

B

J

I

K

Tx3

Tx4

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

Genesis, A, B, C, D, F, E, G, J, I, H, K

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

D

F

G

Tx4

Genesis

A

Tx2

C

E

H

Tx0

Tx1

B

J

I

K

Tx3

Tx4

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

Genesis, A, B, C, D, F, E, G, J, I, H, K

Tx0, Tx1, Tx2, Tx3, Tx4, Tx4

Duplicate

Conflict

Is Conflux safe against double

spend attacks?

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

D

F

G

Tx4

Genesis

A

Tx2

C

E

H

Tx0

Tx1

B

J

I

K

Tx3

Tx4

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

Genesis, A, B, C, D, F, E, G, J, I, H, K

Tx0, Tx1, Tx2, Tx3, Tx4, Tx4

How could an attacker

possibly revert Tx4?

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

Claim1: Attacker cannot revert a transaction

unless it reverts the pivot chain

D

G

Tx4

Genesis

A

C

E

H

Tx0

Tx1

Tx2

B

F

J

I

K

Tx3

Tx4

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

Genesis, A, B, C, D, F, E, G, J, I, H, K

How could an attacker

possibly revert Tx4?

Attacker’s Block

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

Claim1: Attacker cannot revert a transaction

unless it reverts the pivot chain

AttackB

D

G

Tx4

Genesis

A

C

E

H

Tx0

Tx1

Tx2

B

F

J

I

K

Tx3

Tx4

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

As long as AttackB does not get on the pivot chain,

it belongs to a very late epoch

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

Claim1: Attacker cannot revert a transaction

unless it reverts the pivot chain

D

G

Tx4

AttackB

Genesis

A

C

E

H

New Block

Tx0

Tx1

Tx2

B

F

J

I

K

Tx3

Tx4

Epoch of

New Block

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

As long as AttackB does not get on the pivot chain,

it belongs to a very late epoch

Tx0: Mint 10 coins to X

Tx1: Mint 10 coins to Y

Tx2: X sends 8 to Y

Tx3: X sends 8 to Z

Tx4: Y sends 8 to Z

Parent edges

Ref edges

Claim1: Attacker cannot revert a transaction

unless it reverts the pivot chain

D

G

Tx4

AttackB

Genesis

A

C

E

H

New Block

Tx0

Tx1

Tx2

B

F

J

I

K

Tx3

Tx4

Epoch of

New Block

Epoch of

Genesis

Epoch of H

Epoch of E

Epoch of A

Epoch of C

Claim2: An attacker cannot revert an old block

on the pivot chain unless he/she controls 50%

block generation power

Why Need 50%?

Blocks from honest

participants

A

Subtree of A

…

Blocks from

the attacker

Subtree

A’

of A’

• Suppose to revert a pivot chain block A

• Honest participants may create small forks but

always under the subtree of A

• Attacker needs 50% block generation power to

grow subtree A’ to beat A

Theoretical Analysis

A has n blocks at time t-d

A’ has m blocks at time t

A

Subtree of A

…

Subtree

A’

of A’

• Chance of A’ outgrows A after time t is less than:

q (q<1) is the ratio of the

computation power of the

attacker comparing to

honest participants

d is the network delay bound

between honest nodes

Confirmation Strategy

• User make assumptions on

▪ The power of attackers -- q

▪ The tolerable risk of a transaction being reverted -- r

• Find the epoch of the transaction

• Find the pivot chain block of the epoch

• Check if the chance of the pivot chain block being

reverted is small enough

Conflux Architecture

Propagate transactions

and blocks

Run consensus on the

DAG

Maintain a pool of

pending transactions

Evaluation

Experimental Environment

• Run 10k Conflux full nodes on Amazon EC2

• Limit the bandwidth of each full node to 20Mbps

• Run different configurations:

▪ Block sizes: 1MB to 8MB

▪ Block generation rate: 5s to 80s

• Measure the achieved throughput and

confirmation delay

• Compare with standard chain-based protocols,

Bitcoin and GHOST

What’s the throughput of

Conflux?

Achieved Throughput

• Conflux achieves

2.88G/h under 4MB

block and 5s

generation interval.

▪ ~3200 TPS

• 3.7x comparing to

Algorand under the

same environment

• 12.5x comparing to

Bitcoin/GHOST

Block Utilization Ratio

• Fast generation and

large blocks → small

chain ratio in

Bitcoin/GHOST

• Only 8% when

running the 4MB + 5s

setting

• In Contrast, all blocks

in Conflux contribute

to the throughput

How long users have to

wait to obtain high

confidence for a

transaction?

Confirmation Time

• Fast block generation

→ blocks build on

each other quickly →

fast confirmations

• Conflux confirms in

10 minutes on

average (4M + 5s)

• Bitcoin is unsafe in

fast/large block

generation settings

The user assume 20% attacker power, r = 0.0001

Confirmation Time (4MB + 5s)

• As the assumed

attacker power

increases, users need

to wait longer

• The chance of a

transaction being

reverted drops

exponentially as users

wait longer

How is the scalability of

Conflux?

Scalability with Bandwidth Limit

• Conflux cannot run with 4MB/2.5s setting with

20Mbps bandwidth

• Because bandwidth becomes the bottleneck

• Increase the bandwidth limit to 40Mbps

• Conflux successfully runs under the 4MB/2.5s

setting with 40Mbps bandwidth on 10k nodes

▪ Achieve the throughput of 5.76GB/h

▪ Or ~6400 transactions per second (Bitcoin tx size)

• Confirm transactions in 6.3 minutes

Scalability with More Full Nodes

(4MB+5s)

• Conflux scales to 20k

full nodes

• The network

propagation delay d

increases linearly as

the number of full

nodes double

Conflux DAG in Action

Conflux DAG from the 4M + 5s run:

Genesis

The Pivot chain:

Related Work

Reduced

Participation

Decentralized

Algorand

[SOSP’17]

BitcoinNG

[NSDI’16]

PBFT

[OSDI’99]

Hybrid

Consensus [Pass

and Shi], Byzcoin

[USENIX Sec’16]

Stellar

HoneyBagger

[CCS’16]

Bitcoin,

Ethereum

Resolve tx. conflicts

at block generation:

Conflux exploits the fact that

the blockchain transactions

rarely conflict with each other.

Optimistically

process blocks; lazily

resolve tx. conflicts:

Conflux

Summary