A Survey of Zero-Knowledge Succinct Non-Interactive Arguments with preprocessing

In this thesis we study the notion of zero-knowledge succinct non-interactive arguments (zkSNARGs) with preprocessing. Given an arithmetic circuit C, public input x, private input w and public output y, a zkSNARG constitutes a protocol that allows a computationally bounded party, called prover, to convince another, called verifier, that C(x, w) = y, i.e. the circuit with inputs x, w evaluates to y, without the verifier gaining any more information beyond the validity of the computation. Moreover, the prover is not required to interact with anyone in order to generate the proof that the verifier will check, while the produced proof is also succinct, i.e. short to store and quick to verify. Finally, these protocols are universal, in the sense that they can be used for any circuit up to a pre-determined bound on their size, while also being updatable, meaning that their SRS can be updated in a verifiable manner by any user. We present the current landscape of the theory of preprocessing universal and updatable zkSNARKs, which advocates for constructing them in a modular way, separating the information theoretic component of the construction from the cryptographic primitive that is used for the compiling phase. The information theoretic part is a polynomial holographic proof (PHP) for the NP-complete language of Rank 1 Constraint Systems (R1CS), while the cryptographic primitive is a polynomial commitment scheme. Furthermore, we examine the bottleneck of the recent constructions, called Checkable Subspace Sampling (CSS), separately and give constructions for it that achieve different efficiency trade-offs. Finally, we present Basilisk, which achieves the smallest proof size in the literature.