2. R1CS representation

R1CS representation

In this step, we simply convert our system of constraints into vector form, Cw = Aw * Bw.

w here is the witness vector: [1 out x y v1 v2].

What are the dimensions of matrices C, A and B?

• 3 rows: number of constraints

• 6 columns: number of witness elements

Therefore, they have the dimension 3x6.

Cw = Aw * Bw:

Essentially this is the matrix form of our earlier system of constraints:

//     Cw = Aw * Bw
       v1  = y * y
       v2  = x * x 
out -v1 +2 = (4v2 * y)

where matrix C encompasses all the LHS elements, and A and B deal with the RHS elements.

To be perfectly clear:

Notice that the number 2 in last row for matrix C, it represents the +2 in the third constraint.

From this, it should be clear the purpose of having 1 in the witness vector - to allow for representation of addition of constants.

---

For detailed understanding of R1CS rules: https://www.rareskills.io/post/rank-1-constraint-system

---

Why does R1CS require exactly one multiplication per row?

• R1CS requires exactly 1 multiplication per row, so that the constraints can be expressed in the matrix form: Cw = Aw * Bw, where each row is a single constraint.

• Adhering to the Cw = Aw * Bw form is useful to us as it allows us to apply bilinear pairings.

• If there are multiple multiplications per row, the resulting form would be: Cw = Aw * Bw * ... We would not be able to constructively apply bilinear pairings in this case.

If we have more than 1 multiplication per row, we would not be able to apply a bilinear mapping between G1 and G2 to G12. Without a bilinear mapping we cannot turn this into a succinct ZKP.

---

CHECKPOINT

Given a circuit encoded as a rank 1 constraint system, it is possible to create a proof.

• The prover would generate Cw, Aw, Bw, as the proof.

• The verifier will verify if Cw = Aw * Bw, to check the validity of the proof

However, it would not be succinct. Imagine you are dealing with a complex circuit, with numerous constraints. This means that each of the matrices comprise of thousands of rows.

Thus, calculating Cw = Aw * Bw would be time-consuming and intensive with O(n), where n is the number of constraints.

So not very succinct at all. This is why we look to convert the R1CS form into a QAP.

Read more:

• https://www.rareskills.io/post/rank-1-constraint-system

• https://www.rareskills.io/post/r1cs-zkp

• https://www.rareskills.io/post/bilinear-pairing