Frontend refactoring

[ThomasPiellard]

This PR is a long overdue, it cleans up the way the plonk constraint system is added, and makes the code upgradable for different new constraint systems (custom gates, generalised arithmetic circuits, square constraints, etc).

Architecture

The frontend is now organised like this:

frontend/
├── compiler
├── cs
│   ├── plonk
│   └── r1cs
└── utils

frontend/

api.go provides the API interface that a constraint system should implement (with the usual fonctions like Add, Mul, etc). It also provides an interface System with inherits from API, and provides the fonctions

type System interface {
	API
	NewPublicVariable(name string) Variable
	NewSecretVariable(name string) Variable
	Compile(curveID ecc.ID) (compiled.CompiledConstraintSystem, error)
}

circuit.go provides the interface that a circuit should implement (as before).

compiler/

compile.go provides the logic to build a constraint system to its target form (r1cs or sparse r1cs). It provides the same function Compile as in develop. The difference is that buildCS has been renamed bootStrap and takes as parameter the System interface. It acts exactly as in develop, recursively instantiating the inputs and calling Define afterwards.

cs/

cs.go provides the common data shared by each constraint system:

type ConstraintSystem struct {
	compiled.CS

	// input wires
	Public, Secret []string

	CurveID ecc.ID
	// BackendID backend.ID

	// Coefficients in the constraints
	Coeffs         []big.Int      // list of unique coefficients.
	CoeffsIDsLarge map[string]int // map to check existence of a coefficient (key = coeff.Bytes())
	CoeffsIDsInt64 map[int64]int  // map to check existence of a coefficient (key = int64 value)

	// map for recording boolean constrained variables (to not constrain them twice)
	MTBooleans map[int]struct{}
}

It is essentially a list of coefficients, to be affected to wires, it is agnostic of the constraints. It inherits from CS defined in package compile.

r1cs/, plonk/

Those folders contain the actual instantiation of plonk constraint systme and Groth16 constraint system (respectively sparse_r1cs and r1cs in our naming).

r1cs/ contains the same api as in develop, the files were merely moved from frontend/ to r1cs/.
'plonk/' contains the equivalent data but for sparseR1CS. In particular an api.go has been created for handling plonk constraints, so there is no longer a conversion from r1cs to sparser1cs.

Both constraint systems inherit from ConstraintSystem, with an additional field which is the slice of the actual constraints (ex:

type SparseR1CS struct {
	cs.ConstraintSystem

	Constraints []compiled.SparseR1C
}

).

In both r1cs/ and plonk/ there is a conversion.go file providing a Compile function which essentially shifts the IDs of the variables in the logs, etc after a circuit is built. This function is internally called by Compile defined in frontend/compiler/compile.go.

API breaking changes

• frontend.Compile --> compiler.Compile
• type Hint struct {ID hint.ID , Inputs []Variable}--> type Hint struct {ID hint.ID, Inputs []interface{}}

Status

