Goal: Finding a way to combine Commit-and-Prove IOP-based SNARKs with Lookup arguments. Can we design a SNARK that is compatible with existing lookup arguments in the sense that the computation supported can be modeled as a (arithmetic) circuit supporting also lookup table gates.
Construct a more efficient such protocol tailored for the relations to be verified in the Proof of Space used by Filecoin, most notably for SHA computations.
Update March 23: The problem of lookups for SHA is still open. It’s currently frozen as a project since it requires more engineering than cryptographic effort. While it still has some level of uncertainty to its impact, it may be beneficial to reopen in the future.
Directions:
Understanding efficiency of linking lookup arguments and general-purpose SNARKs.
Here is a list of approaches to link lookup arguments such as Baloo with other general-purpose SNARKs. A difference between the approaches below and others, such as Plonkup and Plookup , is that the latter incur a larger overhead for the prover when performing lookup
- Linking Groth 16 transparently
- Pro: no additional setup
- Pro: can reuse optimized implementations of Groth16
- Con: communication complexity is logarithmic (several KB for lookups of order of thousands)
- Grolup: Groth16 with additional trusted setup and a CPLink
- Pro: only one additional G1 for linking
- Pro: can reuse optimized implementations of Groth16
- Con: additional setup to perform linking
- PLONK / Halo2 with KZG / Marlin / Lunar:
- General approach: proving that lookup wires consist of a subcommitment
- such a “subcommitment” proof typically consists of a single group element showing divisibility of a polynomial
- Pros:
- no new trusted setup required. Can use universal setup.
- very little overhead (add handful of group elements to proof)
Lookups for SHA Computations.
Can we achieve better efficiency if we move to a descriptions of SHA based on lookups? We are studying its viability for Filecoin.