R1CS and QAP: A Complete Worked Example

R1CS (Rank-1 Constraint System) and QAP (Quadratic Arithmetic Program) are two closely related algebraic representations used in classical pairing-based SNARKs such as Groth16.

An R1CS represents a computation as a collection of constraints of the form

\[\langle \mathbf{a}_i,\mathbf{w}\rangle \cdot \langle \mathbf{b}_i,\mathbf{w}\rangle = \langle \mathbf{c}_i,\mathbf{w}\rangle\]

where

• $\mathbf{w}$ is the witness vector;
• $\mathbf{a}_i,\mathbf{b}_i,\mathbf{c}_i$ are coefficient vectors;
• $\langle \cdot,\cdot\rangle$ denotes an inner product;
• each constraint contains one multiplication between two linear combinations.

A QAP then converts the entire R1CS instance into a polynomial divisibility relation

\[A_{\mathbf w}(X)B_{\mathbf w}(X)-C_{\mathbf w}(X) = H(X)Z(X)\]

The R1CS representation specifies the constraints that the witness must satisfy, while the QAP combines those constraints into a single polynomial identity.

For QAP-based SNARKs, the broader conceptual pipeline is

flowchart LR
    A["Computation"] --> B["Arithmetic Circuit"]
    B --> C["R1CS"]
    C --> D["QAP"]
    D --> E["SNARK Proof"]

This post develops the pipeline from the computation to the QAP relation. The final transformation from a QAP relation to a concrete SNARK proof will be covered separately.

Throughout this post, all matrix operations, interpolations, and polynomial computations are performed over a prime field $\mathbb{F}_p$.

1. R1CS

1.1 The Computation

Suppose a prover knows private inputs $x$ and $y$, and wants to prove that a public output $z$ was computed correctly according to

\[\begin{aligned} u &= xy\\ v &= (x+1)(y+2)\\ z &= uv+x \end{aligned}\]

After eliminating the intermediate variables $u$ and $v$, the computation is $z=xy(x+1)(y+2)+x$.

However, this high-degree expression cannot be represented directly by a single R1CS constraint. R1CS constraints are quadratic: each constraint can only express one product of two linear combinations.

Therefore, we introduce the intermediate variables $u$ and $v$.

For a concrete execution, let $x=2$ and $y=3$. Then a valid assignment is $(x,y,u,v,z)=(2,3,6,15,92)$.

1.2 Rewriting the Computation as R1CS Constraints

The three program steps can be written as

\[\begin{aligned} x\cdot y &= u\\ (x+1)\cdot (y+2) &= v\\ u\cdot v &= z-x \end{aligned}\]

1.3 The Witness Vector

Define the witness vector as $\mathbf{w}=(1,x,y,u,v,z)^{\mathsf{T}}$.

In a zkSNARK, the full variable assignment is partitioned into public inputs and private witness values. In this example, $z$ is public, while $x$, $y$, $u$, and $v$ are private. For algebraic convenience, all entries are collected in a single vector.

1.4 Encoding an Individual Constraint

For the first constraint $x\cdot y=u$, define

\[\mathbf{a}_1=\begin{bmatrix}0&1&0&0&0&0\end{bmatrix}\\ \mathbf{b}_1=\begin{bmatrix}0&0&1&0&0&0\end{bmatrix}\\ \mathbf{c}_1=\begin{bmatrix}0&0&0&1&0&0\end{bmatrix}\]

The resulting constraint is $ \langle \mathbf{a}_1,\mathbf{w}\rangle \cdot \langle \mathbf{b}_1,\mathbf{w}\rangle = \langle \mathbf{c}_1,\mathbf{w}\rangle, $ which is exactly $x\cdot y=u$.

The second and third constraints are handled in the same way.

1.5 Building the R1CS Matrices

Collecting the coefficient vectors for all three constraints as rows gives the following R1CS matrices

