Distributed Vector Commitments and Their Applications

Vector commitment (VC) schemes enable a prover to commit to a vector and later open any position with a short proof. However, existing VC schemes are designed for centralized settings, and cannot work in decentralized systems, where the input vector is distributed across multiple machines. Similarly, traditional VC schemes cannot leverage distributed parallel computation across multiple machines for acceleration.

To tackle this issue, we introduce a new notion-distributed VC (DVC), which allows multiple machines, each holding only a subvector of the input vector, to collectively commit to the entire vector and generate position proofs in a distributed manner. To the best of our knowledge, there is no prior work on DVCs and no existing work can trivially derive an efficient DVC scheme. The key challenge is that both commitments and proofs depend on the entire vector, while no single machine holds the complete vector in distributed settings.

We propose the first DVC scheme, HLE-DVC, which leverages M machines to process the distributed vector v of length N in parallel, with each machine holding a subvector of length N M . HLE-DVC achieves compact proof size-O(log M) and allows each machine to generate all its position proofs in a single communication round, with communication cost O(log M) and computation cost O( N log N M ). Moreover, HLE-DVC supports batch proving, proof aggregation, and efficient updates. We conduct the experiments and open-source the code. Using 256 machines to generate all proofs for a committed vector of length 2 30 takes 17,515 seconds. This achieves a 256× parallel speedup over HLE-DVC on a single machine, and is 142× faster than Hyperproofs (a famous single machine VC scheme). The communication cost per machine is 0.768 KB.