Minimize memory footprint & improve solving time of constraint systems

[gbotrel]

Following this PR #549 from @ZhAnGeek ;

Problem

We currently store R1CS / PlonK constraints in a "flat" manner, without leveraging 2 facts:

• many constraints have the same shape, and don't use all the wires or coefficients
• it's common in zk circuits (particularly large ones) to have a block of constraint that repeats itself (with different wires) many time.

Solution

@ZhAnGeek proposed to delimit, in circuit such repeating blocks with the API. Store the actual constraints once, and for subsequent calls, store some metadata (input, offset) to re-use the initial constraints.

There are couple of edge-cases to that (nested blocks, hints, logs, .. and "unpure" functions that may generate different constraints at each call).

Idea

Instead of storing a list of flat constraint, we would store constraint.Blueprint objects & meta objects (TBD).
For example with PlonK, a "mul gate" that just does xa * xb == xc, don't need to store qL, qR, qM, q0 and qC. These uint storage adds up and only doing constraint template could save (napkin calculation) up to 60% of memory for R1CS and 50% for plonk.

Here's where I'm right now. Note that this requires a major refactor of the frontend, but would benefits setup, prover, compile time significantly.

We introduce a new object constraint.Blueprint (or maybe constraint.Template) . A Blueprint exposes 2 functions; Compile(*ccs, meta) and Solve(*solution, meta).

During compile time, when we invoke blueprint.Compile(..) , it doesn't physically add new constraints to the constrain system, but just say to the cs "I need N new internal wires".

At solving time, this blueprint knows how to solve itself efficiently and directly contribute the solved values to the solution vector.

What's store in the builders, is a list of []meta. In the worst case scenario, if all constraints are unique and different, we will have as many blueprints as we have meta entries, making this proposition useless.
But in most cases, we will have a limited set of blueprints, and meta object just need to store the input wires (the coeff are stored in the blueprints, probably) and the number of internal variables created so far.

For lone constraints, like repeated mul or addition with same coeffs on the wires, this is useful on its own.
For blocks (like hash function permutation calls) that repeats thousands of time, this is super useful.

Since the blueprint logic is mostly implemented in functions, this is memory on the stack -- when setup needs to iterate on the constraints, we actually never need to store all constraints in memory.

Impact of this would be quite large -- need to figure out hints, logs, debug info, commitment wires... But overall I think it works, allows for nested blueprints, and... probably custom gates for plonk.

Also, blueprint + meta is enough info for the level builder; input wires --> dependency of this block of constraints. Output wires (determined by the offset we stored) --> output. So go routines could be handled in a smarter way in the solver, which is good.

API Proposition

instead of calling

permutation(input1, input2)

do something like:

// mimc hash function
// ...
api.Compiler().Invoke(permutation, input1, input2)
// ...

[ WIP to be continued ]

Ideas:

• Invoke() can speed up compile time; when frontend.Compile hits it the 2nd time, it's almost a no-op
• constraint templates / block could store an extra bit of information for the solver; how to solve it. That would speed up solving time / proof generation time.