# zk-SNARKs

- Introduction
- What is ZKP? A Complete Guide to Zero-knowledge Proof
- Introduction to zk-SNARKs
- Comparing General-purpose zk-SNARKs
- Quadratic Arithmetic Programs - from Zero to Hero
- Explaining SNARKs Series: Part I to Part VII
- Overview
- Part I: Homomorphic Hidings
- Part II: Blind Evaluation of Polynomials
- Part III: The Knowledge of Coefficient Test and Assumption
- Part IV: How to make Blind Evaluation of Polynomials Verifiable
- Part V: From Computations to Polynomials
- Part VI: The Pinocchio Protocol
- Part VII: Pairings of Elliptic Curves

- zk-SHARKs: Combining Succinct Verification and Public Coin Setup
- References

## Introduction

Zero-knowledge proof protocols have gained much attention in the past decade, due to the popularity of cryptocurrencies.
A zero-knowledge Succinct Non-interactive Argument of Knowledge (zk-SNARK), referred to here as an *argument of
knowledge,* is a special kind of a zero-knowledge proof. The difference between a *proof of knowledge* and an *argument
of knowledge* is rather technical for the intended audience of this report. The distinction lies in the difference
between *statistical soundness* and *computational soundness*. The technical reader is referred to
[1] or [2].

zk-SNARKs have found many applications in zero-knowledge proving systems, libraries of proving systems such as
*libsnark* and *bellman* and general-purpose compilers from high-level languages such as *Pinocchio*. "DIZK: A
Distributed Zero Knowledge Proof System", by Wu et al. [3], is one of the best papers on zk-SNARKs, at least from a
cryptographer's point of view. Coins such as Zerocoin and Zcash use zk-SNARKs. The content reflected in this curated
content report, although not all inclusive, covers all the necessary basics one needs to understand zk-SNARKs and their
implementations.

## What is ZKP? A Complete Guide to Zero-knowledge Proof

**Hasib Anwar**

Just is a born geek

### Overview

A zero-knowledge proof is a technique one uses to prove to a verifier that one has knowledge of some secret information, without disclosing the information. This is a powerful tool in the blockchain world, particularly in cryptocurrencies. The aim is to achieve a trustless network, i.e. anyone in the network should be able to verify information recorded in a block.

### Summary

In this post, Anwar provides an excellent zero-knowledge
infographic that summarizes what a zero-knowledge proof is, its main properties (completeness, soundness and
zero-knowledge), as well as its *use cases* such as *authentication*, *secure data sharing* and *file-system control*.
Find what Anwar calls a *complete guide to zero-knowledge proofs*,
here.

## Introduction to zk-SNARKs

**Dr Christian Reitwiessner**

Ethereum Foundation

### Overview

A typical zero-knowledge proof protocol involves at least two participants: the *Verifier* and the *Prover*.
The *Verifier* sends a challenge to the *Prover* in the form of a computational problem. The *Prover* has to solve the
computational problem and, without revealing the solution, send proof of the correct solution to the *Verifier*.

### Summary

zk-SNARKs are important in blockchains for at least two reasons:

- Blockchains are by nature not scalable. They
thus benefit in that zk-SNARKs allow a verifier to verify a given
*proof*of a computation without having to actually carry out the computation. - Blockchains are public and need to be
*trustless,*as explained earlier. The*zero-knowledge*property of zk‑SNARKs as well as the possibility to put in place a so-called*trusted setup*make this*almost*possible.

Reitwiessner uses an example of a mini 4 x 4 Sudoku challenge as an example of an interactive zero-knowledge proof. He
explains how it would fall short of the *zero-knowledge* property without the use of homomorphic encryption as well as
putting in place a *trusted setup*. Reitwiessner proceeds to explain how computations involving *polynomials* are better
suited as challenges posed by the *Verifier* to the *Prover*.

### Video

The slides from the talk can be found here.

