/ZKPedia

An encyclopedia of Zero Knowledge Proof. Also for recording my personal researches in Verifiable Computing and Zero Knowledge Proof area.

MIT LicenseMIT

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.

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.

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

GKR08, GKR15

Thaler13

Thaler15

vSQL/ZGK+17

Hyrax/WTS+18

Libra/XZZ19

Virgo/ZXZ+20

Spartan/Setty20

Virgo++/ZLW+21

Bilinear Pairing Based Protocols

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

GGPR13

Pinocchio/PGHR13

BCTV14

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

Interactive Oracle Proof Based Protocols

ZXH22

Applications

To be finished.

__

Other Learning Materials

To be finished.