Zero-knowledge proof - zkSNARK proof system

This notebook is excerpted from Steven Yue

Three core algorithms:
setup convention circuit, generate random parameters
prove: the prover generates a zero-knowledge proof
verify: the verifier verifies

Completeness:

Proof of knowledge: (verykey)
Prove that the prover does have some information that we don't know, that is, this w does exist

Short Proof: Short and Efficient
Zero-Knowledge: Public input x and proof pi cannot reveal w

PCP Theorem (Probability Verifiable Theorem)

All NP-hard problems can be proved by random sampling by random verification methods

Instead of looking directly at pi, it can only be extracted from itk-bit

In general, it is a random check. The more correct the random check, the lower the possibility of fraud (a bit of a hypothesis test)

Kilian SNARK

PCP may have huge read-only storage area

We will program a commitment in readonly
The prover only needs to attach a Merkle Proof to prove that the data submitted by himself is indeed in the pi when displaying the data
This can avoid storing a large amount of pi information

Non-Interactive Killian SNARK

The verifier does not need to be online when the prover submits the proof, it can verify at random events later
Requires Fiat-Shamir-Heuristic, which can convert any interactive random verification protocol into a non-interactive one
First we need a secure hash function H (random oracle, no matter what the input is, the output value can be regarded as a random number that is not associated with the input)

The key to the transformation is to rely on the random value of the authenticator to generate a secure hash function

LCPC (Linear)

Two polynomials with different coefficients of order d will only have at most d points coincident
By treating the proved value as the coefficient of the polynomial, and then verifying whether the value of the polynomial at a certain point is equal

p>

So we convert SNARK into polynomial form
But it is difficult for the circuit to become polynomial form, so we need aThe program matrix called R1CS

Polynomial interpolation, Vandermonde polynomial, restores eachA coefficient

Construct into polynomials P, Q, R
Prove that P * Q = R

Summary

PCP theorem is to quickly verify the solution of any NP problem by random sampling method.
LPCP is a constrained version of PCP, which describes the method of quickly verifying the coefficients of polynomials by randomly checking the values ​​of polynomials.
Fiat-Shamir Heuristic can turn an interactive protocol into a non-interactive protocol.
Starting from a mathematical operation circuit, after transforming into an R1CS program matrix, it can be finally restored to a polynomial