How to make circuits practical with 200 challenges.

[porcuquine]

[dev-investigate][1] How to make circuits practical with 200 challenges. @porcuquine

[nicola]

Problem: Circuits for PoRep are really large

• Open question: Param generation are taking a long time?
• Open question: Param size might be too large?
• Open question: What is an acceptable size of parameters?

Solutions: Say that this is a real problem. How do we go around it?

1. Status quo: We keep them as they are, the accept large params and proving time
2. Accumulators: We replace merkletree with the accumulators
   • Gives 40x reduction in constraints
   • Gives memory requirements are half
   • Ben is working on a new version of accumulators based on Wesolovsky VDF
   • Might take a long time
3. Aggregation: Splitting circuits in multiple parts and aggregate these multiple parts with snarks Discussing Geppetto solution to aggregate challenges #186
   • Take a large circuit, split it; each subcircuit generates a snark; generate a snark of snarks!
   • This is only implemented in libsnark and might be complicated to implement in Bellman. However, we can mix and match bellman and libsnark: we use bellman for generating the snarks and we use libsnark to aggregate them
   • We don’t know how practical advantages this is gonna give us
4. Recursive composition
   • Take the parts of the circuit that gets repeated; create a circuit with the repeated part + snark verification circuit; recursively compose proofs
   • Complex to implement in bellman; cannot mix and match how to compose them
5. Hyrax: proof system that takes advantages of repeating subcircuits
   • It might be easy to implement a simple merkle tree in hyrax, but difficult to implement DRGPorep

[porcuquine]

#249 implements circuit-splitting, the low-tech way to ensure we can handle 200 challenges. This does mean proof size will grow, though.

[nicola]

• Notes from @lucaniz https://github.com/filecoin-project/research/issues/23
• ZExe paper implements bounded bootstrap https://eprint.iacr.org/2018/962.pdf

[nicola]

@porcuquine this is tagged as alpha, can we add it to the current work plan?

[porcuquine]

It's linked in #218 and attached to that epic in ZenHub. I removed the Alpha label. Did you want a new label too?

[nicola]

@dignifiedquire and I have a plan written here: https://github.com/filecoin-project/research/blob/master/meeting-notes/2018-11-15-future-proofs.md

[nicola]

Latest update (to be completed)

---

Making Poreps practical to prove

• Corollary problems: Large circuits have large parameters
• Note: Bellman supports up to ~200M constraints
• Current circuit size: 1-4B constraints (depending on soundness)

Practical solutions we are working on

1. Partitions: Reuse a small circuit many times

   • Current status: Most of this is implemented

     • Run this to get timing
     • Find max size of partition we can run
     • Implement tapered construction
     • Simulate this for this purpose

   • Pros:

     • Smaller parameters
     • Circuit can be done using bellman

   • Cons:

     • Bigger proof size min 1KB
       • 192byte * number of partitions, theoretical min 5 partitions, if we assume 200M per partition constraints
     • Proving time is still slow

2. Zexe: Same as partition, but batch the individual sub circuits

   • Current status: Waiting on SCIPR-lab for the code
   • Next steps:
     • Simulate proving time
     • Find optimal subcircuit size
     • Get the code
   • Pros:
     • Same as before
     • Proof size is ~200bytes
   • Cons:
     • Proving time is even slower
     • We can aggregate a max of 5000 sub proofs (of 200M each)
       • How do we find the number of subcircuits?
         • The bigger the subcircuit, the bigger the param for the subcircuit
         • The smaller the subcircuit, the bigger the param for the batching circuit, and the bigger the proving time
         • Perfect tradeoff is reducing sub circuit, batching circuit

3. DIZK TODO

4. Accumulators with revealing Q bits

   • Status: Dig is implementing it
   • Feasibility: NO
     • This proofs are too big for Filecoin
     • Would need to change consensus (ideally) OR,
     • Have much larger sector size
   • Next steps
     • Simulate circuit size
     • Simulate actual proving time
     • Simulate memory required for proving (note that accumulators require some extra memory)
     • Implement new circuit
     • Get exact parameters from Ben
     • Check with Filecoin throughput how bad would be to have much larger sectors (250-1TB) and larger proof sizes, maybe we are still fine
   • Pros:
     • Proving time is much cheaper (no merkle trees in snarks!) (probably the cheapest prover mechanism)
     • Small circuit size & smaller parameters
   • Cons:
     • Proofs are larger (250KB so far, could be smaller by reducing soundness)
     • Soundness is based on an heuristic of difficulty of hashing/bruteforcing for collisions

5. Recursive composition

   • Status: no one is working on, we don't have a curve to make this secure (yet! Coda is working on finding this curve)
   • Feasibility: unclear proving time
     • Complex to implement in bellman; cannot mix and match how to compose them
   • Next steps
     • Talk to Coda about progress on finding the curve (and using recursive composition in general)

Other Improvements

1. GPU SNARKs TODO

Experimental solutions we are exploring

1. Accumulators with circuits in SNARKs

   • Status: Open Problem
   • Feasibility: Unclear
   • Next steps
     • Wait on Ben to make this work
     • Explore solution of using SNARKs for the first half of accumulator verification
   • Pros:
     • Proving time (could be) cheaper
     • Circuit is small (a bit bigger than previous construction) & smaller parameters
     • Proof will be 200 bytes
   • Cons:
     • Unknown

2. Recursive composition

• Take the parts of the circuit that gets repeated; create a circuit with the repeated part + snark verification circuit; recursively compose proofs
• Complex to implement in bellman; cannot mix and match how to compose them

1. Hyrax: proof system that takes advantages of repeating subcircuits

• It might be easy to implement a simple merkle tree in hyrax, but difficult to implement DRGPorep

[mhammersley]

matching labels to info in Filecoin Research Prioritization List

[mhammersley]

updating pipeline status per research week

[MariusVanDerWijden]

I've written a poc implementation of fft's on finite elements for gpus at hackathon, which can be used to accelerate Snarks on GPU's.
can be found here: https://github.com/MariusVanDerWijden/gpusnark

[porcuquine]

Thanks, @MariusVanDerWijden. Have you tried (or do you want to try) to integrate this with Bellman? (cc: @dignifiedquire @stefandeml)

[MariusVanDerWijden]

Yes, I planned to integrate it with Bellman, since it uses the same fft algorithm afaik.