Author: 0xAlpha

Introduction

zk-SNARK, short for “Zero-Knowledge Succinct Non-interactive Argument of Knowledge,” allows a verifier to confirm that a prover possesses some knowledge, termed a witness, satisfying a specific relation, all without disclosing any information about the witness itself.

To put this in tangible terms, consider a function $f(w)$ with $w$ as its input. The objective is to demonstrate that the prover knows a confidential input $w_0$ (the witness) such that $f(w_0)=y$, where $y$ is publicly known.

Generating a zk-SNARK for a particular problem consists of the following four phases:

1. The problem (or function) is transformed into an arithmetic gate circuit.
2. This circuit is then translated into a matrix formula.
3. This matrix formula is further converted into a polynomial, which should be divisible by a specific minimal polynomial.
4. Finally, this divisibility is represented within a finite field of elliptic curve points, where the proof takes place.

The first three steps simply transform how the original statement is represented. The final step projects the third step's statement into an encrypted space using homomorphic encryption, allowing the prover to substantiate the mirrored statement therein. Given that this projection leverages asymmetric encryption, retracing back to the statement from the third step is infeasible, ensuring zero knowledge is exposed.

The mathematical background required for this article is equivalent to freshman-level algebra for STEM students. The only potentially challenging concept might be elliptic curve encryption. For those unfamiliar with this, it can be thought of as an exponential function with a special base, bearing in mind that its inverse function remains unsolved.

The following notation rules will be followed in this article:

• Matrix: bold capital letters, e.g. $\bold A$; explicit form written as $\begin{bmatrix}\cdot\end{bmatrix}$
• Vector: low-case letters with arrow on top, e.g. $\vec s$; explicit form written as$\begin{bmatrix}\cdot\end{bmatrix}$; vectors are all column ones by default
• Scalar: regular letters

Let’s use this problem as example:

$$ \begin{equation} f(x)=x^3+x^2+5 \end{equation} $$

Suppose Alice wants to prove that she knows an $x_0 \text{ s.t. }f(x_0)=41$. We will walk through the whole procedure Alice needs to take to generate a zk-SNARK for her proof.

This problem may appear to be too simple since it does not involve control flow (e.g. if-then-else). However, it is not difficult to convert a function with control flow into an arithmetic expression. For instance, let's consider the following problem (or "function" in the language of programming):

f(x, z):
		if(z==1):
				return x*x*x+x*x+5
		else:
				return x*x+5