feat(plonk cs): adding functionality to convert a constraint system to PLONK constraints

[ThomasPiellard]

This PR contains the first step towards implementing PLONK proving system which is to have a PLONK like representation of a constraint system.

Breaking changes

• frontend.Compile(curveID, circuit) --> frontend.Compile(curveID, zkpID, circuit) (zkpID = backend.GROTH16 or backend.PLONK)
• R1CS and SparseR1CS implements frontend.CompiledConstraintSystem (the output of frontend.Compile, to be used as a parameter to the backend ZKP APIs)

SparseR1CS: PLONK constraint system

In PLONK each constraint is of the form aL+bR+cL*R+dO+k=0, where L, R, O are wires, and a, b, c, d, k are constants.

The way a CS is converted to a SparseR1CS follows the pattern that is already there for converting a CS to a R1CS. The API to define a circuit is unchanged.

Under the hood

The object representing a plonk constraint system is defined in backend/compiled/r1cs_sparse.go, it's basically a collection of plonk constraints along with the coefficients (stored in a slice, with a system of indexing similar to what we have in r1cs):

// SparseR1CS represents a Plonk like circuit
type SparseR1CS struct {

	// Variables
	NbInternalVariables int
	NbPublicVariables   int
	NbSecretVariables   int

	// Constraints
	Constraints []SparseR1C // list of Plonk constraints that yield an output (for example v3 == v1 * v2, return v3)
	Assertions  []SparseR1C // list of Plonk constraints that yield no output (for example ensuring v1 == v2)

	// Logs (e.g. variables that have been printed using cs.Println)
	Logs []LogEntry

	// Coefficients in the constraints
	Coeffs    []big.Int      // list of unique coefficients.
	CoeffsIDs map[string]int // map to fast check existence of a coefficient (key = coeff.Text(16))
}

A plonk constraint is actually represented (defined in backend/internal/compiled/r1c_sparse.go) like this:

// SparseR1C used to compute the wires
// L+R+M[0]M[1]+O+k=0
// if a Term is zero, it means the field doesn't exist (ex M=[0,0] means there is no multiplicative term)
type SparseR1C struct {
	L, R, O Term
	M       [2]Term
	K       int // stores only the ID of the constant term that is used
	Solver  SolvingMethod
}

The main file where things actually happen is frontend/cs_to_r1cs_sparse.go, where each r1cs constraints is converted into plonk constraints. The method to convert a r1c to a sequence of plonk constraints is rather simplistic: for a r1c of the form (aiwi)x(bjwj)=ck*wk (double index = sum), we convert each individual linear expression into plonk constraints, in the correct order so they can be solved by solving single equation with a single unkown in a straightforward fashion.

Example: aiwi becomes a0w0+a1w1 = u0, u0+a2w2= u1, etc up to wn. The converting function (called split) takes care of handling the constant terms (that is terms using the ONE_WIRE in a cs) so that they become constants in the plonk constraint system. For binary constraint, a similar pattern is followed, the solver field in the plonk constraint is set to BinaryDec to help the solver (the corresponding boolean constraint is translated in plonk, so there is no ambiguity).

Finally, in internal/backend/<curve>/cs/r1cs_sparse.go, there are the necessary functions to solve a constraint system. Since the constraints are correctly ordered, solving them using the witness consists of looping through the constraints and solve the missing wire at each step (as for the r1cs).

Note: the ONE_WIRE is discarded in PLONK, constants terms are used instead, the the witness parsers have been modified to take a boolean telling wether or not the ONE_WIRE should be taken (by default it should be taken).

status

All tests for solving circuits (against the circuits built in internal/backend/circuits) pass.