FLYCLIENT
SUPER LIGHT CLIENT FOR CRYPTOCURRENCIES
Loi Luu, Benedikt Bünz, Mahdi Zamani

Recall: Bitcoin blockchain format

Hash chain of blocks

prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )H( ) H( )Hash tree (Merkle tree)of transactions in eachblock

H( ) H( )transaction
2transaction

H( ) H( )transaction

transaction

Validity of a blockchain

Hash chain of blocks

prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )✅
H( ) H( )1. Transactions are valid
2. Merkle tree correct✅
H( ) H( )transaction
3✅

transaction

H( ) H( )✅

transaction✅

transaction ✅

3. Validity of a block header
prev:

prev:

H( )

mrkl_root: H( )nonce:

0x7a83hash:

0x0000

✅

H( )

prev:

H( )

mrkl_root: H( )mrkl_root: H( )nonce:

0xffff...
0x0000...
0x0001...
0x0002...
0xf77e...

nonce:

0xffff...
0x0000...
0x0001...
0x0002...
0xf77e...

hash:

0xd0c7...
0x6a1f...
0x300c...
0x0224...
0xc9c8...
0x0000...
0x3485...

hash:

0xd0c7...
0x6a1f...
0x300c...
0x0224...
0xc9c8...
0x0000...
0x3485...

Hash≤ 00000000000000001FB893000000000000000000000000000000000000000000

70+ leading zeroes required...
4✅

Two valid blockchains?

❓

This is theblockchain

No this is theblockchain5Longest chain rule❗
Take the longest chain!
Harder to produce.

6

Proof of work conjecture• Honest mining is a dominant equilibrium strategy• The majority of miners act rational• Implies that longest chain follows the rules of the network• Sleeping beauty property: You can always distinguish honest and honest
chains after being offline• Does not (necessarily) hold for proof of stake• As long as one of the nodes you are connected to is honest you will find thebest chain
7

Blockchain size: A growing problem
How am I going tostore 150 GB

8

Simple Payment Verifying Client (Satoshi 2008)
prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )H( ) H( )Just store theblock headers

H( ) H( )transaction
9transaction

H( ) H( )transaction

transaction

Verify block headers
prev:

prev:H( )mrkl_root: H( )nonce:0x7a83

hash:

0x0000

✅

H( )

prev:

H( )

mrkl_root: H( )mrkl_root: H( )nonce:

0xffff...
0x0000...
0x0001...
0x0002...
0xf77e...

nonce:

0xffff...
0x0000...
0x0001...
0x0002...
0xf77e...

hash:

0xd0c7...
0x6a1f...
0x300c...
0x0224...
0xc9c8...
0x0000...
0x3485...

hash:

0xd0c7...
0x6a1f...
0x300c...
0x0224...
0xc9c8...
0x0000...
0x3485...

Hash≤ 00000000000000001FB893000000000000000000000000000000000000000000

70+ leading zeroes required...
10✅

Use the longest chain rule❗

11

Can’t verify all transactions (but that’s ok)
prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )❓
Assumption:
Longest chain isproduced honestly

H( ) H( )❓
H( ) H( )transaction
12❓

transaction

H( ) H( )❓

transaction❓

transaction ❓

Can verify specific transactions (with help)
prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )transaction
13❓

Can verify specific transactions (with help)
prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )H( )transaction
14✅

15

SPV Properties and Problems•

Can determine the longest chain•

Can’t verify all transactions•

Can verify transaction inclusion•

Grows with #blocks•

Does not grow with #transactions•

Less block time-> larger SPV client•

80 bytes * #blocks (Bitcoin)•

40 MB in Bitcoin•

2.2 GB in Ethereum•

Especially bad for multi-chain clients••

508 bytes * #blocks (Ethereum)
Sufficient for sidechains and swaps

Sublinear SPV-Clients: SNARKs• SNARK or CS-Proof/CIP/STARK (Micali 91, Ben-Sasson et al. 17)• Constant size non-interactive proof that chain has length X• Circuit verifies full blockchain• Not practical for prover• SNARKs closer to being practical but trusted setup

