➗Quadratic Arithmetic Program
Last updated
Last updated
Transformation using FFT:
The Fast Fourier Transform (FFT) is essentially an efficient way to compute the discrete Fourier transform (DFT). In this context, it allows us to transform our sequence (vector) into a different representation, which makes it suitable to be expressed as a polynomial.
When applying FFT on a vector, you're determining how the vector can be represented in terms of sinusoids of varying frequencies. But in the context of zk-SNARKs, we're more interested in how the FFT allows us to evaluate polynomials quickly at many points.
Polynomial Representation:
Now, once the FFT has been applied to our sequence/vector, we can express it in the polynomial domain. The result of the FFT can be seen as the polynomial evaluation of some polynomial
a(x) at multiple points. If you imagine z as a set of points, then the FFT gives us
a(z1),a(z2),...a(zn), which are the values of the polynomial
a(x) evaluated at each of these points.
To relate this back to the original statement from your slides:
"Using fast fourier transform it can be represented as sum
a(x)jZj
"
This is saying that the dot product
a⋅z can be expressed in terms of a polynomial
a(x) evaluated at different points zj.The FFT helps us transition from the vector to this polynomial representation efficiently.
Equation:
A(x)⋅B(x)−C(x)=Zd(x)⋅H(x)
This equation captures the transition from our R1CS constraints to a polynomial format. Let's break it down:
1. A(x),B(x),and C(x)
These are polynomial representations of the matrices A, B, and C you saw in R1CS. The transformation from R1CS to QAP (Quadratic Arithmetic Program) is essentially converting the linear constraints (from R1CS) into polynomial equations.
2.Zd(x): The Vanishing Polynomial
The vanishing polynomial
Zd(x) is a polynomial that "vanishes" over a certain domain D (i.e., it evaluates to zero for all points in that domain). For a domain D of size d, this polynomial is:
Zd(x)=(x−α1)(x−α2)…(x−αd)
where
α1,α2,…,αd are the points in the domain D.
In zk-SNARKs, the vanishing polynomial is used as a tool to ensure that our polynomial
H(x) correctly represents the constraints of our arithmetic circuit.
3. H(x): The Quotient Polynomial
The polynomial
H(x) is what's left when you divide the left side of the equation by Zd(x). The term "quotient polynomial" comes from the fact that when you divide two polynomials, you get a quotient and a remainder.
In the context of the QAP,
H(x) captures the "residue" or the leftover information once you've ensured all constraints (in polynomial form) are upheld.
So, what does this equation mean in context?
This equation ensures that the R1CS constraints are satisfied. If our computation (captured by R1CS) is correct, then
A(x)⋅B(x)=C(x) everywhere except for the points in the domain D. At the points in D,
A(x)⋅B(x)−C(x) should be divisible by Zd(x) with H(x) as the quotient.
Thus, the equation
A(x)⋅B(x)−C(x)=Zd(x)⋅H(x) is a way to represent that all the constraints are correctly upheld in polynomial form. This representation is efficient and plays well with the mathematical structures used in zk-SNARKs.
Domain D:
In algebraic geometry and polynomial math, a domain D is a set of distinct points. In the context of zk-SNARKs and QAPs, this domain usually consists of d distinct points, where d is typically the number of constraints or the number of gates in the original arithmetic circuit. The reason for this is that each gate's operation will correspond to a constraint, and thus a specific point in the domain.
To provide clarity, let's say you have an arithmetic circuit with 3 gates (and thus 3 constraints). Your domain D might be the set of points
{1,2,3}.
Why is a domain needed?
Evaluation: The QAP essentially represents the R1CS constraints as polynomial equations. These polynomial equations are then "evaluated" over the domain D. That means each polynomial is calculated for every point in D
Interpolation: After evaluation, the results can be used to construct, or interpolate, the actual polynomials
A(x), B(x), and C(x).
Vanishing Polynomial:
The vanishing polynomial Zd(x) "vanishes" or evaluates to 0 for every point in D. This property is crucial to ensure the correctness of the QAP. As mentioned earlier, we want the equation
A(x)⋅B(x)=C(x) to hold everywhere, but if it doesn't at points in the domain D, it must be because the left side is divisible by the vanishing polynomial Zd(x).
What does "everywhere except for the points in the domain D" mean?
This statement is a bit nuanced. The QAP ensures that the R1CS constraints are captured by the polynomial equation. However, we expect
A(x)⋅B(x)=C(x) to hold true for every possible value of x except at the points specifically in the domain D. At those specific points in D, we allow for the equation
A(x)⋅B(x)−C(x)
to not be zero, because any non-zero value at these points can be captured by
Zd(x)⋅H(x),
thanks to the properties of the vanishing polynomial.
In essence, the domain D and the properties of the vanishing polynomial Zd(x) play a crucial role in ensuring that our QAP correctly represents the constraints from the arithmetic circuit and provides a polynomial structure that is efficient for zk-SNARKs.
The sequence is transformed from its vector representation to a polynomial representation using the FFT. This allows zk-SNARK systems to leverage the efficiencies of polynomial operations, speeding up the proof generation and verification process.
Why is the QAP evaluated over domain D?
The domain D is specially chosen because it aids in:
1) Efficient polynomial interpolation using FFT.
2) Ensuring the correctness of our system by using the vanishing polynomial.
The Vanishing Polynomial (and its importance):
The idea of a vanishing polynomial might seem abstract, but its role is central. The vanishing polynomial for a set D, Zd(x), has a special property: it equals zero for every point in D.
Why do we need this?
The polynomials
A(x),
B(x),
C(x)
capture our arithmetic circuit's logic. They might not precisely represent the circuit's constraints at every point in D. By using the vanishing polynomial, we allow for 'flexibility' or 'tolerance' at the points in D.
If
A(x)⋅B(x)−C(x)
is not zero at a point in D, it must be because it's divisible by the vanishing polynomial,
Zd(x).
If there isn't a vanishing polynomial, then the left-hand side and right-hand side of our QAP equation might not match perfectly at the points in D. If they don't match, then the equations would not be a correct representation of our circuit.
The Quotient Polynomial
H(x) and its significance:
The quotient polynomial
H(x) captures the 'difference' or the 'error' between the left side and the right side of the QAP equation. Essentially, it's a way to capture any discrepancies at the points in D. If
A(x)⋅B(x)−C(x)
is divisible by
Zd(x)
at a point in D, then the quotient of this division is represented by
H(x)
at that point.
When zk-SNARK proofs are generated, the prover will show that they know a correct H(x) without revealing it. This ensures that the arithmetic circuit's constraints are satisfied.
Remember, zk-SNARKs is all about proving knowledge of something without revealing it. By using the vanishing polynomial and the quotient polynomial in the QAP, we allow the prover to demonstrate that they have correctly evaluated the circuit without revealing specific details about the inputs or the intermediate computations.
