Vector Commitments Effort

A high-level description of our work on Vector Commitments

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.

Primer - Vector Commitments

Applications and Challenges

Where are we at?

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 of opening proofs

- 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

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

Filecoin: Commitments to Storage

Current Solution: Merkle Trees

Next: New VC Compatible with SNARKs

Vector Commitments in Filecoin

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.

Collaborate with us

Upcoming Events

Research Resources

Block Validation in Distributed Ledger

Solution based on Vector Commitments

Property: Updatability

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.

Collaborate with us

Upcoming Events

Research Resources

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

Collaborate with us

Upcoming Events

Research Resources

Current Endeavours

We work on important problems in the area:

Linear-Map VC
Index-Hiding VC
Survey of VC
Trade-off for Provers

RFP-010 Projects

We support academic research projects focussing on building better VC.

Team 1: Tree-based VC
Team 2: Discrete-log VC
Team 3: Lattice-based VC
Team 4: Functional VC

Explorations

We explored some directions in the past and we have some new ideas for what to look at next:

VC Commit-and-Prove SNARKs
Structure-Preserving VC
Verkle Trees

Current Projects

Project 1: Linear-Map Vector Commitments

People: Matteo Campanelli, Anca Nitulescu (DRI), Carla Rafols, 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
giving a generic framework for building such VCs in the pairing-based setting
new efficient construction for inner product openings
new unbounded aggregation for VCs with homomorphic openings

Status: ongoing

Project 2: Index-Hiding Vector Commitments

People: Mary Maller (DRI), Anca Nitulescu, Arantxa Zapico

Goal: A new method to evaluate a polynomial commitment C to a Pedersen commitment cm such that C opens to z at index i. Importantly we do not reveal the coordinate i or the evaluation z.

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 functionally 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

Status: in progress

Project 3: Survey of Vector Commitments

People: Rosario Gennaro(DRI), Anca Nitulescu, Alin Tomescu, Babis

This project aims at publishing a SoK on VC

Starting point: here

Status: in progress

Project 4: Trade-offs for Opening Proofs

People: Anca Nitulescu (DRI), Matteo Campanelli

Goal: Space-Time Matter!

Finding a way to trade time for space when it comes to opening commitments.

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

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:

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.

Status: in progress

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.

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

Project on 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

Project on 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 k-ary 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.

Project on 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

Page updated

Report abuse