Constraint systems

Arithmetization is the process by which a computer program is transformed into a set of polynomial equations for use in a zero-knowledge proof system. There are four main methods:

• R1CS: quadratic rank-1 constraint system, systems of equations, at most quadratic in each variable, of the form, for $\mathbf{a},\mathbf{b},\mathbf{c}\in (F^n{)}^3,\mathbf{z}\in F^n$, $\cdot$ the scalar dot product: $(\mathbf{a}\cdot \mathbf{z})\times (\mathbf{b}\cdot \mathbf{z})-(\mathbf{c}\cdot \mathbf{z})=0$.
• PlonK: system of equations of the form $q_{l}a+q_{r}b+q_{o}c+q_{m}ab+q_c=0$ (models arithmetic gates for addition, multiplication, addition by a constant)
  • $q_l,q_r,q_o,q_m,q_c$ are called selectors, for the left input, the right input, the output, the multiplication, the constant term in an arithmetic gate
  • One can also extend the equations (custom gates): by adding a cubic term, using more than three wires (two inputs and one output), more than one constraint…
• AIR (section 5.1): A matrix representing the evolution of variables over time (execution trace), where the $w$ columns correspond to registers and the rows represent the state of these registers at a given step $i$ (as field elements). There are relations linking the state at step $i$ to the state at step $i+1$, expressed through polynomial constraints: polynomials $\{f_j{\}}_j$ of a predefined degree $d$ and in $2w$ variables. The execution trace is valid if for any polynomial constraint $f_j$, and any consecutive rows ${\mathbf{x}}_{\mathbf{i}}$ and ${\mathbf{x}}_{\mathbf{i}+1}$, $f_j({\mathbf{x}}_{\mathbf{i}},{\mathbf{x}}_{\mathbf{i}+1})=0$.
• CCS: generalizes and captures R1CS, PlonK and AIR, allowing for efficient conversions between these constraint systems