## Comparing General-purpose zk-SNARKs

**Ronald Mannak**

Open-source Blockchain Developer

### Overview

Recently, zk-SNARK constructs such as Supersonic [4] and Halo [5] were created mainly for efficiency of proofs. The following article by Mannak gives a quick survey of the most recent developments, comparing general-purpose zk-SNARKs. The article is easy to read. It provides the technical reader with relevant references to scholarly research papers.

### Summary

The main drawback of zk-SNARKs is their reliance on a *common reference string* that is created using a *trusted setup*.
In this post, Mannak mentions three
issues with reference strings or having a trusted setup:

- A leaked reference string can be used to create undetectable fake proofs.
- One setup is only applicable to one computation, thus making smart contracts impossible.
- Reference strings are not upgradeable. This means that a whole new
*ceremony*is required, even for minor*bug fixes*in crypto coins.

After classifying zk-SNARKs according to the type of trusted setup they use, Mannak compares their
*proof* and *verification sizes* as well as *performance*.

## Quadratic Arithmetic Programs - from Zero to Hero

**Vitalik Buterin**

Co-founder of Ethereum

### Overview

The zk-SNARK end-to-end journey is to create a function or a protocol that takes the proof, given by the Prover, and checks its veracity. In a zk-SNARK proof, a computation is verified step by step. To do so, the computation is first turned into an arithmetic circuit. Each of its wires is then assigned a value that results from feeding specific inputs to the circuit. Next, each computing node of the arithmetic circuit (called a “gate” - an analogy of the nomenclature of electronic circuits) is transformed into a constraint that verifies the output wire has the value it should have for the values assigned to the input wires. This process involves transforming statements or computational problems into various formats on which a zk-SNARK proof can be performed. The following seven steps depicts the process for achieving a zk-SNARK:

`Computational Problem —> Arithmetic Circuit —> R1CS —> QAP —> Linear PCP —> Linear Interactive Proof -> zk-SNARK`

### Summary

In this post, Buterin explains how zk-SNARKs work, using an example that focuses on the first three steps of the process given above. Buterin explains how a computational problem can be written as an arithmetic circuit, converted into a rank-1 constraint system or R1CS, and ultimately transform the R1CS into a quadratic arithmetic program.

## Explaining SNARKs Series: Part I to Part VII

**Ariel Gabizon**

Engineer at Zcash

### Overview

The explanation of zk-SNARKs given by Buterin above, and similar explanations by Pinto (6], [7]), although excellent in clarifying the R1CS and the Quadratic Arithmatic Program (QAP) concepts, do not explain how zero-knowledge is achieved in zk-SNARKs. For a step-by-step and mathematical explanation of how this is achieved, as used in Zcash, refer to the seven-part series listed here.

### [Part I: Homomorphic Hidings]

This post explains how zk-SNARKs use *homomorphic hiding* or
*homomorphic encryption* in order to achieve zero-knowledge proofs. Gabizon dives into the *mathematics* that underpins
the cryptographic security of homomorphic encryption afforded by the difficulty of solving *discrete log problems* in a
finite group of a large *prime* order.

### [Part II: Blind Evaluation of Polynomials]

This post explains how the power of the *homomorphic property* of these types of
hidings is seen in how it easily extends to linear combinations. Since any polynomial evaluated at a specific value
$x = \bf{s} $ is a *weighted linear combination* of powers of $\bf{s}$, this property allows sophisticated
zero-knowledge proofs to be set up.

For example, two parties can set up a *zero-knowledge proof* where the Verifier can request the Prover to prove
knowledge of the "right" polynomial $P(x)$, without revealing $P(x)$ to the Verifier. All that the Verifier requests
is for the Prover to evaluate $P(x)$ at a secret point $\bf{s}$, without learning what $\bf{s}$ is. Thus, instead of
sending $\bf{s}$ in the open, the Verifier sends homomorphic hidings of the necessary power of $\bf{s}$. The Prover
therefore simply evaluates the right linear combination of the hidings as dictated to by the polynomial $P(x)$. This is
how the Prover performs what is called a *blind evaluation of the polynomial* $P(x)$ at a secret point $\bf{s}$
only known by the Verifier.

