- 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).
A distributed storage network based on a blockchain mechanism, where users can provide storage capacity for the network, and thereby earn rewards by periodically producing cryptographic proofs that certify that they are honest.
A distributed ledger-based payment system where neither validators of transactions, nor cryptocurrency users do not need to store the full ledger state.
A system that allows to publicly and efficiently verify the correctness of low-complexity queries on a large dataset stored by an untrusted third-party.
Projects
DRI: Anca Nitulescu
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
[BBF19] Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, by D. Boneh, B. Bünz, B. Fisch, in CRYPTO'19,
[CDHK15] Composable and Modular Anonymous Credential, by J. Camenisch, M. Dubovitskaya, K. Haralambiev M. Kohlweiss, in ASIACRYPT'15,
[CF13] Vector Commitments and their Applications, by D. Catalano, D. Fiore, in PKC'13,
[CFG+20] Vector Commitment Techniques and Applications to Verifiable Decentralized Storage, by M. Campanelli, D. Fiore, N. Greco, D. Kolonelos, L. Nizzardo, in ASIACRYPT'20,
[GRWZ20] Pointproofs: Aggregating Proofs for Multiple Vector Commitments, by S. Gorbunov, L. Reyzin, H. Wee, Z. Zhang, in CCS'20,
[KZG10] Constant-Size Commitments to Polynomials and Their Applications, by A. Kate, G. Zaverucha, I. Goldberg, in ASIACRYPT'10,
[LY10] Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs, by B. Libert and M. Yung, in TCC’10
[LM19] Subvector Commitments with Application to Succinct Arguments, by R. W. F. Lai, G. Malavolta, in CRYPTO'19,
[PSTY13] Streaming Authenticated Data Structures, by Papamanthou, Shi, Tamassia, Yi, in EUROCRYPT'13
[TAB+20] Aggregatable Subvector Commitments for Stateless Cryptocurrencies, by Tomescu; Abraham, Buterin, Drake, Feist, Khovratovich, in SCN’20
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).
Completed Projects
Project 1: Linear-map Vector Commitments
People: Matteo Campanelli, Anca Nitulescu (DRI), Carla Rafols, Alexandros Zacharakis, Arantxa Zapico
Goal: This project explores multiple directions in the area of VC:
- constructing new VC from existing trusted setup
- extending VC to prove not only subvector openings but any linear-map function on the initial vector called LVC
- new unbounded aggregation for LVCs and homomorphic openings
- giving a generic framework for building such LVCs in the pairing-based setting
- new efficient construction for inner product openings with these properties
- new tree-based VCs that can be instantiated with any LVC and offer good trade-offs for space/time
Talk:
Project 2: Linkable Vector Commitments
People: Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Mark Simkin
Goal: A linkable vector commitment scheme allows one to prove in zero-knowledge that a committed value is contained in a public vector commitment. For a vector commitment of size N, we achieve O(log(N)) online prover time assuming O(N log(N)) preprocessing and O(N) storage.
This project explores solutions to some possible applications:
- in anonymous credentials to avoid SNARKs and Merkle tree
- to multi-position opening where we have a single compact commitment cm to all evaluations hiding the indexes as well
- provable look-up table search to prove that the values in a VC are all in a look-up table
- for PoS we can have a commitment to the indexes in a set one published as a challenge and then, the prover can use it to open and the verifier will only need to trust this commitment cm and efficiently check the opening with respect to it
- an index-hiding VC could be used to do a “vector opening” version of the “set membership” work in here
Talk: 🎥 Speaker Arantxa Zapico
Project 3: Trade-offs for Opening Proofs
People: Anca Nitulescu (DRI), missing member with implementation skills
Goal: Finding a way to trade time for space when it comes to opening commitments.
Describe what properties for VC are needed for Big Data with small computations.
How can we make the prover more efficient by storing specific information (in Merkle Trees this is the top of the tree).
Solution: We introduced Muppets, two novel maintainable VC constructions that can be instantiated from any underlying VC scheme with homomorphic proofs. Muppets achieve a stronger, more flexible form of maintainability: they allow to arbitrary tune the memory used to save on the opening time.
One construction is based on multivariate polynomials, the other on univariate polynomials:
- Multivariate construction (generalisation of Hyperproofs):
- we allow for any arity for the trees
- the leaves can be commitments from any VC scheme
- The univariate construction:
- only for binary trees
- reusable setup: powers of tau
- the memory/time tuning can be decided by the prover on the fly
Points of improvement: Aggregation/subvector openings are made via Inner-Pairing Arguments
Status: waiting for implementation
Project 4: Commit-and-Prove SNARKs
People: Anca Nitulescu, Matteo Campanelli (DRI)
Goal: Finding a way to combine Commit-and-Prove SNARKs with Vector Commitments. Can we design a SNARK that is compatible with initial inputs committed under known VC schemes?
Construct a more efficient such protocol tailored for the relations to be verified in the Proof of Space used by Filecoin.
Solution for accumulators: https://eprint.iacr.org/2021/1672.pdf
Status: in progress
RFP-010 Projects
Team 1: Tree-based VC
Grantees: Charalampos (Babis) Papamanthou (IP), Weijie Wang
Institution: Yale University
Description: This project focuses on tree-based vector commitments.What distinguishes tree-based vector commitments from other vector commitments is the fact that all proofs can be updated/maintained in sublinear time, whenever an element of the vector changes. However, due to this convenience, other challenges arise that we plan to investigate as part of this proposal. For example, it is typically hard to provide aggregation in tree-based vector commitments (e.g., Merkle tree proofs cannot be naturally aggregated) and verification of aggregated proofs can be expensive.
Directions:
(a) tree-based commitments based on multilinear trees;
(b) tree-based commitments based on RSA groups;
(c) tree-based commitments based on lattices.
Team 2: Discrete-log VC
Grantees: Carla Rafols (IP), Alexandros Zacharakis
Institution: Universitat Pompeu Fabra
Description: This project focuses on vector commitments in the discrete logarithm setting.
While the discrete logarithm setting is limited, because it does not allow to exploit key structure, it remains quite interesting to explore the problem in this setting for the following reasons:
- DLog cryptographic assumptions are clean, extensively studied, and well-understood,
- The arithmetic in this setting is more efficient, which could lead to more efficient constructions,
- techniques in this setting will probably work in other settings that generalize the discrete logarithm setting, most notably bilinear groups.
Directions: In this project the grantees investigate what subsets of the desired properties of vector commitments can be achieved in the discrete logarithm and with what efficiency. They will use both known techniques mainly inspired from the succinct argument literature, as well as explore new techniques to tackle the problem. Furthermore, the project will explore more restricted scenarios such as designated verifier and distributed trust that can be of practical importance for applications where fully public verifiability is not necessary.
Status: in progress
Team 3: Lattice-based VC
Grantees: Russell Lai, Sri Aravinda Krishnan Thyagarajan, Martin Albrecht, Giulio Malavolta
Institutions:
- Friedrich-Alexander University Erlangen-Nuremberg,
- Royal Holloway - University of London,
- Max Planck Institute for Security and Privacy
Description: This project focuses on lattice-based vector commitments.
Being “lattice-based” allows for some advanced functionalities and, critically, enables potentially post-quantum secure constructions. In particular, utilising the flexibility offered by lattices, the team aims for the first direct construction of any vector commitment with functional openings for any constant-degree polynomial. Moreover, to the best of our knowledge, this would be the first example of a lattice-based vector commitment beyond positional openings (for which there are “trivial” constructions from Merkle trees).
Directions: The proposed construction is likely to only be shown secure against a new family of lattice-based assumptions, which are natural extensions of the short integer solution (SIS) assumption. This family is called the k-Ring Inhomogenous Short Integer Solution assumptions. Such assumptions offer additional algebraic structure, which allows to transfer techniques for pairing-based cryptography to the lattice world.
Team 4: Functional VC
Grantees: Dario Fiore, Dimitris Kolonelos, Dominique Schroder, Hien Chu
Institutions:
- IMDEA Software Institute, Madrid, Spain
- University of Erlangen-Nürnberg, Germany
Description: This project focuses on building functional commitments for a larger class of functions.
In functional commitments, an opening not only discloses single vector entries but can also be used to open a function of the committed vector, still in a concise manner. While there exist several realizations of vector commitments under different assumptions and with a variety of efficiency measures, less is known about functional commitments of which only a few schemes are known.
Exploration Projects
VC for Proof of Retrievability
People: Irene Giacomelli (DRI), Anca Nitulescu, Matteo Campanelli,
Description: Proofs of Retrievability (PoRs) are protocols which allow a client to store data remotely and to efficiently ensure, via audits, that the entirety of that data is still intact. A dynamic PoR system also supports efficient retrieval and update of any small portion of the data.
Further features require reducing the amount of client extra storage, the computation as well as the communication bandwidth, or allowing public verifiability.
The state of the art in Proofs of Retrievability schemes consists of two types of approaches:
- schemes with low audit cost but a high storage overhead
- schemes with a low storage overhead but high computational cost during audits
Goal: The goal is to understand how can we use vector commitments other than Merkle trees for PoR and to find the best tradeoff for PoR schemes between the amount of extra storage and the cost of performing audits.
Next readings: https://hal.archives-ouvertes.fr/hal-02875379v4/document
Status: to be started
Verkle Trees
People: Nicolas Gailly (DRI)
Description: Verkle Trees, inspired by Merkle Trees, allow to commit to vectors in a bandwidth-efficient way. Verkle trees are kary trees that use Vector Commitments rather than cryptographic hash functions to construct a parent node from its k children: the parent is just a Vector Commitment to its children.
Goal: Explore Verkle Trees, as an alternative to Merkle Trees to get faster proving time for Filecoin proofs.
Directions: In general, finding ways to efficiently verify many Verkle opening proofs within a proof system. A first direction is to use the Halo2 proof system by leveraging the recursive gadget which can verify additional openings proofs with a low extra cost.
Challenges: Finding efficient recursion paradigm that fits the Verkle tree setting by verifying opening proofs. For Halo2, implementation is the most challenging part.
Status: on pause, waiting on the recursion gadget to be deployed.
Structure-Preserving VC
People: Rosario Gennaro (DRI), Luca Nizzaro, Matteo Campanelli, Dario Catalano, Dario Fiore
Goal: Construct a scheme that is Structure-preserving Multi-layer VC. These have the property that the committed value is in the same algebraic structure (e.g. group) as the inputs.
More on the layered setting: We commit to different vectors at different levels, so we have many different commitments per layer. The commitments at the layer above are “output” elements (e.g. group elements) that need to be mapped back to input elements (e.g. field elements) in order to be committed to at the next layer.
Directions: Formally define what properties are needed for this batchable hash output to input setting.
Understand if this is realizable just using algebraic/homomorphism/other properties?
Or use a “lightweight” or “ad-hoc” SNARK to prove inclusion (e.g. correctness of the mapping)
Challenges: Is it possible to find a mapping that facilitates the aggregation of the opening proofs at the level above?
Status: dropped