zk-SNARKs

Table of Contents

• Introduction
• What is ZKP? A Complete Guide to Zero-knowledge Proof
  • Overview
  • Summary
• Introduction to zk-SNARKs
  • Overview
  • Summary
  • Video
• Comparing General-purpose zk-SNARKs
  • Overview
  • Summary
• Quadratic Arithmetic Programs - from Zero to Hero
  • Overview
  • Summary
• 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
  • Background
  • Summary
• 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

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

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

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

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

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

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.

“Minimum Disclosure Proofs of Knowledge”

[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.

“Statistical Zero-knowledge Arguments for NP from Any One-way 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/sec18-wu.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://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.

“The Vanishing Polynomial for QAPs”