ZK Proving Systems

https://github.com/matter-labs/awesome-zero-knowledge-proofs#bulletproofs

SNARKs

An approximate introduction to how zk-SNARKs are possible

Setup Ceremonies

• https://zkproof.org/2021/06/30/setup-ceremonies/

Pinocchio Protocol + Groth16

R1CS -> QAP -> Trusted Setup -> NILP (Non-interactive Linear Proof) -> pairing-based NIZK (non-interactive zero knowledge) proof

• R1CS arithmetization
• Requires phase 2 non-universal trusted setup

Quadratic Arithmetic Program (QAP)

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

Pinocchio Protocol

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

Groth16

• https://eprint.iacr.org/2016/260.pdf
• https://www.zeroknowledgeblog.com/index.php/groth16
• need 3 pairings
• "common reference string" = phase 1 + 2 trusted setup
• verifier does not need full reference string:
  
  (verification key)
• $\ell$ inputs, $m-\ell$ witness variables, $n$ constraints

PLONK

• https://eprint.iacr.org/2019/953
• https://vitalik.ca/general/2019/09/22/plonk.html
  
• PLONK arithmetization
• universal and updateable trusted setup
• uses KZG commitment

TurboPLONK

PlonK with custom gates

UltraPLONK

TurboPLONK plus plookup

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

Halo 2

Implements UltraPLONK

• https://zcash.github.io/halo2/
• Halo 2 Learning Group intro presentation by Ying Tong
• Uses IPA for polynomial commitments and splits IPA for recursive aggregation

ewfew

• PSE fork uses KZG commitments instead

Nova

Bulletproofs

Original paper

• https://eprint.iacr.org/2017/1066
• Uses IPAs

Halo (original ZCash)

• https://eprint.iacr.org/2019/1021.pdf
• https://vitalik.ca/general/2021/11/05/halo.html
• Recursive aggregation of IPA-based proofs

STARKs

• 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

Polynomial Commitment Schemes (PCS)

Table from https://vitalik.ca/general/2021/11/05/halo.html

Technology	Cryptographic assumptions	Proof size	Verification time
FRI	Hashes only (quantum safe!)	Large (10-200 kB)	Medium (poly-logarithmic)
Inner product arguments (IPAs)	Basic elliptic curves	Medium (1-3 kB)	Very high (linear)
KZG commitments	Elliptic curves + pairings + trusted setup	Short (~500 bytes)	Low (constant)
IPA + Halo-style aggregation	Basic elliptic curves	Medium (1-3 kB)	Medium (constant* but higher than KZG)

*constant = $\log (\text{size of incremental step})$

KZG (Kate, Zaverucha and Goldberg)

• https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf
• https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html

IPAs (Inner product arguments)

• https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html
• https://vitalik.ca/general/2021/11/05/halo.html
• Pedersen vector commitments

FRI

• Fast Reed-Solomon Interactive Oracle Proofs of Proximity
• https://vitalik.ca/general/2017/11/22/starks_part_2.html