🚧Rank-1 Constraint System (R1CS)
R1CS is a system of equations used to express and validate arithmetic circuits. Essentially, it's a way to represent our circuit using linear constraints, making it compatible with zk-SNARKs protocols.
Why can't we use the arithmetic circuit directly?
zk-SNARKs, at their core, deal with polynomial equations. The arithmetic circuit provides a structural representation of our computation but isn't readily compatible with the polynomial-based techniques used in zk-SNARKs. The R1CS representation serves as a bridge between the circuit and these polynomial equations, setting up the problem in a manner suitable for the zk-SNARKs protocol.
How exactly is the arithmetic circuit converted to R1CS? Why can't we go from the computation directly to R1CS?
The arithmetic circuit is made up of gates that perform specific operations (e.g., addition, multiplication). Each of these gates can be translated into a set of constraints that verify its correctness, and this is how we derive our R1CS.
Why not directly from computation to R1CS?
The arithmetic circuit serves as a structural breakdown of our computation, making it easier to systematically convert it to R1CS. Jumping directly from the high-level computation to R1CS would be akin to trying to solve a puzzle without first categorizing and understanding each piece.
Converting the Arithmetic Circuit to R1CS (Rank 1 Constraint System)
Having represented the IsZero() function as an arithmetic circuit, the next crucial step is to transform this circuit into a format suitable for zk-SNARKs. This is where R1CS, or Rank 1 Constraint Systems, come into play.
Understanding R1CS
At its heart, an R1CS is a way to represent an arithmetic circuit as a set of linear equations. Each gate in the circuit is translated to a particular type of equation that verifies the correct operation of that gate. In essence, the R1CS acts as a bridge, taking the computational logic of the arithmetic circuit and converting it into a mathematical structure that zk-SNARKs can work with.
To put it succinctly:
R1CS translates the operation of each gate in the arithmetic circuit into a system of equations.
R1CS Matrices - A, B, C
In the context of zk-SNARKs and R1CS, we generally use three matrices: A, B, and C. These matrices represent the linear combinations used to transform the gates of an arithmetic circuit into the linear constraints suitable for zero-knowledge proofs.
Matrix A: Represents the left side of the constraint equations.
Matrix B: Represents the middle portion.
Matrix C: Represents the right side.
Every row of these matrices (let's say the i-th row of A, B, and C) corresponds to a particular gate's constraints in the arithmetic circuit.
Dot Products and Hadamard Product
Dot Product (⋅): This is a standard mathematical operation applied between two vectors. When you take the dot product of two vectors, you're multiplying each corresponding entry and summing them all up. In mathematical terms, for vectors v and w, their dot product is:
v⋅w=v1w1+v2w2+⋯+vnw n
Hadamard Product (∘ or hollow dot): This is an element-wise multiplication. If you have two vectors v and w, their Hadamard product is another vector where each element is the product of the corresponding elements from v and w.
Vectors
A vector is essentially a one-dimensional array of numbers. For example:
v=[v1,v2,v3]
w=[w1,w2,w3]
Here, v and w are vectors, each with three components.
Element-wise Multiplication (Hadamard Product): When you take the Hadamard product of these two vectors, you'll multiply each corresponding pair of numbers from the two vectors:
v∘w=[v1×w1,v2×w2,v3×w3]
So, using the vectors
v and
w from our example, their Hadamard product is:
v∘w=[v1w1,v2w2,v3w3]
This is different from the dot product, where you'd multiply corresponding elements and then sum them up to get a single number.
What is Z?
Z is a witness vector. It's a vector that contains the actual values from the computation. This includes both the known public inputs and the secret inputs the prover knows but isn't revealing directly. When the R1CS equations are constructed, they are done so without specific knowledge of these values. The witness vector Z is used to "fill in" these values to check if the equation holds true.
The Check:
A⋅Z∘B⋅Z=C⋅Z
This equation ensures the constraints we've set in our R1CS are satisfied. Here's how:
A⋅Z: It's the dot product of the A matrix with the witness vector, resulting in a new vector.B⋅Z: Similarly, the dot product of the B matrix with the witness vector.C⋅Z: Dot product of the C matrix with the witness vector.
The equation A⋅Z ∘ B⋅Z = C⋅Z is checking that the Hadamard product of the results from A⋅Z and B⋅Z equals C⋅Z for each respective element. This "check" confirms that our R1CS system's constraints (expressed by matrices A, B, and C) are correctly upheld by the witness vector Z. If they aren't, then our proof wouldn't be valid.
The equation
A⋅Z∘B⋅Z=C⋅Z is an internal consistency check within the R1CS system itself. Let's break it down:
R1CS Matrices (A, B, C): These matrices represent linear constraints derived from the arithmetic circuit. They encode how the gates of the arithmetic circuit operate. Each row of these matrices corresponds to a constraint from one of the gates.
Witness Vector (Z)
This vector contains the values from the computation, including inputs, outputs, and intermediate values (the values on each wire for every gate in the circuit).
Matrix-vector Products (A⋅Z, B⋅Z, C⋅Z)
When you multiply each matrix by the witness vector, you're essentially computing the values each gate should output for each of the constraints, based on the values in the witness vector.
Hadamard Product (∘)
This is an element-wise multiplication between two vectors. If
A⋅Z yields one set of values and B⋅Z yields another, their Hadamard product represents the result of multiplying the respective elements of these two vectors together.
Now, for the equation to hold true:
The results of the computations described by the matrix-vector products A⋅Z and
B⋅Z must be consistent with the constraints encoded in the matrix
C when multiplied by the same witness vector.
So, when we ask "what is it checking against?", the answer is:
The equation checks that the values in the witness vector, when plugged into the constraints encoded by matrices A, B, and C, uphold the logic of the arithmetic circuit. If the equation doesn't hold true for the given Z, then Z is not a valid witness (i.e., the values in Z do not result in a valid execution of the computation described by the arithmetic circuit).
how each gate in our arithmetic circuit corresponds to rows in matrices
To understand how each gate in our arithmetic circuit corresponds to rows in matrices A, B, and C, it's essential to recognize that each gate in our circuit can be transformed into a constraint equation of the form:
a⋅b−c=0
Here, a, b, and c can be values, variables, or expressions. In R1CS, the terms on the left (i.e., a and b) represent the vectors multiplied against the matrix rows, and c represents the result. The main idea is to express the operations of the circuit gates as linear constraints.
Let's transform your gates into such equations:
Gate 0: w1⋅(−1)−w2=0
Gate 1:w2⋅w3−w4=0
Gate 2: w4+1−w5=0
(For addition, we often add a pseudo-multiplication to fit into the R1CS format, so we can represent it as
w4⋅1−w5+1=0
Gate 3: w1⋅w5−w6=0
Now, let's represent these equations in matrices A, B, and C:
For Gate 0:
Matrix A row: [w1]
Matrix B row: [-1]
Matrix C row: [-w2]
For Gate 1:
Matrix A row: [w2]
Matrix B row: [w3]
Matrix C row: [-w4]
For Gate 2:
Matrix A row: [w4]
Matrix B row: [1]
Matrix C row: [-w5 + 1] (Because we combined two operations, multiplication and addition, to fit this into our R1CS format)
For Gate 3:
Matrix A row: [w1]
Matrix B row: [w5]
Matrix C row: [-w6]
This is a simplified representation, but the general idea is:
Matrix A contains the first part of each gate's operation.
Matrix B contains the second part.
Matrix C contains the resulting value.
Z Witness
When constructing an arithmetic circuit (like the one we discussed earlier with gates and wires), each wire represents a value. Some of these values are direct inputs or outputs, while others might be intermediate values resulting from operations in the gates.
Let's revisit the example:
Gate 0: w1 • (-1) = w2
Gate 1: w2 • w3 = w4
Gate 2: w4 + 1 = w5
Gate 3: w1 • w5 = w6
Here, w1, w2, w3, w4, w5, and w6 are wire values. Some might be input values, some might be outputs, and others might be intermediary values.
In the context of R1CS and zk-SNARKs:
Arithmetic Circuit:
We have the circuit with its gates and wires, but we don't have specific values for them yet. We just know how they relate to each other.
Witness (or satisfying assignment):
This is where we provide specific values that make the circuit equations true. For our example, a satisfying assignment would provide values for w1, w2, w3, w4, w5, and w6 such that all the gates' equations are satisfied.
The vector Z (often called the witness vector) will contain these values. So, for our example,
Z would be a vector like:
Z=[w1,w2,w3,w4,w5,w6]
If we had a much larger circuit,
Z would contain values for all the wires in that circuit.
The phrase "Z would also include values for all possible wires in the circuit" is highlighting that this vector contains values for every wire, not just the input or output ones. It's capturing the entire state of the circuit for a particular computation.
The witness vector
Z could have multiple valid solutions, depending on the problem at hand and its constraints. However, for a specific set of inputs and outputs, there's typically a unique satisfying assignment.
To understand this:
Unique solutions:
For many problems, a given set of inputs will always result in the same outputs and hence the same intermediate values. For example, in most deterministic functions or computations, given the same input, you'll always get the same output. So, the witness vector would be unique in these cases.
Multiple solutions:
For some problems, there might be more than one valid witness that satisfies all the constraints. This might be the case in more complex or non-deterministic problems. However, in the context of zk-SNARKs and many applications using them, we usually deal with deterministic functions, leading to unique solutions.
When constructing a zk-SNARK proof:
The prover needs a valid witness Z to construct the proof. It doesn't necessarily matter which valid Z they use (in cases where multiple valid witnesses exist) as long as it satisfies all constraints.
The verifier doesn't need to know Z at all. They just need to be convinced that such a Z exists based on the proof provided by the prover.
For most use cases, it's crucial that the prover uses the correct and honest
Z because the integrity and truthfulness of their claim depend on it.
Secrets vs. Proof:
While zk-SNARKs allow the prover to demonstrate knowledge of a secret without revealing it, this doesn't mean that the process of constructing or validating the proof hides values from itself. When we construct R1CS equations, we are building a framework for any possible valid input. When we "witness" a solution with vector Z, we are applying specific known and secret values to this framework to see if it yields a valid proof.
The "secrecy" comes into play when the prover sends the proof to the verifier. The verifier can confirm the proof's validity without needing to see the actual secret values. They don't need to know what's in
Z; they just need to know that a valid Z exists.
Public and Secret Inputs:
For many zk-SNARK applications, there are both public and secret inputs. Think of it like a function f(x,y) where x is public and y is secret. The prover says, "I know a y such that
f(x,y)=z", and they can prove it without revealing y. Both x and y are in the witness vector, but only x is revealed to the verifier.
R1CS Construction vs. Checking:
When we're building the R1CS system, we don't know the specific values of the inputs that the prover might use. We're creating a generic set of constraints. But when we want to prove knowledge of a specific solution, we use the witness vector Z to plug in specific values (both public and secret) into our R1CS system. If the system's constraints hold with this Z, we have a valid proof for those inputs. This is what is meant by "filling in" these values to check if the equation is true.
Example using vector A, the same sort of matrix multiplication will apply for vector B and C
Vector Dot Products
The operation:
a⋅z is a dot product. For vectors:
a=[a1,a2,...,an] and z=[z1,z2,...,zn], the dot product is:
a⋅z=a1z1+a2z2+...+anzn
This can be thought of as the "weighted sum" of the elements of z using the elements of
a as weights.
Vector Representation:
Let's start with our vector representation:
a⋅z=a1z1+a2z2+...+anzn
This is a weighted sum of the elements of z, where the weights are the elements of a.
Last updated
