Zk-SNARK(Pinocchio Protocol)

Zk-SNARK Background

    Zero-Knowledge Proof was proposed by S.Goldwasser, S.Micali and C.Rackoff in the early 1980s. It means that the prover can convince the verifier that a certain assertion is correct without providing any useful information to the verifier. This technology was first proposed theoretically not to solve the problem of anonymity of transactions in the blockchain. Later, as people became more aware of the technology behind zk-SNARKs (zero-knowledge proofs), someone proposed to use this technology In the direction of blockchain, for example, zcash is a privacy coin that uses zero-knowledge proof technology; in addition, the mixed currency contract on Ethereum is also a relatively well-known application in the field of zero-knowledge proof technology.
    But unfortunately, many of the existing materials only explain some of the technical problems in zk-snark, which is still obscure for most people who have almost no foundation in cryptography. Everyone is still very difficult to understand. It is difficult to understand the whole picture of zk-snark through this part of the information. This report mainly explains the rather complicated technology in a relatively concise and clear way, and introduces you step by step the development of zero-knowledge proof technology.

Definition of zero-knowledge proof

    To make it easier for everyone to understand, zero-knowledge proof can be defined as: the prover can convince the verifier that a certain assertion is correct without providing any useful information to the verifier. In order to facilitate the understanding of the meaning of the above passage, here is a very classic case of zero-knowledge proof.

Interactive zero-knowledge proof---Color Blind Game

    Verifier is color blind, and prover is not color blind. There are currently two balls of exactly the same size, but the colors of the balls are different. Therefore, the verifier cannot know the colors of the two balls, and the prover must prove to the verifier that the two balls are indeed different, which conforms to the definition of zero-knowledge proof.
    Verifier picks up two balls in front of the prover, the blue ball in his left hand and the red ball in his right hand. Then put the two hands behind your back, and then randomly choose whether to exchange the balls in the two hands, and finally consult the prover whether the two balls have exchanged positions, if the prover can see the color on the ball, then every time the verifier has changed the ball After the position, the prover can answer the verifier's question correctly.

    After the first iteration, the verifier can say that the assertion stated by the prover is true with a 50% probability. If the prover answers correctly the second time, then the verifier can say that the prover statement is true with a 75% probability. If the prover has passed the inspection for n consecutive times, then the verifier 1 - (0.5) ^ n probability can be considered that what the prover said is true. The two balls are indeed red and blue.

Interactive zero-knowledge proof---polynomial

    Now let’s study the polynomial in the mathematical equation. The polynomial corresponding to the curve below is f(x) = x³ – 5x² +7x– 2. The polynomial has a very good feature that any very small modification to the polynomial will be reflected in Within a certain area, the curves represented by two polynomials are difficult to overlap.

    As the value of x changes continuously on the x axis, the y value will be different. Suppose we set the value range of x to (0, +∞), and any value has d similarities (d is obviously limited).Then the probability that the prover gives the correct solution every time without knowing the solution is 0.