Table of Contents
 Introduction
 What is ZKP? A Complete Guide to Zeroknowledge Proof
 Introduction to zkSNARKs
 Comparing Generalpurpose zkSNARKs
 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
 zkSHARKs: Combining Succinct Verification and Public Coin Setup
 References
Introduction
Zeroknowledge proof protocols have gained much attention in the past decade, due to the popularity of cryptocurrencies. A zeroknowledge Succinct Noninteractive Argument of Knowledge (zkSNARK), referred to here as an argument of knowledge, is a special kind of a zeroknowledge 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].
zkSNARKs have found many applications in zeroknowledge proving systems, libraries of proving systems such as libsnark and bellman and generalpurpose compilers from highlevel languages such as Pinocchio. “DIZK: A Distributed Zero Knowledge Proof System”, by Wu et al. [3], is one of the best papers on zkSNARKs, at least from a cryptographer’s point of view. Coins such as Zerocoin and Zcash use zkSNARKs. The content reflected in this curated content report, although not all inclusive, covers all the necessary basics one needs to understand zkSNARKs and their implementations.
What is ZKP? A Complete Guide to Zeroknowledge Proof
Hasib Anwar
Just is a born geek
Overview
A zeroknowledge 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 zeroknowledge infographic that summarizes what a zeroknowledge proof is, its main properties (completeness, soundness and zeroknowledge), as well as its use cases such as authentication, secure data sharing and filesystem control. Find what Anwar calls a complete guide to zeroknowledge proofs, here.
Introduction to zkSNARKs
Dr Christian Reitwiessner
Ethereum Foundation
Overview
A typical zeroknowledge 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
zkSNARKs are important in blockchains for at least two reasons:
 Blockchains are by nature not scalable. They thus benefit in that zkSNARKs 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 zeroknowledge property of zk‑SNARKs as well as the possibility to put in place a socalled trusted setup make this almost possible.
Reitwiessner uses an example of a mini 4 x 4 Sudoku challenge as an example of an interactive zeroknowledge proof. He explains how it would fall short of the zeroknowledge 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 Generalpurpose zkSNARKs
Ronald Mannak
Opensource Blockchain Developer
Overview
Recently, zkSNARK 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 generalpurpose zkSNARKs. The article is easy to read. It provides the technical reader with relevant references to scholarly research papers.
Summary
The main drawback of zkSNARKs 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 zkSNARKs 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
Cofounder of Ethereum
Overview
The zkSNARK endtoend journey is to create a function or a protocol that takes the proof, given by the Prover, and checks its veracity. In a zkSNARK 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 zkSNARK proof can be performed. The following seven steps depicts the process for achieving a zkSNARK:
Computational Problem —> Arithmetic Circuit —> R1CS —> QAP —> Linear PCP —> Linear Interactive Proof > zkSNARK
Summary
In this post, Buterin explains how zkSNARKs 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 rank1 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 zkSNARKs 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 zeroknowledge is achieved in zkSNARKs. For a stepbystep and mathematical explanation of how this is achieved, as used in Zcash, refer to the sevenpart series listed here.
[Part I: Homomorphic Hidings]
This post explains how zkSNARKs use homomorphic hiding or homomorphic encryption in order to achieve zeroknowledge 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 zeroknowledge proofs to be set up.
For example, two parties can set up a zeroknowledge 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 nonnegligible 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 zeroknowledge proof with negligible probability that the Verifier would accept a wrong polynomial as correct. The low probability is guaranteed by a wellknown 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 noninteractive 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 noninteractive 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 noninteractive 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).
zkSHARKs: Combining Succinct Verification and Public Coin Setup
Madars Virza
Scientist, MIT
Background
Most of the research done on zeroknowledge 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 socalled zkSHARKs (short for zeroknowledge Succinct Hybrid ARguments of Knowledge) designed by Mariana Raykova, Eran Tromer and Madars Virza.
Summary
Virza starts with a concise survey of the best zkSNARK protocols and their applications while giving an assessment of the efficiency of zeroknowledge proof implementations in the context of blockchains. He mentions that although zeroknowledge proofs have found practical applications in privacy preserving cryptocurrencies, privacy preserving smart contracts, proof of regulatory compliance and blockchainbased sovereign identity, they still have a few shortcomings. While QAPbased zeroknowledge proofs can execute fast verifications, they still require a trusted setup. Also, in Probabilistically Checkable Proof (PCP)based zkSNARKs, 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 zeroknowledge 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 zkSHARK is introduced as one such zeroknowledge protocol that implements these two types of verification modes. It is a hybrid, as it incorporates a Noninteractive Zeroknowledge (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 specialpurpose SNARK, which constitutes the main part of the zkSHARK, is dedicated to verifying an encoded polynomial delegation problem.
The design of zkSHARKs 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/BCC88jcss.pdf. Date accessed: 2019‑12‑07.
“Minimum Disclosure Proofs of Knowledge”
[2] M. Nguyen, S. J. Ong and S. Vadhan, “Statistical Zeroknowledge Arguments for NP from any Oneway Function (Extended Abstract)” [online]. Available: http://people.seas.harvard.edu/~salil/research/SZKargsfocs.pdf. Date accessed: 2019‑12‑07.
“Statistical Zeroknowledge Arguments for NP from Any Oneway Function (Extended Abstract)”
[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/sec18wu.pdf. Date accessed: 2019‑12‑07.
“DIZK: A Distributed Zero Knowledge Proof System”
[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.
“Transparent SNARKs from DARK Compilers”
[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.
“Halo: Recursive Proof Composition without a Trusted Setup”
[6] A. Pinto, “Constraint Systems for ZK SNARKs” [online]. Available: http://coderserrand.com/constraintsystemsforzksnarks/. Date accessed: 2019‑03‑06.
[7] A. Pinto, “The Vanishing Polynomial for QAPs”, 23 March 2019 [online]. Available: http://coderserrand.com/thevanishingpolynomialforqaps/. Date accessed: 2019‑10‑10.
“The Vanishing Polynomial for QAPs”