Fraud Proofs
Maximising SPV Security and Scaling
Blockchains with Dishonest Majorities

Mustafa Al-Bassam
6 October 2018

Motivation
Currently there is a hugetrade off between
decentralisation and onchain scalability.
Because SPV nodes (non Decentralisation
fully validating nodes) will
accept invalid blocks.

On-chainthroughput

They assume that themajority of the consensus
is honest.

06/10/18

2

Can we reduce this tradeoff?
The big question: how can we make nonfully validating (SPV) nodes reject
invalid blocks, so that they don’t haveto trust miners?
Let’s use fraud proofs and data availability proofs!

06/10/18

3

Read the full paper (33 pages)
Fraud Proofs: MaximisingLight Client Security andScaling Blockchains withDishonest Majorities
Mustafa Al-Bassam, Alberto
Sonnino, Vitalik Buterin

https://arxiv.org/abs/
1809.09044

06/10/18

4

Fraud proofs: the basic idea

06/10/18

5

Fraud proofs: the basic idea...but what if the miner
doesn’t release the tx
data?
A: Then we can’t
generate a fraudproof. 😱
06/10/18= We also need a way toguarantee data availability! 6

Earlier discussion on fraud proofs
The original Bitcoin whitepaper briefly mentions “alerts”;
which are messages that full nodes can send to SPV clientsto alert them the block is invalid. (Vulnerable to DoS.)
G. Maxwell and P. Todd have done some work on “compactfraud proofs”. Early proposals require a different fraud
proof for each way to violate the rules. We improve on this.
G. Maxwell has discussed on IRC using erasure coding fordata availability with a scheme using a “designated source”
with PoW rate-limiting (and no way to deal with incorrectly
generated codes?)06/10/18

7

Generalising the blockchain as astate transition system
Each transaction reads and modifies the state of theblockchain.
transition(state, tx) = state' or error

statei
Block X

06/10/18

txi+1txi+2statei+1statei+2txi+3statei+3txi+4statei+4
Block X+18

Generalising the blockchain as astate transition system
Each transaction reads and modifies the state of theblockchain.
transition(state, tx) = state' or error

But what if one of the transitions is errorneous?
We need a way to prove this.

stateiBlock X

06/10/18

txi+1txi+2statei+1statei+2txi+3statei+3txi+4statei+4
Block X+19

Representing the entire state as aMerkle root
We can store the state as a key-value store.
Key: UTXO ID. Value: 1 if unspent, 0 otherwise.

We can use a Sparse Merkle tree to do this.
A tree with 2256 leaves (every possible SHA-256 hash).

06/10/18

10

Representing the entire state as aMerkle root
Merkle proofs are still O(log(n)) as most branches will only
contain leaves with default values (0).
To access key K in the tree, access the hash(K)th item.
We can thus represent the entire state of the blockchain as asingle Merkle root.

06/10/18

11

Generalising the blockchain as astate transition system
Each transaction changes the state root of the blockchain.
transitionRoot(stateRoot, tx, witnesses) = stateRoot' or error
The witnesses of a transaction are Merkle proofs of all theparts of the state the transactions accesses.

Execution trace: we need to include the post-state root oftransactions in the block. (e.g. every few transactions)state txi+1
Rooti
Block X

06/10/18

state txi+2
Rooti+1

state txi+3Rooti+2txi+4
state
Rooti+3

state
Rooti+4
Block X+1

12

Generalising the blockchain as astate transition system
The fraud proofs consisters of the transaction and its prestate root, post-state root, witnesses (+ Merkle proofs).
If the Merkle proofs are valid, androotTransition(stateRooti+1, txi+1, witnessesi+1) != stateRooti+2
then the fraud proof is valid.
Fraud proof

state txi+1
Rooti
Block X

06/10/18

state txi+2
Rooti+1

state txi+3
Rooti+2txi+4
state
Rooti+3stateRooti+4
Block X+1