### [Part III: The Knowledge of Coefficient Test and Assumption]

In this post, Gabizon notes that it is necessary to force the Prover to comply
with the rules of the protocol. Although this is covered in the next part of the series, in this post he considers *the
Knowledge of Coefficient (KC) Test*, as well as its *KC assumption*.

The KC Test is in fact a request for a *proof* in the form of a challenge that a Verifier poses to a Prover. The
Verifier sends a pair $( a, b )$ of elements of a prime field, where $a$ is such that $b = \alpha \cdot a$, to the
Prover. The Verifier challenges the Prover to produce a similar pair $( a', b' )$, where $b' = \alpha \cdot a' $ for
the same scalar $\alpha$. The KC assumption is that if the Prover succeeds with a non-negligible probability, then the
Prover knows the ratio between $a$ and $a'$. Gabizon explains how this two concept can be formalized using an
*extractor* of the Prover.

### [Part IV: How to make Blind Evaluation of Polynomials Verifiable]

In this part of the series, Gabizon explains how to make the *blind
evaluation of polynomials* of Part II above, verifiable. This requires an extension of the *Knowledge of Coefficient
Assumption* considered in Part III. Due to the homomorphic property of the used homomorphic hiding function, the Prover
is able to receive several hidings of $\alpha$-pairs from the Verifier, evaluate the polynomial $P(x)$ on a
particular linear combination of these hidings of $\alpha$-pairs and send the resulting pair to the Verifier. Now,
according to the extended *Knowledge of Coefficient Assumption* of degree $d$, the Verifier can know, with a high
probability, that the Prover knows the "right" polynomial,
$P(x)$, without disclosing it.

### [Part V: From Computations to Polynomials]

This post aims to translate statements that are to be proved and verified
into the language of polynomials. Gabizon explains the same process discussed above by Buterin, for transforming a
computational problem into an *arithmetic circuit* and ultimately into a QAP. However, unlike Buterin, Gabizon does
not mention constraint systems.

### [Part VI: The Pinocchio Protocol]

The Pinocchio protocol is used as an example of how the QAP computed in the
previous parts of this series can be used between both the Prover and the Verifier to achieve a zero-knowledge proof
with negligible probability that the Verifier would accept a wrong polynomial as correct. The low probability is
guaranteed by a well-known theorem that "two different polynomials of degree at most $2d$ can agree on at most $2d$
points in the given prime field". Gabizon further discusses how to restrict the Prover to choose their polynomials
according to the assignment $\bf{s}$ given by the Verifier, and how the Prover can use randomly chosen field elements
to *blind* all the information they send to the Verifier.

### [Part VII: Pairings of Elliptic Curves]

This part of the series aims to set up a Common Reference String (CRS) model that
can be used to convert the *verifiable blind evaluation* of the polynomial of Part IV into a *non-interactive proof
system*. A homomorphic hiding that supports both addition and multiplication is needed for this purpose. Such a
homomorphic hiding is created from what is known as *Tate pairings*. Since *Tate pairings* emanate from Elliptic Curve
Groups, Gabizon starts by defining these groups.

The Pinnochio SNARK, however, uses a relaxed notion of a *non-interactive proof*, where the use of a CRS is allowed. The
CRS is created before any proofs are constructed, according to a certain randomized process, and is broadcast to all
parties. The assumption here is that the randomness used in creating the CRS is not known to any of the parties.

The intended non-interactive evaluation protocol has three parts; Setup, Proof, and Verification. In the Setup, the CRS and a random field element $\bf{s}$ are used to calculate the Verifier's challenge (i.e. the set of $\alpha$-pairs a in Part IV).

