This is a note part 1 of the paper Why and How zk-SNARK Works. It explains how zk-SNARK works and why it works and how it come to be this way.

1 Introduction

zk-SNARK is one kind of ZKP and stands for zero-knowledge Succinct Non-interactive ARgument of knowledge. Some ZKP applications are:

  • Proving statement on private data
    • Person A has more than X in his bank account
    • In the last year, a bank did not transact with an entity Y
    • Matching DNA without revealing full DNA
    • One has credit score higher than Z
  • Anonymouos authorization (without revealing its id and password)
    • Prove that requester R has right to access sensitive data
    • Prove that one is from the list of allowed countries/states
    • Prove that one owns a monthly pass to a subway/metro
  • Anonymous payment
    • Payment detached from any kind of id
    • Paying taxes without revealing one’s earning
  • Outsourcing computation
    • Outsource an expensive computation and validate that the result is correct without redoing the execution – trustless computing
    • Chaning a blockchain model from everyone computes the same to one party computes and everyone verifies

Interactive ZKP was introduced by GMR85. Non-interactive proof was by BMF88.

In any ZKP system, there is a prover who wants to convince a verifier that some statement is true without revealing any other information. A ZKP should satisfy three properties:

  • Completeness — if the statement is true then a prover can convince a verifier
  • Soundness — a cheating prover can not convince a verifier of a false statement
  • Zero-knowledge — the interaction only reveals if a statement is true and nothing else

zk-SNARK term was introduced in Bit+11.

2 The Medium of a Proof

Two non-equal polynomials of degree at most d can intersect at no more than d points. This is because a polynomial with a degree d has at most d values to make it 0. As a result, an evaluation of any polynomial at an arbitrary point is akin to the representation of its unique identity.

If a prover claims to know some polynomial that the verifier also knows, they can verify the statement using the following polynomial identity check protocol:

  • Verifier choose a random value for x and evaluate his polynomial.
  • Verifier gives x to the prover and asks to evaluate the polynomial in question.
  • Prover evaluates his polynomial at x and gives the result to the verifier.
  • Verifier checks if the local result is equal to the prover’s result, and if so then the statement is proven with a high confidence.

If x is an interger from the range of 1 to 10^77, then the number of points where evaluations are different is 10^77 - d. The probability that x accidentally hits any of the d shared points is equal to d / (10^77).

3 Factorization

Knowning a d-degree polynomial means one knows the d+1 coefficients. A solvable polynomial equation can be represented as a product of its factors: (x-a0)(x-a1)...(x-an) = 0. The factorized form has all the solutions on the surface.

For example: x^3 - 3x^2 + 2x = (x-0)(x-1)(x-2). If a prover claims to know a degree 3 polynomial such that x=1 and x=2 are two of all possible solutions (roots), it means the polynomial has the form: (x-1)(x-2)... where (x-1) and (x-2) are the cofactors of the polynomial in question. The Prover want to prove that indeed his polynomial has those roots without disclosing the polynomial itself. The t(x)=(x-1)(x-2) is called a target polynomial. He wants to prove that his polynomial p(x) is the multiplication of the target polynomial and an arbitrary h(x) such that p(x) = t(x) * h(x).

Using the polynomial identity check protocol we can compare polynomials p(x) and t(x) * h(x):

  • verfifier samples a random value r, calculates t = t(r) and gives r to the prover.
  • prover calculates h(x) = p(x) / t(x), evaluates p=p(r) and h=h(r) and sends (p, h) to verifier.
  • verifier checks that p = h * t that means p(x) has t(x) as a cofactor.

If the prover uses a different p'(x) that doesn’t have the necessary cofactors, there will be a remainder for p'(x) / t(x). There is a non-negligible low probability that the remainder will be divisible by t(x). However, the check requires the polynomial coefficients to be integers too, creating a significant limitation to the protocol. This is the reason to introduce cryptographic primitives which make such division impossible, even if the raw evaluations happen to be divisible.

There are several issues with the above protocol:

  1. Prover can select a random number h and set p = t * h.
  2. Because prover knows the random point r, he can construct any polynomial that has a shared point at r with t(r) * h(r). For example, when x=23, the polynomials x^3 - 3x^2 + 2x and x^3 - 3x^2 + 46 has the same value.
  3. There is no enforcement of a particular degree.

4 Obscure Evaluation

