ZkSNARKs (Zero knowledge proof) brief introduction

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.

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.

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.

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}

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.

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(g​x​​,g​y​​)=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.

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

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.