Vector Commitment Research
📏

Vector Commitment Research

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

🛠
Vector Commitments are powerful primitives that find applications in:
Proof of (Persistent) Space (PoS)

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.

Stateless Cryptocurrency

A distributed ledger-based payment system where neither validators of transactions, nor cryptocurrency users do not need to store the full ledger state.

Verifiable Small Computation on Big Data

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.

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 of opening proofs
  4. transparent setup to generate public parameters
💡
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
image

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

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.

image
image

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

🎓
Grants
💼
Open Positions
Events

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

  1. constructing new VC from existing trusted setup
  2. extending VC to prove not only subvector openings but any linear-map function on the initial vector called LVC
  3. giving a generic framework for building such VCs in the pairing-based setting
  4. new efficient construction for inner product openings
  5. new unbounded aggregation for VCs with homomorphic openings
  6. new tree-based VCs that can be instantiated with any LVC and offer good trade-offs for space/time

Status: in submission

Project 2: Linkable Vector Commitments

People: Mary Maller, Anca Nitulescu, Arantxa Zapico

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:

  1. in anonymous credentials to avoid SNARKs and Merkle tree
  2. to multi-position opening where we have a single compact commitment cm to all evaluations hiding the indexes as well
  3. provable look-up table search functionally to prove that the values in a VC are all in a look-up table
  4. 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
  5. an index-hiding VC could be used to do a “vector opening” version of the “set membership” work in here

Project 3: Trade-offs for Opening Proofs

People: Anca Nitulescu (DRI), Matteo Campanelli

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

What are the equivalent possibilities in constant-size vector commitments?

Status: in progress

Project 4: VC for Proof of Retrievability

People: Anca Nitulescu (DRI), Matteo Campanelli, Irene Giacomelli

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.

Status: to be started

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.

Status: in progress

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:

  1. DLog cryptographic assumptions are clean, extensively studied, and well-understood,
  2. The arithmetic in this setting is more efficient, which could lead to more efficient constructions,
  3. 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.

Status: in progress

Team 4: Functional VC

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.

Directions:  This project aims at studying the foundations of functional commitments with a particular focus on the computational assumptions and the minimal efficiency measures needed to build schemes for linear functions and more.

Status: in progress

Exploration Projects

Commit-and-Prove SNARKs

People: Anca Nitulescu (DRI), Matteo Campanelli

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: not started yet

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

Exploration Projects

Commit-and-Prove SNARKs

  • People: Anca Nitulescu (DRI), Matteo Campanelli
  • 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: not started yet

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