## zk-SHARKs: Combining Succinct Verification and Public Coin Setup

**Madars Virza**

Scientist, MIT

### Background

Most of the research done on zero-knowledge proofs has been about the efficiency of these types of proofs and making
them more practical, especially in cryptocurrencies. One of the most recent innovations is that of the so-called
*zk-SHARKs* (short for *zero-knowledge Succinct Hybrid ARguments of Knowledge*) designed by Mariana Raykova, Eran Tromer
and Madars Virza.

### Summary

Virza starts with a concise survey of the best zk-SNARK protocols and their applications while giving an assessment of
the efficiency of zero-knowledge proof implementations in the context of blockchains. He mentions that although
zero-knowledge proofs have found practical applications in *privacy preserving cryptocurrencies*, *privacy preserving
smart contracts*, *proof of regulatory compliance* and *blockchain-based sovereign identity*, they still have a few
shortcomings. While QAP-based zero-knowledge proofs can execute fast verifications, they still require a *trusted
setup*. Also, in Probabilistically Checkable Proof (PCP)-based zk-SNARKs, the speed of verification decays with the
increasing statement size.

Virza mentions that the danger of slow verification can tempt miners to skip validation of transactions. This can cause
forks such as the July 2015 Bitcoin fork. He uses the Bitcoin fork example and slow verification as motivation for a
zero-knowledge protocol that allows multiple verification modes. This will allow miners to carry out an *optimistic
verification* without losing much time and later check the validity of transactions by using *prudent verification*. The
*zk-SHARK* is introduced as one such zero-knowledge protocol that implements these two types of verification modes. It
is a *hybrid,* as it incorporates a Non-interactive Zero-knowledge (NIZK) proof inside a SNARK. The internal design of
the NIZK verifier is algebraic in nature, using a new compilation technique for linear PCPs. The special-purpose SNARK,
which constitutes the main part of the zk-SHARK, is dedicated to verifying an *encoded polynomial delegation* problem.

The design of zk-SHARKs is ingenious and aims at avoiding unnecessary coin forkings.

### Video

The slides from the talk can be found here.

## References

[1] G. Brassard, D. Chaum and C. Crepeau, "Minimum Disclosure Proofs of Knowledge" [online]. Available: http://crypto.cs.mcgill.ca/~crepeau/PDF/BCC88-jcss.pdf. Date accessed: 2019‑12‑07.

[2] M. Nguyen, S. J. Ong and S. Vadhan, "Statistical Zero-knowledge Arguments for NP from any One-way Function (Extended Abstract)" [online]. Available: http://people.seas.harvard.edu/~salil/research/SZKargs-focs.pdf. Date accessed: 2019‑12‑07.

[3] H. Wu, W. Zheng, A. Chiesa, R. A. Popa and I. Stoica, "DIZK: A Distributed Zero Knowledge Proof System", UC Berkeley [online]. Available: https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-wu.pdf. Date accessed: 2019‑12‑07.

[4] B. Bünz, B. Fisch and A. Szepieniec, "Transparent SNARKs from DARK Compilers" [online]. Available: https://eprint.iacr.org/2019/1229.pdf. Date accessed: 2019‑12‑07.

[5] S. Bowe, J. Grigg and D. Hopwood, "Halo: Recursive Proof Composition without a Trusted Setup" [online]. Available: https://eprint.iacr.org/2019/1021.pdf. Date accessed: 2019‑12‑07.

[6] A. Pinto, "Constraint Systems for ZK SNARKs" [online]. Available: http://coders-errand.com/constraint-systems-for-zk-snarks/. Date accessed: 2019‑03‑06.

[7] A. Pinto, "The Vanishing Polynomial for QAPs", 23 March 2019 [online]. Available: http://coders-errand.com/the-vanishing-polynomial-for-qaps/. Date accessed: 2019‑10‑10.