What are SNARKS

SNARK stands for Succinct Non-Interactive ARgument of Knowledge. Assume that a party (usually referred as the Prover) holds a public input $x$ and a secret input $y$ (sometimes referred as the witness). The goal of the Prover is to convince the Verifier (who knows $x$) that he knows y such that $z=F(x,y)$ for a certain computation F. To that extent the Prover creates a “certificate of correctness” of the computation which is sent along with the result $z$.

Such a proof is therefore “Non-Interactive”. The Succinctness property refers to the fact that the proof should be much shorter than the length of the inputs and a description of the function $F$. Theoretically speaking one wishes the size of the proof to be sublinear in those parameters, with logarithmic and/or constant size proofs being of course preferred. In cryptography, a proof is usually referred as an Argument, if it is only computationally convincing (in other words it is possible but computationally infeasible to produce false proofs).

SNARKs in Filecoin

Currently in Filecoin SNARKs are used to “compress” or “aggregate” the openings of subvectors in a vector commitment (VC). The SNARK currently used for this task is the Groth16 one, which is general purpose, meaning that it can handle arbitrary computations $F$ (encoded as a circuit). The VC is currently implemented via a Merkle Tree.

There are two proofs where SNARKs are used. In ProveCommit the function $F$ takes as public input the root of the Merkle Tree and the indices of the subvector to be opened. The private input is the subvector and the seed used to generate the incompressible encoding. The function verifies that the Prover knows the correct subvector and all its Merkle Tree openings, and that this subvector is the output of a particular incompressible encoding. In WindowPost the function F only verifies the opening of the subvector.

Goal

The goal of this project is to build a “better SNARK” for Filecoin. In its most general form the problem is to reduce the overhead of creating the proofs needed for ProveCommit and WindowPost. Currently the commitment of a single sector requires 10 SNARKs due to the large size of the circuit (with one of the bottlenecks being the trusted generation of a large set of public parameters in the Groth16 proof).

Question: Can we design a SNARK with lover overhead for such large circuits

This general, somewhat vague question, can be refined into more specific objectives directly connected to the FileCoin protocol needs. Given the discussion above, the question of what is a “better” SNARK for FileCoin seems to be intrinsically connected to the type of VC and incompressible encoding that is used. The research directions listed below will therefore consider a combination of approaches in the design of VC, PoRep and SNARKs.