<aside> đź’ˇ TL;DR Arithmetic circuits provide a formal way to understanding the complexity of computing polynomials, as well the efficiency that surrounds these computations. This leads to Preprocessing Systems which are the basis for SNARK systems. SNARK systems implement preprocessing through the setup algorithms. The three types of setup procedures used specifically in cryptography are highlighted in the final section, ranking from worst to best (in theory, not always practice as we will later see).
</aside>
In order to better understand the underlying technology of zk-SNARKS, we must first build a basis for Arithmetic Circuits.
Consider a fixed finite field (think of a set of integers) $\mathbb{F} = \{0,...,p-1\}$ for some prime number $p<2$ wherein all arithmetic is done modularly. An Arithmetic Circuit takes inputs $C: \ \mathbb{F}^n \rightarrow \mathbb{F}$ with $n$ elements in a field to produce one field element. Using internal nodes, labeled $+,-$ or $x$ with inputs $1,x_1,...,x_n$, this arithmetic circuit takes these inputs and produces some multivariable polynomial, as well as a “recipe” for how to evaluate this polynomial.
Take an example with inputs $1,x_1,x_2$ that, through a series of arithmetic operations, produces a the multivariable polynomial $x_1(x_1+x_2+1)(x_2-1)$. We will also denote the number of gates in $C$ as $|C|$, with this example $|C|=3$, as three is the number of arithmetic gates, or inputs.
Source: DeFi MOOC Lecture 10: Privacy on the Blockchain
Arithmetic Circuits are an extremely powerful computing model that can be used to accomplish nearly anything in the blockchain space. To demonstrate how, we can look at the following example derived from a DeFi MOOC lecture on privacy:
The Hashing Circuit
This system takes as input the hash value $h$ and message $m$ and will output $0$ if $\text{SHA}256(m)=h$ and $\ne 0$ otherwise
$C_{\text{hash}} (h,m): \text{outputs} \ 0 \text{ if } \text{SHA}256(m)=h, \ne 0 \text{ otherwise}$
Arithmetic Circuit: $C_{\text{hash}}(h,m) = (h-\text{SHA}256(m), \ \ \ \ \ \ \ |C_{\text{hash}}| \approx 20K$ gates
Signature Verification
Using the inputs $pk$ for public key, $m$ for message, and $\sigma$ for signature, $C_\text{sig} (pk,m,\sigma)$ will output $0$ if $\sigma$ is a valid ECDSA signature on $m$ with respect to $pk$.
One specific type of non-interactive argument systems is a preprocessing argument system. In similar fashion to the previous examples, let’s begin with two parties, a Prover $P$ and a Verifier $V$. We will then fix a circuit $C$ that has two inputs, a statement $x$ that we are trying to prove, which is a list of $n$ elements in a Field $F$, and a secret witness $w$ with $m$ elements in a field.
$C(x,w) \rightarrow \mathbb{F}$
In a preprocessing argument system, we will first preprocess the circuit with setup algorithm $S$ that takes the Circuit and produce produces public parameters called $S_p, S_v$ for the prover and verifier respectively.
$S(C)\rightarrow$ public parameters $(S_p,S_v)$
For this system, the prover takes $S_p,x$ and $w$ as inputs and the verifier $S_v$ and $x$. Unlike interactive systems, wherein the prover and verifier iterate back and forth, in this system, the prover will send over proof $\pi$ to the verifier where they will use $S_v,x$ and $\pi$ to Accept or Reject the argument.
$P(S_p, x, w) \rightarrow \pi$
$V(S_v,x,\pi) \rightarrow$ Accept or Reject
A system like the one above has a few requirements similar to that of a NP Proof, wherein it must be complete, and provide an argument of knowledge (soundness), simply stating that if the verifier accepts the proof then the prover knows the witness in which the circuit is equal to zero. Additionally, a zero-knowledge constraint can be applied to ensure that $(S_v, x, \pi)$ reveals nothing about the secret witness $w$.