Cryptology ePrint Archive: Report 2021/1500

Succinct Erasure Coding Proof Systems

Nicolas Alhaddad and Sisi Duan and Mayank Varia and Haibin Zhang

Abstract: Erasure coding is a key tool to reduce the space and communication overhead in fault-tolerant distributed computing. State-of-the-art distributed primitives, such as asynchronous verifiable information dispersal (AVID), reliable broadcast (RBC), multi-valued Byzantine agreement (MVBA), and atomic broadcast, all use erasure coding.

This paper introduces an erasure coding proof (ECP) system, which allows the encoder to prove succinctly and non-interactively that an erasure-coded fragment is consistent with a constant-sized commitment to the original data block. Each fragment can be verified independently of the other fragments.

Our proof system is based on polynomial commitments, with new batching techniques that may be of independent interest. To illustrate the benefits of our ECP system, we show how to build the first AVID protocol with optimal message complexity, word complexity, and communication complexity.

Category / Keywords: cryptographic protocols / avid, asynchronous verifiable information dispersal, broadcast, erasure coding, polynomial commitments

Date: received 12 Nov 2021

Contact author: nhaddad at bu edu, duansisi at mail tsinghua edu cn, varia at bu edu, bchainzhang at aliyun com

Available format(s): PDF | BibTeX Citation

Version: 20211115:125704 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]