Why and How zk-SNARK Works 4: General-Purpose Computation

This is a series of articles. Part 3, ​ PDF version.

We have paved our way with a simple yet sufficient example involving most of the zk-SNARK machinery, and it is now possible to advance the scheme to execute zero-knowledge programs.


Algorithm 1: Operation depends on an input
function calc(w, a, b)
if w then
return a × b
return a + b
end if
end function

From a high-level view, it is quite unrelated to polynomials, which we have the protocol for. Therefore we need to find a way to convert a program into the polynomial form. The first step then is to translate the program into the language of math, which is relatively easy, the same statement can be expressed as following (assuming w is either 0 or 1):

Executing calc(1, 4, 2) and evaluating ​ f (1, 4, 2) will yield the same result: 8. Conversely calc(0, 4, 2) and ​ f(0,4,2) ​would both be resolved to 6. We can express any kind of finite program in such a way.

What we need to prove then (in this example), is that for the input (1, 4, 2) of expression ​ ​f(w,a,b) the output is 8, in other words, we check the equality:

Single Operation

Two operands (i.e., values) are being operated upon by an operator (e.g., +,–,×,÷). For example for operands 2 and 3 and operator “multiplication” these will resolve to 2 × 3 = 6. Because any complex computation (or a program) is just a series of operations, firstly we need to find out how single such operation can be represented by a polynomial.

Arithmetic Properties of Polynomials

For x = 1 these will evaluate to: ​ f(1) = 2 – 9 + 10 = 3, ​​g(1) = – 4 + 15 – 9 = 2. Let us multiply the polynomials: h(x) = f(x) × g(x) = – 8x⁴ + 66x³ – 193x² + 231x – 90. Visually multiplication can be seen as:

If we examine evaluations at x = 1 on the resulting polynomial ​ f(x) × g(x) we will get: h(1) = – 8 + 66 – 193 + 231 – 90 = 6, hence the values at x = 1 of ​f(x) and g(x) has multiplied, and respectively at every other x.

Likewise if we add ​ f(x) and g(x) we will get ​ –2x² + 6x + 1 which evaluates to 5 at x = 1.

Note: evaluations at other x-s were also added together, e.g., examine x = 2, x = 3.

If we can represent operand values as polynomials (and we indeed can as outlined) then through the arithmetic properties, we will be able to get the result of an operation imposed by an operand.

Enforcing Operation

The same can be represented as an operation polynomial:

where for some chosen a:

  • l(x) — at a represents (evaluates to) the value of the left operand
  • r(x) — at a represents the value of the right operand
  • o(x) — at a represents the result (output) of the operation

Therefore if the operands and the output are represented correctly for the operation by those polynomials, then the evaluation of ​ l(a) ​ operator r(a) = o(a) should hold. And moving output polynomial ​ ​o(x) to the left side of the equation ​ l(a) ​ operator r(a) – o(a) = 0 ​ is surfacing the fact that the operation polynomiall(x) ​ operator r(x) – o(x) = 0 has to evaluate to 0 at a, if the value represented by the output polynomial o(x) is the correct result produced by the operator on the values represented by operand polynomials l(x) and ​ r(x). Henceforth operation polynomial must have the root a if it is valid, and consequently, it must contain cofactor (x – a) as we have established previously (see factorization section), which is the target polynomial we prove against, i.e., t(x) = x – a.

For example, let us consider operation:

It can be represented by simple polynomials ​ l(x) = 3x, ​ ​r(x) = 2x, ​ o(x) = 6x, which evaluate to the corresponding values for ​ a = 1, i.e., l(1) = 3; r(1) = 2; o(1) = 6.

Note: The value of ​ “a” can be arbitrary.

The operation polynomial then will be:

Which is visualised as:

It is noticeable that the operation polynomial has (x – 1) as a co-factor:

Therefore if the prover provides such polynomials ​ l(x), r(x), o(x) instead of former ​ p(x) then the verifier will accept it as valid, since it is divisible by ​ t(x). On the contrary if the prover tries to cheat and substitutes output value with 4, e.g., o(x) = 4x, then the operation polynomial will be 6x² – 4x = 0:

Which is not have a solution x = 1, henceforth ​ l(x) × r(x) – o(x) is not divisible by t(x) without remainder:

Hence such inconsistent operation will not be accepted by the verifier (as described in the factorization section).

Proof of Operation

That is why the evaluations of polynomials ​ l(s), r(s), o(s) have to be provided separately by the prover. This means that the knowledge of polynomial must be adjusted. In essence what a verifier needs to check in encrypted space is that l(s) × r(s) – o(s) = t(s)h(s). While a verifier can perform multiplication using cryptographic pairings, the subtraction (– o(x)) is an expensive operation (would require to find inverse of gᵒ⁽ˢ⁾ ) that is why we move o(x) to the right side of the equation: l(x)r(x) = t(x)h(x) + o(x). In encrypted space verifier’s check translates to:

Note: recall that the result of cryptographic pairings supports encrypted addition through multiplication, see section on pairings.

While the setup stage stays unchanged, here is the updated protocol:

Such protocol allows to prove that the result of multiplication of two values is computed correctly.

One might notice that in the updated protocol we had to let go of the zero-knowledge component. The reason for this is to make the transition simpler. We will get back to it in a later section.

Multiple Operations

As discussed previously we can represent one such operation by making operand polynomials evaluate to a corresponding value at some arbitrary x, for example 1. Having this the properties of polynomials does not restrict us in representing other values at different x, for example 2, e.g.:

Such independence allows us to execute two operations at once without “mixing” them together, i.e., no interfering. The result of such polynomial arithmetic will be:

Where it is visible that the operation polynomial has roots x = 1 and x = 2. Therefore both operations are executed correctly.

Let us have a look at example of 3 multiplications 2 × 1 × 3 × 2, which can be executed as follows:

We need to represent those as operand polynomials, such that for operations represented by x ∈ {1, 2, 3} the ​ l(x) pass correspondingly through 2, 2 and 6, i.e., through points (1, 2), (2, 2), (3, 6), and similarly r(x) ∋ (1, 1),(2, 3),(3,2) and o(x) ∋ (1, 2), (2, 6), (3, 12).

However, how do we find such polynomials which passes through those points? For any case where we have more than one point, a particular mathematical method has to be used.

Polynomial Interpolation

  • Set of equations with unknowns
  • Newton polynomial
  • Neville’s algorithm
  • Lagrange polynomials
  • Fast Fourier transform

Let us use the former for example. The idea of such method is that there exists a unique polynomial p(x) of degree at most n with yet unknown coefficients which pass through given n + 1 points such that for each point {(xᵢ, yᵢ)}, i ∈ [n+1], the polynomial evaluated at ​ xᵢ should be equal to ​ ​yᵢ, i.e. p(xᵢ) = yᵢ for all i. In our case for three points it will be polynomial of degree 2 of the form:

Let us equalize the evaluated polynomial for each point of the left operand polynomial (green) and solve the system of equations by expressing each coefficient in terms of others:

Therefore the left operand polynomial is:

Which corresponds to the following graph:

We can find r(x) and o(x) in the same way:

Multi-Operation Polynomials

Firstly, l(x) and r(x) are multiplied which results in:

Secondly, the o(x) is subtracted from the result of l(x) × r(x):

Where it is already visible that every operands multiplication corresponds to a correct result. For the last step a prover needs to present a valid cofactor:

Using long division we get:

With h(x) = – 3x + 4 a verifier can compute t(x)h(x):

It is now evident that l(x) × r(x) – o(x) = t(x)h(x) which is what had to be proven.

Continue reading part 5