ZK-SNARKS - HackMD

# ZK-SNARKS A beginner's guide into zkSNARKs. ## Primer A basic understanding of modular arithmetic, groups, fields is required to understand the maths behind zero-knowledge concepts. A quick glossary of terms used in the blog:  - **Primitive Root:** $g$ is a primitive root modulo $p$ if, for every integer $a$ coprime to $p$ (meaning $gcd(a,p)=1$), there exists an integer k such that $g^k≡a\ (mod\ p)$. - **R1CS:** An R1CS (Rank-1 Constraint System) consists of a series of triplets of vectors $(a, b, c)$. The solution to an R1CS is a vector $s$, where $s$ needs to fulfill the equation $s.a*s.b−s.c=0$, where $.$ represents dot product and $*$ represents element-wise multiplication. For example, $\begin{matrix} a = [0 & 3 & 0]^T\end{matrix}$, $\begin{matrix} b = [2 & 0 & 0]^T\end{matrix}$ and $\begin{matrix} c = [3 & 1 & 2]^T\end{matrix}$ and we have $\begin{matrix} s = [1 & 1 & 1]^T\end{matrix}$, then $$\begin{bmatrix} 1 & 1 & 1\end{bmatrix} . \begin{bmatrix} 0 \\ 3 \\ 0\end{bmatrix} * \begin{bmatrix} 1 & 1 & 1\end{bmatrix} . \begin{bmatrix} 2 \\ 0 \\ 0\end{bmatrix} - \begin{bmatrix} 1 & 1 & 1\end{bmatrix} . \begin{bmatrix} 3 \\ 1 \\ 2\end{bmatrix}$$ $$3\ *\ 2\ -\ 6\ =\ 0$$ The R1CS form is converted to QAP(form which can be verified by zk-SNARKs) using Lagrange (or other) interpolations. > **Lagrange Interpolation:** If you have a set of points (ie. (x, y) coordinate pairs), then doing a Lagrange interpolation on those points gives you a polynomial that passes through all of those points. - **QAP:** A QAP performs the same logic as by R1CS except it uses polynomials instead of dot product. So we have $A(x) * B(x) - C(x)\ =\ H*Z(x)$. In this scenario, the dot product check involves performing a series of additions and multiplications of polynomials. If this resulting polynomial, when evaluated at each x-coordinate, equals zero, it indicates that all checks pass. However, if the resulting polynomial, evaluated at any x-coordinate, produces a nonzero value, it implies inconsistencies in the inputs and outputs. [Check out [blog](https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649) for in-depth understanding] - **Generic Group Model:** In this model, the adversary only has access to a randomly chosen encoding of a group, rather than efficient encodings commonly used in practice. Additionally, the model provides an oracle that performs the group operation, allowing for the efficient extraction of coefficients used to express the output of the oracle as a linear combination of initial group elements. ## Zero-knowledge proofs ZKPs can be used by a prover to prove the verifier that he knows a secret (called witness) which satisfies some function, without actually revealing any information about the witness to the verifier. Example, consider a function `F(x,w)`, the function takes a public input $x$ and a secret witness $w$ as input and returns true or false. The prover need to prove that for a given public input $x$, he knows a secret $w$ such that `F(x,w) == true`. Characteristics of ZKPs: - **Completeness:** True statements by honest provers are always accepted by honest verifiers. - **Soundness:** Incorrect or forged proofs are not accepted by honest verifiers. ZKPs can be of two types: - One that requires prover to interact with the verifier (exchange messages) in order to prove the verifier that some mathematical statement is true - **Interactive ZKPs**. Take as an example the Interactive Schnorr Protocol: Alice wants to prove Bob that she knows the discrete logarithm of a given value. - Bob selects a large prime number p and a primitive root g modulo p. - Define $h$ = $g^x\ mod\ p$ - Bob makes $p,g,h$ public. However $x$ is kept secret to him. - Alice randomly chooses a value $r$ and computes $c\ =\ g^r\ mod\ p$. She send this value $c$ to Bob. - Bob selects a value $e$ at random and sends it to Alice. - Alice computes $s\ =\ r\ +\ ex$ and sends $s$ to Bob. - Bob verifies the proof by evaluating if $g^s \equiv c.h^e\ mod\ p$. If it holds, Bob is convinced Alice knows the discrete logarithm. Clearly there were rounds of interactions between Alice and Bob and hence Interactive Zero-Knowledge Proof. - Other one requires the prover to create proof which can be verified directly by the verifier without any further interaction. One example of this is Fiat-Shamir transformation of Schnorr Protocol - **Non-Interactive Zero-Knowledge Proof** for Discrete Logarithm. It relies on a secure cryptographic hash function - the random oracle model - both the prover and verifier have access to the random oracle. - The prover computes $T=g^t\ mod\ p$, where t is a random integer $\in [1,p-2]$. - The prover computes the hash $c=H(T)$, where $H$ is a secure cryptographic hash function like SHA-256. - The prover computes $s=xc\ +\ t\ mod\ (p−1)$. - The prover then sends $(T,s)$ to the verifier. - The verifier verifies the proof by evaluating $g^s \equiv h^cT$, where verifier takes $h = g^x\ mod\ p$ as input. $x$ is a secret $\in [1,p-2]$. Since there is no interaction between the prover and the verifier, these are non-interactive. We'll dive deeper into this class of ZKPs in the rest of the blog. ## What are ZK-SNARKs? ### A gentle introduction ZK-SNARKs i.e. Zero-Knowledge Succint Non-interactive Arguments of Knowledge are zero-knowledge proofs with two additional requirements: - *Non-Interactive*: There are no rounds of interaction between prover and verifier. The prover provides the result $z$ of $f(x,w)$ where $w$ is the secret input and $x$ is publicly known input to function $f$. Along with this he provides a string $\pi$. These two inputs are enough for the verifier to verify that the prover knows $w$. - *Succintness*: The size of the proof is very small compared to the size of the statement of the witness(i.e the computation). And the verification and proof generation short and quick. ### Algorithms The protocol consists of three main algortihms: - The *setup algorithm*: generates the string, $S_p$ used in proving and verification key, $S_v$ (can be a secret to the verifier). This is generated by some trusted party. - The *prove algorithm*: It takes $S_p$, statement $x$, and its corresponding witness w, and generates a proof $\pi$. The $\pi$ provided by the prover must have size $\mathcal{O}_{\lambda}(log(|C|))$ i.e. logarithmic in size of the circuit (number of gates in the circuit) and a security parameter $\lambda$. - The *verify algorithm*: It takes the verification key $S_v$, statement $x$, and proof $\pi$, and returns bool if the proof is accepted or rejected. The verification should be short with a verification runtime of $\mathcal{O}_\lambda(|x|+log(|C||)$ i.e. linear in size of statement, $x$ and logarithmic in size of circuit, $C$ (even less than the time to read the circuit). <center> <img src="https://hackmd.io/_uploads/ryHxZVihT.png"> </center> The pre-process or setup step is needed to complete the time constraint on verifier by summarising the circuit in public parameter $S_v$. ### Four elements of implementations #### Encoding The problem to be verified is presented as a quadratic equation of polynomials, $h(x).t(x)\ =\ w(x).v(x)$, $h(x)$ is the computation performed by the prover, $t(x)$ is the computation done by the verifier and $w(x), v(x)$ are auxiliary polynomials. #### Succintness This is accomplished by random sampling. The verifier chooses a secret evaluation point $s$ to reduce the problem from multiplying polynomials and verifying polynomial function equality to multiplication and equality check on numbers. This reduces the proof size and verification time. #### Homomorphic Encryption Homomorphic encryption is a type of encryption scheme that allows for performing computations on encrypted data without decrypting it. In simpler terms, it enables computations to be carried out on ciphertexts (encrypted data), producing encrypted results that, when decrypted, are the same as if the computations were performed on the plaintext (original) data. For example, consider two numbers, 5 and 3, encrypted as ciphertexts $E(5)$ and $E(3)$. With homomorphic encryption, you can perform addition or multiplication operations directly on these ciphertexts. Let's say you want to add them: $$E(5)+E(3)=E(5+3)=E(8)$$ The resulting ciphertext, $E(8)$, is the encryption of the sum of the original plaintexts (5 and 3). When decrypted, it yields the correct result, 8. Let us state the encryption function:$$E(x)\ =\ g^x\ mod\ n$$ where $x$ is the value we want to encrypt, $g$ is the public base number (generator). Utilizing an encoding or encryption function $E$ with homomorphic properties enables the prover to perform computations on encrypted data without revealing the actual values. This empowers the prover to calculate $E(t(s)),\ E(h(s)),\ E(w(s)),\ and\ E(v(s))$ without knowledge of s, maintaining privacy and security. An important limitation of homomorphic encryption is though we have the capability to multiply an encrypted value by an unencrypted one, it's not feasible to multiply (or divide) two encrypted values or to exponentiate an encrypted value which is needed for *polynomial restriction* check in the verification. This is where the **Bilinear Pairings** come in. In simple terms cryptographic pairings (bilinear map) are mathematical constructs represented by the function $(e(g^*,g^*))$. These pairings take two encrypted inputs (for instance, $(g^a, g^b ))$ from a single set of numbers and deterministically map them to their multiplied representation in another set of numbers. The operation can be expressed as $( e(g^a, g^b ) = e(g, g)^{ab})$. It allows for the multiplication of encrypted values while transitioning them to a different set of numbers, preserving the integrity of the computations. From a technical view, the outcome of a pairing operation is an encrypted product of original values under an alternative generator $G$ within the target set, represented as $e(g^a, g^b) = G^{ab}$. Hence, this operation exhibits characteristics of homomorphic encryption.  #### Zero-Knowledge To maintain confidentiality, the prover permutes the encoded values $E(h(s)), E(t(s)), E(w(s))$, and $E(v(s))$ using a random number $\delta$. This ensures that the verifier can validate the proof's correctness without gaining insights into the prover's inputs or computations. ### Building a simple zk-SNARK Let us define a simple zk-SNARK to prove knowledge of a $n$-degree polynomial $p(x)$ given a target polynomial $t(x)$. If $a_1,a_2,...a_n$ are the $n$ roots of $p(x)$ then, $$p(x) = (x-a_1).(x-a_2)....(x-a_n)$$ Let us assume V, the verifier knows $d<n$ roots of the polynomial and hence the target polynomial, $t(x)$, $$t(x) = (x-b_1).(x-b_2).....(x-b_d)$$ where $d<n$ and $b_is$ are from the set of $a_is$. Now we reformulate the problem, and say the prover P wants to prove the verifier V, his knowledge of a polynomial, $$h(x)=\frac{p(x)}{t(x)}$$ The algorithm is based on **Schwartz-Zippel Lemma**, which states that for any multivariable polynomial $(f: F^m \rightarrow F)$ of degree $n$ over a field $F$, and for any finite set $S \subseteq F$, if we uniformly choose $u$ from $S^m$, the probability of $u$ being a set of roots for $f$ is at most $\frac{n}{|S|}$. This probability decreases significantly when $S$ is the finite field $F$, as the field size is typically much larger than $n$. $$Pr_{u \leftarrow S^m}(f(u) = 0) = \frac{n}{|S|}$$ While it may appear counterintuitive, the Schwartz-Zippel lemma enables us to show knowledge of a polynomial $f$. Instead of proving the knowledge of all coefficients of $f$, we only need to prove that we know how to compute the pair $(s, f(s))$ for any $s$ belonging to $F^m$. This lemma provides the efficiency required in zk-SNARK. **Parameter Setup** - Each party takes two secret parameters, $s$, $\alpha$ at random. These parameters are important to prove the verifier that P knows the polynomial and prevent forgery using any of the values transmitted during the process using **Knowledge-of-Exponent** concept, which states, given a prime number $q$ such that $2q+1$ is also prime, and a generator $g$ of the group $\mathbb{Z}_{2q+1}$, along with another element $g′=g^{\alpha}$, where $\alpha$ is a secret exponent, the assumption states that the only way to obtain a pair $(x,y)$ such that $x \neq g, y \neq g'$, and $y=x^α$ is by knowing an exponent $c$ such that $x=g^c$. - Each party computes **common reference strings**: $g^\alpha, G, \alpha G$. The common reference strings consists of evaluation key $(G, \alpha G)$ and verification key $(g^\alpha, g^{t(s)})$. Once we compute these, we can get rid of the secret values $s$ and $\alpha$ and broadcast their obfuscated values. This provides non-interactivity to the zk-snark. $$G = (g^{s^i})_{i=0...n}$$ - The values $s$, $\alpha$ are deleted. - The evaluation and verification keys are broadcasted. **Proof** * Assuming P knows polynomial $p(x)$, P computes $h(x)$. * P evaluates $p(x)$ and $h(x)$ and computes $g^{p(s)}$ and $g^{h(s)}$ using the evaluation key. Solving everything in powers of $g$ provides the necessary homomorphic encryption/obfuscation stated earlier, $$g^{p(x)} = g^{c_0+c_1x+c_2x^2...c_nx^n} = g^{c_0}.(g^{x})^{c_1}.(g^{x^2})^{c_2}...(g^{x^n})^{c_n}$$ which can be computed using $G$. * Further, P computes $g^{p(\alpha.s)}$ using the evaluation key, incorporating the discrete log hardness with $\alpha$. * P takes a random $\delta$. Use of $\delta$ provides zero-knowledge to the verifier from the proof transmitted. * P broadcasts the proof, $\pi=g^{\delta.p(s)}, g^{\delta.h(s)},g^{\delta.p(\alpha.s)} = g^{\delta.p}, g^{\delta.h},g^{\delta.p'}$ **Verification** The verifier checks whether, $$e(g^{\delta.p'},g) = e(g^{\delta.p},g^{\alpha})$$ $$e(g^{\delta.p},g) = e(g^{t(s)},g^{\delta.h})$$ where $e(g^a,g^b)=e(g,g)^{a.b}$ is the representation for bilinear pairing which allows to check for equality of products in obfuscated domain. *P.S. Some maths workout will surely be helpful in understanding the above ;)* *In-detail explanation of the above example can be checked in this really insightful [blog](https://medium.com/iovlabs-innovation-stories/building-zk-snarks-volume-2-444ec711efe0).* ### SNARK Workflow There are a number of high level languages like Circom, Cairo, Leo, Snarky etc which compile into (arithmetic) circuits which are actually used by the SNARK system. A typical snark workflow looks like: <center> <img src="https://hackmd.io/_uploads/BkYvRmi3a.png"/> </center> ## Dig Further? The blog presents a basic introduction to the vast field of zk-SNARKs. A number of optimization schemes and developments have followed to use and improve the protocol. There are few things to keep in mind when working with SNARKs. To utilize zk-SNARKs effectively, the computational problem must first be transformed into a "quadratic arithmetic program" (QAP). This conversion process is complex and involves adapting the function's code into this specific format. Once the code is transformed into a QAP, another process runs alongside, allowing the creation of a corresponding solution or "witness" to the QAP given an input. Subsequently, a fairly intricate process is involved in creating the actual "zero knowledge proof" for this witness. Additionally, there's a separate process for verifying a proof provided by someone else, ensuring its validity without revealing any sensitive information about the witness or the computation involved. So there's a lot going on actually. Another important thing includes *trusted parties* that might be required to generate some initial parameters in the very first step (the setup algorithm). Recent researches are looking into efficiently utilizing something called *multi-party computation* for a more trustless setup generating the parameters. You may also be interested in diving into different approaches of constructing snarks: from QAPs, SSPs, PCPs, LIPs etc and the various arithmetization techniques (PLONKs for example) or commitment schemes (KZG for instance) employed. You may even want to check the state-of-the-art for SNARK for QAPs - the celebrated result of *Groth* that achieves proof size of three group elements in the Generic Group Model or wanna explore into building up compilers for SNARKs. As any cryptographic field, the field is endless and into active research, so maybe keep learning and building :) ## References - [Why and How zk-SNARKs work?](https://medium.com/@imolfar/why-and-how-zk-snark-works-2-proving-knowledge-of-a-polynomial-f817760e2805) - [zkSNARKs in a nutshell](https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell) - [An Exploration of Zero-Knowledge Proofs and zk-SNARKs](https://fisher.wharton.upenn.edu/wp-content/uploads/2020/09/Thesis_Terrence-Jo.pdf) - [ZKSnarks, Anca Nitulescu](https://www.di.ens.fr/~nitulesc/files/Survey-SNARKs.pdf) - [What is zk-SNARK?](https://www.youtube.com/watch?v=gcKCW7CNu_M) - [Introduction to ZKSnarks](https://consensys.io/blog/introduction-to-zk-snarks) - [QAPs](https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649) - [Zk-SNARKs: Under the Hood](https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6) - [Building zk-SNARKs](https://medium.com/iovlabs-innovation-stories/building-zk-snarks-volume-2-444ec711efe0)