  Light clients, also known as Simple Payment Verification (SPV) clients, are
nodes which only download a small portion of the data in a blockchain, and use
indirect means to verify that a given chain is valid. Typically, instead of
validating block data, they assume that the chain favoured by the blockchain's
consensus algorithm only contains valid blocks, and that the majority of block
producers are honest. By allowing such clients to receive fraud proofs
generated by fully validating nodes that show that a block violates the
protocol rules, and combining this with probabilistic sampling techniques to
verify that all of the data in a block actually is available to be downloaded,
we can eliminate the honest-majority assumption, and instead make much weaker
assumptions about a minimum number of honest nodes that rebroadcast data. Fraud
and data availability proofs are key to enabling on-chain scaling of
blockchains (e.g. via sharding or bigger blocks) while maintaining a strong
assurance that on-chain data is available and valid. We present, implement, and
evaluate a novel fraud and data availability proof system.
