zk-SNARK in a nutshell(1)

Introduction

What’s zero knowledge proof?

Zero-knowledge proof, abbreviated as ZKP, was originally proposed by S. Goldwasser, S. Micali and C. Rackoff in the 1985 paper “The Knowledge Complexity of Interactive Proof Systems”[1], referring to the ability of the prover to convince the verifier that an assertion is correct without providing any useful information to the verifier.

Properties of zero-knowledge proofs

  • Completeness: As long as the assertion is correct, the prover can convince the verifier of the assertion.
  • Soundness: If the assertion is false, the cheating prover cannot convince the verifier of the assertion.
  • Zero-knowledge: The interaction of the protocol only reveals whether the assertion is correct or not, without revealing any other information.

What are the applications of zero-knowledge proofs?

Justify a statement about privacy data

  • Prove that someone has an account balance of more than 100 million without revealing the account balance
  • Match DNA without exposing DNA data

Anonymous authentication

  • Prove that the requester has access to certain resources without revealing their identity
  • Prove that someone belongs to an identity group without revealing which

Anonymous payments

  • Pay taxes without disclosing income

Outsourced computing

  • The Ethereum scaling technology ZK-Rollup can be understood as a kind of outsourcing calculation, the calculation process is carried out off-chain, and the result is put on-chain for verification

What is ZK-SNARK?

ZK-SNARK is short for zero-knowledge succinct non-interactive arguments of knowledge. We understand it from the name:

  • zero-knowledge: The interaction of the protocol only reveals whether the assertion is correct or not, without revealing any other information.
  • succinct: Succinctness, which means that the proof size is relatively small. For a simple example, the prover wants to prove that he knows a polynomial of order d. He can provide all the coefficients to prove it, but it is obvious that the size of the proof is related to the order of the polynomial. As the order of the polynomial increases, the size of the proof also increases. One solution is random sampling. The verifier can randomly select 100 points in different positions for sampling and verify whether the results given by the prover are correct. If all are correct, then the prover is very likely to know the polynomial(note that it is very likely). In fact, there are many algorithms in cryptography that are probabilistic algorithms, such as the Miller-Rabin primality test[2]. The simplicity of ZK-SNARK is an important reason why ZK-Rollup is highly regarded in the Ethereum Layer 2 scaling scheme, which ensures that the proof verified on the chain is relatively small.
  • non-interactive: Non-interactivity means that no interaction is required or the number of interactions required is small. Non-interactivity brings a lot of convenience and does not require both parties to interact online at the same time.
  • arguments of knowledge: Note that the premise of the rationality of ZK-SNARK is that the prover only has the computing power of polynomial time. If the computing power of the prover is infinite, then the prover can forge the proof (the prover with unlimited computing power can break through the elliptic curve discrete logarithm problem).

Preliminaries

Polynomial

  • Polynomials are the medium of ZK-SNARK proofs.
  • Knowledge of polynomials is actually the coefficients of polynomials.
  • Schwartz-Zippel theorem[3] : Suppose f(x_1,x_2,…,x_n) is an n-variable polynomial, and the order of the polynomial is d. If r_1,r_2,…,r_n are randomly selected from the finite set S, then the probability of f(r_1,r_2,…,r_n)=0 is less than or equal to d /|S|. Simply put, if the multivariate polynomial is randomly selected in a large set, the probability that the function f is equal to 0 is almost 0. This theorem is the basis for the succinctnessof ZK-SNARKs.

P, NP and QAP

  • P problem: a class of problems solvable in polynomial time.
  • NP problem: It is unsolvable in polynomial time, but given a solution, it can be verified whether the solution is correct in polynomial time. In addition, there are NP complete problems, which are the hardest type of NP problems, and any NP problem can be reduced to an NP-complete problem. The nature of the NP problem is one-way, and it cannot be quickly solved, but it can be quickly verified.
  • QAP problem: given a polynomial z(x) of order n, and three sets of polynomials of order less than or equal to n, the solutions of these polynomials equal to zero are the same. The vector s=(1,s_1,…,s_m) cannot be calculated in polynomial time, satisfying the following divisibility relation

Principle analysis: If the value space of the vector element s_i is α, then the above formula is called a quadratic algorithm polynomial, or QAP polynomial for short. If you do not know the vector s, you can only randomly select a vector s, calculate the QAP polynomial, and then check whether z(x) satisfies the divisibility relationship with it. Therefore, it takes exponential time O(α^m) to brute force the vector s. However, once the vector s is given, it can be quickly verified whether the constructed QAP polynomial satisfies the divisibility relationship with z(x). The divisibility relationship between the polynomial z(x) and the QAP polynomial satisfies the one-way property, which constitutes an NP problem.

Elliptic curve discrete logarithm problem

Knowing that k is a positive integer, P is a point on the elliptic curve (called a base point), and knowing k*P and P, it is difficult to calculate k.

The above is the elliptic curve discrete logarithm problem, which forms the basis of elliptic curve encryption.

Homomorphic encryption

Homomorphic encryption is a form of encryption that allows one to perform certain forms of algebraic operations on ciphertext to obtain a result that is still encrypted, and to decrypt it yields the same result as performing the same operation on plaintext.

Homomorphic encryption can be divided into the following three types according to the type of computation supported and the degree of support:

  • Partially Homomorphic Encryption (PHE): Only one operation of addition or multiplication is supported. Among them, the one that only supports addition operation is also called Additive Homomorphic Encryption (AHE);
  • Somewhat Homomorphic Encryption (SWHE): supports both addition and multiplication operations, but supports a limited number of computations;
  • Fully Homomorphic Encryption (FHE): Supports any number of addition and multiplication operations.

In the elliptic curve encryption algorithm, E(x)=x*G (G is the generator of the elliptic curve), then E(x)+E(y)=x*G+y*G=(x+ y)*G=E(x+y), which has additive homomorphism, but not multiplicative homomorphism.

Bilinear mapping (bilinear pairing)

A bilinear map is a function from two elements in the vector space to generate an element in the third vector space, and the function is linear for each parameter.

The bilinear mapping in cryptography is relatively complex:

The above cryptographic tools will be used repeatedly in the following zero-knowledge proof protocols.

Reference

[1] Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems[J]. SIAM Journal on computing, 1989, 18(1): 186–208.

[2] https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

[3] https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

[4] D. Boneh, M. Franklin. Identity Based Encryption from the Weil Pairing. SIAM J. of Computing, Vol. 32, №3, pp. 586–615, 2003, Extended Abstract in Crypto 2001.

[5] S. Galbraith, K. Harrison and D. Soldera. Implementing the Tate Pairing. Algorithm Number Theory Symposium — ANTS V, LNCS 2369, Springer- Verlag (2002), pp. 324–337.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Eigen Network

Eigen Network

Where make transaction secure and private for Web3.0(https://eigen.cash)