# Introduction to Zero Knowledge Proofs

A zero knowledge proof (ZKP or just ZK) is a proof of computation satisfying:
* **Succinctness**: the size of the proof is constant (or in some cases logarithmic) in the size of the computation
* **Zero knowledge**: certain inputs or intermediate variables of the computation can be hidden from the verifier of the proof

Contrary to the name, the succinctness property is more central to current applications of ZK, whereas the zero knowledge aspect is often not used and can be turned off.

The general dynamic of a zero knowledge proof is that a Prover generates a ZKP of a computation and sends the (constant sized) ZKP to a Verifier. The Verifier then runs some constant time verification algorithm on the ZKP: if it passes, then the Verifier is assured that the Prover executed the claimed computation truthfully. Most importantly, the Verifier has this assurance **without trusting** the Prover. The precise assurance is of the form "under certain cryptographic assumptions, ___ is true with probability $2^{-100}$".

## How it works
There are now front-ends with varying levels of abstraction (Rust API libraries, domain-specific languages) to translate arbitrary NP computations to **ZK circuits**. Given computation specific inputs, a ZK circuit generates a ZK proof to be submitted to the Verifier.

This step of translation from familiar computation to ZK circuit is not quite straightforward and there is still a lot of low-hanging fruit. At the lowest level, ZK circuits are not described in a Turing complete language; as the name suggests, "circuits" are closer in spirit to circuits in hardware chips.

In a ZK circuit, a computation is represented as a collection of vectors together with imposed **constraints** (aka relations) between certain entries in the vectors. For example, computing `1 + 1 = 2` could be saying we have a vector `(a,b,c)` and constraints `a == 1, b == 1, a + b == c`. One way to think about constraints is that in a trustless environment, all entries of the vector can be adversarially selected, and your only safeguard is the constraints you impose on these numbers.

