Swanand Kadhe's full lecture at the 2020 European School of Information Theory Stuttgart, Germany
In this tutorial, we will demonstrate how coding theory can play an instrumental role in addressing some of the fundamental challenges in the emerging field of blockchains. We will begin with a quick primer on blockchains, covering the essentials. Then, we will focus on the problem of reducing blockchain storage costs. We will present a ‘Secure Fountain (SeF)’ architecture, based on fountain codes, that enables users to encode blocks into a small number of coded blocks, thereby reducing storage costs by orders of magnitude. Here, we will demonstrate that the peeling decoder admitted by fountain codes turns out to be crucial for security against adversarial nodes. In the second half, we will consider data availability attacks in blockchains, wherein adversarial miners withhold portions of the block. We will describe how product codes and low-density parity-check (LDPC) codes can be used to mitigate data withholding attacks. Inspired by the data availability problem, we will introduce a new class of codes, referred to as codes with local proofs of incorrect coding. We will show that these codes are related to locally recoverable codes. We will conclude by highlighting how blockchains open up novel code design problems.