- What are Vector Commitments?
- Projects
- Applications and Challenges
- References
- Vector Commitments in Blockchain
- Vector Commitments in Proof of Space
- Vector Commitments in Stateless Cryptocurrencies
- Vector Commitments in Anonymous Payments
- Completed Projects
- Project 1: Linear-map Vector Commitments
- Project 2: Linkable Vector Commitments
- Project 3: Trade-offs for Opening Proofs
- Project 4: Commit-and-Prove SNARKs
- RFP-010 Projects
- Team 1: Tree-based VC
- Team 2: Discrete-log VC
- Team 3: Lattice-based VC
- Team 4: Functional VC
- Exploration Projects
- VC for Proof of Retrievability
- Verkle Trees
- Structure-Preserving VC

# 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).

**Proof of (Persistent) Space (PoS)**

**Stateless Cryptocurrency**

**Verifiable Small Computation on Big Data**

**Projects**

**DRI:** Anca Nitulescu

Muppets: Maintainable Updatable Tree-based Vector Commitments

**Applications and Challenges**

**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:

- aggregation of different opening proofs
- updatability of commitments and proofs
- homomorphism for commitments and for opening proofs
- transparent or universal setup to generate public parameters

- 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

## References

**Vector Commitments in Blockchain**

**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.**Proof of SpaceTime (Audit):**The verifier and the prover run a protocol in order to check that the prover stores the vector of data. This phase can be repeated many times.

A classical PoS protocol is based on **Merkle trees **and random spot-checks, recently generalized to work with Vector Commitments. A drawback of this construction is that proofs grow with the number of spot checks (and the size of the tree) and become undesirably large in some applications, e.g., if needed to be stored in a blockchain.

Combined with **Arguments of Knowledge of Subvector Opening (AoK)** with constant-size proofs, the properties of recent Vector Commitment schemes can lead to an efficient construction of Proof of Space for decentralized usages.

## Vector Commitments in Stateless Cryptocurrencies

Stateless Cryptocurrency are distributed ledger-based payment systems that use a blockchain in order to post and record peer-to-peer payment transactions where the nodes that store and check the transactions log do not need to store all the ledger state.

We call *validators *the nodes that participate in reaching consensus on what is the current state of the public ledger. To reduce the amount of storage required of validators, there have been solutions based on vector commitments: Instead of storing the entire ledger state, the validators can keep commitments to vectors representing the state.

The following properties from vector commitments are important for the stateless cryptocurrency application in order to provide the best trade-off between storage, bandwidth, and computation:

**Conciseness of Commitment:**validators store only a commitment to the ledger state.**Short Opening Proofs:**to submit a transaction, users will send their account balance values and a proof that this is consistent with respect to the commitments stored by the validators.**Efficient Verification:**to validate transactions, validators check opening proofs against the commitment.**Updatability:**after the transaction is accepted, the validators should be able to update the commitment to the old state to a commitment to the new state that includes the changes made by the transaction.**Aggregation:**to minimise communication in the transactions, some nodes can "pack" together multiple opening proofs for a batch of transactions into a single small proof.

## Vector Commitments in Anonymous Payments

Privacy-Preserving Cryptocurrency are decentralized anonymous ledgers that offer strong privacy guarantees: payment transactions do not contain any public information about the payment's origin, destination, or amount. The correctness of the transaction in currently known privacy-preserving currency protocols is demonstrated via the use of Merkle trees and zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs).

An alternative way would be by replacing the Merkle trees with vector commitments with special properties. In anonymous transaction, users first hide the private information of a coin, by hashing both the coin's value and the owner identity (secret key). Individual nodes maintain a Vector Commitment over all of the coin hashes indexed by the users public keys. Any user should then demonstrate ownership of a coin hash via an opening proof that does not reveal neither the secret key value, nor the public key of the user (index-hiding opening).

GrantsOpen Positions Events