There are different ways to represent the execution trace as vectors + constraints, these are called **arithmetizations**. Nowadays there are "front-ends" with different levels of abstraction and customizability for translating a ZK circuit into an arithmetization. For more details with an example, see [this section](#Example-PLONK).

### Prover-Verifier Dynamic
Once we have an arithmetization (vectors + constraints), the prover-verifier dynamic goes as follows:
1. The Prover sends Verifier some **commitment** to the vectors and further commitments (details omitted) to the constraints
2. The Verifier sends Prover some random numbers
3. Prover uses previous commitments to show that the polynomials evaluate at the random numbers to 0.

The above procedure is interactive, since the Verifier needs to provide randomness, but we remark that there is a general way to make it non-interactive: see [Fiat-Shamir Heuristic](https://www.zkdocs.com/docs/zkdocs/protocol-primitives/fiat-shamir/). In the non-interactive protocol, the prover does all the steps and sends the result to the verifier.

#### Polynomial Commitments
One can think of a commitment as a more expressive hash: it pins down the vector so you can't change it later, plus some other properties.

The question of how to commit to vectors is an area of active research. First, most vector commitments translate a vector into a polynomial (by Lagrange interpolation) and then work with the polynomial. Then, broadly speaking, they are currently in two categories:
* Use elliptic curve cryptography (not quantum-secure, additional assumptions for security, slower runtime)
* Hash the polynomials and do some sampling (proof sizes are larger, additional [assumptions](https://a16zcrypto.com/snark-security-and-performance/) for security)

For an overview of polynomial commitments from the API perspective, see this [video](https://learn.0xparc.org/materials/halo2/miscellaneous/polynomial-commitment).

## Example: PLONK

### Frontend
There are various options of what kind of front-end to use to design a ZK circuit. While there are some domain specific languages (DSLs) such as [circom](https://docs.circom.io/) and [cairo](https://www.cairo-lang.org/) that try to make circuit design as close to traditional programming as possible, we have opted to use a lower level rust library called [halo2](https://zcash.github.io/halo2/index.html) because we believe it is the most customizable and future-proof.

Halo2 uses the PLONKish arithmetization. We will explain the slightly simpler [PLONK](https://eprint.iacr.org/2019/953.pdf) arithmetization here to give a flavor for how circuit design works. A PLONK circuit consists of a table/matrix with the following fixed columns and nearly arbitrary number of rows:

| $a$ | $b$ | $c$ | $q_L$ | $q_R$ | $q_M$ | $q_C$ | $q_O$ |
| -------- | -------- | -------- | -- | -- | -- | -- | -- |
| . | . | . | | | | | |

where the numbers in the columns $q_L, \dotsc, q_O$ are **fixed** once and for all at compile time. Meanwhile the numbers in columns $a, b,c$ are called **witnesses** and specified by the prover each time a new proof is generated. What makes the circuit meaningful, and not a random collection of numbers, is that for each row $i$, the following equation is guaranteed to hold:
$$
q_L \cdot a + q_R \cdot b + q_M \cdot a \cdot b + q_C = q_O \cdot c
$$
Since the $q$s are fixed once and for all, specifying these numbers allows you to "mold" the circuit to constrain the witnesses $a,b,c$ to perform certain computations.

For example, if you want to add $a_i + b_i = c_i$ in row $i$, put:
| $a$ | $b$ | $c$ | $q_L$ | $q_R$ | $q_M$ | $q_C$ | $q_O$ |
| -------- | -------- | -------- | -- | -- | -- | -- | -- |
| $a_i$ | $b_i$ | $c_i$ | 1 | 1 | 0 | 0 | 1 |

To multiply $a_i \cdot b_i = c_i$ in row $i$, put:
| $a$ | $b$ | $c$ | $q_L$ | $q_R$ | $q_M$ | $q_C$ | $q_O$ |
| -------- | -------- | -------- | -- | -- | -- | -- | -- |
| $a_i$ | $b_i$ | $c_i$ | 0 | 0 | 1 | 0 | 1 |

To force $a_i$ to be a known constant $A$, put:
| $a$ | $b$ | $c$ | $q_L$ | $q_R$ | $q_M$ | $q_C$ | $q_O$ |
| -------- | -------- | -------- | -- | -- | -- | -- | -- |
| $a_i$ | * | * | 1 | 0 | 0 | $-A$ | 0 |

Note that $b_i, c_i$ can be any numbers and it doesn't matter.

So far, we can use the above to do single line computations. There is one more ingredient: one can also specify once and for all that certain predetermined cells in the table above are always equal. For example for some $i_0$, we must have $c_{i_0} = a_{i_0 + 1}$. This now allows us to carry results of previous computations into new computations, "chaining" to create longer computations.

To summarize, creating a ZK proof involves the following steps:

Once and for all, specify the circuit itself:
- Specify all cells in columns $q_L, q_R, \dotsc, q_O$.
- Specify any equality constraints between cells.
- The verifier received a *commitment* to the above information - this is called a **verifying key**
- The prover holds onto a copy of the above information itself - this is called a **proving key** (the proving key is usually much larger than the verifying key because the data has not been compressed)

To submit a proof:
- Do the computation itself, i.e., generate the witnesses $a_i, b_i, c_i$.

Now that you understand PLONK, you can read about general PLONKish arithmetizations [here](https://hackmd.io/@aztec-network/plonk-arithmetiization-air).

#### Exercises
1. Using the PLONK setup above, how would you create a circuit to divide two numbers? (Caveat: numbers really mean numbers in a [finite field](#Numerical-architecture), so don't worry about rounding.)
2. How do you prove the computation sending a number `a` to `1` if `a != 0` or `0` if `a = 0`? To clarify, `a` is a number in a specific [finite field](#Numerical-architecture), and `a = 0` means the number is congruent to zero in the finite field.

### Backend

While circuit design involves just filling out a table using some front end, to actually create a proof there is a backend that takes the PLONK table above and does a bunch of computations involving polynomial commitment schemes. This part is largely independent of the circuit design, but different backends lead to different performance characteristics, which become important to understand for production use cases.

More coming soon.

## Example: STARKs

STARKs are a special kind of SNARK that uses hashes for their vector commitments and AIR for its arithmetization. There has been a lot of early development around STARKs due to Starkware, so there are more introductions in this area. I just found a good guide [here](https://aszepieniec.github.io/stark-anatomy/).

## Challenges
Why is ZK not used more prevalently if it can compress any computation? One reason is that only recently has the dev tooling and cryptographic systems become expressive and stable enough for people to actual build on top of them.

There are also some intrinsic challenges related to the nature of ZK circuits:

### Overhead
While proof size and proof verification time are constant, the runtime to generate a proof is far from it. Right now, the estimated overhead of generating a proof for a particular computation is around 10-100x. This is an active engineering problem with many facets for improvement:
* Improving circuit design - this involves finding the optimal way to translate the computation into an arithmetization
* General performance engineering - some of the open source code used for proof generation was developed for other purposes, and serious performance optimization has not been applied yet
* Choice of proving system: the combination of arithmetization and polynomial commitment scheme forms a **proving system**. New research in this area can lead to step change improvements in performance.
* Hardware: many core algorithms (Fast Fourier Transform, Elliptic Curve Multiscalar Multiplication) involved in the polynomial commitments can be parallelized or otherwise optimized using GPUs, FPGAs, ASICs.

### VM / Turing completeness
As mentioned above, a ZK circuit in its purest form is not Turing complete (you cannot have recursive functions or infinite loops). It also does not behave in the way we are used to a general purpose VM (e.g., LLVM) behaving. For example, the notion of an "if" statement is very different: assuming boolean `a`, to replicate

if a:
    f(b)
else:
    g(b)

in a circuit, we need to compute *both* `f(b)` and `g(b)` and then return `a * f(b) + (1 - a) * g(b)`.

There are ways to build general or customized VMs from ZK circuits, and this is a direction that we must eventually go in to provide the familiar developer environment necessary to get more people to build interesting applications atop ZK.

This transition from circuit -> VM is possible using the principles of recursion and aggregation of ZK circuits. For example, to create a ZKP of `f(g(x))`, you would create ZKP `A` for `y == g(x)` and then a ZKP `B` that verifies the proof `A: y == g(x)` and further computes `f(y)`. This is a more advanced topic which we will write about in more depth later, but for now we direct the interested reader to this blog [post](https://0xparc.org/blog/groth16-recursion).

### Numerical architecture
A fundamental difference between traditional compute and all ZK circuits is the numerical system the compute is applied on top of. In traditional architecture, we work in the world of bits: numbers are `uint32, uint64, int32, int64`, etc. Meanwhile, due to the cryptographic underpinnings behind ZK, all ZK circuits involve [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic), i.e., numbers are element in a finite field. This usually means there is a special prime number $p$, and then all operations are performed modulo $p$.

This difference means that:
* Operations that are cheap for bits (bit shifts, `AND`, `XOR`, `OR`) are expensive to implement in ZK.
* Since ZK circuits still need to be implemented in traditional architectures, the implementation of things like finite field arithmetic adds another layer of overhead to all computations.

There are continual developments to overcome this challenge, such as ZK friendly [hashes](https://eprint.iacr.org/2019/458.pdf) or using "lookup tables" for ZK-unfriendly operations, but for now it is still a source of difficulties for performance and development.

## Closing Remarks

The potential of things ZK can build is tremendous and only increasing exponentially. We believe that a key ingredient in successfully building new ZK applications is to have a good understanding of the current features and limitations of ZKPs.

## Further Reading

We haven't gone into the weeds of the math involved with ZK.
* For the classic explanation of ZKPs that you can repeat at dinner parties (no math): see [here](https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/)
* For a more math-y intro that gives a better flavor of how ZK works now, see Vitalik's post on QAPs [here](https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649). This uses a more straightforward but restrictive arithmetization known as R1CS.
* While R1CS is no longer considered the most suitable arithmetization for production use, there is a nice DSL called [circom](https://docs.circom.io/circom-language/signals/) that you can play around with in-browser [here](https://zkrepl.dev/).
* Currently we are using the [PLONKish arithmetization](https://hackmd.io/@aztec-network/plonk-arithmetiization-air) with the [Halo2](https://zcash.github.io/halo2/index.html) frontend.
* Introduction to Halo2 [slides](https://docs.google.com/presentation/d/1UpMo2Ze5iwzpwICPoKkeT04-xGFRp7ZzVPhgnidr-vs/edit#slide=id.p)
* Proof system for zkRollups by Ye Zhang [[slides]](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/6aabe8b9-35a9-45c1-ab04-8ada983d48a1/rec_0xparc.pdf?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=AKIAT73L2G45EIPT3X45%2F20221121%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20221121T235344Z&X-Amz-Expires=86400&X-Amz-Signature=300a67fd671a36233a7a609f2ac3ba63d356cc252a1b19fac3ef8895a905ff67&X-Amz-SignedHeaders=host&response-content-disposition=filename%3D%22rec_0xparc.pdf%22&x-id=GetObject) [[youtube]](https://www.youtube.com/watch?v=tGaD8qpQi6c)
* The talk is more advanced but the first half gives an overview of the pipeline (including frontend vs backend) of ZK proofs
* A more advanced history and overview of ZK proving systems: https://twitter.com/SrikarVaradaraj/status/1521189005496311808
* To start diving into actual proving systems and polynomial commitment schemes: see resources [here](https://hackmd.io/@jpw/BJAf6spB9).
* And of course, contact us to ask questions and discuss further!