Rank-1 Constraint System (R1CS)

Every constraint in an R1CS is a single multiplication of two linear combinations, equated to a third linear combination. This enforces that the system is rank-1—each gate has exactly one multiplication.

• Form: (A · w) × (B · w) = (C · w)
• A, B, C: Matrices defining linear combinations of the witness vector w
• Witness w: Includes public inputs, private inputs, and intermediate values
• Example: For z = x × y, the constraint ensures the prover computed the product correctly

R1CS serves as the compilation target for higher-level circuit description languages like Circom and ZoKrates. Any computation expressed as addition and multiplication gates over a finite field can be flattened into this format.

• Flattening: Complex expressions are decomposed into binary operations
• Wire labeling: Each intermediate value gets a unique index in the witness vector
• Field arithmetic: All operations occur modulo a large prime p
• Example: A hash function like Poseidon is compiled into thousands of R1CS constraints

The witness is the secret assignment to all variables that satisfies every constraint. In zkML, the witness includes private model weights and input data that the prover wants to keep hidden.

• Public inputs: Known to both prover and verifier (e.g., model architecture hash)
• Private witness: Model parameters and inference inputs
• Satisfiability: The prover must find a witness w such that A·w ∘ B·w = C·w for all rows
• Soundness: It is computationally infeasible to find a satisfying witness for a false statement

R1CS is converted into a Quadratic Arithmetic Program (QAP) to enable succinct proofs. This step interpolates the constraint matrices into polynomials, allowing verification through a single divisibility check.

• Interpolation: Each column of A, B, C becomes a polynomial over a domain
• Target polynomial: Z(x) = ∏(x - rᵢ) vanishes at all constraint evaluation points
• Divisibility check: The prover shows A(x)·B(x) - C(x) is divisible by Z(x)
• Succinctness: The verifier checks the polynomial identity at a random point, not all constraints

The cost of a zkSNARK proof is directly proportional to the number of R1CS constraints. Circuit designers optimize for minimal constraints to reduce prover time and proof size.

• Multiplication gates: Each non-linear operation adds one constraint
• Linear operations: Additions are free—they only affect matrix coefficients
• Lookup tables: Non-arithmetic ops (XOR, AND) can use lookup arguments to reduce constraints
• Example: A single SHA-256 compression requires ~25,000 R1CS constraints
• Optimization: Using PLONKish arithmetization can reduce constraint count vs. pure R1CS

R1CS is tightly coupled with Groth16, which requires a circuit-specific trusted setup ceremony. The common reference string (CRS) is generated for the exact constraint matrices A, B, C.

• Toxic waste: Secret randomness used to generate the CRS must be destroyed
• Circuit-specific: Changing any constraint requires a new setup ceremony
• Verification key: A short key derived from the CRS enables fast verification
• Alternative: Universal setups (PLONK) avoid per-circuit ceremonies but use different arithmetization