A Vector commitment (VC), first defined by Catalano and Fiore, allows one to commit to a sequence of values and later on reveal (open) one or many values at a specific position and prove the opening consistent with the initial commitment. Vector commitments are used to trade off storage (all values in a vector vs. one commitment) for bandwidth (taken up to reveal values and prove them). This means that the commitment and the proofs of opening should have a reduced size.
Known constructions of VC either need some public parameters generated by a trusted setup, or they rely on controversial intractability assumptions. The VC schemes avoiding new assumptions and trust requirements have another drawback: they do not achieve constant-size opening proofs. Ideally, we would like to construct VC schemes that have the minimal public parameters size and that allow opening a committed vector at a set of positions with an opening of size independent of both the vector’s length and the number of opened positions.
The solutions proposed for this RFP will address our published open problems on Vector Commitments with Applications to Proof of Space. Please review the problems in detail for requirements and constraints.
The goal of this RFP is to stimulate improvements to the Vector Commitment constructions used in Filecoin and other Web3 protocols. We are funding research that addresses any of the five Open Problems listed in the above Open Problem Statement:
- Problem 1: Augmented Aggregation for SVC
- Problem 2: Functional Vector Commitments
- Problem 3: Improving Merkle Tree Openings
- Problem 4: Updatability Property for SVC
- Problem 5: Assumptions and Algebraic Settings for VC
Successful applications will include an explicit formulation of the objectives they propose to deliver, a description of the use-cases for which their solution is optimized, and a description of how the performance or correctness of the solution will be demonstrated and evaluated relative to the current state-of-the-art.
Solutions (or impossibility results) should take the form of a scientific paper or technical report. Additional follow-on funding is available to support the preparation of submissions to open-access journals and conference proceedings, including travel and presentation costs.
Rolling: we will be reviewing applications in batches corresponding to calendar months. The call will close on August 30, 2021 or earlier if awarded.
We expect the technical depth of the work to be at the level of a researcher in the field or a graduate student. We suggest that a team of one PI and one PhD part-time for 9-12 months or one PI and one postdoctoral researcher part-time for 6-8 months is appropriate for most problems.
Applicants may build a collaborative project with researchers from multiple institutions if desired.
- Recommended expertise: Mathematicians and/or Computer Scientists familiar with Applied Cryptography, Codes, Information Theory, Public Key Cryptography
Up to $50,000 USD per proposal. Possibility of up to 20% paid in FIL.
60% upon award and 40% on completion (adjustable to accommodate institutional requirements).
Anca Nitulescu (@ninitrava) and Luca Nizzardo (@lucaniz). We encourage you to reach out to research-grants@protocol.ai if you are considering applying or have any questions.
Submit your proposal using our application management system at https://grants.protocol.ai/.
**Results are to be released as open source under the Permissive License Stack (Dual License Apache-2 + MIT).