\[A = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \\[1em] B = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix} \\[1em] C = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & -1 & 0 & 0 & 0 & 1 \end{bmatrix}\]

The entire constraint system is written compactly as $(A\mathbf{w})\circ(B\mathbf{w})=C\mathbf{w}$, where $\circ$ denotes the Hadamard product, or element-wise multiplication.

1.6 Evaluating the Matrix Products

Using $\mathbf{w}=(1,x,y,u,v,z)^{\mathsf{T}}=(1,2,3,6,15,92)^{\mathsf{T}}$, we obtain

\[A\mathbf{w}=\begin{bmatrix}x\\x+1\\u\end{bmatrix}=\begin{bmatrix}2\\3\\6\end{bmatrix}\\[1em] B\mathbf{w}=\begin{bmatrix}y\\y+2\\v\end{bmatrix}=\begin{bmatrix}3\\5\\15\end{bmatrix}\\[1em] C\mathbf{w}=\begin{bmatrix}u\\v\\z-x\end{bmatrix}=\begin{bmatrix}6\\15\\90\end{bmatrix}\]

1.7 Verifying the R1CS Relation

Now compute the Hadamard product:

\[(A\mathbf{w})\circ(B\mathbf{w}) = \begin{bmatrix} 2\\ 3\\ 6 \end{bmatrix} \circ \begin{bmatrix} 3\\ 5\\ 15 \end{bmatrix} = \begin{bmatrix} 6\\ 15\\ 90 \end{bmatrix}\]

We conclude that $(A\mathbf{w})\circ(B\mathbf{w})=C\mathbf{w}$, the witness satisfies all three constraints.

2. QAP

R1CS defines the constraints that a valid witness must satisfy, but checking all constraints directly requires work proportional to the number of constraints. Classical pairing-based SNARKs such as Groth16 therefore transform the R1CS instance into a QAP.

2.1 Choosing the Constraint Points

In our example, there are three constraints, so assign one distinct field element to each constraint: $(r_1,r_2,r_3)=(1,2,3)$.

The corresponding Lagrange basis polynomials are

\[L_1(X)=\frac{(X-2)(X-3)}{(1-2)(1-3)}=\frac{(X-2)(X-3)}{2}\\[1em] L_2(X)=\frac{(X-1)(X-3)}{(2-1)(2-3)}=-(X-1)(X-3)\\[1em] L_3(X)=\frac{(X-1)(X-2)}{(3-1)(3-2)}=\frac{(X-1)(X-2)}{2}\]

They satisfy

\[L_i(r_j) = \begin{cases} 1,& i=j\\ 0,& i\neq j \end{cases}\]

Therefore, a polynomial of degree at most two whose values at $1,2,3$ are $q_1,q_2,q_3$ can be written as $q(X)=q_1L_1(X)+q_2L_2(X)+q_3L_3(X)$.

2.2 Interpolating the Columns

Recall that

\[A= \begin{bmatrix} 0&1&0&0&0&0\\ 1&1&0&0&0&0\\ 0&0&0&1&0&0 \end{bmatrix}\]

The $j$-th QAP polynomial $A_j(X)$ interpolates the $j$-th column of $A$: $A_j(r_i)=A_{i,j}$.

Hence,

\[\begin{aligned} A_0(X) &=0L_1(X)+1L_2(X)+0L_3(X) =L_2(X)\\ A_1(X) &=1L_1(X)+1L_2(X)+0L_3(X) =L_1(X)+L_2(X)\\ A_2(X) &=0\\ A_3(X) &=0L_1(X)+0L_2(X)+1L_3(X) =L_3(X)\\ A_4(X) &=0\\ A_5(X) &=0 \end{aligned}\]

Similarly,

