SNARK overview
Succinct Non-interactive Argument of Knowledge
I think all the previous courses and guides developed a good sense of the term in my mind :) Now I can tell you what the abbreviation stands for without looking at Wikipedia!
Typical SNARK system is a triple of S(C), P(pp, x, w), and V(vp, x, π):
- S stands for Setup, it provides public parameters pp and vp
- P produces a short proof π for some circuit C based on the public parameters and some witnesses
- V is a function for verification of the proof based on public parameters
To be succinct, we require SNARK to be at least $len(π) = Oλ (log (|C|))$ in terms of the length of a proof and $time(V ) = Oλ (|x|, log (|C|))$ in terms of the verification time. This means the proof must be short and quick to verify.
The setup phase was actually a part of the verification, but some reasonable minds decided it could be extracted and put separately. This is what I’ve understood from the podcasts in the homework, at least (listen to them; they’re really good).
Different kinds of SNARKs:
- Non-universal with separate setup per circuit and large Common Reference String (CRS); Groth16, for example;
- Universal with only one setup and smaller CRS like PLONK;
- Transparent with no need for setup and the smallest CRS like STARK.
The last one seems like an obvious choice, but universality or transparency comes with a big drawback in the form of worse proof size and verification time, and these two parameters are essential.
General process of SNARK system creation:
- Write a program in DSL (Kairo, Noir) or other language (Rust libraries)
- Represent it as an arithmetic circuit (R1CS)
- Convert it to a polynomial or some kind of relation that acts similar
- Make it non-interactive
