In this talk I will present the notion of vector commitments, give an overview of the state of the art in this area, and cover some of the recent efficient constructions. I will also discuss applications and open problems.

In this talk we will present some theoretical and practical contributions to algebraic vector commitments. From a theorical point of view, we propose a framework adopting Linear Vector Commitments (LVC) [LaiMal19] as a starting point for defining SVC with updatability and aggregation properties. In particular we show how LVC with minimal properties can be boostrapped to obtain stronger ones.

A succinct non-interactive argument of knowledge (SNARK) allows a prover to produce a short proof that certifies the veracity of a certain NP-statement. In the last decade, a large body of work has studied candidate constructions that are secure against quantum attackers. Unfortunately, no known candidate matches the efficiency and desirable features of (pre-quantum) constructions based on bilinear pairings. In this work, we make progress.

In this work we present techniques for opening/proving knowledge of subvectors of algebraic vector commitments. First, we present combinatorial techniques for proving opening of an algebraic commitment generalizing previous results (Hyperproofs). The techniques are generic and can be instantiated using any proof of knowledge of opening of a commitment. We consider (1) a transparent instantiation based.

We present a new compiler for efficient vector commitments. By taking as input any vector commitment that is updatable, aggregatable, and has O(nlogn) time to open all proofs, our compiler can produce another vector commitment that balances, with the help of bookkeeping, the time complexity between UpdateAllProofs() and Aggregate(). More specifically, the produced vector commitment requires O(√nlogn) time.

Vector commitments (VCs) allow one to commit concisely to an ordered sequence of values, so that the values at desired positions can later be concisely and verifiably revealed. In addition, a VC can be statelessly updatable, meaning that commitments and proofs can be updated to reflect changes to individual entries, using knowledge of just those changes (and not the entire vector). To date, there have been relatively few post-quantum constructions.

Are Merkle trees a panacea? In this talk, I argue they are not and present several tree-based vector commitments that offer interesting trade-offs when compared to Merkle’s classic construction. First, I will cover previous work on tree-based VCs from polynomial commitments and lattices. Unlike Merkle trees, these constructions have a combination of smaller proof sizes, useful homomorphisms and more efficient proof aggregation.