Golden Observation | Summary of Zero Knowledge Proof Classical Literature (collectable)

  The a16z crypto has published a series of classic literatures, from the DAO classic last year to the earlier NFT classic (and the original encryption classic before that).

This article; A16z crypto has selected a group of resources for those seeking to understand, deepen and build zero knowledge: powerful basic technologies, which hold the key to blockchain scalability and represent the future of private applications, including applications in encryption/web3 and countless other innovations.

These innovations have a long history: Shafi Goldwasser, Silvio Micali and Charles Rackoff introduced the zero knowledge proof system in 1985, which has had a revolutionary impact on the field of cryptography; As a result, they won the 2012 ACM Turing Award. Since this work has been brewing for decades, especially in the process from theory to practice, we also shared the second part of our classic series for the first time, which is the annotated reading list organized by Justin Thaler according to the theme and chronology.

This paper is the first part.

Basis, background and evolution

Some of these papers also involve more general cryptography (not all zero knowledge itself), including an overview of the problem or key progress that zero knowledge proof solves today: how to ensure privacy and authentication in open networks.

New directions in cryptography (1976)

By Whitfield Diffie and Martin Hellman

https://ee.stanford.edu/ ~hellman/publications/24.pdf

A method for obtaining digital signatures and public key cryptosystems

Author: Ronald Rivest, Adi Shamir, Leonard Adelman

https://citeseerx.ist.psu.edu/viewdoc/download ; jsessionid=856E21BC2F75800D37FD611032C30B9C? doi=10.1.1.40.5588& rep=rep1& type= pdf

Protocols for public key cryptosystems (1980) -- Public Key Cryptosystems Protocol (1980)

By Ralph Merkle

http://www.merkle.com/papers/Protocols.pdf

Secure communications over secure channels (1978)

By Ralph Merkle

https://www.merkle.com/1974/PuzzlesAsPublished.pdf

Use of elliptic curves in cryptography (1988)

Author: Victor Miller

https://link.springer.com/content/pdf/10.1007%2F3 -540-39799-X_ 31.pdf

The knowledge complexity of interactive proof systems (1985)

By Shafi Goldwasser, Silvio Micali, Charles Rackof

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132& ; rep=rep1& type=pdf

Computational sound proofs (2000)

Author: Silvio Micali

https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

From extractable collision resistance to succeed non interactive arguments of knowledge [SNARKs], and back again (2011)

Author: Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer

https://eprint.iacr.org/2011/443.pdf

Efficient zero knowledge argument for correction of a shuffle (2012)

By Stephanie Bayer, Jens Groth http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

Succinct non interactive zero knowledge for a von Neumann Architecture (2013)

By Eli Ben Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza

https://eprint.iacr.org/2013/879.pdf

Scalable, transparent, and post quantum secure computational integrity (2018) - Scalable, transparent, and post quantum secure computing integrity (2018)

By Eli Ben Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev

https://eprint.iacr.org/2018/046.pdf

Public coin zero knowledge arguments with (most) minimum time and space overhead (2020)

Author: Alexander Block, Justin Holmgren, Alon Rosen, Ron Rothblum, Pratik Soni

https://www.iacr.org/cryptodb/data/paper .php? pubkey=30645

Overview and introduction

Proof, arguments, and zero knowledge

This paper summarizes verifiable computing and interactive proof and argumentation, which enables the verifier to ensure to the verifier that the verifier has correctly executed the encryption protocol of the requested computing, including zero knowledge (proof does not reveal any other information except their own validity). Zk argument has countless applications in cryptography, and has leapt from theory to practice in the past decade.

Author: Justin Thaler

https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

An evolution of models for zero knowledge proofs

Looking back on zero knowledge proof, Meiklejohn (University College London, Google) focuses on the applications that promote its development, the different models emerging to capture these new interactions, the structures we can implement, and other work.

Author: Sarah Meiklejohn

https://www.youtube.com/watch?v=HO97kVMI3SE

ZK whiteboard sessions - ZK whiteboard meetings: introductory articles