13

Generalising the blockchain as astate transition system
You don’t have to include the state root after everytransaction – this saves block space but the fraud proof getsbigger.

Fraud proof

state txi+1
Rooti
Block X

06/10/18

state txi+2
Rooti+1txi+3txi+4
stateRooti+3

state
Rooti+4
Block X+1

14

The data availability problem...but what if the miner
doesn’t release the tx
data?
A: Then we can’t
generate a fraudproof. 😱
06/10/18= We also need a way toguarantee data availability! 15Erasure coding
Using erasure coding, you can extend data t pieces long to
2t pieces, such that you can recover the whole data from anyt pieces.

2t

Original data

Extended datat
06/10/18

16

Naive data availability scheme
We can require miners to commit to the Merkle root of theerasure coded verison of the block data. In order for a miner
to hide any piece of the block, they must hide 50%.
Thus clients can randomly sample parts of the block (withreplacement), and if 50% is hidden, then there is a 2-s chance oflanding on an unavailable piece, then the block is rejected.
Clients gossip pieces to full nodes for recovery.
2t

Original data

Extended datat
06/10/18

17

Naive data availability scheme
Problem: what if the miner incorrectly generates the erasurecode?
In order to prove this, the fraud proof consists of the entire
block, as clients will need to download and regenerate theerasure code to check if it’s correct.
That’s O(blocksize). Back to square one!
2t

Original data

Extended datat
06/10/18

18

Multidimensional coding
We can use multidimensional coding to fix this.
If any row or column is incorrectly generate, a fraud proof
that the code is incorrectly generated is limited to thatspecific row or column. That’s O(sqrt(blocksize)).

06/10/18

Fraud proof

19

Multidimensional coding
Miner has to hide roughly 25% of the square to hide anypieces.

06/10/18

20

Probability analysis
What is the probability of a client landing on at least one
available piece if the miner has hidden ~25% of the square(if sampling without replacement)?
60% after 3 samplings; 99% after 15 samplings.

06/10/18

21

Selective releasing of pieces
What if a miner only releases pieces as clients ask for them?
Then the miner can always pass the sampling challenge of thefirst couple of hundred to thousand clients.
The exact number of how many clients can be fooled depends
on how many samples they make each (s) and how wide is
the square (k).

06/10/18

22

Preventing selective releasing ofpieces
We can prevent this by assuming an enhanced networkmodel.
Clients send requests anonymously.
The order in which requests are received by the network are
uniformly random (i.e. client’s sampled are interleaved). For
example, using a mix net.

This would mean that a miner would have same probabilityof fooling all clients, including the first ones to ask forsamples.
Because requests are unlinkable to clients; sampling
challenges cannot be satifisfied on a per-client basis.
06/10/18

23

Block validity security assumptions
comparison
What additional security assumptions are necessary to only
accept valid blocks?
Full nodes

06/10/18

SPV clients

SPV clients +fraud proofs+ 51% of consensus ishonest+ at least one honest
full node in connected
network graph+ maximum network
delay to receive proofs(e.g. 5 mins)+ minimum number oflight clients (fewhundred)24

Implementation
2D Reed-Solomon Merkle tree data availability scheme:
https://github.com/musalbas/rsmt2d
Fraud proofs prototype:
https://github.com/asonnino/fraudproofs-prototype
Sparse Merkle tree library with support for state transition
witness verification:
https://github.com/musalbas/smt

06/10/18

25

Performance: space/bandwidth

06/10/18

26

Performance: computation

06/10/18

27

Read the full paper (33 pages)
Fraud Proofs: MaximisingLight Client Security andScaling Blockchains with
Dishonest Majorities
Mustafa Al-Bassam, Alberto
Sonnino, Vitalik Buterin

https://arxiv.org/abs/
1809.09044

06/10/18

28

Thank you
Questions?
Twitter: @musalbas
Email: mus@musalbas.com

06/10/1829