Preamble
This is the fourth part in a series of articles exploring zk-SNARK, a technology that allows proving the correctness of a piece of knowledge without having to reveal secret information. In the previous parts, we learned some complex concepts like Quadratic Arithmetic Program and Elliptic Curve Pairings (copy part 3 link in this bold text).
The Quadratic Arithmetic Program allows computational problems to be represented using polynomials, and Elliptic Curve Pairings provides a useful coding tool for checking the correctness of data. By combining them with some other algorithm, we can allow the prover to prove that they know the solution to a particular QAP without revealing anything else. This provides trust without revealing sensitive data.
This article will focus on the Pinocchio Protocol for QAP , which allows proving that a variable satisfies certain conditions without having to reveal details about the variable's value.
This proof is easy to create and can be authenticated without checking each computational step, ensuring data privacy and security in blockchain applications and other areas that require secure authentication. secure and high-performance without revealing private information.
Non-zero-knowledge Pinocchio Protocol Construction
We start by illustrating how the Pinocchio protocol works as follows:
Let G be a group with prime order p. Let E : Fp → G be a homomorphic encoding. As follows:
for a generator g
Put
The above expression is a “bilinear map” of an Elliptic curve. Suppose the prover P knows a witness as shown below
for the original arithmetic circuit. By simplifying, she will know some polynomial such that
At this point, we will still find it a bit confusing, right! Don't worry, read each line carefully and study the formulas, I'll explain the main idea of this protocol right below!
V(verifier) wants to test P(Prover) at a random point (random point) z ∈ Fp against the values of the above polynomial. P is queried for the value of
and h(z) at some random z ∈ Fp. P will homomorphically encode) these values and send them to V . Thanks to the homomorphic and bilinear map properties, V can verify that the homomorphically encoded value satisfies the same equation (20) above.
If it does so, the Verifier can be confident that the Prover actually knows a witness without learning about that witness. Below is more detailed information about the main idea just described.
The first step of the protocol is to create a Common Reference String (CRS), which contains homomorphic encodings of multiples of z.
CRS will serve two purposes:
First, the Prover can generate homomorphic encodings for its proof using linear combinations (linear combinations) of the group elements of the CRS without knowing z.
Second, setting up a CRS eliminates the need for V to manually generate z and send an encrypted message from z to P. This allows this proof to be completely non-interactive, because Once the CRS is created, P is in a position to produce convincing evidence.
We can think of CRS as two sets of public group elements:
The evaluation key, which contains the group elements needed to build the proof, and the verification key, which contains the elements needed for verification.
Common Reference String:
Randomly choose α, βu, βv, βw, γ, z ∈ F ∗ p .
Implement the CRS below, then remove all group elements used in its creation (toxic waste).
Prover’s message:
Suppose Prover has the following polynomial:
First the Prover computes h(x). Then, the prover's evidence includes the following:
Verification:
Upon receiving the prover's proof, the verifier first checks whether the terms u(z), v(z), w(z), h(z) are constructed as linear combinations calculation of terms in CRS or not, perform the following 4 checks:
Next, check that each term u(z), v(z), w(z) is generated using the same linear coefficients:
This can be checked by verifying the following equation:
Finally, we check the key condition that characterizes the polynomial divisibility criterion:
We have successfully constructed the Non-zero-knowledge Pinocchio Protocol if and only if all the checks from (21) to (26) hold.
Next, we will go to the step of analyzing the Non-zero-knowledge Pinocchio Protocol !
Non-zero-knowledge Pinocchio Protocol Analysis
First, we need to learn the Knowledge of Exponent Assumption
Suppose Alice is given a pair of group elements (x, αx)
We call such a pair α−separated. Then, for Alice, generating another α−separated pair (y, αy) is infeasible, except to generate it in the following way:
Given n α−separated pairs, if Alice returns another α−separated pair, it must be a linear combination of the original α−separated pairs with high probability.
Going back to our protocol, the main condition that V needs to check is the polynomial divisibility condition:
However, in addition to this equation, there should be other equations that the verifier must also check.
This is because it is possible for the Prover to generate values that satisfy this equation, but are not generated from an actual witness s for the arithmetic circuit. To ensure this, Verifier needs a way to check that the polynomials used by Prover are actually a linear combination of the underlying polynomials in the CRS.
The “Knowledge-of-Exponent” assumption is useful because if a pair of group elements that Prover sends and a given pair are both α− separated, the Prover pair must be generated as a linear combination of the α− pairs separated given.
Therefore, the Verifier can use a concatenation function to effectively test that these two pairs are both α− separated, to ensure the Prover generated using a truly satisfactory representation of the arithmetic circuit . More specifically, for two pairs (x, αx),(y, αy), the following is true:
Verifier can use this to perform the following checks:
Using this idea, the verifier needs to verify three things:
From there, we can prove that the Pinocchio protocol satisfies two properties: completeness and soundness. (This proof is quite complicated, you can read more about the source documents I put below to understand better! )
Zero-knowledge Pinocchio Protocol Modification
Essentially, if verifier V generates their own proof s' = (s'₁, s'₂, …, s'ₙ), they can compute E(u'(z)), E (v'(z)), E(w'(z)), E(h'(z)) according to the prover's protocol.
If these values differ from E(u(z)), E(v(z)), E(w(z)), E(h(z)), which the prover calculates in s, then the verifier concludes that the prover's proof is not s' (Explaining SNARKs Part VI: The Pinocchio Protocol)
To eliminate this “zero-knowledge” violation, the prover P adds a random shift to the polynomials u, v and w (Pinocchio: Nearly Practical Verifiable Computation)
Random shift will be a multiple of t(x), so that everything remains the same mod t(x). For random δ₁, δ₂, δ₃ belonging to Fp, randomly selected:
Then, P will evaluate them at z using CRS and submit shifted terms (shifted terms) in his proof in place of the corresponding unshifted terms.
So, the step of Zero-knowledge Pinocchio Protocol Modification has been completed. At this point, everyone feels confused =))))))
But that's all, thank you again for reading this far. If you liked this article, don't forget to follow it and leave a round of applause.
So ends a series of articles about my “Discovering zk-SNARK” . I hope you leave your contributions so I can improve and be motivated to write the next articles!
Article source: Team Tech/Research AlphaTrue
Reference source:
Chen, T., Lu, H., Kunpittaya, T., & Luo, A. (2022). A review of zk-snarks. arXiv preprint arXiv:2202.06877. https://arxiv.org/pdf/2202.06877.pdf