Tests pass, except the circuits_stats tests for several of the circuits used in integration tests have been extended to cover more cases. There is no change in Groth16 in terms of number of constraints (Groth16 logic hasn't been modified at all, the files were merely moved around).

[gbotrel]

not sure it makes sense to move that in a separate package; it adds API breaking change for all existing circuits, but the logic is not living in this new package anyway.

I suppose it was made this way to avoid import cycles??

[ThomasPiellard]

Yes 😁

[ivokub]

I have refactored the branch a bit more.

I reverted the move of Compile function into a sub-package. In addition, I added two registries:

• a registry for frontend -> compiler mappings.
• a registry for backend -> frontend mappings.

Now, when someone wants to add (or even use their internal backend), it is possible to use a gnark compiler without having to change the library. Similarly, it is possible to define a new compiler (a frontend actually as every frontend can have only a single compiler).

This has a small side-effect though -- as the registrations are performed lazily in inits (due to needing to avoid the import cycles), then in strange workflows the compilers won't be registered and compilation will fail (for example, when compiling a circuit without later proving or verifying it). I tried making the corresponding errors quite explanatory so that the user would know what to do.

There are still tons of things to do (and I would actually split some stuff into smaller PRs), for example:

• fix failing tests (they were failing locally even before my additional refactoring)
• make API smaller by moving out frontend-independent methods
• move frontend debugging stuff out
• bring back compiler options (they were already lost in the PR)

Does this API make sense? I'll move on polishing it more.

[gbotrel]

@ivokub I think this is not the best solution -->

then in strange workflows the compilers won't be registered and compilation will fail (for example, when compiling a circuit without later proving or verifying it).

--> I think this may happen quite often (use of the backend or the frontend independently), typically in dev cycles or serializing only the compiled circuit.

I don't see why the backend should know which frontend it "accepts". That limits gnark extensions; if someone wants to write a new R1CS frontend, suddenly they can't use our backend/groth16 package.

my proposition is essentially:

1. rename / move System in frontend/cs/ to frontend/Builder
2. have frontend/cs/r1cs and frontend/cs/plonk declare a public

func Builder(curveID ecc.ID) frontend.Builder {
	return newR1CS(curveID)
}

package level function. + public R1CS struct, all the rest, package private.

(or wrap it as you did in another function if you want to manage errors)

3. have the frontend.Compile signature change to:

func Compile(circuit Circuit, builder Builder, ...)

so that the caller code looks like

frontend.Compile(&circuit, r1cs.Builder(ecc.BN254)) 

I think it was a mistake to put the zkpID (backend.ID) in frontend.Compile in the first place; you can build a R1CS in different backend, so it makes no sense semantically to tie it to backend.GROTH16.

I started a branch (refactor-flexible-compiler) that did that, but can't finish tonight. You can pick it up or throw it away and come w/ a better approach :) . I stopped when I realized that the APIs of the assert.ProverSucceeded... assumed such a 1-1 mapping between frontend and backend, and that we need to think this through --> the testing package will need to know which pair of frontend / backend you want to test with. We can provide a default mapping, but I assume we need new TestOptions to allow users to supply their own backend / frontend .

[ivokub]

@ivokub I think this is not the best solution -->

then in strange workflows the compilers won't be registered and compilation will fail (for example, when compiling a circuit without later proving or verifying it).

--> I think this may happen quite often (use of the backend or the frontend independently), typically in dev cycles or serializing only the compiled circuit.

It was not a fatal error - due to lazy registration the compiler does not get registered if it is not explicitly imported by anything. Adding a blank import (import _ "github.com/consensys/gnark/frontend/cs/r1cs") fixes the compilation.

I don't see why the backend should know which frontend it "accepts". That limits gnark extensions; if someone wants to write a new R1CS frontend, suddenly they can't use our backend/groth16 package.

But there is a dependence between a backend and a constraint system? Any Groth16 backend requires R1CS and PLONK backend requires SparseR1CS. Right now we have the constraint system (i.e. a list of constraints) and a circuit->CS compiler coupled. A backend does not necessarily require a specific compiler, but it still requires a specific CS.

In my branch the built-in backends register default compilers themselves. It would make sense to add a compile option to pick a particular compiler.

my proposition is essentially:

1. rename / move System in frontend/cs/ to frontend/Builder
2. have frontend/cs/r1cs and frontend/cs/plonk declare a public

func Builder(curveID ecc.ID) frontend.Builder {
	return newR1CS(curveID)
}

package level function. + public R1CS struct, all the rest, package private.

(or wrap it as you did in another function if you want to manage errors)

What about separating the CS and compilers? This means having structure:

• frontend/ -- user API, generic Compile which uses registry for picking compiler, compilation options
• frontend/cs/ -- your Builder, definitions of R1CS and SparseR1CS structures
• frontend/compiler -- built-in compilers for compiling circuits into R1CS and SparseR1CS. Every compiler has New (rename?) variable of type Builder so that the compiler can be called bypassing the registry

3. have the frontend.Compile signature change to:

func Compile(circuit Circuit, builder Builder, ...)

so that the caller code looks like

frontend.Compile(&circuit, r1cs.Builder(ecc.BN254)) 

I think it was a mistake to put the zkpID (backend.ID) in frontend.Compile in the first place; you can build a R1CS in different backend, so it makes no sense semantically to tie it to backend.GROTH16.

I think having it makes some sense -- from a user point of view who just wants to construct a proof from a circuit, it doesn't really matter what is the underlying CS. Right now, due to the default mapping from a backend to compiler the user can just define which backend they intend to use and the frontend.Compile function picks a default one. It would make sense to add a compile option to allow choosing different compilers if the user really knows what they are doing, but otherwise the default choices should be sane.

Most of all, I think it wouldn't be great to change the frontend.Compile signature.

I started a branch (refactor-flexible-compiler) that did that, but can't finish tonight. You can pick it up or throw it away and come w/ a better approach :) . I stopped when I realized that the APIs of the assert.ProverSucceeded... assumed such a 1-1 mapping between frontend and backend, and that we need to think this through --> the testing package will need to know which pair of frontend / backend you want to test with. We can provide a default mapping, but I assume we need new TestOptions to allow users to supply their own backend / frontend .

I'll try.

[gbotrel]

I think having it makes some sense -- from a user point of view who just wants to construct a proof from a circuit, it doesn't really matter what is the underlying CS. Right now, due to the default mapping from a backend to compiler the user can just define which backend they intend to use and the frontend.Compile function picks a default one. It would make sense to add a compile option to allow choosing different compilers if the user really knows what they are doing, but otherwise the default choices should be sane.

Most of all, I think it wouldn't be great to change the frontend.Compile signature.

OK makes sense. Not a fan either of changing the Compile signature. So te be clear, idea is in the future, if we support other "builders" or "compilers " than the ones provided by gnark, call would be through compile options :
frontend.Compile(BN254, GROTH16, circuit, frontend.WithBuilder(myCustomBuilder))

[ivokub]

OK makes sense. Not a fan either of changing the Compile signature. So te be clear, idea is in the future, if we support other "builders" or "compilers " than the ones provided by gnark, call would be through compile options : frontend.Compile(BN254, GROTH16, circuit, frontend.WithBuilder(myCustomBuilder))

Yes, that is the idea. I think it wouldn't be too much to add to this PR, but having it in a separate PR would make more sense when creating changelog.

edit: looks like decoupling the frontend and backend definitions of constraint systems requires a bit more effort. It is definitely worth it's own PR.

[ivokub]

Rebased on top of develop, it now mergeable without conflicts. All the tests are now green and the discovered bugs fixed. Orthogonal to the refactoring work I had to modify compiled circuit serialization to/from CBOR so that the serialization tests would succeed.

[gbotrel]

looks awesome thanks @ivokub & @ThomasPiellard , will do few cosmetic edits and merge 👍

[gbotrel]

@ivo.kubjas I still don't like that we have to do this:

ccs, err := frontend.Compile(curve.ID, backend.UNKNOWN, &circuit, frontend.WithBuilder(plonk.NewBuilder))

instead of this

ccs, err := frontend.Compile(curve.ID, backend.PLONK, &circuit)