Constraint System

A constraint system is a translation of a computation into an arithmetic circuit over a finite field. This circuit consists of addition and multiplication gates, where wires carry field elements. The system's constraints enforce that the output of each gate is the correct sum or product of its inputs. This representation is fundamental because ZKP protocols operate natively on polynomial equations, not high-level code.

R1CS is a widely used format that flattens an arithmetic circuit into a set of quadratic constraints. Each constraint takes the form of a Hadamard product between a linear combination of the witness vector and a second linear combination, equated to a third. This standardization allows any computation to be expressed as a matrix equation (A*w) ∘ (B*w) = (C*w), making it solvable by protocols like Groth16.

Modern systems like Plonk use a more flexible format where constraints are defined as multivariate polynomials that must vanish over a specific domain. Instead of rigid gate types, a single 'gate' polynomial can encode addition, multiplication, or custom logic by selecting different coefficients. This enables custom gates and lookup arguments, drastically reducing the total number of constraints for complex operations like bitwise XOR or SHA-256 hashing.

The witness is the complete assignment of values to every wire in the circuit that satisfies all constraints. It includes both public inputs (the statement being proven) and the prover's secret auxiliary data. In a zkML context, the witness might encode the private model weights and the intermediate activations of a neural network layer. The core goal of a ZKP is to prove knowledge of a valid witness without revealing it.

The degree of a constraint system refers to the highest algebraic degree of its polynomial equations. R1CS constraints are degree-2 (quadratic), which is optimal for pairing-based SNARKs. Higher-degree custom gates can pack more logic into a single constraint, reducing the total number of gates but potentially increasing the cost of polynomial commitments. The design of a constraint system is a trade-off between gate count and gate complexity.

A valid constraint system must guarantee two properties: Completeness—if a prover knows a valid witness, they can always generate a valid proof. Soundness—a malicious prover without a valid witness cannot forge a proof, except with negligible probability. The system's constraints mathematically encode every logical condition of the original program, ensuring that a satisfying assignment is computationally equivalent to correct execution.