Here is an attempt to define a relatively low level language/intermediary representation (IR)

for turboPLONK programs that is similar to r1cs, in the sense of being defined by low-degree constraints between the program variables.

It is related but more high level to the definition of turboPLONK programs here

A program is defined by:

Selector Variables: q_1,...,q_l

Program degree d (usually d\in \{3,4\})

Program width w (usually w\in \{3,4\})

Gates: G_1,..,G_s

Each gate is a polynomial G(q_1,\ldots,q_\ell,X_1,\ldots,X_v) of degree at most d in the selector variables q_1,\ldots,q_l

and at most 2w additional variables.

Similar to r1cs, a program will have public variables, x_1,\ldots,x_\ell and private variables x_{\ell+1},\ldots,x_n.

Now the turboPLONK program will consist of a set of constraints of the following form:

Each constraint consists of a choice of gate G among G_1,\ldots,G_s, a choice of values

a_1,\ldots, a_\ell for the selector variables, a choice of program variables x_{i_1},\ldots,x_{i_v} to constrain.

The constraint itself enforces:

G(a_1,\ldots,a_\ell, x_{i_1},\ldots,x_{i_v}) =0

Given such a set of constraints and values c_1,\ldots,c_\ell for the public variables, TurboPLONK can be used to generate a zero-knowledge proof of knowledge for values c_{\ell+1},\ldots,c_n such that

c_1,\ldots,c_n satisfy all constraints.

Example:

This is what we call “Standard PLONK”.

We can use d=3,w=3 and only one gate, the arithmetic gate.

G(q_L,q_R,q_O,q_M,q_C,X_1,X_2,X_3) = q_L X_1 + q_R X_2 + q_O X_3 + q_M X_1 X_2 + q_C

This one gate, allows us in particular to do addition and multiplication.

E.g., if for program variables x,y,z we want to check

x+y = z.

We set q_L=1,q_R=1, q_O=-1, q_M=0,q_C=0 (and obviously the choice of program variables for the constraint to x,y,z).

To check x\cdot y =z we set

q_L=0,q_R=0, q_O=-1, q_M=1,q_C=0.