Protocol Labs Research
2020.2.17 / Report
Vector commitment techniques and applications to verifiable decentralized storage
Theory and Practice of Blockchains 2020 / 2020.07.01
Matteo Campanelli, Dario Fiore, Nicola Greco , Dimitris Kolonelos, Luca Nizzardo


Vector commitments with subvector openings (SVC) [Lai-Malavolta and Boneh-Bunz-Fisch, CRYPTO'19] allow one to open a committed vector at a set of positions with an opening of size independent of both the vector’s length and the number of opened positions.

We propose a new SVC construction in groups of unknown order that, similarly to that of Boneh et al. has constant-size public parameters, commitments and openings, but in addition enjoys new features. First, our SVC has incremental aggregation: one can merge openings in a succinct way an unbounded number of times. Thanks to incremental aggregation we obtain: faster generation of openings via preprocessing, and a method to generate openings in a distributed way. Second, we propose efficient arguments of knowledge of subvector openings for our SVC, which immediately yields a keyless proof of storage with compact proofs.

Finally, we introduce and contruct Verifiable Decentralized Storage (VDS), a cryptographic primitive that allows to check the integrity of a file stored by a network of nodes in a distributed and decentralized way.