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.

Lookups for SHA (offboarding doc)

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.