Paper 2021/1500

Succinct Erasure Coding Proof Systems

Nicolas Alhaddad, Sisi Duan, Mayank Varia, and Haibin Zhang


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
avidbroadcasterasure codingpolynomial commitments
Contact author(s)
nhaddad @ bu edu
duansisi @ mail tsinghua edu cn
varia @ bu edu
bchainzhang @ aliyun com
2022-02-03: revised
2021-11-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Alhaddad and Sisi Duan and Mayank Varia and Haibin Zhang},
      title = {Succinct Erasure Coding Proof Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1500},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.