\[\begin{aligned} B_0(X)&=0L_1(X)+2L_2(X)+0L_3(X)=2L_2(X)\\ B_1(X)&=0\\ B_2(X)&=1L_1(X)+1L_2(X)+0L_3(X)=L_1(X)+L_2(X)\\ B_3(X)&=0\\ B_4(X)&=0L_1(X)+0L_2(X)+1L_3(X)=L_3(X)\\ B_5(X)&=0\\[1em] C_0(X)&=0\\ C_1(X)&=0L_1(X)+0L_2(X)-L_3(X)=-L_3(X)\\ C_2(X)&=0\\ C_3(X)&=1L_1(X)+0L_2(X)+0L_3(X)=L_1(X)\\ C_4(X)&=0L_1(X)+1L_2(X)+0L_3(X)=L_2(X)\\ C_5(X)&=0L_1(X)+0L_2(X)+1L_3(X)=L_3(X) \end{aligned}\]

2.3 Aggregating the Polynomials with the Witness

For the valid assignment $\mathbf w=(1,2,3,6,15,92)^{\mathsf T}$, define $A_{\mathbf w}(X)=\sum_{j=0}^{5}w_jA_j(X)$.

Substituting the witness values gives

\[\begin{aligned} A_{\mathbf w}(X) &=1A_0(X)+2A_1(X)+3A_2(X)+6A_3(X)+15A_4(X)+92A_5(X)\\ &=2L_1(X)+3L_2(X)+6L_3(X)\\ &=X^2-2X+3 \end{aligned}\]

Its value at every constraint point $r_i$: $A_{\mathbf w}(1)=2,A_{\mathbf w}(2)=3,A_{\mathbf w}(3)=6$.

These are exactly the entries of $A\mathbf w=(2,3,6)^{\mathsf T}$.

Similarly,

\[\begin{aligned} B_{\mathbf w}(X) &=1B_0(X)+2B_1(X)+3B_2(X)+6B_3(X)+15B_4(X)+92B_5(X)\\ &=3L_1(X)+5L_2(X)+15L_3(X)\\ &=4X^2-10X+9 \end{aligned}\] \[\begin{aligned} C_{\mathbf w}(X) &=1C_0(X)+2C_1(X)+3C_2(X)+6C_3(X)+15C_4(X)+92C_5(X)\\ &=6L_1(X)+15L_2(X)+90L_3(X)\\ &=33X^2-90X+63 \end{aligned}\]

In general,

\[A_{\mathbf w}(r_i)=\langle \mathbf a_i,\mathbf w\rangle\\ B_{\mathbf w}(r_i)=\langle \mathbf b_i,\mathbf w\rangle\\ C_{\mathbf w}(r_i)=\langle \mathbf c_i,\mathbf w\rangle\]

The interpolation therefore preserves the three R1CS linear-combination evaluations at the selected constraint points.

2.4 Constructing the Target and Quotient Polynomials

The target polynomial vanishes at every constraint point $r_i$:

\[\begin{aligned} Z(X) &=(X-1)(X-2)(X-3)\\ &=X^3-6X^2+11X-6 \end{aligned}\]

Now define

\[\begin{aligned} P(X) &=A_{\mathbf w}(X)B_{\mathbf w}(X)-C_{\mathbf w}(X)\\ &=4X^4-18X^3+8X^2+42X-36 \end{aligned}\]

The witness satisfies all three constraints, so $P(1)=P(2)=P(3)=0$, $P(X)$ is divisible by $Z(X)$.

Polynomial division gives $H(X)=P(X)/Z(X)=4X+6$.

Hence, $A_{\mathbf w}(X)B_{\mathbf w}(X)-C_{\mathbf w}(X)=H(X)Z(X)$.

This is the complete QAP divisibility relation for the example. Given the interpolation construction above, it is equivalent to the three original R1CS constraints.

However, a QAP relation is still only an algebraic statement, not a SNARK proof. A concrete proof system must cryptographically encode and randomize the relevant QAP-derived values so that the verifier can check the relation succinctly without learning the private witness. Groth16, for example, performs this final transformation using elliptic-curve points. That proof-system layer will be covered separately.