Partnered With:

Fully understand the zero knowledge proof

Read this article in 29 Minutes

Zero-knowledge proof is widely used in cryptography and highly proves that this concept and application can solve many problems.

原文标题：《分析｜零知识证明》

Originally written by Cryptoyc Tech, Cryptoyc Labs

The zero-knowledge proof was proposed by S.Goldwasser, S.Micali and C. Rackoff in the 1980s. The point of this proof is to convince the other party that a certain conclusion is true without having to show the other party the process of proving or solving the problem. Zero-knowledge proof is widely used in cryptography and highly proves that this concept and application can solve many problems.

Zero knowledge proof definition

Zksnark, short for zero-knowledge Succint non-interactive ARguments of knowledge

Succinct: The amount of data proved was small

Non-interactive: no or very little interaction.

ARguments: Validators are only valid for proofs with limited computational power. Proofers with sufficient computing power can forge proofs. This is also called "computational reliability" (as opposed to "perfect reliability").

of Knowledge: It is impossible for the prover to construct a set of parameters and proofs without knowing the evidence (Witness, such as the input of a hash function or a path to a deterministic Merkle-tree node).

An example of zero knowledge proof -- take sudoku as an example

prove

One day, Xiao Ming had a very difficult Sudoku problem. Xiao Hong spent a long time trying to solve the Sudoku problem, but she could not get the result. Xiao Hong felt that Xiao Ming was playing with her, "This problem has no solution at all! Xiao Ming you play me!" She went to Xiao Ming to complain. "I can prove to you that there is a solution to this problem, and I know the solution," Xiao Ming calmly replied. "OK," Xiao Hong thought to herself, "Hum, after you prove it to me, I'll write down the solution and then go to play with Xiao Gang and do it for him." Xiao Ming then said: "I will prove to you the solution of this problem with zero knowledge proof method. That is to say, I will not show you the solution, but I can convince you that I do have the solution of this problem." Little red does not believe that he can do so, still imagine the appearance of Xiaogang being played. Xiao Ming took out 81 (9x9) blank cards and put them on the table. On each piece of paper, he wrote a number from 1 to 9. He asked Xiao Hong to turn around and close her eyes. The card representing the puzzle, the number is placed face up on the table.

Randomized trial

After Xiao Ming put the card, let Xiao Hong opened her eyes and turned around. Xiao Hong is very excited, she felt that the answer to the riddle is going to be revealed, very happy. It took her several days to work out the problem. Xiao Ming said to Xiao Hong, "Xiao Hong, you can't peek at these cards facing down." ", it is obvious that Xiao Hong is disappointed, she thought she could see a complete solution. "But I can let you test the solutions: you can choose to test my solution in rows, columns, or 3x3 boxes. Pick one." Xiao Hong told Xiao Ming that she decided to test it in rows. Xiao Ming then put the nine cards in each row into a separate sack. All the cards were collected and put into nine burlap bags. Xiao Ming then shook each sack, breaking up the cards in order. Finally give the nine sacks to Xiao Hong.

validation

"OK, now you can open these bags," xiao Ming said to xiao hong, "each bag should have exactly nine cards with the numbers 1-9, without repeating the numbers." xiao hong opened each bag and saw that it was true.

"But that doesn't prove anything! I can do this to show you. I just need to make sure that each row is 1-9 of the nine cards, regardless of whether the numbers in the column and the nine grids are not repeated," said Xiao Hong. "But I don't know in advance whether you will choose to collect the cards by row, column, or grid. I arrange the cards by the solution, so I'm not afraid of what you choose."

Repeated verification

