✏️Linear Interactive Proof
Last updated
Last updated
Linear Interactive Proof (LIP) from QAP: Once we have the Quadratic Arithmetic Program (QAP) represented by the equation
A(x)⋅B(x)−C(x)=Zd(x)⋅H(x), the next step in the zk-SNARK process is to transform this into a Linear Interactive Proof (LIP).
A Linear Interactive Proof is an interactive protocol where the verifier sends a random challenge to the prover, and in response, the prover sends back some values. The verifier then checks the validity of the proof using linear combinations of these values. It's called "linear" because the verifier's checks are linear operations on the prover's responses.
Variables and Notations:
x: A generic variable that represents the polynomial's input.
s: A specific secret point chosen by the prover, where the polynomial will be evaluated. It's a concrete value in the field, but remains hidden from the verifier.
α: A challenge issued by the verifier to the prover during the interaction. It's used to form linear combinations of the polynomials.
Encoding the Witness:
The prover encodes their secret witness as the values of the polynomials
A(x), B(x), C(x), and H(x) at a secret point s, chosen randomly from the field over which the polynomials are defined.
Verifying Polynomial Evaluation:
At this stage, the prover must convince the verifier that they've correctly evaluated the polynomials
A(s), B(s), C(s), and H(s) without revealing the specific value of s or the polynomial evaluations at s.
Random Challenge:
As part of the interaction, the verifier sends a random value α to the prover. This challenge is not related to
x or s. It's a separate value used to ensure that the prover's responses aren't pre-computed and are based on this specific interaction.
The random challenge α serves an essential purpose in interactive proofs. Let's break down its role step by step:
Purpose of α:
The random challenge is meant to ensure that the prover isn't just providing pre-computed answers, but is actually responding based on the specific interaction and challenge presented by the verifier. This prevents a malicious prover from "faking" knowledge of a solution.
Usage of α in zk-SNARKs:
Given the original relation from the QAP:
A(x)⋅B(x)−C(x)=Z(x)⋅H(x)
The verifier asks the prover to provide a linear combination of the polynomials weighted by α. For example:
P(x)=A(x)+α⋅B(x)+α^2⋅C(x)
The prover will then evaluate this combined polynomial at the secret point s, resulting in P(s), and send this value to the verifier.
Why is this significant?:
By combining the polynomials in this manner, the prover demonstrates knowledge of each individual polynomial's evaluation at s without revealing the evaluations directly. If they didn't know the real evaluations, they wouldn't be able to correctly compute the combined polynomial's value at s.
The verifier, using properties of the QAP and the received combined evaluation, can then check if the prover's response is consistent with the relation. If the prover's response is correct, it indicates that the prover likely knows the correct evaluations A(s), B(s), C(s), and H(s), even though they haven't directly revealed them.
Given our original equation:
A(x)⋅B(x)−C(x)=Zd(x)⋅H(x)
The prover provides evaluations of the polynomials
A(s), B(s), C(s), and H(s) without directly revealing them.
Let's consider the linear combination created using α as the challenge:
P(x)=A(x)+α⋅B(x)+α^2⋅C(x)
The prover evaluates this combined polynomial at the secret point s and sends P(s) as the response.
Now, the verifier's role is to ensure that the given polynomial evaluations satisfy the original equation when combined in a manner dictated by the challenge α.
In the context of zk-SNARKs and the QAP, the key is the polynomial Zd(x). Recall that Zd(x) is the vanishing polynomial, which has roots that correspond to the domain of the original computation. The prover's secret point
s is one of the roots.Because of this, the verifier can utilize the properties of the vanishing polynomial
Zd(x). Specifically, the verifier can create their own version of a combined polynomial, incorporating Zd(x) and the challenge α, and then evaluate this polynomial at s. If the prover's response matches the verifier's expectation (while taking into account the evaluations
A(s), B(s), C(s), and H(s) in some obscured manner), it indicates the prover's claims are consistent with the relation.
A detailed example would require delving into the specific math behind the QAP, its domain, and how the values interplay. However, the high-level idea is that the challenge and the response mechanism ensures a prover who doesn't genuinely "know" the correct polynomial evaluations would have an astronomically small chance of correctly guessing the response for the randomly chosen challenge α.
The inclusion of H(x) in the equation essentially captures the "error" or difference in the evaluations. It represents the difference between the left-hand side and the right-hand side of the equation. So, when the prover provides H(s), they are effectively giving the verifier a way to check the consistency of the equation at the point s.
Knowledge of Zd(x):
Both the prover and verifier are aware of the vanishing polynomial Zd(x) since it is constructed based on the domain D of the system, which is public information. This polynomial is known to evaluate to 0 at specific points determined by D. However, the verifier does not have knowledge of how Zd(x) interacts with
H(x) in the prover's equations unless the prover reveals H(s).
The challenge-response interaction ensures that the prover must genuinely know the polynomials to generate valid responses. Coupled with the verifier's knowledge of certain public parameters and structures (like Zd(x)), it makes it computationally infeasible for a dishonest prover to deceive the verifier.
secret evaluation point
In zk-SNARKs, s (often referred to as the secret evaluation point) is indeed chosen randomly by the prover. The randomness of s ensures several things:
Privacy:
Since s is random, it acts as a one-time mask for the polynomial evaluations, ensuring that the actual evaluations A(s), B(s), C(s), and H(s) don't reveal any useful information about the witness (solution) to the verifier.
Soundness:
By evaluating the polynomials at a random point, the prover prevents the verifier from being able to "guess" or infer the polynomials based on a set of known evaluation points. It's a fundamental property of polynomials that given a polynomial of degree d, if you know its value at d+1 distinct points, you can determine the polynomial completely. By choosing a random s for each proof, the prover avoids giving the verifier enough information across multiple proofs to reconstruct the polynomial.
Zero-Knowledge:
The randomness of s plays a crucial role in ensuring the zero-knowledge property of the zk-SNARK. The verifier never learns s or the direct polynomial evaluations at s, so they gain no knowledge about the witness, other than that the prover possesses a valid one. While the point s is randomly selected for each proof, it remains fixed throughout the interaction between the prover and verifier for that particular proof. This means that the prover uses the same s to evaluate all their polynomials and generate their responses for a given proof session.
The secrecy of s
The secrecy of s (the secret evaluation point) is pivotal for the security and zero-knowledge properties of the protocol. Here are the reasons:
Zero-Knowledge:
One of the central properties of zk-SNARKs (and many other zero-knowledge proofs) is that the verifier learns nothing about the prover's secret witness, other than the fact that it exists. If s were known to the verifier, then the evaluations A(s), B(s), C(s), and H(s) would directly reveal information about the polynomials A(x), B(x), C(x), and H(x), which encode the secret witness. Keeping s secret ensures that the verifier learns nothing about these polynomials or the witness from the evaluations.
Soundness:
If s were publicly known, a dishonest prover could craft specific polynomials that evaluate correctly at
s but are incorrect elsewhere. This would enable the prover to potentially convince the verifier of a false statement. By keeping s secret and random, the prover is effectively "boxed in" and cannot specifically craft polynomials just for that s.
Replay Attacks:
If s were publicly known and constant across proofs, a dishonest verifier (or anyone eavesdropping on the protocol) could replay previous proofs or responses from the prover in future sessions to potentially extract information or cause other security issues.
Uniqueness:
A fresh, secret s ensures that every proof is unique, even if the prover is proving the same statement multiple times. This adds an additional layer of privacy and unpredictability to the proof.
In summary, the secrecy of s is not an arbitrary design choice but rather a foundational component to ensure the security, soundness, and zero-knowledge properties of the zk-SNARK protocol.
In essence:
The prover claims: "I know polynomials A(x), B(x), and C(x) that satisfy our equation, and I'll prove it without revealing these polynomials."
The prover does this by sending the evaluations at a secret point s.
The verifier checks these claims using its knowledge of Zd(s).
Multiple Rounds:
Sometimes, multiple rounds of challenges and responses are used to reduce the probability that a cheating prover can guess the correct responses. In each round, a new α is chosen, ensuring the prover isn't just getting "lucky" with their responses.
