The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs

Author: 0xAlpha Co-founder @DeriProtocol; Compiler: DODO Research

Introduction

zk-SNARKs, or “zero-knowledge concise non-interactive arguments of knowledge”, enable a verifier to confirm that a prover has certain specific knowledge, known as witnesses, that satisfy specific relationships without revealing anything about the witness itself.

Generating zk-SNARKs for a specific problem consists of the following four phases:

• Convert a problem (or function) into an arithmetic gate circuit.
• This circuit is then translated into a matrix formula.
• This matrix formula is further converted into a polynomial, which should be divisible by a specific minimum polynomial.
• Finally, this divisibility is represented in elliptic curve points in finite fields, where the proof takes place.

The first three steps simply convert the representation of the original statement. The final step uses homomorphic encryption to project the statement of step 3 into the cryptographic space, enabling the prover to verify the mirror statement in it. Given that this projection makes use of asymmetric cryptography, it is not feasible to trace back to the original statement from step three, ensuring zero-knowledge exposure.

The math background required to read this article is equivalent to the freshman level of algebra for STEM majors. The only concept that can be challenging is probably elliptic curve encryption. For those unfamiliar with this, it can be thought of as an exponential function with a special cardinality, while keeping in mind that its inverse remains unsolved.

This article will follow the following notation rules:

• Matrix: bold capital letters, e.g. A; Write explicitly in form
• Vector: lowercase letters with arrows, written in explicit form [ ] ; By default, all vectors are columnar vectors
• Scalar: Regular letter representation

Let’s use this question as an example:

f(x)=x^3+x^2+5 (1)

Let’s say Alice wants to prove that she knows one. We’ll walk through the entire procedure that Alice needs to take to generate zk-SNARKs for her proofs.

This question may seem too simple because it doesn’t involve control flow (e.g., if-then-else). However, it is not difficult to convert a function with a control flow into an arithmetic expression. For example, let’s consider the following question (or “function” in a programming language):

f(x, z):

if(z==1):

return x*x*x+x*x+5

else:

return x*x+5

It’s easy to rewrite this problem into the following arithmetic expression (assuming z belongs to (0,1)), which is not much more complicated than equation (1).

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

In this article, we will continue to use equation (1) as the basis for the discussion.

Step 1: Arithmetic gate circuit

Equation (1) can be broken down into the following basic arithmetic operations:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128057_watermarknone.png)

This corresponds to the following arithmetic gate circuit:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7127628_watermarknone.png)

We also refer to equation (2) as a set of 4 “first-order constraints”, each of which describes the relationship of an arithmetic gate in a circuit. In general, a set of n first-order constraints can be generalized as a quadratic arithmetic procedure (QAP), which will be explained next.

Step 2: Matrix

First, let’s define a “witness” vector as follows:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128058_watermarknone.png)

where y, s1, s2, s3 are the same as defined in equation (2).

In general, for a problem with m inputs and n arithmetic gates (i.e., n-1 intermediate steps and final output), this witness vector will be (m+n+1) dimensional. In a practical problem, the number n can be very large. For example, for a hash function, n is usually a few thousand.

Next, let’s construct three n*(m+n+*1) matrices A,B,C so that we can rewrite equation (2) as follows:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128059_watermarknone.png)

Equation (3) is just another representation of Equation (2): each group (ai, bi, ci) corresponds to a gate in the circuit. We only need to unambiguously expand the matrix formula to see this:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128060_watermarknone.png)

So LHS=RHS is exactly the same as equation (2), and each row of the matrix equation corresponds to a first-order constraint (i.e., an arithmetic gate in the circuit).

We skipped the build steps (A, B, C), which are relatively straightforward. We only need to convert them into matrix form according to the corresponding first-level constraints, so as to determine the content of each row of (A, B, C), I.E. (AI, BI, CI). Take the first line as an example: it is easy to see that in order for the first order constraint x to be multiplied by x equal to s1 to hold, we need to multiply [0,1,0,0,0,0], [0,1,0,0,0] and [0,0,0,1,0,0] with the vector s.

Thus, we have succeeded in converting the arithmetic gate circuit into a matrix formula, i.e., equation (3). At the same time, we have also changed the object that needs to be proved to be mastered from to a witness vector s.

Step 3: Polynomials

Now, let’s construct an n*(*n+m+*1) matrix PA that defines a set of polynomials about z:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128061_watermarknone.png)

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128062_watermarknone.png)

These are four sets of linear equations for six variables that can be solved by traditional methods. However, a more efficient way to solve PA in this case is Lagrangian interpolation, which takes advantage of the specificity of the problem. Here we skip the process of solving for PA, which is a bit tedious but straightforward.

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128063_watermarknone.png)

Thereinto:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128064_watermarknone.png)

