Understanding Zero-Knowledge Proofs: Part 5-Arithmetic Circuits and R1CS

5 min readJul 14, 2024

In previous posts, we have looked at some basics of zero-knowledge proofs for privacy-sensitive verifiable computation. In part 4 we looked at how proofs can be generated for knowledge of polynomials. In this post, we will discuss how we can go from general computations to algebraic equations such as polynomial equations for which zero-knowledge proofs can be generated.

Arithmetic Circuits: An arithmetic circuit is a way of representing computations as a directed acyclic graph where input nodes are variables and constants and the intermediate nodes are additions or multiplications. The output of the arithmetic circuit is going to be some polynomial function of the input variables. Note that these arithmetic circuits operate over a given finite field Fp, with the addition and multiplication operations being done modulo p. This representation turns out to be powerful enough to capture very general computations. Let’s consider a couple of examples.

Say you want to capture the relationship w= v/u. Though the operations are limited to addition and multiplication, it can be depicted by the following circuit by adding a new variable.

An arithmetic circuit to depict division: w = v/u. Note that u*t = 1 => t = u^-1. Therefore w = v*t = v*u^-1 = v/u

With some effort, other operations including boolean operations, conditionals, as well as other computational primitives can also be represented as arithmetic circuits. The following circuit ensures that b is a boolean variable.

This arithmetic circuit ensures that b is a Boolean variable, by ensuring that b*(1-b) = 0.

The following shows another example, of an arithmetic circuit implementing a conditional statement: if b then w = u + v, else w = u * v, where b is a Boolean variable. We see that it utilizes the above circuit as a “gadget” (the part of this circuit that is to the left of the dashed line is the same as the one above).

Arithmetic circuit to implement a conditional calculation, where the condition is constrained to be Boolean.

Rank-1 Constraint System (R1CS): A standard intermediate format that arithmetic circuits are represented in is known as the Rank-1 Constraint System. An R1CS is a collection of equations of the form:

s·A * s·B = w·C.

Here, A, B, C, s are all vectors, the “·” operation is the scalar dot product of the corresponding two vectors, and * is multiplication.

Let’s work out a simple example: consider the equation w = 3u² + 2v. We can express it as 3u² = (w — 2v) => [0 0 3 0]·[1 w u v]*[0 0 1 0]·[1 w u v] = [0 1 0 -2]·[1 w u v], which is in the desired form, with s = [1 w u v], A= [0 0 3 0], B= [0 0 1 0], C= [0 1 0 -2]. Note that s is essentially a collection of variables in the circuit, along with a single 1 for constant terms.

For more complex computations, there will be multiple such R1CS equations. Consider the example we gave before of the algebraic circuit to encode the conditional statement as b*(u+v) + (1-b)*(uv) where b is a Boolean represented by b*(1-b)=0. This can be converted to the following equations:
b*(1-b) = 0 ; b*(u+v) = t1 ; uv = t2 ; (1-b)*t2 = t3 ; (t1+t3) = w
If we consider s = [1 b u v t1 t2 t3 w], we can express each of the above in the R1CS form, giving just the three vectors A,B,C for each of the above five equations as follows (try to verify for yourself how they come about):
[0 1 0 0 0 0 0 0], [1 -1 0 0 0 0 0 0], [0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0], [0 0 1 1 0 0 0 0], [0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 0 0], [0 0 0 1 0 0 0 0], [0 0 0 0 0 1 0 0]
[1 -1 0 0 0 0 0 0], [0 0 0 0 0 1 0 0], [0 0 0 0 0 0 1 0]
[0 0 0 0 1 0 1 0], [1 0 0 0 0 0 0 0], [0 0 0 0 0 0 0 1]

In general, the number of R1CS constraints in the system will be equal to the number of non-constant products in the given arithmetic circuit.

The vector s is called the witness. Say we ran the above computation with inputs b = 1, u = 0, v = 2. We see that the condition b being Boolean and true will result in w = u+v = 2. And the intermediate values t1, t2, t3 can be determined as well as t1 = 2, t2 = 0, t3 = 0. The corresponding value of the witness would then be [1 1 0 2 2 0 0 2]. We can roughly think of this witness as evidence that the whole computation was run with the given inputs and generated the correct intermediate values and outputs. If all of the R1CS constraints are satisfied by a given witness, it corresponds to a correct execution of the given arithmetic circuit. (For example, if a wrong witness is provided that has a 2 in the second element corresponding to b it will fail the verification because the first constraint corresponding to b*(1-b)=0 will not hold, i.e. because b is not a Boolean 0/1 value as it should have been. Likewise, if a wrong witness is provided where b = 1, u and v are set to 0 and 2, t1 = 2, t2 = 0, t3 = 0, but w = 3, then it would fail the verification corresponding to (t1+t3) = w.)

Additional Notes: R1CS was first defined by Ben Sasson et al. in 2013 as follows:

An early definition of R1CS — called rank-1 quadratic equations — in Ben Sasson et al. 2013

In the paper on Aurora in 2019, the authors explain the benefits of R1CS thus: “We choose R1CS because it strikes an attractive balance: it generalizes circuits by allowing “native” field arithmetic and having no fan-in/fan-out restrictions, but it is simple enough that one can design efficient argument systems for it. Moreover, R1CS has demonstrated strong empirical value: it underlies real-world systems and there are compilers that reduce program executions to it… This has led to efforts to standardize R1CS formats across academia and industry.”

Next Article: Next, we will discuss how to convert an R1CS to a Quadratic Arithmetic Program which simplifies the verification of Arithmetic circuits in the form of Polynomial evaluations.

Further Reading:

Understanding Zero-Knowledge Proofs: Part 5-Arithmetic Circuits and R1CS

Written by Bhaskar Krishnamachari