What are Vector Commitments?

Vector commitments (VC) allow to commit to a sequence of values and later only reveal (open) one value at a specific position and prove that the opening is consistent with the initial commitment. Moreover, Vector Commitments with subvector openings (SVC) enable to open a committed vector at a set of multiple positions. This is done with reduced overhead, both in communication and for the verification time. Vector commitments are used to trade off storage (all values in a vector vs. one commitment) for bandwidth and computation (communication needed to open values and effort to verify these openings).

<aside> 🛠 Vector Commitments are powerful primitives that find applications in:

• Proof of (Persistent) Space (PoS)
• Stateless Cryptocurrency
• Verifiable Small Computation on Big Data </aside>

Projects

DRI: Anca Nitulescu

Muppets: Maintainable Updatable Tree-based Vector Commitments

Caulk: Lookup Arguments in Sublinear Time

https://docs.google.com/presentation/d/14c80YAfP5_Gl2EIegNEdktGIFPkExc4fzaEtFkBcLzU/present?slide=id.gfb5a0ed566_6_0

Applications and Challenges

Known constructions of VC have proof sizes either constant or logarithmic in the size of the vector. They rely on various assumptions, such as bilinear groups, RSA or class groups, hash functions and lattices. Some important properties for VC schemes are:

1. aggregation of different opening proofs
2. updatability of commitments and proofs
3. homomorphism for commitments and for opening proofs
4. transparent or universal setup to generate public parameters

<aside> 💡 Ideally, we would like to construct VC schemes that have:

• minimal public parameters size, with minimal trust requirement on their generation
• efficient proof generation (or time-space trade-offs) and efficient verification
• proof-size independent of both the vector’s length and the number of opened positions </aside>

References

Vector Commitments in Blockchain

Vector Commitments in Proof of Space

Proof of Space (PoS) protocols allow a client to verify that a server is storing intactly a file via a short communication challenge-response protocol.

A decentralised storage system, such as Filecoin uses a public blockchain for the challenge-response in order to realise the PoS in two steps:

• Proof of Replication (Initialisation): The data is encoded as a vector of random values (replica) and a commitment to this vector is created. The vector is stored by the prover, while the verifier knows only the commitment.