The first two issues are possible becuase r and t(r) are plaintext. It would be ideal if those values are hidden by encryption or hashing but still be able to compute operations on those obscure values – this is exactly what homomorphic encryption is designed for. There are multiple ways to achieve it.

For example, choosing a base g and encrypt a number as g^a. Then multiplication, addtion, subtraction can be performed on the encrypted value with different operations. a * b becomes (g^a)^b), a + b becomes g^a * g^b, and a - b becomes g^a / g^b.

However, since the base is public, it is easy to go back to the secret number by find the gth root of a result.

This is where the modular arithmetic comes to rescure. Modular arithmatic has some important properties:

  • it is closed in the range of numbers.
  • the order of operations and modulo doesn’t matter.
  • common arithmetic properties are preseved.
  • many operations have the same result.

All the homomorphic properties such as encryption, mutiplication, and addition of the scheme are preseved in the modular realm. These properties mean that we can operate on the numbers and hide the original secret number. If the modulo is sufficiently large, it becomes infeasible to find the exponent a from the v and the result of E(v) = g^v (mod n). But calculation of g^v is easy with a logN complexity.

There are some limitations: 1) wen cannot multiple two encrypted values. 2) we cannot exponentiate an encrypted value. These turn out to be the cornerstone of zk-SNARK.

To encrypt a polynomial such as p(x) = x^3 - 3x^2 + 2x, given that homomorphic encryption doesn’t allow to exponentiate an encrypted value, the value of E(x), E(x^2), and E(x^3) must be provided and the encrypted evaluation becomes g^p(x) = E(x^3)^1 / E(x^2)^3 * E(X)^2 while the value of x is hidden. Because of the homomorphic property, the encrypted evaluations of the same polynomials are always the same in encrypted space. Now the protocol can be defined as follows:

  • Verifier samples a random secret value s, calculates the target polynomial t = t(s) and encryptions of s for all powers i in 0, 1, , , d, i.e.: E(s^i) = (g^s)^i. Send all E(s^i) to prover.
  • Prover calculates h(x) = p(x)/t(x), then evaluates Ep = (E(p(s)) and Eh = (Eh(x)) using all E(s^i) in the encrypted space. Prover sends Ep and Eh to verifier.
  • Verifier checks that p = t(s) * h in encrypted space, i.e., Ep = Eh ^ t, which is g^p = (g^t)^h.

Because the secret s is hidden, it makes it hard for the prover to come up with non-legitimate but still matching evaluations. But the third issue, the constraint of degree is not enforced. For example, for some random r, let z_h = g^r and z_p = (g^t)^r, then z_p = g^t^r = (z_h)^t where the z_p has a different polynomial degree.

5 Restricting a Polynomial

Consider an elementary example of degree 1 polynomial with one variable and one coefficient f(x) = cx. The corresponding encryption of s is E(s) = g^s. We want to make sure that the prover only uses this value g^s to perform homomorphic multiplication with an arbitrary coefficent c, i.e., it must be of the form (g^s)^c.

One way to do this is to require the prover to perform the same operation on another shifted encrypted value alongside with the original one, i.e., s' = s^a ensuring that the result is exponentiation of the original value. Because the prover needs to provide both s^c and (s')^c, he has to

  • use the same exponent, i.e., c to both values.
  • only use the original s and s' because a is unknow to him. Operations of multiplication, addition, and subtraction violate the a-shift relationship. Exponentiation is not supported in encrypted space.

