# ZK Proving Systems

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

## SNARKs

[An approximate introduction to how zk-SNARKs are possible](https://vitalik.ca/general/2021/01/26/snarks.html)

### 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](https://eprint.iacr.org/2012/215)
- [PGHR13](https://eprint.iacr.org/2013/279.pdf)
- 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](https://docs.google.com/presentation/d/1UpMo2Ze5iwzpwICPoKkeT04-xGFRp7ZzVPhgnidr-vs/edit?usp=sharing)
- Uses IPA for polynomial commitments and splits IPA for recursive aggregation

ewfew
- PSE [fork](https://github.com/privacy-scaling-explorations/halo2) uses KZG commitments instead

### Nova

## Bulletproofs

### Original paper
- https://eprint.iacr.org/2017/1066
- Uses [IPAs](#IPAs-Inner-product-arguments)

### 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://eccc.weizmann.ac.il/report/2017/134/)
- https://vitalik.ca/general/2017/11/22/starks_part_2.html