2. R1CS representation
Last updated
Was this helpful?
Last updated
Was this helpful?
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:
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
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:
