The possibilities of zkSNARKs are impressive because you can check that a calculation is correct without performing it, or even knowing exactly what it’s doing — and the only information you know is that it’s done correctly. Unfortunately, most explanations of zkSNARKs are superficial, and they tend to leave a bit of “magic” behind and imply that only the smartest people can understand how zkSNARKs work. In fact, zkSNARKs can be summed up in four simple techniques, each of which will be explained in this article. Anyone who understands how THE RSA encryption system works will have a better idea of the zkSNARKs currently in use. Let’s see!

To start with a brief summary, the zkSNARKs we are currently using consist of four main parts (we will explain each part in detail in the following chapters) :

**A) code as A polynomial problem**

Write the program to be verified as a quadratic polynomial equation: t(x) h(x) = W (x) v(x). This equation is true if and only if the program computes correctly. The prover has to convince the verifier that this is true.

**B) Simple random sampling**

The verifier will choose a private evaluation point S to reduce the problem of polynomial multiplication and verification polynomial function equality to the problem of simple multiplication and verification equation T (s) H (s) = W (s) V (s).

This not only reduces the amount of proof, but also greatly reduces the verification time.

**C) Homomorphic coding/encryption**

We use an encoding/encrypting function E that has some homomorphic properties (not completely homomorphic, at least in practice, some that are not). This function allows the prover to calculate E(t(s)), E(h(s)), E(w(s)), E(v(s)) without knowing s, she only knows E(s) and some other useful encrypted information.

**D) zero knowledge**

The prover replaces the values of E(t(s)), E(h(s)), E(w(s)), E(v(s)) by multiplying them by a number, so that the verifier can still verify their correct structure without knowing the actual encoding value.

One rough idea is that because the checksum t(s)h(s) = w(s) V (s) and the checksum T (s) H (s) k = W (s)v(s) k (for a private random number k that is not equal to zero) are almost exactly the same, The difference is that if you only receive (T (s) H (s) K) and (W (s)v(s) K) then it’s almost impossible to get the values of T (s) H (s) or W (s)v(s).

Of course, this is just scratching the surface to give you an idea of what zkSNARKs really are, but now let’s dive into the details.

## RSA and zero knowledge proof

Let’s take a quick look at how RSA works, regardless of the trivial details. If you think about it, we often modulo some numbers with a single number, not all integers. The equation here “A + b ≡ c (mod n)” is equivalent to “(a + b) % n = c % n”. Note that the ‘(mod n)’ part is not applied to ‘C’, but to ‘≡’ and all the other ‘≡’ of the same equation. It’s very difficult to read, but I promise to use them sparingly. Then let’s go back to RSA:

The prover provides the following figures:

- P, Q: two random private prime numbers
- n := p q
- D: 1 < d < n-1 random number
- E: D E ≡ 1 (MOD (P-1)(Q-1))

The public key is (e, n), and the private key is D. Prime numbers p and Q can be discarded, but not exposed.

Message M is encrypted using the following formula:

E ( m ) : = m e % n E(m) := m^{e} \,\%\,n E(m):=me%n

C = E(m) decrypted by the following formula:

D ( c ) : = c d % n D(c) := c^{d}\,\%\,n D(c):=cd%n

Because c d c ^ {d} CD ≡ (m e % n) d (m ^ {e} \ % n) ^ {d} (me % n) ≡ m e d d (m o n d) m ^ {of} Ed (mod \ \, n) med (modn), And the exponent of m is the modulo of the set of numbers (p-1)(q-1), so we get med≡m(modn) m^{Ed} \equiv m(mod \,\,n) med≡m(modn). Moreover, the security of RSA is based on the assumption that n cannot be easily factored efficiently and d cannot be computed by e (if we know p and Q, we can easily get the desired value).

One cool feature of RSA is homomorphic multiplication. In general, two operations are said to be homomorphic if you can switch the order of the two operations without affecting the result. In homomorphic encryption, this is a property that you can perform calculations on encrypted data. Fully homomorphic encryption exists, but is not yet in practice. It can perform calculations on any program based on encrypted data. If a multi is used here for RSA, we only talk about group x. To be more precise: E(x)E(y) E(x)E(x)E(x)E(y) E(y)≡ x E y E x^ey^exeye ≡ (xy) E(xy)^ E(xy) E ≡ E(x y) (mod n)E(xy) (mod \,n)E(xy)(modn), which is described in words: The product of two encrypted messages equals the encryption of the product of two messages.

This homomorphism property has some zero-knowledge proof of multiplication: the prover knows some private numbers X and y and calculates their product, but only sends the verifier the encrypted version: A = E(x), b = E(y), and C = E(x y). The verifier checks whether the equation (a b) % n ≡ c % n is true. At this point, the verifier only knows the product of the encrypted version and whether the product is computed correctly, but she does not know the two multipliers and the real product. If you use addition instead of multiplication, that’s a blockchain direction where the main operation is to add the balance.

## Interactive validation

Now that we’ve covered the concept of zero knowledge, let’s focus on another major feature of zkSNARKs: succinctness. You’ll see later that this simplicity is the more awesome part of zkSNARKs, because the zero-knowledge part is implemented because of this particular code, and this particular code is a homomorphic code of a finite form.

SNARKs is short for succinct non-interactive arguments of knowledge. The common setup is called an interactive protocol because there is a prover and a verifier, and the verifier wants to convince the verifier of an expression (such as f(x) = y) by exchanging information. In general, no prover can convince the verifier of a false expression (reliability), and there must be a definite strategy for the verifier to convince the verifier of any true expression (completeness). The meanings of each part of SNARKs are as follows:

- Succinct: The size of the message we sent was small compared to the actual length needed to be calculated
- Non-interactive: There is no or very little interaction. In the case of zkSNARKs, this is after the prover sends a message to the verifier. In addition, SNARKs often have a property called a “public verifier,” which means anyone can verify without interacting again, which is crucial for blockchain.
- Arguments: Validator is only valid for validators with limited computational power. A prover with enough computing power can create proofs and arguments about the error expression (note that with enough computing power, any public-key cryptosystem can be broken). This is also called “computational reliability”, as opposed to “perfect reliability”.
- Of Knowledge: It is not possible for the prover to construct a set of parameters and proofs without knowing something called witness (such as the preimage of a hash function or a path to determine a Merkle-tree node).

If you prefix it with zero knowledge, then you need a property in the interaction where the verifier knows nothing other than whether the expression is correct or not. In particular, the validator cannot know about the Witness String – we’ll explain what that is in more detail later.

As an example, let’s consider the following transaction validation calculation: If and only if $σ_1$and $σ _2 $are root hashes of accounts merkle-trees (pre and post states) and s and R are sender and receiver accounts, P s p_s ps and pr p_r pr are Merkle-tree proofs that the balance of S in $σ_1 $is at least V when v is transferred from the balance of S to the balance of r, and their result is $σ_2 $instead of σ_1. When these conditions are established, f ($$, sigma _1 $sigma _2 $, s, r, n, p, s p_sps, p r p_rpr, v) = 1.

It is relatively easy to verify the calculation of f if we know all the inputs. Because we can convert f to a zkSNARK, only $σ_1$and $σ_2$are exposed, (S, R, V,ps, P r, V) (S, R, V, p_S, p_R, V) (S,r,v,ps,pr,v) is witness String. The zero-knowledge nature now allows the verifier to check that the prover knows of witness that converts the root hash from $σ_1$to $σ_2$in a way that does not affect normal transactions, but that the verifier does not know exactly who sent how much money to whom.

Knowledge about zero parts of relatively formal definition (still lack of some details) is: there is a simulator, it can generate some setting field, but don’t know the secret witness, it can also interact with the verifier, but external observer cannot distinguish which interaction with verifier, which is the interaction with the certifier.

## NP and simplified complexity theory

To understand what kind of problems and calculations zkSNARKs can be used for, we have to define some statements based on complex theories. If you don’t know what “Witness” is, you won’t know what it is even after “reading” the zero-knowledge proof, and you won’t know why zkSNARKs are only good for certain polynomial problems, if that’s the case, then you can skip this section.

### P and NP

First, we restrict functions to printing only 0 and 1, and call such functions problems. Since you can query each bit of a long result individually, this isn’t really a limitation, but it makes the theorem a bit simpler. Now we want to measure how “hard” it is to solve a given problem (compute a function). For a particular machine implementation M of a mathematical function F, given an input x, we can calculate the number of steps required for this function F — this is called the execution time of x on M, where the “number of steps” is not really important. Because programs tend to require more steps for larger inputs, the execution time is measured by the size or length of the input value (the number of bits). This is where the example “n2 n^{2} n2 algorithm” comes in – this is an algorithm that takes at most n2 n^{2} n2 steps when the input value is of n size. Here “program” and “algorithm” are broadly the same.

Programs with execution times of at most N k n^{k} nk are also called “polynomial-time programs”.

There are two main categories in complexity theory, and they are P problems and NP problems:

- P problem is a class of problems with polynomial time

While k exponents are indeed very large for some problems, in practice P problems with k not greater than 4 are still considered “solvable” for non-artificial problems. Confirming a bitcoin transaction is a P problem, as it takes polynomial time to evaluate (and outputs only zeros and ones). To put it simply, if you just calculate some values and don’t “search”, then the problem is a P problem. But if you have to search for something, then you fall into another category called NP problems.

### NP problem

Almost all NP problems are zkSNARKs, and the zkSNARKs used in practice today are NP problems in a general sense. What we don’t know yet is whether zkSNARKs exist that aren’t NP problems.

All NP problems have a specific structure that comes from the definition of NP problems:

- The NP problem is a class of L (polynomial time program V), which can verify a factor given a polynomial scale called witness. More formally, L(x) = 1 is true if and only if some polynomial scale string w (called Witness) satisfies V(x, w) = 1.

Let’s look at an example of an NP problem, such as a Boolean function satisfiability problem (SAT). First, let’s define the Boolean function:

Any variable A 1,x2,x3, a_1, X_2, x_3, A1,x2,x3… Both are Boolean (we will also use other letters to set variables) If F is a Boolean, then ¬f is also a Boolean (no proposition) If f and G are both Boolean, then (F ∧ g) and (F ∨ g) are both Boolean (∧ is and, ∨ is or)

The string “((x_1∧ x_2) ∧ ¬x_2)” is also a Boolean function.

If it is possible to assign a true value to the variable and then the Boolean function evaluates to true (¬true is false, ¬false is true, true ∧ false is false, etc.), we say that the Boolean function is satisfiable, Satisfiability problem SAT is the set of all satisfiable functions.

- SAT(f):= 1 holds if and only if f is a satisfiable function that is not 0

The example above “((x1 x_1x1∧ x2 X_2x2) ∧ ¬ x2 X_2x2)” is not satisfiable and therefore does not belong to SAT. Proving that a given formula satisfies the definition while ensuring that the variables it assigns are also satisfiable is a problem that can be solved in polynomial time.

### P = NP ?

If you define an NP problem as witness strings of length 0, you’ll see that it’s a P problem. So every P problem is an NP problem. One of the main tasks in the study of complexity theory is to discover the difference between these two kinds of problems – that is, an NP problem that is not P. It seems obvious here, but if you can prove it in general, then you can get $1 million. And as a bonus, if you can prove the opposite, that P and NP are equal, you can also get that bonus. The odds are high that digital money will one day prove it. The reason I say this is that it is obviously easier to find a proof of the solution to a working problem than it is to collide a hash function or find a private key by address. These are NP problems, and since you’ve just proved that P = NP, there must be a polynomial time program for these NP problems. However, this paper will not discuss it, although most researchers believe that the P problem and NP problem are not equivalent.

### NP complete problem

Let’s go back to the SAT. An interesting property of this seemingly simple problem is that it is not only an NP problem, but an NP-complete problem. The word ‘complete’ here means the same thing as’ Turing complete ‘. This means that it is the hardest problem in NP, but even more important is the definition of NP-complete — the input to any NP problem can be converted to an identical SAT input using the following method:

All NP problems L have a reduction function f that is computable in polynomial time:

- L(x) = SAT(f(x))

Such a reduction function cannot be considered a compiler: a compiler is a machine that can translate the source code written in some programming language equivalently into another programming language, that is, a machine language with semantic behavior. Since the SAT is NP-complete, such a restore is available for any possible NP problem, such as verifying that a Bitcoin transaction is legitimate, given a proper block hash. It is also possible to convert a transaction into a reduction of a Boolean function, so the Boolean function is satisfied if and only if the transaction is legal.

### Reduction of the sample

To understand such a reduction approach, let’s first consider evaluating polynomials. First, let’s define a polynomial (similar to a Boolean function) consisting of integer constants, variables, addition, subtraction, multiplication, and (correctly matched) parentheses. Now let’s consider the following question:

- If f is a polynomial whose variables all come from the set {0, 1} and which contains a zero term, then PolyZero(f):= 1

Now we can build a reduction method from SAT to PolyZero, which shows that PolyZero is also nP-complete (I’ll leave it to you as a little exercise to verify that it’s NP).

It is possible to define a reduction function r on the structural elements of a Boolean function. For any Boolean function f, r(f) has the same number of variables, and if and only if r(f)(a 1,.., a k) r(f)(a_1,.. ,a_k) r(f)(a1,.. ,ak) = 0 f(a 1,..,ak) f(a_1,.. ,a_k) f(a1,.. ,ak) is true, where true is 1 and false is 0, and r(f) only assumes the value 0 or 1 from the set {0, 1} :

- X_i := (1 – x_i)
- R (¬f) := (1 – r(f))
- R ((f ∧ g)) := (1 – (1 – r(f))(1 – r(g)))
- R ((F ∨ g)) := r(f)r(g)

Some might assume that r((f ∧ g)) is defined as r(f) + r(g), but then the polynomial results would be outside the set {0, 1}.

Using the function r, (Sunday afternoon y (x) ∨ x) was transformed into (1 – (1 – (1 – x)) (1 – (1 – y)) (1 – (1 – x)).

Note that for R, each substitution rule satisfies the stated purpose, so r also implements the restore correctly:

- SAT(f) = PolyZero(r(f)) or f is satisfied if and only if r(f) contains a 0 in the set {0, 1}

### Witness preserving

From this example you can see that the reductor only defines how to convert the input, but when you look at it carefully (or after reading how to complete a usable restore evidence) you will know how to convert an available Witness with the input. In our example, we only defined how to convert the function to a polynomial, but we don’t know how to convert the evidence we interpret into witness that satisfies the assignment. This Witness conversion at the same time is not necessary for transactions, but is usually included. This is crucial for zkSNARKs, because his only job for the prover is to convince the prover that witness exists without revealing anything about it.

## Quadratic Span Programs

In the previous section, we saw how calculations of NP problems can be reduced to each other, especially those that are NP complete, and those that are essentially regenerated into other NP problems — including transaction validation problems. Then it becomes easy for us to find a zkSNARKs that is universal for all NP problems: we just need to choose the suitable NP-complete problems. So if we wanted to show how to use zkSNARKs to verify transactions, showing how to deal with this deterministic NP-complete problem would be an effective way to do it, and much more acceptable than explaining it in theory.

Based on paper GGPR12 (which links to more technical reports than the original article), the authors of this paper identified a problem called Quadratic Span Programs (QSP) that was designed exactly for zkSNARKs. A Quadratic Span Program consists of a set of polynomials and a linear combination of tasks to find multiples of a given polynomial. In addition, each individual bit of the input string limits the polynomial you can use. To be specific (GSPs is generally not very restrictive, but we need a strongly restrictive version, as we will use it later) :

The QSP problem on field F for input length n consists of the following parts:

A set of polynomials over field F v0 v_0v0… , vm v_mvm, w0 w_0w0,… , w m w_m wm domain F t (target) polynomial of a polynomial on an injective function F: {(I, j) | 1 I n or less, or less j ∈ {0, 1}} – > {1,… , m}

The task here is very crude, which is to multiply polynomials by a factor and add them up (also called “linear combinations”) so that their sum is a multiple of T. For each binary input string u, f limits the polynomials that can be used, or more strictly, the factors that must be linear combinations. The formal expression is:

An input u will be accepted (or validated) by QSP if and only if a tuple from field F = (a1 a_1A1… , am a_mam), b = (b1 b_1b1,… , bm b_mbm) satisfies:

If k= f(I, u[I]) then ak,bk=1 a_k,b_k =1 AK,bk=1 (u[I] is the ith bit of U) Then ak, B k=0 a_k,b_k = 0ak,bk=0 Target polynomial t divisible by v A, W b, V A V_A, W_B, V_A VA, WB, VA = V 0+a1v0 v_0 + a_1 v_0V0 + A1v0 +… + amvm a_mv_mamvm, wb w_bwb = w0+b1w0 w_0 + b_1 w_0w0+b1w0 +… + b m w m b_m w_m bmwm

Note that here, when 2n is less than m, the choice tuples A and B still have a lot of freedom. This means that QSP is only valuable for inputs of a certain size — a problem that can be solved by using heterogeneous complexity, a topic that we won’t go into in depth today, except that our cryptography works well when input values are small.

To make an analogy with the satisfiability of Boolean functions, you can see that the factors a, 1, a_1A1… , am a_mam, b1 b_1b1,… B m b_m BM as the assigned variable, or the witness of the NP problem. Since QSP is in NP, all verifiers must (as long as she knows the factors) check whether the polynomial t is divisible by v A W b v_A W_bvawb, which is also a polynomial-time problem.

We will not discuss here how to reduce the general-purpose computation and routing problems to QSP problems, as this does not help us understand the basic concepts, except that QSP is NP-complete (or more complete than some non-uniformly distributed problems like NP/ POLY). In fact, this simplification is an “engineering” part — there has to be a clever way to make the QSP problem as small as possible and have some other nice features.

One thing we know about QSPS is how to verify them more efficiently: the verification task is to check whether one polynomial is divisible by another polynomial. If the prover can provide a polynomial h such that T h= V A W B th= V_A W_B th=vawb, then the task is transformed to checking a polynomial identity, In other words, testing th− V a W b=0 t H – V_A W_B = 0th−vawb=0 is actually testing whether a particular polynomial is a zero polynomial. Although this may seem simple, the polynomials we are going to use are so large (about 100 times the order of the original circuit control stage) that obtaining the product of the two polynomials is not an easy task.

So instead of actually calculating v A, W b, V_A, W_BVA,wb and their product, the validator only needs to select a private random point (which is part of the “toxic waste” in zCash), And then for all k, t(s), V k(s), V_k (s), vk(s), and W k(s), W_k (s), wk(s), And verify the equation with them as well as v A (s) V_A (s) VA (s) and W b(s) W_B (s) WB (s) : T (s) h (s), t (s) h (s) t (s) h (s) = v (s) w b (s) v_a w_b (s) (s) va wb (s) (s). All of this series of polynomial additions, scalar multiplication and a polynomial product can be reduced to multiplication and addition over a field.

Verifying polynomial identities at a single point rather than all points of the path reduces security, but the only time the prover can cheat is when th− V a W B T h-V_A W_bth − Vawb is not a zero polynomial, even if the prover succeeds in obtaining a zero term of the polynomial, But she doesn’t know s either, and the number of zeros is small compared to the possible value of S (the number of elements in the field), so it’s actually quite safe to only validate at a single point.

## ZkSNARK,

Now let’s describe zkSNARK on QSP in detail. It performs each individual QSP during the initial setup phase. In zCash, the circuit of the transaction verifier is fixed, so the polynomial of the QSP is fixed, and this QSP is only allowed to be executed once in the setup phase, and then reused over all transactions that have only a different input u. This initial setting generates a common Reference String (CRS) where the verifier selects a random and private field element and encrypts the value of the polynomial at this point. The verifier uses some specific encryption methods E and exposes E(vk v_kvk(s)) and E(W k w_kwk(s)) in CRS. CRS also contains values that make validation more efficient and add zero-knowledge attributes. The encryption method E used here has an explicit isomorphic property that allows the prover to calculate E(v(s)) without knowing vk v_kvk(s).

### How to use zero knowledge to estimate a polynomial simply

Let’s first look at a simple case, the cryptographic valuation of a polynomial at a private point, rather than the full QSP problem.

To do this, we choose a group (where elliptic curves are usually used) and a generator G. For the element G in the group, if there is a number n (order of the groups) such that the list G <em>0, G 1, G 2,</em>g<em>0, g_1, g_2,</em>g<em>0,g1,g2,</em>… , g gg{n-1} contains all the elements of the group, then we call g “generator”. The encryption method is simple: E(x) := gx g^ XGX. Now the verifier selects a private domain element S and publishes it as part of the CRS

E (0 s), E (1 s) E ^ 0 (s), E (s ^ (1) E (s0), E (s1),… E(sd) E(s^d)E(sd) — d is the highest order of all polynomials

After that, s can (or must) be forgotten. This is what zCash calls “toxic waste”, because if someone recovers the toxic waste and then picks some secret value, he can falsify evidence at will by finding the zero term in the polynomial.

Without knowing s, E(s2)4 E(s^2)^4 E(s2)4 The prover can use these values to compute E(f(s)) for any polynomial f: Let’s say our polynomial is f of x is equal to 4×2 plus 2x plus 4 f of x is equal to 4x squared plus 2x plus 4 f of x is equal to 4×2 plus 2x plus 4 if we want to compute E of f of s, We get E(f(s)) = E(4s 2 + 2s + 4) = g (4s 2 + 2s + 4) = E(s 2) 4e (s 1) 2e (s 0) 4e (f(s)) = E(4s^2) + 2 + 4) = g4s s ^ 2 + 2 s + 4 = E (s ^ 2) ^ 4 E s ^ (1) ^ 2 E (s) ^ 0 ^ 4 E (f) (s) = E (4 s2 + 2 s + 4) = g4s2 + 2 s + 4 = E (s2) 4 (s1) 2 E E (s0) 4, These values can be obtained from the public CRS without knowing the definite S.

The only problem here is that when s is destroyed, the verifier can’t verify that the prover computed the polynomial correctly. So we also need to select another private domain element, A, and expose the following “transition” values:

E (a 0 s), E (a s 1) E (as ^ 0), E (as ^ 1) E (as0), E (as1),… , E ( a s d ) E(as^d)E(asd)

After the setup phase, A is destroyed along with S, and neither the verifier nor the prover knows this value. But using these encrypted values, the prover can easily calculate E(α f(s)), as in the example above: E ( 4 a s 2 + 2 a s + 4 a ) = E ( a s 2 ) 4 E ( a s 1 ) 2 E ( a s 0 ) 4 E(4as^2 + 2as + 4a) = E(as^2)^4 E(as^1)^2 E (as ^ 0) ^ 4 E (4 as2 as + 4 a + 2) = E (as2) 4 E E (as0) 4 (as1) 2. So if the prover announces A := E(f(s)) and B := E(α f(s))), then the prover can verify whether these values match. To verify a match, we need to use our other main trick, the pairing function e. The elliptic curve and the pairing function must be chosen together, so that x and y satisfy the following equation:

e ( g x , g y ) = e ( g , g ) x y e(g^x, g^y) = e(g, g)^{xy} e(gx,gy)=e(g,g)xy

Using this pairing function, the verifier can verify that e(A,g A)=e(B,g) e(A,g ^ A)=e(B,g) e(A,ga)=e(B,g) — note that the verifier knows ga, Because it’s part of the CRS of E(as0) E(as^0) E(as0). To make sure that this method works and that the prover is not cheating, let’s look at the following equation: e ( A , g a ) = e ( g f ( s ) , g a ) = e ( g , g ) a f ( s ) e(A, g^a) = e(g^{f(s)}, g^a) = e(g, g)^{a f(s)}e(A,ga)=e(gf(s),ga)=e(g,g)af(s) e ( B , g ) = e ( g a f ( s ) , g ) = e ( g , g ) a f ( s ) e(B, G) = e (g ^ {a (s)} f, g) = e (g, g) ^ {a, f (s)} e (B, g) = e (gaf (s), g) = e (g, g) af (s), however, A more important question is whether the prover can provide e(A, g A) = e(B, g) e(A, g^ A) = e(B, G) e (A, ga) = e (B, g) instead of e (f) (s) e (f) (s) e (f) (s) and e (A f (s))) e (A f (s))) e (af (s))) of A and B. The answer to that question is “we hope he doesn’t”. Strictly speaking, we call this the “d-power exponential knowledge hypothesis,” and we don’t know if a cheating prover can do it. This hypothesis is also an extension of other similar assumptions used to prove the security of public-key encryption schemes, and these assumptions do not seem to confirm whether they are correct.

In fact, the protocol above does not really require the verifier to verify the polynomial f(x)=4×2+2x+4 f(x)=4x ^2 +2x+ 4f(x)=4×2+2x+4 provided by the prover, the verifier only needs to verify “a few” polynomials at the point S. The zkSNARK of the QSP problem also contains an additional value that allows the verifier to verify that the prover has really evaluated the correct polynomial.

The example shown here shows that the verifier does not need a full polynomial to prove this, just the pairing function. The next step is to add the zero-knowledge part so that the verifier can’t construct any f(s) values, not even the encrypted information E(f(s)).

To do this, the prover will pick A random \delta and send A ‘:= E(δ + f(s)) and B := E(α (δ + f(s))))) instead of A: = E (f) (s) A: = E (f) (s) : A = B and E (f) (s) : = E (A f (s))) : B = E (A f (s))) : B = E (af (s))). If we assume that the encryption algorithm is unbreakable, the property of zero knowledge becomes obvious. Now we need to verify two things: 1. The prover can actually compute these values. 2. The verifier’s result is still true.

**For the first thing, note: A ‘= E (delta) + f (s) = g ^ {delta + f (s)} = g ^ ^ the delta g (s)} {f = E (delta) E (f) (s) = E (delta). A, in the same way, B = ‘E (alpha (delta + f (s)))) = E (alpha delta alpha + f (s))) = g ^ {alpha delta alpha + f (s)} = g ^ ^ {alpha delta} g {alpha f (s)} = E (alpha) delta E (alpha f (s) = E (alpha) delta B.**

**Second, because the only thing the verifier has to do is verify that the A and B she receives satisfy the equation based on A: A = E(A) and B = E(α A). So the a here obviously satisfies a = delta + f(s), which is essentially a = f(s).**

Ok, so now we know a little bit about how the prover can compute a polynomial encrypted value over an encrypted private point without the verifier knowing that value. Let’s apply this to the QSP problem.

### QSP problem SNARK

Remember, in the QSP problem we had some polynomials v0, v_0,v0… V m,w0, v_m, w_0, VM,w0… , wm w_mwm, the target polynomial t (highest order D) and a binary input string U. The prover will find a, 1, a_1, A1… ,am b1 a_m b_1 am b1… , bm b_MBm (these values all depend on u) and the polynomial h:

T ht HTH = (v0+a1v1+ (v_0 + a_1v_1 +(v0+a1v1+… +amvm)(w0+b1w1+ + a_m v_m) (W_0 + b_1w_1 ++ AMVM)(w0+ b_1w1 +… + b m w m ) + b_m w_m)+bmwm)

In the previous section we explained how CRS is generated. Now we choose a private s and a and publish them:

E (0 s), E (1 s), E (s ^ 0), E (s ^ (1), E (s0), E (s1),… D, E (s) E (s ^ d) E (sd) and E (a 0 s), E (a 1 s), E (as ^ 0), E (as ^ 1), E (as0), E (as1),… , E ( a s d ) E(as^d) E(asd)

Since we don’t have a single polynomial, and the list of polynomials is fixed for the current problem, we also need to publish the derived polynomials immediately:

E (t) (s), t (s) (a) E E 0 (s) (v), E (t) (s), E (a t (s)) E (v_0 (s)), E (t) (s), E (at) (s) E (where v0 (s)),… M (s), E (v), E (a v 0 (s)), E (v_m (s)), E (a v_0 (s)), E (vm (s)), E (av0 (s)),… M (s)), E (a v E 0 (s) (w), E (a v_m (s)) E (w_0 (s)), E (avm (s)) E (w0 (s)),… M (s), E (w), E (a w 0 (s)), E (w_m (s)), E (a w_0 (s)), E (wm (s)), E (aw0 (s)),… , E ( a w m ( s ) ) E(a w_m(s))E(awm(s))

We also need a private number for future use βv, β W, γ (which will be used to verify that polynomials are extrapolated, not arbitrary polynomials) and publish them:

E(γ), E(β_v γ), E(β_w γ) E(β_v v_1(s)),… , E(β_v v_m(s)) E(β_w w_1(s)),… , E(β_w w_m(s)) E(β_v t(s)), E(β_w t(s))

That’s the full CRS. Some elements in CRS are not necessary in the actual implementation, but that would complicate our expression.

Now what else does the prover have to do? She uses the reduction function explained above to find the polynomials H and A 1, a_1, A1… ,am b1 a_m b_1 am b1… B, M, b_m, bm, these values. It’s important to use a witness-preserving reduction here, because only then will a1, A_1, A1,… ,am b1 a_m b_1 am b1… , B m B_MBM can be calculated along with reduction, otherwise it will be very, very difficult. To describe the proof that the prover sends to the verifier, we have to look again at the definition of QSP.

There is a limit a < e m > 1. < / e m > a < em > 1. < / em > < em > 1, a < / em >… ,am b1 a_m b_1 am b1… , b, m b_m bm these values of injective function f: {(I, j) | 1 I n or less, or less j ∈ {0, 1}} – > {1,… , m}. Since m is relatively large, the output of f will not contain these numbers for any input. And these subscripts are not restricted, so we’ll just call them I, II{free}, Then based on all subscripts k in I<em>free</em> I<em>{free} </em>I<em>free</em> v vv{free}(x) = σ _ka_kv_k (x). For the equation w(x) w(x) w(x)= b1w1(x)+b_1w_1(x) + b1w1(x)+… + BMWM (x)+ b_mw_m(x)+ BMWM (x), our proof will consist of the following:

V < e m > f r e e : = E ( v < / e m > f r e e ( s ) ) , W : = E ( w ( s ) ) , H : = E ( h ( s ) ) V*{free} := E(v*{free}(s)), W := E(w(s)), H: = E (H (s)) V < em > free: = E (V < / em > free (s)), W: = E (s) (W), H: = E (s) (H) : Y = E (beta V V {free} (s) + beta _w W (s)))

The final equation checks to see if the correct polynomial is used (this is not covered yet, but it will be covered in other examples). It should be noted that all of our encrypted values can be calculated by the prover only need to know CRS.

The validator now has to do this:

Since k is not a subscript of “free”, the value of a_k can be calculated directly by entering u (the verifier also knows the value of u, which is the value to be checked). The verifier can also calculate the sum from v:

`E (v_ {in} (s)) = E (Σ _k a_kv_k (s)) is k here with all the "not" I_} {free of subscriptCopy the code`

Given the above formula, the verifier can use the pairing function E (don’t be afraid…). To confirm the following equation:

`E (V '_} {free, g) = e (V {free}, g ^ alpha), e (W, e (1)) = e (W, e (alpha)), e (H', e (1)) = e (H, e (alpha)) e (e (gamma), Y) = e (e (beta, _v gamma), V_} {free) e (e (beta _w gamma), W) e (e (v_0 (s)) e (V_ {in} (s)) V_} {free, e (w_0 (s)) W) = e (H, e (t (s)))Copy the code`

To understand the key concept here, you must know that the pairing function allows us to perform a limited number of calculations on encrypted information: first we can use any number of additions, but not multiplication. Secondly, the addition is the addition homomorphism from the encryption method itself, and the multiplication rule is realized by pairing two parameters of the function. So e(W ‘, e(1)) = e(W, e(α)) is basically multiplying 1 by W ‘in encrypted space and comparing it with \alpha times W. Recall the above definitions and you will see that W and W ‘should be E(W (s)) and E(α W (s)) (if the prover provides the correct proof).

If you remember from above how to deduce polynomials at a private point, the first three points to check basically confirm that the prover does know some polynomials constructed from parts of CRS. The second entry is often used to ensure that the prover is using the correct polynomials V and W, rather than arbitrary polynomials. The logic behind it is that the prover cannot compute the cryptographic combination E(β_v v{free}(s) + β_w w(s)), except to obtain exact values from E(v{free}(s)) and E(w(s)). Because β_v is isolated in CRS and not part of CRS, the value of β _V is only known when combined with the polynomial w_k(s). And the only way to “mix” them together is with the same encryption gamma.

Assuming the prover provides a correct proof, let’s check that the equation is satisfied. The left and right parts are:

`E (e (gamma), Y) = e (e (gamma), e (beta _v v_} {free beta _w (s) + w (s))) = e (g, g) ^ {gamma (beta _v v_} {free beta _w (s) + w (s))} e (e (beta, _v gamma), V_} {free) e (e (beta _w gamma), W) = e (e (beta, _v gamma), e (V_} {free (s))) e (e (beta _w gamma), e (s)) (W) = e (g, g) ^ {(beta) _v gamma V_ (s)} {free} e (g, G) ^ {(beta _w gamma) w (s)} (g, g) = e ^ {gamma (beta _v v_} {free beta _w (s) + w (s))}Copy the code`

The third entry essentially checks (v_0(s) + a_1v_1(s) +… + a_mv_m(s)) (w_0(s) + b_1W_1 (s) +… + b_MW_m (s)) = h(s) t(s), which is also the main condition of QSP problem. One note is to convert multiplication of encrypted values to addition of unencrypted values, because E(x) E(y) = g^x g^y = g^{x+y} = E(x +y).

### Add zero knowledge

As I said at the beginning, the most remarkable feature of zkSNARKS is not zero knowledge per se, but simplicity. From now on we’ll see how to add this zero-knowledge property, and the next section will focus on brevity. The idea of zero knowledge is that the prover now “shifts” through a random private value, and then “shifts back” in other equations to achieve balance. The prover will select δ_{free}, δ _W, and perform the following substitution in the proof:

`With v_} {free (s) + delta _} {free t (s) to replace v_} {free (s) with w (s) + t (s) to replace the delta _w w (s)Copy the code`

With these two substitutions, V_{free} and W, which contain the encoding of the Witness factor, are essentially indistinguishable random values and therefore impossible to extract from Witness. Most equality checks are immune to modification, and we want to make sure that the correct value is H or H of s. So let’s make sure that:

`(v_0(s) + a_1v_1(s) +... + a_mv_m(s)) (w_0(s) + b_1W_1 (s) +... + b_mw_m (s)) = h (s) t (s), or (v_0 v_ (s) + {in} (s) + v_} {free (s)) (w_0 (s) + w (s)) = h (s) t (s)Copy the code`

These two equations are true. After modification, we get:

`(s) + v_ (v_0 {in} (s) + v_} {free (s) + delta _} {free t (s)) (w_0 (s) + w (s) + delta _w t (s))Copy the code`

Then expand the result and we can replace it with h(s) :

`H (s) + delta _} {free (w_0 (s) + w (s)) + delta _w (v_0 v_ (s) + {in} (s) + v_} {free (s)) + (delta _} {free delta _w) t (s)Copy the code`

## Take a compromise value between the input and the Witness size

As you can see in the sections above, our proof consists of seven elements of a group (that is, an elliptic curve). And the verifier’s job is to check the equality of some pairing function and compute E(v_{in}(s)), a linear task that follows the size of the input. Most importantly, neither the size of the Witness string nor the amount of work needed to validate QSP (no SNARKs) is required during this validation process. This means that SNARKs verification is a complex problem, and simple problems are often the same. The main reason for this result is that we only tested the consistency of the polynomial on a single point, not all points. Polynomials can get very, very complicated, but a point is still a point. The only parameters that affect the validation results are the level of security (such as the size of the group) and the maximum size of the input value.

It is possible to reduce the second argument by moving part of the input value into Witness: Instead of validating the function f(u, w), where u is the input and w is witness, we hash once and then validate:

`F '(H, (u, w)) := f(u, w) ∧ H (u) = HCopy the code`

This means that we can use a hash to represent the input h(u) (which will be shorter). In addition to verifying f(x, w), we also need to verify that the hash of some value x is equal to h(u) (in which case x is most likely equal to u). This moves the original input u to the Witness string, which increases the size of Witness but reduces the size of the input value to a constant.

This is awesome, because it means we can check any complex expression in constant time.

## Relationship with Ethereum

Because validation computing is at the heart of the Ethereum blockchain, zkSNARKs and Ethereum are closely related. With zkSNARKs, not only can we do private computations that anyone can verify, but we can do them efficiently.

Although Ethereum uses a Turing-complete virtual machine, it is currently impossible to implement a zkSNARK on Ethereum. Conceptually, the verifier’s task seems simple, but the pairing function is really hard to calculate and consumes more gas in a single block. The multiplication of elliptic curves is already relatively complex, and the pairing function adds another level of complexity.

Existing zkSNARK systems like zCash use the same problem, circuit computing, for every task. In zCash, that’s transaction verification. On Ethereum, zkSNARKs will not simply solve a computing problem, but will allow anyone to build their own zkSNARK system without releasing a new blockchain. Each zkSNARK system added to Ethereum requires a new private and trusted preparation phase (some reusable, some not), such as generating a new CRS. Things like adding a zkSNARK system for a “universal virtual machine” will become possible. This way when you use a new instance, you won’t need to reset because you won’t need to publish a new blockchain for a new smart contract on Ethereum.

### Combine zkSNARKs on Ethereum

There are many ways to enable zkSNARKs on Ethereum. All of these methods reduce the real losses for pairwise functions and elliptic curve operations (all other necessary operations are simple), so we also reduce the gas consumed by these operations.

- Improve (ensure) EVM performance
- EVM performance is improved only on certain pairing functions and elliptic curve multiplication

The first one obviously pays off well in the long run, but it’s harder to pull off. We are already adding some new features and limitations to EVM, such as better support for just-in-time compilation and the implementation of the interpreter with minimal changes to the existing implementation. Of course, eWASM does not rule out replacing EVM directly.

The second can be achieved by forcing all Ethereum clients to perform a certain pairing function and certain elliptic curve multiplication called a precompiled contract. This has the advantage of being simple and fast to implement. The downside is that we’re going to be fixed to a certain pairing function and a certain elliptic curve. All new clients on Ethereum will have to implement this precompiled contract again. So, if there’s anything new, or if someone can find a better way to zkSNARKs, a better pairing function, a better elliptic curve, or if there’s something wrong with elliptic curve, pairing function and zkSNARK, then we’ll add it to the new precompiled contract.