Paper 2021/1500
Succinct Erasure Coding Proof Systems
Nicolas Alhaddad, Sisi Duan, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- avidbroadcasterasure codingpolynomial commitments
- Contact author(s)
-
nhaddad @ bu edu
duansisi @ mail tsinghua edu cn
varia @ bu edu
bchainzhang @ aliyun com - History
- 2022-02-03: revised
- 2021-11-15: received
- See all versions
- Short URL
- https://ia.cr/2021/1500
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1500,
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},
url = {https://eprint.iacr.org/2021/1500}
}
