Paper 2019/226

Flyclient: Super-Light Clients for Cryptocurrencies

Benedikt Bünz and Lucianna Kiffer and Loi Luu and Mahdi Zamani

Abstract

To ensure the validity of transactions, cryptocurrencies such as Bitcoin and Ethereum require nodes to verify that a proof-of-work blockchain is valid. Unfortunately, this often entails downloading and verifying all transaction blocks, taking days and gigabytes of bandwidth and storage to verify the blockchain. As a result, clients with limited resources such as mobile phones cannot verify transactions independently without trusting full nodes. As a solution to this, Bitcoin and Ethereum offer light clients known simplified payment verification (SPV) clients, that can verify the chain by downloading only the block headers which have significantly-smaller size than the full blocks. Unfortunately, the storage and bandwidth of SPV clients still increase linearly with the chain length. In Ethereum, for example, an SPV client needs to download and store more than 3.6 GB of data. Recently, Kiayias et al. proposed a solution, known as the non-interactive proof of proof-of-work (NIPoPoW), that requires a light client to download and store only a polylogarithmic number of block headers. Unfortunately, NIPoPoWs suffer from several drawbacks: they are succinct only as long as no adversary influences the honest chain. Furthermore, they can only be used for proof-of-work chains that have a fixed block difficulty, which is not the case in most cryptocurrencies, including Bitcoin and Ethereum, that require adjusting block difficulty frequently according to the network hashrate. In this paper, we introduce Flyclient, a novel transaction verification protocol for light clients that is efficient both asymptotically and practically. Our protocol requires to download only a logarithmic number of block headers to synchronize and verify transactions while storing only a single block header between executions. We formally prove that Flyclient is optimal for this class of protocols. For Ethereum, our protocol achieves a proof size of only less than 500 KB. This is achieved by utilizing a simple design based on Merkle Mountain Range (MMR) commitments and a probabilistic block sampling protocol. Flyclient overcomes the limitations of NIPoPoWs and generates shorter proofs over all measured parameters. We also discuss how Flyclient can be implemented via a soft fork in Bitcoin/Ethereum.