Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities

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