Xiao Hong is still unconvinced. Think Xiaoming still may cheat her, so ask Xiaoming to restore the card, according to the original method, re-elected. So in succession tried several times, small red each time to choose a different test method. I have tried it many times with the same result. Xiao Hong had to admit that Ming was either lucky enough to bet on which experiment she would choose every time, or that he did know the solution to the problem (or that Ming could read her mind and know in advance what experiment she would choose). Xiao Hong was very disappointed. After so many tests, she still did not know the real solution to the problem. She only knew that there was a high probability that every row, every column and every nine grid in the arrangement of the cards Ming placed were indeed not repeated 1-9, which indicated that there was a high probability that the problem could be solved, and Ming knew the solution to the problem.

The essence of a zero-knowledge proof is to prove to others that there is a high probability (and this is important, because zero-knowledge proof is ultimately a probabilistic proof) that I do know or own something without revealing it.

The thing to prove in the story is the solution of a Sudoku problem. Xiao Ming asked Xiao Hong to randomly select rows, columns and nine-grid cards each time and collect them together to randomly scramble them. Xiao Hong could not know the solution of the problem by opening the bag, but she could believe that Xiao Ming did know the solution of the problem very likely.

The Zk-Snipm in this story also alludes, half-jokingly, to the Zk-Snarks (Zero-Knowledge Succinct Non-Interactive Arguement of Knowledge) algorithm, which is now the most common in zero-knowledge proof. Although ZK-Snipm in the story has loopholes, he still has room for improvement. For example, he scans all the combinations of cards in the first time with a scanner, and then verifies all the test sequences at one time. This makes it hard to crack the machine through trial and error.

The original interactive proof method between Xiao Ming and Xiao Hong implies interactive zero-knowledge proof. Interactive zero-knowledge proof requires the verifier (Xiao Hong) to continuously send random trials after the verifier (Xiao Ming) has placed the answer (Commitment). If the verification and verification parties have collaborated in advance, they can simulate/forge a proof without knowing the real answer.

Non-interactive proofs do not require this interaction. But it would require some extra machine or program, and it would require a sequence of experiments that no one could know about. With such a program and a sequence of tests, the proof machine can automatically calculate a proof and prevent either party from cheating.

Zero Knowledge Proof Analysis -- Problem Disassembly

The zero-knowledge proof basically consists of four parts:

Transformation of Polynomial Problems - The problem to be proved is transformed into a polynomial problem T (x) H (x) = W (x) V (x), and the prover submits the proof for the verifier to confirm that the polynomial is true.

Randomly selected validation & NBSP; - Select the verification value S at random and verify that T (S) H (S) = W (S) V (S). Relative to verifying polynomial equality T (x) H (x) = W (x) V (x), random selection verification, simple, verification data is less. Randomly selected validation is certainly not as safe as polynomial equality verification, but if it is indeed random enough, it is still quite safe.

Homomorphic concealment & NBSP; - Homomorphic hiding refers to a property of a function. The calculation of input and the calculation of output remain "homomorphic". Taking additive homomorphism as an example, a function E(x) that satisfies the following three conditions is called additive homomorphism:

1. Given E(x), it is difficult to deduce x.

E(x+y) can be calculated from E(x), E(y). The multiplicative homomorphism is similar.

Zero knowledge & have spent - Proof and verifier do not know any knowledge other than the knowledge of "whether the problem is proved or not" (do not know the randomly selected values, do not know the polynomial results of the selected values, etc.).

Polynomial problem transformation

NP 问题以及约化

It takes time to solve a problem. The problem can be said to have polynomial complexity if there is a polynomial relationship between the time required to solve the problem and the size of the problem. General problems can be divided into two categories: P problems and NP problems. P problems are problems that are solvable in polynomial time. Non-deterministic Polynomial Problem (NP) is a Problem that cannot be solved in Polynomial terms, but can be verified in Polynomial time.

Obviously, a P problem is also an NP problem, but is an NP problem a P problem, where NP=P? So far no one has been able to prove it. It is generally believed that NP problems are not equal to P problems, that is, there is no polynomial solution to NP problems.

Reduction, "Reduction," can be understood as the transformation in question. If the input of any program A can be transformed into the input of program B by some rule, so that the output of the two programs is the same, then we can say that problem A is reducible to problem B.