Author Dan Boneh et al

https://zkhack.dev/whiteboard/

Security and privacy for crypto with zkps -- security and privacy of zkps encryption

Leading zero knowledge proof in practice; What zkps are and how they work... including live "demos"

By Zooko Wilcox

https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

Top technical topics, explained

Including the general definition and meaning of zero knowledge

Author: Joe Bonneau, Tim Roughgarden, Scott Kominers, Ali Yahya, Chris Dixon

https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos

Zero knowledge explanation - Level 5 difficulty

Author: Amit Sahai from Wired

https://youtu.be/fOGdb1CTu5c

How the coming privacy layer will fix a broken web

Author: Howard Wu

https://future.com/a-privacy-layer-for-the-web-can-change-everything/

Introduction to zkSNARKs

Author: Howard Wu, Anna Rose

https://zeroknowledge.fm/38-2/

Why and how zk SNARK Works: a definitive explanation -- zk SNARK mechanism and how it works: an authoritative explanation

Author: Maksym Petkus

https://arxiv.org/pdf/1906.07221.pdf

An introduction to zero knowledge proofs

By Fredrik Harrisson, Anna Rose

https://www.zeroknowledge.fm/21  

[and summary articles elsewhere https://blog.goodaudience.com/understanding-zero-knowledge-proofs-through-simple-examples-df673f796d99 ]

ZK SNARKs: under the hood -- ZK SNARKs: essence

By Vitalik Buterin

https://medium.com/ @VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

https://vitalik.ca/general/2016/12/10/qap.html

https://vitalik.ca/general/2017/01/14/exploring_ecp.html

https://vitalik.ca/general/2017/02/01/zk_snarks.html

Decentralized speed - Decentralized speed

Progress on Zero Knowledge Proof and Decentralized Hardware

Author: Elena Burger

https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

Cutting edge zk research

Mary Maller, Anna Rose, Kobi Gurkan, zk researcher of Ethereum Foundation

https://zeroknowledge.fm/232-2/

Exploring zk research

Guest: DFINITY Research Director; Jens Groth, Anna Rose, Kobi Gurkan from Groth16

https://zeroknowledge.fm/237-2/

SNARK research & Pedagogy -- SNARK Research and Teaching Method

From one of the co founders of ZCash and Starkware and Alessandro Chiesa, Anna Rose

https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

In depth: course, decomposition, builder's guide

Foundations of probabilistic proofs

Interactive proof course with 5 units and more

Author: Alessandro Chiesa

https://www.youtube.com/playlist?list=PLGkwtcB -DfpzST-medFVvrKhinZisfluC

9th BIU Winter School on Cryptography

From Applied Cryptography and Network Security Research Center

Author: Yehuda Lindell, Benny Pinkas, Eli Ben Asson, Jens Groth, Carmit Hazay, Yuval Ishai, Alon Rosen, Ron Rothblum

https://cyber.biu.ac.il/event/the-9th-biu-winter-school-on-cryptography/

Interactive proofs and zero knowledge

From Stanford CSS 355 Cryptography Theme (2018)

Author: Henry Corrigan Gibbs, Sam Kim, David Wu

https://crypto.stanford.edu/cs355/18sp/lec3.pdf

Interactive demonstration of the zero knowledge proof protocol for 3-colored graphs

Allow a person to convince the verifier of the truth of a fact (i.e., a graph is 3-colored) without revealing the actual three colors of the graph

http://web.mit.edu/ ~ezyang/Public/graph/svg. html   [For more information, see https://www.cs.cmu.edu/ ~goyal/s18/15503/scribe_ notes/lecture23.pdf]

SNARK design, part 1 —— SNARK Design, Part 1

Survey, use in Rollup and more

Author: Justin Thaler

https://www.youtube.com/watch?v=tg6lKPdR_e4

SNARK design, part 2 - SNARK design, part 2

Rollup, performance, security

Author: Justin Thaler

https://www.youtube.com/watch?v=cMAI7g3UcoI

STARKs: part I, II, III -- STARKs: part I, II, III

By Vitalik Buterin

https://vitalik.ca/general/2017/11/09/starks_part_1.html

https://vitalik.ca/general/2017/11/22/starks_part_2.html

https ://vitalik.ca/general/2018/07/21/starks_ part_ 3.html

Anatomy of a STARK -- Analysis of STARK

Six part tutorial, explaining the mechanism of the STARK certification system

By Alan Szepieniec

https://aszepieniec.github.io/stark-anatomy/

Measuring SNARK performance

Front end, back end, more

Author: Justin Thaler

https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

Understanding PLUNK

Author: Vitalik

https://vitalik.ca/general/2019/09/22/plonk.html

The PLUNK zero knowledge proof system

12 short video series on how PLUNK works

Author: David Wong

https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg -Vng2V6EYVidTFCC

From AIRs to RAPs —— From AIRs to RAPs

How PLUNK style algorithms work

Author: Ariel Gabizon

https://hackmd.io/ @aztec-network/plonk-arithmetiization-air

Multiset checks in PLUNK and Plookup -- Multiset checks in PLUNK and Plookup

Author: Ariel Gabizon

https://hackmd.io/ @arielg/ByFgSDA7D

Halo2 design - Halo2 design

From ECC

https://zcash.github.io/halo2/design.html

Plonky2

https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

Applications and tutorials: proof of concept, demos, tools, etc

Applied zk

Learning resources to provide materials for engineers without formal mathematical background to speed up their solid understanding of basic theories

Author: 0xPARC

https://learn.0xparc.org/materials/intro

An online development environment for zkSNARKs -- zkREPL

ZkREPL is a new set of tools for interacting with the Circle tool stack in the browser

Author: Kevin Kwok

https://zkrepl.dev

Quadratic arithmetic programs from zero to hero

By Vitalik Buterin

https://medium.com/ @VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

On zkEVMs -- On zkEVM

Guest: Alex Gluchowski, Anna Rose

https://zeroknowledge.fm/175-2/

Different types of zkEVMs -- different types of zkEVMs

By Vitalik Buterin

https://vitalik.ca/general/2022/08/04/zkevm.html

ZK machine learning -- ZK machine learning

Tutorial and demonstration of introducing neural network into SNARK

Author: Horace Pan, Francis Ho, Henri Palacci

https://0xparc.org/blog/zk-mnist

On ZK languages -- Discuss ZK language

Guest: Alex Ozdemir and Anna Rose

https://zeroknowledge.fm/172-2/

Arkworks - Rust ecosystem developed and programmed using zkSNARKs

https://github.com/arkworks-rs

Dark Forest - applying zk cryptography to games: Dark Forest

Fully decentralized and persistent RTS (real-time strategy) games

https://blog.zkga.me/announcing-darkforest

ZKPs for engineers

Dark Forest ZKP Research

https://blog.zkga.me/df-init-circuit

A dive into zero knowledge

Guests: Elena Nadolinkski, Anna Rose, James Prestwich

https://zeroknowledge.fm/182-2/

ZkDocs: Zero knowledge information sharing

By Sam Ragsdale, Dan Boneh

https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

Privacy protecting crypto airdrops with zero knowledge proofs

By Sam Ragsdale

https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

ZK Hack - riddles, more

https://zkhack.dev/events/mini.html#puzzles

On chain trusted setup ceremonies

By Valeria Nikolaenko, Sam Ragsdale

https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

Crypto regulations, illegal finance, privacy, and beyond

Including the zero knowledge part in the regulatory/compliance environment; The difference between "privacy protection" and obfuscation technology

Guests: Michele Korver, Jai Ramaswamy, Sonal Chokshi

https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

Other resources

ZkMesh Communication

Monthly newsletter to share the latest decentralized privacy protection technology, privacy protocol development and zero knowledge system

https://zkmesh.substack.com/

Zero Knowledge podcast

Experts on the latest zk research and zk applications as well as building encryption privacy technology together

Guest: Anna Rose

https://zeroknowledge.fm/