16

Sublinear SPV-Clients: NiPoPoWs• Kyriasis, Miller, Zindros 17• Based on Kiayias, Lamprou, Stouka 16 and Back et al. 14• Insight: If I want to find x such that H(x) has n 0s then I will find 2 x’ such thatH(x’) has n-1 0s, 4 x’’ such that H(x’’) has n-2 0s …
• Best quality proof of work indicates quality of whole chain• Use a skiplist to point to proofs with less proofs of work
• O(log(n)*log(log(n))) proof size

17

NiPoPoW bribery attack• High quality blocks do not give extra reward• But they are important for NiPoPows1• Bribe honest rational miners to throw away super high quality blocks• Main chain “looks” worse which makes fooling SPV client easier• Does not violate NiPoPow’s security proof because honest mining and not
rational mining is assumed• Motivates search for different NiPoPows
18

Merkle Mountain Ranges (Todd 16)
Root 3

Root 1

Root 0Append L3

Append L2

L0

L1L0L1L2Log(n) inclusion proofs
Log(n) updates
nth tree commits to kth tree k<nLog(n) difference proofs

L0L1L2L3

Flyclient: A different approach to super-light clients20

prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )Flyclient: A different approach to super-light clients
Store justthe head21

root: H( )root: H( )root: H( )trans: H( )trans: H( )trans: H( )Flyclient: A different approach to super-light clients
Store justthe head

Merkle Tree22

root: H( )root: H( )trans: H( )trans: H( )Verifying Transaction
root: H( )root: H( )trans: H( )trans: H( )Chain headH( )transaction
23✅

Flyclient: Two heads?

❓

This is thehead

No this is thehead

24

Assumption:
At least one
chain is honest
Other one has at
most a c fractionof the miningpower
Ex: c=1/3

Flyclient Strawman 1
Give me k
blocks:
7,13,210…

25

Flyclient Strawman 1: sample constant # of blocks
Head 1

Honest chain

Sample k blocks + Merkle inclusion proof for eachMalicious chain (only 1/3 of the blocks have a PoW)
Head 226

Flyclient Strawman 1: sample constant # of blocks
Head 1

Honest chain

Malicious chain (only 1/3 of the blocks have a PoW)
Head 227

Flyclient Strawman 1: sample constant # of blocks
Head 1

Honest chain

Malicious chain (only 1/3 of the blocks have a PoW)
Head 228

Flyclient Strawman 1: sample constant # of blocks
Head 1

Honest chain

Malicious chain (only 1/3 of the blocks have a PoW)
Head 229

Flyclient Strawman 1 problem: Forking
Honest chain

Malicious Fork

Head 1

Head 230

Flyclient idea: Find Fork Point
Honest chain

Malicious Fork

Head 1

Head 2

Knowing this point suffices︸
Sample blocks after fork

31

Flyclient Strawman 2: Interactive Binary Search
Honest chain

Malicious Fork

Head 1

Head 232

Binary search tofind fork point
Log(n) messages

Flyclient Strawman 2: Interactive Binary Search
Honest chain

Malicious Fork

Head 1

Binary search tofind fork point
Log(n) messages

Head 2Works but two provers may
not want to interact33Flyclient: Idea bound forking point
Head 1

Head 234

Honest chain

Flyclient: Idea bound forking point
Head 1

Head 235

Honest chain

Flyclient: Idea bound forking point
Head 1

Head 236

Honest chain

Step 3: Repeat

Flyclient: Idea bound forking point
Head 1

Head 237

Honest chain

Step 3: Repeat

Flyclient: Idea bound forking point
Head 1

Head 238

Honest chain

Step 4: Check final L blocks (to prevent short forks)

Flyclient Analysis

39•

In each interval check k blocks, k independent of chain length n•

k dependent on attacker strength•

Check log(n) intervalls•

For each block do log(n) merkle inclusion proof•

O(log(n)^2) overall•

For n=1000000->

Non Interactive Flyclient40

Thanks
BUENZ@CS.STANFORD.EDU

bbuenz.github.io