The NPC problem is an NP problem, and all other NP problems can be reduced to it. Simply put, NP problems can be reduced to each other, one NP problem can be solved, other NP problems can be solved.

For example, NP problems and reduction of NP problems are illustrated.

Boolean formula satisfiability (SAT) is an NP problem. Boolean formula is defined as follows:

• Assumption variable x1 , x2 , x3 . It's Boolean formula

• Assuming F is Boolean formula, ￢ f It's also Boolean's formula.

• Assuming that f and g are Boolean formulas, F Sunday afternoon g And & have spent F ∨ g It's also Boolean's formula

A Boolean formula is satisfied, which means that if the input is 0/1, there is an output that is true. The SAT problem is to find all the Boolean equations that can be satisfied. SAT problems, it seems, have no better solution than enumerating possible Boolean formulas, which are polynomially unsolvable. If you know a satisfying Boolean formula, it is easy to verify (see if the output is true if the input is 0/1). SAT problems are NP problems.

Consider another NP problem: the Polyzero problem. A PolyZero problem is one in which the output of a polynomial is 0 if the input of the polynomial is 0 or 1.

PolyZero(f):=1

If f is the case where the input is 0/1, the output of the polynomial is 0.

A Boolean expression f can be converted to a polynomial by the following reduction function r:

R. (xi) : = (1 - xi)

R. (￢ f) : = (1 - r (f))

• r (f) Sunday afternoon g: = (1 - (1 - r (f)) (1 - r (g)))

• r (f) ∨ g: = r (f) r (g)

That is, an SAT problem can be reduced to a Polyzero problem by reducing the function r: f is satisfiable if and only if the output of r(f) is 0.

SAT(f)=PolyZero(r(f))

To summarize, an NP problem is one that has no solution in polynomial time, but can be validated in polynomial time. NP problems can be reduced to each other.

QSP problem

To put it simply, Zksnark deals with NP problems. Since NP problems can be reduced to each other, an NP problem should be determined first. All other NP problems can be reduced to this NP problem and then proved, that is, if one NP problem is proved, all NP problems can be proved, and QSP problem is NP problem, which is particularly suitable for Zksnark.

Given a set of polynomials, and given a target polynomial, find a combination of polynomials that is divisible into the target polynomial. The QSP problem with N bits of input is defined as follows:

Given multiple polynomials: V0... ,vm ,w0 ,... ,wm

Target polynomial: T

Given 1≤ I ≤n,j∈0,1}→{1... m}

Given a Witness U, it can be verified that U is the solution of the QSP problem if the following conditions are met:

ak ,bk =1 If k = f (I, u [I])

ak ,bk =0 If k = f (I, 1 - u [I])

VA Wb divisible & Nbsp; T, where Va = V0 + A1 V1 +... +am vm ,wb =w0 +b1 w1 +... +bm wm

For a piece of evidence U, two mapping calculations are performed for each bit (U [I] And 1-u [I] ) And determine the coefficients between polynomials. Because for each bit of evidence u, calculate it twice to determine the coefficients between the polynomials, if 2n < M, there's still a lot of flexibility in choosing polynomials.

If the prover knows the solution to the QSP problem, it needs to provide proof (i.e. U). In the case of obtaining evidence U, the verifier restors the coefficients of the polynomial according to the above rules, and verifies VVVb Is it divisible by t: th= VA Wb & NBSP; . To facilitate verifier verification, the verifier can provide H at the same time. In the case of large dimensions of polynomials, multiplication of polynomials is more complicated.

A simple idea is that instead of verifiers checking to see if the entire polynomial is equal, let's just pick a random number and test it. Assuming that the verifier randomly selects the verification value S, the verifier only needs to verify that T (S) H (S)= VA (S) WB (S)& NBSP; .

Examples of polynomial proof problems

The proof of a polynomial problem