The one-term polynomial (monomial) can be used to a multi-term polynomial because the coefficient assignment of each term is calculated separatedly and then homomorphically added together. the ((Ep)^a = Ep') holds in multi-term polynomial. Prover cannot use anything else other than the original p and p'.

6 Interactive Zero-Knowledge

On the other side, a verifier can extract knowledge only from the data, i.e., Ep = g^p, Ep' = g^p', Eh = g^h, sent by the prover. To hide the data while making the verification valid, the prover can encrpt those data by selecting a random number b send back Ep ^ b, Ep' ^ b and Eh ^ b. We have achieved zero-knowledge.

So far we had an interactive zero-knowledge scheme that has the following issues:

  • the verifier can collude with the prover.
  • the verifier can generate fake proofs.
  • the verifier has to store t and s until its proof are verified, which allows an extra attack surface.

Therefore a separate interaction with every verifier is required in order for a statement to be proven. Though it is useful for an individual verifier, the proof is not trusted by other verifiers or it is inefficient when one needs to convince many parties simultaneously or permanently. To achieve that, we need the secret parameters to be reusable, public, trustworthy and infeasible to abuse.

7 Non-interactivity

Because the above homomorphic encryption doesn’t support the multiplication of two encrypted values, which is necessary for both verification checks multiplications of p = t * h and p' = p * a, it is impossible to encrypt t and a the same way encrypting pwoers of s.

Cryptographic pairings (bilinear map) is a mathematical construction, denoted as a function e(g^a, g^b) = e(g, g)^(ab). Giving a pair of encrypted inputs (g^a, g^b) from an input set, it maps the pair deterministically to their multiplied representation in a different output set of numbers. The source and output numvber sets are different therefore the output cannot be used as input – it resembles a hash function.

A rudimentary and technically incorrect mathematical analogy for pairing e(g*, g*) would be to state that there is a way to swap each input’s base and exponent, e.g., g^a -> a^g, then e(g^a, g^b) = e(g^b, g^a) = e(g^(ab), g^1) = e(g^1, g^(ab)) = e(g^1, g^a)^b = e(g^1, g^1)^(ab). Technically the result of a pairing is an encrypted product of raw values under a different generator g of the target set, i,e., e(g^a, g^b) = g^(ab). It has the properties of the homomorphic encryption, e.g., e(g^a, g^b) * e(g^c, g^d) = g^(ab) * g^(cd) = g^(ab + cd).

Assume that a trusted party to generate scrects s and shift value a. Then it generates all encrypted values include g^a and all necessary powers of s with the corresponding shift values g^s^i and g^s^a^i for i in {0, 1, ..., d}. It may also generate encrypted value Et = g^t of the trget polynomial for optimization. The raw values of a and s are deleted. The generated parameters (g^a, g^s^i, g^s^a^i) are referred to as common reference string (CRS). The process is called Trusted Party Setup.

Then with proving/evaluation key: (g^s^i, g^s^a^i) and verification key: (g^t, g^a), one can verify the proof with two checks:

  • check that p = t * h in encrypted space: e(g^p, g^1) = e(g^t, g^h) = e(g, g)^(t * h) which is equivalent to e(g, g)^p = e(g, g)^(t * h).
  • check polynomial restriction: e(g^p, g^a) = e(g^p', g).

8 Multi-Party Trusing

While the trusted setup is efficient, it is not effective since multiple users of CRS will have to trust that one deleted a and s, since currently there is no way to prove that. Hence a dishonest party would be able to produce fake proofs without being detected. It is necessary to minimize or eliminate that trust. One way to achieve that is by generating a composite CRS by multiple parties. Each party generates a random pair of (s, a) and augument another party through homomorphic multiplications. For example, three parties A, B, and C can generate composite s^i = (s_A)^i ^ ((s_B)^i) ^ ((s_C)^i) and a = a_A ^ (a_B) ^ (a_C). The process can be repeated for as many participants as neccessary. Even if one out of all is honest, it will be infeasible to produce fake proofs.

The consistency of each participnt can be checked by two formulas: e(g^s^i, g) = e(g^s^1, g^s^(i - d)) and e(g^s^i, g^a) = e(g^a^s^i, g).

To make sure that each party uses the previous data, every party has to publish his secret parameters (g^a, g^s^i, g^s^a^i) in addition to the composite CRS.

9 Succinct Non_Interactive Argument of Knowledge of Polynomial (zk-SNARKOP)

Having agreed upon target polynomial t(x) and degreed d of the prover’s polynomial, the zk-SNARKOP protocol is defined as follows:

  • Setup
    • sample ranomd values s, a
    • calculate encryptions (CRS) g^a, {g^s^i}, {g^s^a^i}
    • proving key: ({g^s^i}, {g^s^a^i})
    • verification key: (g^a, g^t)
  • Proving
    • assign coefficients {c_i}
    • calculate polynomial h(x) = p(x) / t(x)
    • evaluate g^p and g^h
    • evaluate g^(ap)
    • sample random b
    • set the randomized proof pi = (g^b^p, g^b^h, g^b^(ap))
  • Verficiation
    • parse proof pi as (g^p, g^h, g^p')
    • check polynomial restriction e(g^p', g) = g(g^p, g^a)
    • check polynomial cofactors e(g^p, g) = e(g^t, g^h)