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

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

https://grants.protocol.ai/

The Protocol Labs Research Grant Program aims to both support collaborative work on problems defined by the broader research community and drive progress on clearly scoped research projects critical to our work at Protocol Labs. We encourage proposals aligned with PL's mission to drive breakthroughs in computing to push humanity forward, and we welcome unique perspectives and diverse backgrounds.

grants.protocol.ai

Research Scientist, CryptoNetLab

Protocol Labs drives breakthroughs in computing to push humanity forward. Protocol Labs is a product-development lab, but behind the protocols and tools we build, behind the research and implementations, are passionate people, teammates and community members. Most teams in the Protocol Labs Network are fully distributed and work remotely around the world.

boards.greenhouse.io

Event Schedule

Vector commitments are powerful primitives that find applications in many blockchains protocols. The goal of this workshop is to survey the state of the art in research in Vector Commitments with survey talks, the presentation of recent breakthrough results and discussions about the important open problems, and how they are motivated by practical applications.

cryptonet.vercel.app

Cryptographic Frontier 2022

Workshop on Open Cryptographic Problems in Decentralized Computation

sites.google.com

Completed Projects

RFP-010 Projects

Exploration Projects