Let's say I have a polynomial

Prove a polynomial that, given an input x, provides f(x) Proof.

3.1 Basis of Wired Group Theory (Elliptic Curves)

A finite group, whose generator is G and whose order is N, consists of the following elements: G0, G1, G2... And designed.the gn - 1. Encryption by finite group is simple: E(x):= Gx. In other words, if you know gx, you can't invert x.

3.2 Select random number

The verifier randomly selects elements of a finite group, such as S. Provide the following calculation results (encryption results of different orders of S) :

E(s0),E(s1),... ,E(sd)

After you generate these calculations, you don't need S anymore, you can forget about S.

3.3 E (f) (s) & have spent To calculate

For example, f(x)=4+2x+4x2, E(f(s))=E(s0)4E(s1)2E(s2)4. Obviously, E (f) (s) & have spent It can be calculated based on the data provided by the verifier without knowing S.

Examples of polynomial proof problems

The proof of a polynomial problem

3.4 alpha & have spent right

Note that the prover does not know the parameters of the polynomial to be proved, even if the prover provides E(F (S)) , the verifier is also unable to verify. Alpha & have spent The correct method allows the verifier to confirm that the verifier calculated the result using a polynomial. In addition to 3.2, the verifier also randomly selects another element Alpha & have spent And provide additional calculation results:

E (alpha s0), E (alpha s1),... , E (alpha sd)

The certifier is required to provide E(F (S)) And E (alpha f (s) & have spent .

E(f(s))=E(s0)4E(s1)2E(s2)4

E (alpha f (s)) = E (alpha s0) 4 E (alpha s1) 2 E (alpha s2) 4

3.5 Pairing function

The paired function E satisfies the following definition:

e(gx,gy)=e(g,g)xy

The verifier verifies alpha pairs simply by checking whether the following equation holds:

E (e) (f (s), alpha g) = e (e (alpha f (s)), g)

Assuming A= E(E(F (S)),B=E(α F (S)), the derivation process is as follows:

E alpha (A, g) = e (e) (f (s), alpha) g = e alpha (gf (s), g) = e (g, g) alpha f (s)

E (B, g) = e (e (alpha f (s)), g) = e (g alpha f (s), g) = e (g, g) alpha f (s)

So far, if the verifier provides alpha pairs, the verifier can prove that a result is computed from a polynomial, and the verifier does not know the parameters of the specific polynomial

Examples of polynomial proof problems

The proof of a polynomial problem

3.6 & have spent The delta & have spent The offset

Furthermore, Δ&Nbsp is used as the proof. Offset, don't even want the verifier to know E of F of S. Using the delta & have spent Offset, the prover no longer provides A and B, but A random δ parameter, providing A 'and B'.

Obviously, the verifier cannot deduce E(F (S)) from A ', but the verifier can also verify that the α pair pairing function is true:

多项式证明问题举例--整体过程

Sksnark proof of QSP problem

The Sksnark proof process is divided into two parts:

A) Setup phase & NBSP;

B) The proof stage.The QSP problem is that given a series of polynomials V0... ,vm,w0,... ,wm and the target polynomial t, prove the existence of a proof u. The highest order of these polynomials is d.

4.1 setup and CRS

CRS-Common Reference String, that is, pre-setup public information. With s and α selected, publish the following information:

The calculation results of S and α & Nbsp;

Calculation results of α pairs of polynomials & NBSP;

The polynomial β V,β W,γ& Nbsp; Calculation results of parameters

4.2 The certifier provides evidence

In the mapping function of QSP, if 2n < M, 1,... Some of the numbers in m don't map to. These unmapped numbers form Ifree and are defined (k is the unmapped number) :

The evidence to be provided by the certifier is as follows.

4.3 Verification by the verifier

In the mapping function of QSP, if 2n < M, 1,... , the binomial composed of all the numbers mapped to in m as the composition coefficient is defined as (complementary with vfree) :