ZKPedia

This repository is an encyclopedia of Zero Knowledge Proof. Zero Knowledge Proof (ZKP) is a special family of Verifiable Computing (VC) which has an extra property called Zero Knowledge, actually. It has been proved that any VC system can be converted into a zero-knowledge version additionally. So it is important for researchers to learn VC system as well. The repository records the basic concepts of VC and ZKP, and a series of important articles and books in these areas (which are classical or novel achievements from a aspect of academic), along with some actual applications in various scienarios as well.

The repository is also for recording my personal researches in Verifiable Computing and Zero Knowledge Proof area.

We'd like to collect other awesome materials as well, if they are related. Any useful revisions and pull requests (PR) are welcomed!

Better reading experience.

Introduction

What's Zero Knowledge Proof? And what does zk-SNARKs, zk-STARK... mean? What about interactive proofs and non-interactive proofs? Here gives an overview of these "profound" terms.

Tech Terms

These are some important technique terms (or, preliminaries, in a researcher's tongue) that may be learned before diving into this area. Some of the terms may appear during the journey as well.

• Group, Ring and Field

• Schwartz-Zippel Lemma

• Commitment

  • Polynomial Commitment

  • Vector Commitment

• Probabilistically Checkable Proof (PCP)

• Bilinear Paring

• Low Degree Extension

• Quadratic Span Program (QSP), Quadratic Arithmetic Program (QAP)

  • Quadratic Span Programs and Succinct NIZKs without PCPs

Articles and Books

Articles and books of awesome and beautiful implementations that introduce ZK argument systems and other cryptography primitives in recent years.

Parts of the contents are inspired by the below graph from a speech given by Yupeng, Zhang.

Pioneer Work

GMR85, GMR89

• The knowledge complexity of interactive proof-systems

• The concept of interactive proof is introduced. And the distinction between public coin and private coin (whether the verifier’s randomness is open/visible to the prover) is proved to be not crucial in the follow works.

• Give an argument system that proof consists of 8 group elements and the verification cost of the verifier is some exponentiations and checking pairing product equation of 6 pairings.

Fiat-Shamir Heuristic

• How to prove yourself: Practical solutions to identification and signature problems

Interactive Proof Based Protocols

CMT12

• Practical verified computation with streaming interactive proofs

GKR08, GKR15

• Delegating Computation: Interactive Proofs for Muggles

• This work have 2 different version, one in STOC08, the other in JACM15.

Thaler13

• Time-Optimal Interactive Proofs for Circuit Evaluation

Thaler15

• A Note on the GKR Protocol

vSQL/ZGK+17

• vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases

• This paper combines GKR(CMT) protocol with KZG polynomial commitment together. That obtains a succinct interactive proof system allows for any size of inputs and high proving efficiency. This protocol is applied to a verifiable database scenario for verifying arbitrary SQL query against probably malicious server.

• Multilinear extension and its compositional property.

• A zero-knowledge version: A zero-knowledge version of vSQL.

Hyrax/WTS+18

• Doubly-Efficient zkSNARKs Without Trusted Setup

• Doubly-Efficient: Means efficiency for both the prover and the verifier.

Libra/XZZ19

• Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation

Virgo/ZXZ+20

• Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof

Spartan/Setty20

• Spartan: Efficient and general-purpose zkSNARKs without trusted setup

Virgo++/ZLW+21

• Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time

Bilinear Pairing Based Protocols

These protocols are designed based on the bilinear pairing assumption. And they are non-interactive proof systems.

GGPR13

• Quadratic Span Programs and Succinct NIZKs without PCPs

• Found an insightful construction of polynomial equations based on Lagrange interpolation polynomials yielding a pairing-based NIZK argument with a CRS size proportional to the size of the statement and witness.

Pinocchio/PGHR13

• Pinocchio: nearly practical verifiable computation

• Give an argument system that proof consists of 8 group elements and the verification cost of the verifier is some exponentiations and checking pairing product equation of 6 pairings.

BCTV14

• Scalable, transparent, and post-quantum secure computational integrity

• Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture

Groth16

• On the Size of Pairing-Based Non-interactive Arguments

  • A beautiful proof for the notions: completeness, soundness and zero knowledge, which is worth learning for researchers.

• Give an argument system for arithmetic circuit where a proof consists of only 3 group elements. And the verifier just needs to compute a number of exponentiations proportional to the statement size and check a single pairing product equation, which only has 3 pairings.

Sonic/MBKM19

• Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings

Interactive Oracle Proof Based Protocols

ZXH22

• Polynomial Commitment with a One-to-Many Prover and Applications

Applications

To be finished.

__

Other Learning Materials

To be finished.