Step 4: Ellipse Curve Points

Rewrite equation (4) to:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128065_watermarknone.png)

where i(z)=1 is just a trivial zero-order polynomial for z, which is used to unify the equation - all terms are quadratic. The need to do so will soon become clear. Note that this equation contains only the addition and multiplication of the polynomial of z.

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128066_watermarknone.png)

Next, we’ll explain the actual steps in more detail.

Elliptic curve encryption

The general theory of elliptic curves is far beyond the scope of this article. For the purposes of this paper, elliptic curves are defined as mapping from the prime domain Fp to the E function, where E includes points satisfying y^2=x^3+ax+b (called elliptic curve points, or ECPs for short).

Note that while we’ve been talking about regular arithmetic so far, now when we convert to prime fields, the arithmetic operations on numbers are done in a modular way. For example, a+b=a+b(mod p), where p is the order of Fp.

On the other hand, the addition definition of two elliptic curve points is shown in the following figure:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128067_watermarknone.png)

Specifically, the addition of two ECPs, P and Q:

Find the intersection of the line PQ and the curve R, defined as -(P+Q)

Flip to the ‘mirror’ point R’ on the curve for R.

So we define the addition of elliptic curve points P+Q=R’:

Note that this rule also applies to special cases, i.e. where an ECP self-additive, where the tangent of the point will be used.

Now suppose we pick a random point G and map the number 1 to it. (This “initial mapping” sounds a bit arbitrary.) More on that later). Then for any n to belong to Fp, we define:

E(N)=G+G+G+…+G=G

This has an action expression. Actions that define +G are “generators” and are denoted as g. Then the above definition is equivalent to:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128068_watermarknone.png)

For those unfamiliar with elliptic curves, you can analogy this mapping to a regular exponential function where the cardinal g replaces the real numbers. Arithmetic operations behave similarly. However, a key difference is that the inverse function of g^n is not computationally feasible. That is, there is no way to calculate the elliptic curve version! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128069_watermarknone.png)。 This is, of course, the basis of elliptic curve cryptography. Such a mapping is known as one-way encryption.

Note that given an elliptic curve, since selecting G (and therefore Generator g) is arbitrary (except for points on the x-axis), there are an infinite number of ways to map it. Choosing (G or g) can be analogous to choosing the cardinality of an exponential function (2^x, 10^x, e^x, etc.) as part of common sense.

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128070_watermarknone.png)

However, the equation (5) that Alice wants to prove is quadratic and therefore not linear enough. In order to deal with quadratic terms, we need to define multiplication in cryptographic space. This is known as a pairing function, or bilinear map, and will be explained next.

Bilinear mapping

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128071_watermarknone.png)

Common reference string

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128072_watermarknone.png)

The entire process is called the “verification key”, or VK for short. There are only 7 elliptic curve points (ECPs) involved here, which need to be provided to the verifier. It is important to note that no matter how many inputs and first-level constraints are involved in the problem, VK is always made up of 7 ECPs.

In addition, it is worth mentioning that the “trusted setup” and the process of generating PK and VK can be done once for a particular problem.

Proof & Verification

Now with the public key (PK), Alice will calculate the following elliptic curve points (ECPs):

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128073_watermarknone.png)

These 9 elliptic curve points are the key to zero-knowledge concise non-interactive proofs (zk-SNARKs)!

Note that Alice is actually just doing some linear combinatorial operations on the elliptic curve points in the public key. This is particularly critical and will be checked during validation.

Now that Alice has handed over the zk-SNARK proof, let’s finally enter the verification process, which is a three-step process.

First of all, it is important to make sure that the first 8 elliptic curve points are really a linear combination of those points in the generic reference string.

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128074_watermarknone.png)

If all three checks are true, then equation (5) is verified, so we believe that Alice knows the witness.

Let’s explain the rationale behind the equation. Take the first equation in the first part as an example, which holds because of the bilinear nature:

! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128075_watermarknone.png)

However, since Alice does not know the value of the symbol alpha, she is unable to calculate this addition explicitly. The only way she could come up with a pair that satisfies the equation (EA, EA’) was to use the same set of vectors s each, calculate! [The Power of Zero-Knowledge Proofs: Mathematically Decoding zk-SNARKs] (https://img.jinse.cn/7128076_watermarknone.png).

References

“Zk-SNARKs: Under the Hood” (Vitalik Buterin)

“A Review of Zero Knowledge Proofs” (Thomas Chen, Abby Lu, Jern Kunpittaya, and Alan Luo)

“Why and How zk-SNARK Works: Definitive Explanation” (Maksym Petkus)

Website: Zero-Knowledge Proofs

Wikipedia: Elliptic curve

Wikipedia: Finite field

Wikipedia: Pairing-based cryptography