Error correcting codes for blockchains

Error correcting codes have manifold applications to enhance security and performance of blockchain systems. We use codes to improve the resilience-overhead tradeoff in consensus and rollups.

Often, a system made from various components fails as soon as one of the components fails, for example when a large file is chunked up and each chunk is stored in a different storage server. As soon as one of the storage servers fails, it is not possible to recover the whole file anymore. Error correcting codes can be used to increase the resilience to component failures at the expense of injecting a bit of overhead. Supported by a gift from Input-Output Global (IOG), we explore applications of this paradigm in the blockchain context. For example, error correcting codes have been used in Verifiable Information Dispersal, which we refine to speed up consensus or to improve the resilience/overhead tradeoff of off-chain data storage in Validium rollups.

Key Publications

• “DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks”, Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, David Tse, USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2022, arXiv 2110.04371
• “Information Dispersal with Provable Retrievability for Rollups”, Kamilla Nazirkhanova, Joachim Neu, David Tse, arXiv 2111.12323