'Zero-Knowledge Proof Algorithm, PLONK—Protocol: Sin7Y Tech Review (17)' by Sin7Y_Labs sin7y blockchain
L=L2, R=R2, O=O2F=L * R - O=0If the polynomial function F has zeros at X=1,2,3, then the constraint relationship of the gates is valid. If the polynomial function F has zeros at X=1,2,3, then the polynomial F can be divisible by .
To be consistent with the paper, we set this polynomial function as Z:If we can prove T is a polynomial, then polynomials F and Z share the same zeros. Therefore, the constraint relationship of the gate is valid.However, there are two issues in this process. One is complexity. If the order of F is n, then the communication complexity is O. The other is the security issue. The polynomial F will be completely exposed to V.Polynomial Commitment What is the polynomial commitment? That is, the prover P uses a short string of data to represent a polynomial F. These short strings of data can be used by the verifier V to verify that the value of the polynomial F at a certain point is indeed the value z claimed by the prover P.Setup: initialize and generate some necessary parameters required to compute the polynomial commitment.Open: return to the polynomial function corresponding to the polynomial commitment.CreateWitness: verify whether the value of the polynomial function at a certain point is the value claimed by the prover P. The mathematical method is to confirm whether the polynomial is divisible. VerifyEval: the verifier V verifies whether the value of the polynomial function at a certain point is the value claimed by the prover P. The mathematical method uses bilinear pairing to prove its mathematical multiplication logical relationship.Based on the polynomial commitment protocol, the prover P wants to prove that the value of the polynomial function F=0 when X=1. Therefore, the verifier V only needs to prove that:In summary, the polynomial commitment can achieve complexity optimization and privacy protection.Figure 2 illustrates the proof relation in the PLONK algorithm. To elaborate: w represents the input and output in the circuit, with a total of 3n. n is the number of multiplication gates in the circuit, and each gate has a left input, right input, and output, so there are 3n w in total. q* represents the selection vector, and its value corresponds to a multiplication gate, an addition gate, or other similar constraints. σ represents the permutation polynomial and refers to the consistency constraint index among the gates.The penultimate formula represents the constraint relationship of the gate is valid.Figure 3 displays the CRS settings in the PLONK algorithm and the inputs by the prover P and the verifier V. To clarify: The entire protocol is dependent on polynomials, so it’s necessary to construct the respective polynomial form. The order of the polynomial σ is 3n. Since the highest order of CRS related to the polynomial commitment is n+2, it is necessary to split σ into three polynomials S and record each polynomial’s permutation relationship . To reduce communication complexity and protect privacy, the protocol is constructed based on polynomial commitments, so the input of the verifier V is the commitment value.b1,…b9 are random numbers for security purposes.[a],[b],[c] represent the commitment value of the polynomial. Refer to the commitment computing method in the polynomial commitment section. Figure 5 displays the operations of the prover in the PLONK algorithm, mainly permutation check. Refer to the permutation verification process to generate polynomial z in the previous article PLONK-Circuit. To clarify: Both β and ϒ are used to generate the parameters of the permutation verification function. Please refer fThe generation method of z corresponds to the generation process of cross-polynomials in permutation check. Li is a Lagrange polynomial satisfying that when x=i, it is 1 and 0 for others. Distinguish between ω and w. ω is the generator of the group H and the value of the independent polynomial variable. w is the left input, right input, and output of the circuit, and is the value of the polynomial L, R, O corresponding to group H. Figure 6 presents the operations of the prover P in the PLONK algorithm, mainly the combination of the constraint relationship of the gate and the constraint relationship among the gates through α. To elaborate: As mentioned above, the values of the gate-constrained polynomial and the consistency-constrained polynomial corresponding to all elements in group H are all 0, by which the polynomial ZH is divisible. This is equivalent to the T mentioned above. Therefore, if the prover can prove that the result of the division is indeed a polynomial, it can prove the values of the gate-constrained polynomial and the consistency-constrained polynomial corresponding to all elements in group H are all 0. All the constraint relationships are valid, which means the circuit logic is valid. The order of t is up to 3n. Still, the CRS used to compute the commitment only reaches the level of n, so it is necessary to split the polynomial t and then calculate the commitment value separately. Figure 7 displays the operations of the prover P in the PLONK algorithm. Previously P computed the value of multiple polynomials when x=z based on the polynomial commitment protocol. We need to prove this computing is correct utilizing the polynomial commitment protocol. To clarify: In order to reduce the operational complexity of the verifier V, the value of the numerator r of t at x=z should be computed by P, and then the verifier directly verifies it. Other operations are similar.Based on the CreateWitness operation in the polynomial protocol, Wz needs to prove that when x=z, the values of these polynomials r, a, b, etc. are equal to r, a, b, etc. respectively. The same logic applies to Wzw and returns the commitment value.Prover P has completed all the operations. The following operations are performed by the verifier V. Figure 8 shows the operations of the verifier V in the PLONK algorithm, mainly generating the relevant parameters to ensure the operations by the prover P. To clarify: From the input perspective, they are public inputs and proof outputs by the prover P, which are relatively straightforward. According to the input, some parameters are required to establish the permutation verification process. Figure 9 displays the operations of the verifier V in the PLONK algorithm. For less complex polynomials, it’s more convenient to compute the value at x=z directly. To clarify: According to the process of the prover P, the main job of the verifier V is to verify two polynomial commitments. The verification of two polynomial commitments requires two pairs. Each pair can be done by a parameter, namely μ. Before the verification, compute the value of the denominator of Wz and Wzw at x=z. The subtrahend and the minuend correspond to [F] and [E], respectively. μ, as a coefficient, corresponds to polynomial Wzw. Lastly, complete the verification of the two polynomial commitments through a bilinear pairing operation.We have analyzed all the protocol principles of the PLONK algorithm. If you have any questions or would like to share your thoughts, please contact us directly through
United States Latest News, United States Headlines
Similar News:You can also read news stories similar to this one that we have collected from other news sources.
Phase Zero: Episode 2x10: Ms. Marvel Trailer Breakdown, Big Deadpool 3 News on Apple PodcastsNew PhaseZeroCB MCU episode! -MsMarvel trailer breakdown -First MoonKnight reactions -Daniel Radcliffe's Wolverine -Nicolas Cage's GhostRider -Defenders on Disney+ -More, more, more! Download & subscribe: Apple: Spotify:
Read more »
The End of Zero: Prepare for a World With Higher RatesHeard on the Street: Inflation and tight job markets are forcing the hands of central banks to end an era of ultra-low interest rates. The results will be profound.
Read more »
China weighs exit from 'zero COVID' and the risks involvedEven as authorities lock down cities in China’s worst outbreak in two years, they are looking for an exit from what has been a successful but onerous COVID-19 prevention strategy.
Read more »
Coronapod: how vaccine complacency is plaguing 'COVID zero' strategiesSome countries managed to suppressed COVID for years, but are now facing huge outbreaks in the face of vaccine complacency
Read more »