# Overview: Post-quantum zk-SNARKs
This is an overview of widely used post-quantum zk-SNARK (zero-knowledge succinct non-interactive argument of knowledge) proof systems, explained using a modular breakdown of their arithmetisations, polynomial IOPs, and polynomial commitment schemes (Fig. 1). *This document is not meant to serve as a comprehensive index or standard.*

Modern SNARKs consist of three components:
1. an *arithmetisation*, encoding a computation as an algebraic constraint satisfaction problem;
2. an information-theoretic *polynomial interactive oracle proof (PIOP)*, in which the constraint satisfaction problem from (1) is expressed as a polynomial identity;
3. a compatible cryptographic *polynomial commitment scheme (PCS)*, which compiles the PIOP into an argument system by introducing cryptographic hardness assumptions.


*Fig. 1: Common arithmetisations, polynomial IOPs, and (post-quantum) polynomial commitment schemes*

> When instantiated with a linear-time encoding codes, it is known as Brakedown Polynomial Commitments. When instantiated with Reed-Solomon codes, it is known as Ligero Polynomial Commitments AHIV17. (And when used to instantiate Spartan they are known as Brakedown and Shockwave respectively.)

*Fig. 2: The components of a proof system.*

If the proof system is knowledge sound, then the prover must have knowledge of the witness in order to construct a valid proof. If it is also zero knowledge, then witness entries can be private, and an honestly generated proof leaks no information about the private inputs to the circuit beyond the fact that it was obtained with knowledge of some satisfying witness.

When we talk about a zkSNARK being post-quantum secure, we are almost entirely referring to the polynomial commitment scheme, as the arithmetization is simply a deterministic re-representation of the original computation, and the PIOP is information-theoretic. However, not all components are cross-compatible -- for example, some post-quantum zkSNARKs require a specific arithmetization that is only compatible with certain IOPs.

**Table of contents**

[TOC]

## Benchmarks
Setup / proving key / verifying key size
Proof size / communication cost
Proving time on mobile

### plonky3
Plonkish -> PlonK IOP -> FRI

### Anonymous credentials from ECDSA [FS24]
Layered arithmetic circuits -> GKR + Ligero IOP -> Ligero PCS ?

### Ligetron
WASM (?) -> Ligero -> Ligero

0.61 SHA256 per second on my mobile browser?
https://dev-platform.ligetron.com/speedtest

## Arithmetisations
A relation $R$ contains pairs of $(x, w)$ where:
- the instance $x$ consists of the parameters of the proof system, the circuit, and the public inputs to the circuit (i.e. the instance vector);
- the witness $w$ consists of values provided by the prover, including (potentially private) prover inputs to the circuit, and any intermediate values (including fixed values) that are not inputs to the circuit but are required in order to satisfy the relation.

We say that $x$ is a valid instance whenever there exists some witness $w$ such that $(x,w) \in R$. The language $L$ contains all valid instances. Our goal is to prove that some instance $x \in L$.

An arithmetisation is a language that a proof system uses to express statements. A circuit is a program in this language. The associated computation has been computed correctly if and only if all of the constraints in the circuit are satisfied, which corresponds to some relation $R$ being satisfied. Thus, an arithmetization allows us to reduce a proof of computation to a proof of having $(x,w)$ satisfying some relation $R$. The arithmetisation we choose for our circuit will effect the relation $R$ that the computation needs to satisfy.

### R1CS [VG]

The R1CS (rank-1 constraint system) is a way of representing an arithmetic circuit in the form of matrix-vector relationships.

#### Instances
The relation $\mathcal{R}_{\mathsf{R1CS}}$ takes instances of the following form:

| Instance element | Description |
| ----------------- | -------- |
|$\mathbb{F}$ | A prime field. |
| $A, B, C$ | Constraint matrices. |
| $io$ | The public input/output of the circuit|
| $n$ | Dimension of the matrices. |
| $m$ | The upper-bound for the number of nonzero entries in a matrix. |

#### Witnesses
The relation $\mathcal{R}_{\mathsf{R1CS}}$ takes witnesses of the following form:

| Witness element | Description |
| ----------------- | -------- |
| $\vec{w}$ | The witness vector $\vec{w} \mathrel{⦂} \mathbb{F}^{n - \|io\| - 1}$. |

#### Definition of the relation

Given the above definitions, the relation $\mathcal{R}_{\mathsf{R1CS}}$ corresponds to a set of $\,(\!$ instance $\!,\,$ witness $\!)\,$ pairs
$$
\Big(x = \big(\mathbb{F}, A, B, C, io, n, m\big),\, \vec{w} \Big)
$$
such that:

$$(A \cdot z) \circ (B \cdot z) = (C \cdot z) $$ where $\vec{z} = (io, 1, \vec{w}), \cdot$ represents a matrix-vector product, and $\circ$ represents an element-wise (Hadamard) product.

#### Example

Say we are trying to show that we know an input $x$ such that $z_0^2 + 3z_0 + 2 = 6.$ In order to convert this to a relation $\mathcal{R}_{\mathsf{R1CS}}$, first we need to rewrite the equation in a specific arithmetic circuit form, such that each constraint only has one multiplication.
$$\begin{align*}
z_1 &= z_0 \cdot z_0 \\
z_2 &= 3 \cdot z_0 + z_1 \\
z_3 &= z_2 + 2 \\
\end{align*}$$

We know that $x = 1$ is a possible solution, so it is our input. Therefore $in = z_0 = 1, z_1 = 1, z_2 = 4, out = z_3 = 6.$ The witness $\vec{w}$ is formed by $(z_1, z_2) = (1, 4)$, and therefore $\vec{z} = (io, 1, w) = (1, 6, 1, 1, 4)$. Each equation can be represented by the following sparse vectors $(\vec{a}, \vec{b}, \vec{c})$ such that $\vec{a} \cdot {z} \circ {\vec{b} \cdot {z} = \vec{c} \cdot {z}}$ where $\cdot$ is dot product and $\circ$ is a Hadamard product:
| Equation | $\vec{a}$ | $\vec{b}$ | $\vec{c}$ |
| -------- | --------- | --------- | --------- |
| $z_1 = z_0 \cdot z_0$ | $(1, 0, 0, 0, 0)$ | $(1, 0, 0, 0, 0)$ | $(0, 0, 0, 1, 0)$ |
| $z_2 = 3 \cdot z_0 + z_1$ | $(3, 0, 0, 1, 0)$ | $(0, 0, 1, 0, 0)$ | $(0, 0, 0, 0, 1)$ |
| $z_3 = z_2 + 2$ | $(0, 0, 2, 0, 1)$ | $(0, 0, 1, 0, 0)$ | $(0, 1, 0, 0, 0)$ |.

Putting these together, our R1CS constraint matrices are:
$$ A = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
& & \vec{0} & & \\
& & \vec{0} & & \\
\end{bmatrix}
$$

$$ B = \begin{bmatrix}
3 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 \\
& & \vec{0} & & \\
& & \vec{0} & & \\
\end{bmatrix}
$$

$$ C = \begin{bmatrix}
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 & 0 \\
& & \vec{0} & & \\
& & \vec{0} & & \\
\end{bmatrix}
$$

### Plonkish
The Plonkish arithmetisation is a family of arithmetisation variants based on PlonK [^plonk] (This section has been adapted from the ZKProof Plonkish Constraint System Working Group [^zkproof-standards]).

#### Instances
The relation $\mathcal{R}_{\mathsf{plonkish}}$ takes instances of the following form:

| Instance element | Description |
| ----------------- | -------- |
| $\mathbb{F}$ | A prime field. |
| $t$ | Length of the instance vector. |
| $\phi$ | The instance vector $\phi \mathrel{⦂} \mathbb{F}^t$. |
| $n > 0$ | Number of rows. |
| $m > 0$ | Number of columns. |
| $\equiv$ | An equivalence relation on $[0,m) \times [0,n)$ indicating which witness entries are equal to each other. |
| $S$ | A set $S \subseteq ([0,m) \times [0,n)) \times [0,t)$ indicating which witness entries are equal to instance vector entries. |
| $m_f \leq m$ | Number of columns that are fixed. |
| $f$ | The fixed content of the first $m_f$ columns, $f \mathrel{⦂} \mathbb{F}^{m_f \times n}$. |
| $p_u$ | Custom multivariate polynomials $p_u \mathrel{⦂} \mathbb{F}^m \rightarrow \mathbb{F}$. |
| $\mathsf{CUS}_u$ | Sets $\mathsf{CUS}_u \subseteq [0,n)$ indicating rows on which the custom polynomials $p_u$ are constrained to evaluate to 0. |
| $L_v$ | Number of table columns in each lookup table $\mathsf{TAB}_v$. |
| $\mathsf{TAB}_v$ | Lookup tables $\mathsf{TAB}_v \subseteq \mathbb{F}^{L_v}$, each with a number of tuples in $\mathbb{F}^{L_v}$. |
| $q_{v,s}$ | Scaling multivariate polynomials $q_{v,s} \mathrel{⦂} \mathbb{F}^m \rightarrow \mathbb{F}$ for $s \leftarrow 0 \text{..} L_v$. |
| $\mathsf{LOOK}_v$ | Sets $\mathsf{LOOK}_v \subseteq [0,n)$ indicating rows on which the scaling polynomials $q_{v,s}$ evaluate to some tuple in $\mathsf{TAB}_v$. |

#### Witnesses
The relation $\mathcal{R}_{\mathsf{plonkish}}$ takes witnesses of the following form:

| Witness element | Description |
| ----------------- | -------- |
| $w$ | The witness matrix $w \mathrel{⦂} \mathbb{F}^{m \times n}$. |

Define $\vec{w}_j$ as the row vector $\big[\, w[i, j] : i \leftarrow 0 \text{..} m \,\big]$.

#### Definition of the relation
Given the above definitions, the relation $\mathcal{R}_{\mathsf{plonkish}}$ corresponds to a set of $\,(\!$ instance $\!,\,$ witness $\!)\,$ pairs
$$
\Big(x = \big(\mathbb{F}, t, \phi, n, m, \equiv, S, m_f, f, \big[\, (p_u, \mathsf{CUS}_{u}) \,\big]_u, \big[\, (L_v, \mathsf{TAB}_v, \big[\, q_{v,s} \,\big]_s, \mathsf{LOOK}_v) \,\big]_v\big),\, w \Big)
$$
such that:
$$
\begin{array}{ll|l}
w \mathrel{⦂} \mathbb{F}^{m \times n}, \ f \mathrel{⦂} \mathbb{F}^{m_f \times n} & & i \in [0,m_f), \ j \in [0,n) \Rightarrow w[i, j] = f[i, j] \\[0.3ex]
S \subseteq ([0,m) \times [0,n)) \times [0,t), \ \phi \mathrel{⦂} \mathbb{F}^t & & ((i,j),k) \in S \Rightarrow w[i, j] = \phi[k] \\[0.3ex]
\equiv\; \subseteq ([0,m) \times [0,n)) \times ([0,m) \times [0,n)) & & (i,j) \equiv (k,\ell) \Rightarrow w[i, j] = w[k, \ell] \\[0.3ex]
\mathsf{CUS}_u \subseteq [0,n), \ p_u \mathrel{⦂} \mathbb{F}^m \rightarrow \mathbb{F} & & j \in \mathsf{CUS}_u \Rightarrow p_u(\vec{w}_j) = 0 \\[0.3ex]
\mathsf{LOOK}_v \subseteq [0,n), \ q_{v,s} \mathrel{⦂} \mathbb{F}^m \rightarrow \mathbb{F}, \ \mathsf{TAB}_v \subseteq \mathbb{F}^{L_v} & & j \in \mathsf{LOOK}_v \Rightarrow \big[\, q_{v,s}(\vec{w}_j) : s \leftarrow 0 \text{..} L_v \,\big] \in \mathsf{TAB}_v
\end{array}
$$

### Layered arithmetic circuit (fan-in-two)

A layered arithmetic circuit of fan-in-two consists of a "wiring" and "nodes", and an ordering of layers such that any node in layer $i$ (where $i$ is not the input layer) consists of exactly two input wires from nodes in layer $i + 1$, along with a binary operation.

Therefore, the $j$th node from layer $i$, $\mathcal{L}_i[j]$, can be represented as $\mathcal{L}_{i+1}[l] \star \mathcal{L}_{i+1}[r]$ where $\star$ is the binary operation, and $l$ and $r$ are the indices of the "left" and "right" nodes wired to the $j$th node in $\mathcal{L}_i.$

#### Instances
The relation $\mathcal{R}_{\mathsf{LAC}}$ takes instances of the following form:

| Instance element | Description |
| ----------------- | -------- |
|$\mathbb{F}$ | A prime field. |
| $d$ | Number of layers, or depth. |
| $n$ | Number of nodes in the input layer. |
|$\textsf{add}_i$| An array of tuples $(z, x, y)$ such that the element found in layer $i+1$ at label $x$ added to the element found in layer $i+1$ at label $y$ is the value of the element in layer $i$ at label $z$. Must be provided for all layers $i$ except the input layer, layer $d + 1$. |
|$\textsf{mul}_i$| An array of tuples $(z, x, y)$ such that the element found in layer $i+1$ at label $x$ multiplied by the element found in layer $i+1$ at label $y$ is the value of the element in layer $i$ at label $z$. Must be provided for all layers $i$ except the input layer, layer $d + 1$. |
|$\vec{o}$| The values of the elements expected in layer $0$.

#### Witnesses
The relation $\mathcal{R}_{\mathsf{LAC}}$ takes witnesses of the following form:

| Witness element | Description |
| ----------------- | -------- |
| $\vec{w}$ | The witness vector $\vec{w} \mathrel{⦂} \mathbb{F}^{n}$, which constitutes of the values that populate the input layer. |

#### Definition of the Relation
Given the above definitions, the relation $\mathcal{R}_{\mathsf{LAC}}$ corresponds to a set of $\,(\!$instance $\!,\,$ witness $\!)\,$ pairs
$$
\Big(x = \big(\mathbb{F}, d, n, [\textsf{add}_i], [\textsf{mul}_i], \vec{o}),\, \vec{w} \Big)
$$
such that:

When taking the witness $\vec{w}$ is taken as input, and computing the layer-wise values for each layer $i$ using the $\textsf{add}_i$ and $\textsf{mul}_i$ wirings, at the output layer we have the result $\vec{o}$.

#### Example


The circuit above is a layered arithmetic circuit which consists of 4 layers (including an input and an output layer), with 6 input elements and 1 output element. It encodes the following relationship:
$$y = [(x_1 + x_2) \cdot (x_3 \cdot x_4)] + [(x_3 \cdot x_4) + (x_5 + x_6)].$$

## Polynomial IOPs
Contrary to classical proofs, a fundamental building block to most cryptographic proof-systems are interactive protocols (IPs), which involve two parties: a prover $\mathcal{P}$ and a verifier $\mathcal{V}$. $\mathcal{P}$ and $\mathcal{V}$ are able to interact with each other, typically in the form of $\mathcal{V}$ sending "challenges" to $\mathcal{P}$, and $\mathcal{P}$ sending messages to $\mathcal{V}$ in response to its challenges.

Before getting to PIOPs, it is useful to understand the role randomness can play in proof verification. If a proof is large, the verifier typically needs to read the entire proof in order to assess the validity of the prover's claim. However, in a probabilistically checkable proof (PCP), the verifier only needs to read a small portion of $\mathcal{P}$'s proof. The verifier only reads random parts of the proof--and because $\mathcal{P}$ was not aware of which parts of the proof $\mathcal{V}$ would be reading, $\mathcal{V}$ should be convinced with high probability of the truth of $\mathcal{P}$'s statement if it passes the verifier's checks.

It can then be seen that interactive protocols are useful when coupled with randomness in the form of PCPs--primarily in the verifier sending the prover random challenges during each round of interaction in exchange for a small probability that the verifier could not catch a cheating prover. Such protocols are called interactive oracle proofs (IOPs). Interactive oracle proofs assume that along with each of the prover's messages, $\mathcal{V}$ also has access to an oracle that it can query for "free" (in $O(1)$ time) to access parts of the prover's message. This also follows the form of PCP, in which proof succinctness and verifier efficiency comes from choosing to read only parts of the prover's message.

In a polynomial IOP, the prover's messages are in the form of a polynomial with degree lower than a given bound, and the verifier has access to an oracle in which it can query the polynomial at any point.

*Fig. 2: A $k$-round interactive oracle proof. In the $i$-th round: the verifier $V$ sends a message $m_i$ to the prover $P$; then, $P$ replies with a message $f_i$, which $V$ can query (via random access) in this and all later rounds. After the $k$ rounds of interaction, $V$ either accepts or rejects.*

### Sumcheck-based

The sumcheck protocol is a protocol in which the prover convinces the verifier that the sum over the boolean hypercube of $\ell$ dimensions (i.e., all the bit-strings from $0$ to $2^\ell$) of a polynomial $g$ over $\ell$ variables equals a claimed value $C$.

Naively, verifying the claim of a summation over $2^{\ell}$ terms would take time $O(2^{\ell})$ -- the verifier could compute the sum over the $2^{\ell}$ terms on its own and sum them up. However, the sumcheck protocol reduces the verifier work to $O(\ell)$ multiplications (evaluating and summing linear polynomials) and a single oracle query, and involves only $O(\ell)$ rounds of communication.

The protocol is as follows:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#ffffff"
    noteBkgColor: "#ffffff"
    noteBorderColor: "#ffffff"
    signalColor: "#909090"
    signalTextColor: "#808080"
---
sequenceDiagram
    participant Prover
    participant Verifier
    Note left of Prover: $$C = \sum\limits_{(x_1, \dots, x_\ell) \in \{0,1\}^\ell} g(x_1, \dots, x_\ell)$$
    Prover->>Verifier: $$C$$
    Note left of Prover: $$s_1(X_1) = \sum\limits_{(x_2, \dots, x_\ell) \in \{0,1\}^{\ell-1}} g(X_1, x_2, \dots, x_\ell)$$
    Prover->>Verifier: $$s_1(X_1)$$
    Note right of Verifier: $$s_1(0) + s_1(1) ?= C$$
    Verifier->>Prover: $$r_1$$
    Note left of Prover: $$s_2(X_2) = \sum\limits_{(x_3, \dots, x_\ell) \in \{0,1\}^{\ell-2}} g(r_1, X_2, x_3, \dots, x_\ell)$$
    Prover->>Verifier: $$s_2(X_2)$$
    Note right of Verifier: $$s_2(0) + s_2(1) ?= s_1(r_1)$$
    Prover->>Verifier: $$\cdots$$
    Verifier->>Prover: $$\cdots$$
    Verifier->>Prover: $$r_{\ell - 1}$$
    Note left of Prover: $$s_\ell(X_\ell) = g(r_1, \cdots, r_{\ell - 1}, X_\ell)$$
    Prover->>Verifier: $$s_\ell(X_\ell)$$
    Note right of Verifier: $$s_\ell(0) + s_\ell(1) ?= s_{\ell-1}(r_{\ell - 1})$$
    Note right of Verifier: $$r_\ell$$
    Note right of Verifier: $$s_\ell(r_\ell) ?= g(r_1, \cdots, r_\ell)$$

1. The prover sends over $C$, the claimed value of $\sum\limits_{(x_1, \dots, x_\ell) \in \{0,1\}^\ell} g(x_1, \dots, x_l)$, along with a claimed univariate polynomial $s_1(X_1) = \sum\limits_{(x_2, \dots, x_\ell) \in \{0,1\}^{\ell-1}} g(X_1, x_2, \dots, x_\ell)$. We can think of this polynomial as encoding the sum of $g$ over a slice of a hypercube at a particular coordinate $X_1.$
2. The verifier then checks that $s_1$ is consistent with the claimed $C$, by checking that $s_1(0) + s_1(1) = C$. The verifier then sends over a random challenge $r_1$ to zoom into.
3. The prover fixes $r_1$ as the first coordinate of polynomial $g$, and now sends over linear polynomial $s_2(X_2) = \sum\limits_{(x_3, \dots, x_\ell) \in \{0,1\}^{\ell-2}} g(r_1, X_2, x_3, \dots, x_\ell)$.
4. The verifier checks that $s_2$ is consistent with the claimed $s_1$, i.e. that $s_2(0) + s_2(1) = s_1(r_1)$. The verifier then sends over the next random challenge $r_2$ to zoom into.
$\dots$
2$\ell$-1. The prover has fixed verifier challenges $r_1, r_2, \dots, r_{\ell-1}$ as the first $\ell-1$ coordinates of $g$, and sends over linear polynomial $s_{\ell}(X_{\ell}) = g(r_1, \dots, r_{\ell-1}, X_{\ell})$.
$2\ell$. The verifier checks that $s_{\ell}$ is consistent with the claimed $s_{\ell-1}$, i.e. that $s_{\ell}(0) + s_{\ell}(1) = s_{\ell}(r_{\ell-1})$.
$2\ell + 1$. Finally, the verifier samples random challenge $r_{\ell}$ and checks that $s_{\ell}(r_{\ell}) = g(r_1, \dots, r_{\ell})$ where $g(r_1, \dots, r_{\ell})$ is obtained through oracle query to $g$.

Finally, the verifier samples a random challenge $r_{\ell}$ and checks that $s_{\ell}().

*Soundness*: At each step in time, a malicious prover $P^*$ can cheat if the random challenge at which the verifier decides to "zoom in" on their false polynomial $s_i^*$ agrees with the polynomials computed by an honest prover. Since these are linear polynomials, this event happens with probability at most $1/|F|$ for each round $i$. Thus, applying a union bound over rounds $i$, the probably of a verifier accepting a false proof is at most $l/|F|$.

#### Spartan
(This section was adapted from Section 4 of the Spartan paper[^spartan].)

The main idea of Spartan is that it reduces checking an R1CS relation (see [R1CS](#r1cs-vg)) to a sumcheck. We can think of the R1CS relation as a statement on each of $n$ rows, where $n$ is large (the size of the circuit $|F|$, equivalently the size of the full witness). To reduce this to checking a single statement, we construct a coefficient polynomial to take a random linear combination across the rows.

For a given R1CS instance $\mathbb{x} = (\mathbb{F}, A, B, C, \textsf{pub_input}, m, n)$, let $s = \lceil\log m\rceil$, define the functions:
- the matrices $A, B, C$ map from two $s$-bit (row, column) labels to a field element $\{0,1\}^s \times \{0,1\}^s \rightarrow \mathbb{F}$;
- given a purported witness $w$ to $\mathbb{x}$, let $Z = (\textsf{pub_input}, 1, w)$, mapping from an $s$-bit identifier to a field element $\{0, 1\}^s \rightarrow \mathbb{F}$.

The R1CS satisfiability problem can now be encoded as a zerocheck on the following function:
$$F(x) = \left(\sum_{y \in \{0,1\}^s} A(x,y)\cdot Z(y)\right) \cdot \left(\sum_{y \in \{0,1\}^s} B(x,y)\cdot Z(y)\right) - \sum_{y \in \{0,1\}^s} C(x,y)\cdot Z(y),$$
where $w$ is a satisfying witness if and only if $F(x) = 0$ on all $x \in \{0, 1\}^s$.

By encoding these functions as their multilinear extensions, we can use the sumcheck protocol to efficiently perform the zero-check:
$$\tilde{F}(x) = \left(\sum_{y \in \{0,1\}^s} \tilde{A}(x,y)\cdot \tilde{Z}(y)\right) \cdot \left(\sum_{y \in \{0,1\}^s} \tilde{B}(x,y)\cdot \tilde{Z}(y)\right) - \sum_{y \in \{0,1\}^s} \tilde{C}(x,y)\cdot \tilde{Z}(y).$$

To check that this holds on all $\tilde{F}(x) = 0$ on all $x$, we introduce another sumcheck

$$
Q(z) = \sum_{x \in \{0,1\}^s} \tilde{F}(x) \cdot \tilde{\textsf{eq}}(z, x),
$$

where $\tilde{\textsf{eq}}(z, x) = \prod_{i=1}^{s} \left(z_i \cdot x_i + (1 - z_i) \cdot (1 - x_i)\right).$ Notice that, for $z, x \in \{0, 1\}^s$, $\tilde{\textsf{eq}}(z, x) = 1$ when $z = x$, and $0$ otherwise: this means that $Q(z) = \tilde{F}(z)$ for all $z \in \{0, 1\}^s$,. In other words, $Q(\cdot)$ is a zero polynomial if and only if $\tilde{F}(\cdot)$ evaluates to $0$ at all points in the $s$-dimensional Boolean hypercube $z \in \{0, 1\}^s$. We can efficiently perform a zero-check on $Q(\cdot)$ by evaluating it at a random point $\zeta$:

$$
Q(\zeta) = \sum_{x \in \{0,1\}^s} \tilde{F}(x) \cdot \tilde{\textsf{eq}}(\zeta, x),
$$

and using the sumcheck protocol to check if $Q(\zeta) \overset{?}{=} 0.$

#### GKR

The GKR protocol[^gkr] is used in conjunction with a layered arithmetic circuit (AC) arithmetization. Here we show how the GKR protocol applies to proving the correct evaluation of a layered arithmetic circuit over $\mathbb{F} = GF(2)$ with fan-in 2, where all gates are either ADD or MULT.

The overall idea of the GKR protocol is that to prove the correct evaluation of the output gate, the prover will engage in a series of reductions, where each reduction reduces the claim in one layer of the circuit to a claim in the next layer up using the sumcheck protocol. Eventually, the claim will be reduced to a claim on the input layer of the circuit, which the verifier can verify by themselves given the circuit inputs. Note that GKR is not zero-knowledge.

Spelled out in more detail, suppose we have a layered arithmetic circuit of size $S$ gates and depth $D$, and the prover wishes to prove the correct evaluation of the. Let us index the gates of the circuit by elements $z \in H^m$, where $|H| \in \mathbb{F}$ such that $|H|^m = S$.

Now for each layer $i$ of the circuit and a gate $z$, we associate a polynomial $V_i: H^m \rightarrow \mathbb{F}$, where $V_i(z)$ is the value on the output wire. We can consider the low degree extension (LDE) $\widetilde{V_i}: \mathbb{F}^m \rightarrow \mathbb{F}$ (which we will need to run sumcheck). Thus, the prover needs to prove $\widetilde{V_0}(z_0) = 1$, where $z_0$ is the output gate of the layered AC.

At each layer $i$, we will reduce checking expressions of the form $V_i(r_i) = C$ to checking expressions of the form $V_{i+1}(r_{i+1})$, representing a layer up in our circuit. Eventually, this will look like checking claims $V_{d-1}(r_{d-1})$ at the input layer, which the verifier can check because of access to inputs.

Full protocol:
1. The prover sends the claimed evaluation $\widetilde{V_0}(z_0) = 1$, where $z_0$ is the index of the only output gate.
2. The prover expresses
$$\begin{align}
\widetilde{V_0}(z_0) = &\sum_{p \in H^m} (\chi_p(z_0) V_0(p)) \\
= \sum_{p \in H^m} \bigg[ \chi_p(z_0) &\sum_{w_1, w_2 \in H^m} \bigg(\widetilde{ADD}(p, w_1, w_2)(V_1(w_1) + V_1(w_2)) \\
& + \widetilde{MULT}(p, w_1, w_2)V_1(w_1)V_1(w_2) \bigg)\bigg]
\end{align}$$
where $\widetilde{ADD}(p, w_1, w_2): (\mathbb{F^m})^3 \rightarrow \{0,1\}$ is the unique LDE of the polynomial $ADD(p, w_1, w_2): (H^m)^3 \rightarrow \{0,1\}$ defined to equal $1$ whenever $p$ is an ADD gate and $w_1, w_2$ are the two input gates, and $0$ otherwise. We define $\widetilde{MULT}(p, w_1, w_2)$ similarly to equal $1$ whenever $p$ is a MULT gate and $w_1, w_2$ are the two input gates, and $0$ otherwise
3. In an effort to reduce the above equation to a sumcheck argument, the prover rewrites $\chi_p(z_0)$ as a low-degree polynomial in $p$. The prover defines a multilinear extension $\tilde{\beta}(p, z_0): (F^m)^2 \rightarrow \mathbb{F}$ of the function $\beta(p, z): (H^m)^2 \rightarrow \mathbb{F}$, where $\beta(p,z) = 1$ for all $z=p$ and $0$ otherwise. Now for any constant $z_0$, $\tilde{\beta}(p, z_0)$ is a low degree polyomial in $p$. Thus we can rewrite above equation as
$$
\begin{align}
V_0(z_0) = \sum_{p \in H^m} \bigg[ \widetilde{\beta}(p, z_0) &\sum_{w_1, w_2 \in H^m} \bigg(\widetilde{ADD}(p, w_1, w_2)(\widetilde{V_1}(w_1) + \widetilde{V_1}(w_2)) \\
& + \widetilde{MULT}(p, w_1, w_2)\widetilde{V_1}(w_1)\widetilde{V_1}(w_2) \bigg)\bigg] \\
= \sum_{p, w_1, w_2 \in H^m} \bigg[ \widetilde{\beta}(p, z_0) & \bigg(\widetilde{ADD}(p, w_1, w_2)(\widetilde{V_1}(w_1) + \widetilde{V_1}(w_2)) \\
& + \widetilde{MULT}(p, w_1, w_2)\widetilde{V_1}(w_1)\widetilde{V_1}(w_2) \bigg)\bigg] \\
\end{align}
$$
4. Now the prover and verifier can engage in a sumcheck protocol to show that $V_i(z_0) = \sum_{p, w_1, w_2 \in H^m} \widetilde{Q}(p, w_1, w_2)$, where $\widetilde{Q}$ is the low degree polynomial such that
$$
\begin{align}
\widetilde{Q}(p, w_1, w_2) = \bigg[ \widetilde{\beta}(p, z_0) \bigg(&\widetilde{ADD}(p, w_1, w_2)(\widetilde{V_1}(w_1) + \widetilde{V_1}(w_2))\\
&+ \widetilde{MULT}(p, w_1, w_2)\widetilde{V_1}(w_1)\widetilde{V_1}(w_2) \bigg)\bigg]
\end{align}
$$
This results in the prover making a claims of the form $V_1(r_{w_1}) = C_1$ and $V_1(r_{w_2}) = C_2$ for random challenges $r_{w_1}, r_{w_2} \in \mathbb{F}^m$, which is a statement about evaluations of $V_1$ representing layer $1$.
5. To prove these evaluations, we can once again decompose $\widetilde{V_1}(r_{w_1})$ and $\widetilde{V_1}(r_{w_1})$ each into a sum over $\widetilde{\beta}(p, r_{w_1}), \widetilde{ADD}(p, w_1, w_2), \widetilde{MULT}(p, w_1, w_2), V_2(w_1)$ and $V_2(w_2)$. Then the prover and verifier run another a sumcheck in parallel (on the same random challenges) to reduce the claim to claimed evaluations of $V_2$ representing layer $2$ of our circuit. **Note**: it is crucial here that these sumchecks are run in parallel on the same verifier randomness, so that we reduce the argument to checking $V_2$ at two random challenges as opposed to four (so there is no exponential blowup).
...

These reductions continue using one sumcheck for each layer $0, \dots, d-2$ of the arithmetic circuit until the all claims have been reduced to the evaluations of $V_{d-1}$ at random challenge points $r$. Finally, the verifier can check these evaluations themself using the Lagrange interpolation formula
$$\widetilde{V}_{d-1}(r) = \sum_{p \in H^m} V_{d-1}(p) \chi_p(r),$$ where for each gate $p = (p_1, p_2, \dots, p_m) \in H^m$, we have the explicit formula
$$\chi_p(x_1, \dots, x_m) = \prod_i \chi_{p_i}(x_i) = \prod_i \prod_{p_i' \in H, p_i' \neq p_i} \frac{(x_i - p_i')}{h'-h}.$$

The reader can verify that $\chi_{p_i}(x_i) = 1$ if $x_i = p_i$ and $0$ otherwise, and that similarly $\chi_p(x_1, \dots, x_m) = 1$ if $(x_1, \dots, x_m) = (p_1, \dots, p_m)$, and finally that $\chi$ is itself a multilinear extension of these points given the closed form.

### PlonK [JX]

Univariate, multivariate

HyperPlonk is known as the multivariate version of. The main

### Ligero [JX]

###

## Polynomial Commitment Schemes
A polynomial commitment scheme (PCS) is a two-phase protocol where a prover $P$ convinces a verifier $V$ of an opening claim[^zk-jargon-decoder]:
$$C = \textsf{PCS.Commit}(p) \land p(x) = y.$$

In the commitment phase, $P$ generates a commitment to some polynomial $C = p(X)$. The type of this commitment object varies depending on the PCS being used.

The main properties of a commitment scheme are that they must be *hiding* and *binding*. The hiding property ensures privacy of any data inside our SNARK that is now represented by polynomials. The binding property ensures that a prover cannot "cheat" a proof by changing their underlying polynomial in response to the verifier's challenge.

Both of these properties enable a polynomial commitment scheme to compile an IOP into a non-interactive and zero-knowledge scheme.

Note: Using a hiding PCS is not always sufficient to guarantee zero-knowledge, which formally requires a simulator to be able to produce an indistinguishable distribution without access to the witness. For example, the PLONK protocol opens some of the polynomial commitments at random challenge points -- these are not indistinguishable from a uniformly random (simulatable) distribution unless we add random multiples of a vanishing polynomial to the original polynomial that we commit to (and ensure challenges lie outside the hypercube).

The evaluation phase is often an interactive protocol between $P$ and $V$, where:
- $V$ chooses a point $x$ at which it wants to learn the evaluation of $p$;
- $P$ produces a claimed evaluation $y$ and an “opening proof”; and
- finally, $P$ and $V$ use the commitment $C$, claimed evaluation $y$ and the opening proof as inputs to a (sometimes interactive) protocol to convince $V$ of the opening claim.

### Hash-based

#### Ligero

#### FRI/STIR [YT]

#### WHIR

#### Brakedown [JX]

This section is based off of the Brakedown paper[^brakedown].

There are two main key advantages to the Brakedown polynomial commitment scheme:
1. It works *over arbitrary finite fields* of any size (not necessarily prime fields). This is particularly beneficial, as representing witnesses in terms of field elements of a prime order is a high-overhead task at a hardware level.
2. When instantiated with a custom linear-time code, it yields a linear-time polynomial commitment scheme (as opposed to PLONK for example, which involves using an FFT to convert from evaluation form to coefficient form). This allows for a linear-time prover, as evaluating polynomial commitments is often the bottleneck for prover efficiency.

Brakedown specifically provides a commitment scheme for multilinear polynomials, which are determined by their evaluations on the boolean hypercube. Thus, it can be used in conjunction with, say, the Spartan proving system (which uses R1CS and the sumcheck polynomial IOP). In particular, Brakedown PCS will allow the opening of the multilinear extension polynomials $\widetilde{A}, \widetilde{B}, \widetilde{C}$ above at the final challenge $(r_1, r_2, \dots, r_s) \in \mathbb{F}^s$.

Suppose we have some $m$-variate multilinear polynomial $w$ that we would like to commit to. Here are the steps to committing to a $m$-variate multilinear extension $w$, which is defined by the evaluations on the $m$-dimensional hypercube.

1. The prover rearranges the evaluations on the hypercube $\{0,1\}^m$ into a square $[M] \times [M]$ where $M = 2^{m/2}$. Let $U = \{u_i\}_{i=1}^{M} \in (\mathbb{F}^M)^M$ denote the matrix representing these evaluations on the square, where ${u_i}$ is the $M$-vector of evaluations on row $i$.
2. The prover encodes each row of this matrix using a linear code $C: \mathbb{F}^M \rightarrow \mathbb{F}^N$ with constant rate (e.g. Reed Solomon) to get a new matrix $E \in (\mathbb{F}^N)^M$ of $m$ codewords. Then the prover compute a Merkle commitment of $E$.
3. To test that the commitment is indeed of a multilinear extension polynomial -- prover sends $E$ as well as a requested random linear combination of rows. The verifier checks this random linear combination of rows of $E$ is indeed close to the codespace, and also that $E$ matches with the Merkle commitment.
* Note that this test suffices by a property of codes known as *proximity testing*, where if any row is far away from the codespace, then a random linear combination will also likely be far away from the codespace.
* In the instance of Reed-Solomon codes, the verifier checks that it is a low degree polynomial using a ["Low Degree Test"](https://sites.math.rutgers.edu/~sk1233/courses/topics-S17/lec10.pdf)
4. To evaluate the multilinear extension at random challenge point $(r_1, \dots, r_n)$, recall that we can always express the evaluation of a multilinear extension $w(r_1, \dots, r_n) = \langle q_1 \otimes q_2, U \rangle$ for some "linear combinations" $q_1$ and $q_2$. Thus, the prover sends over vector $u' = \sum_{i=1}^m r'_i u_i$, defined to be the desired linear combination of the row vectors $u_i$ given by challenge $(r_1, \dots, r_n)$. Then the verifier evaluates $w(r_1, \dots, r_n)$ as the linear combination of values in vector $u_i$ given by challenge. Finally, the verifier checks consistency with the encoding $E$ by checking that $Enc(u') = \sum_{i=1}^m r'_i E_i = \sum_{i=1}^m r'_i Enc(u_i)$.

Note: Brakedown itself as a PCS is not hiding of the witness. As seen above, to open the polynomial at a point we must provide public random linear combinations of private evaluations on the square. However, Orion uses Virgo to wrap Brakedown SNARK proofs into zero-knowledge.

Brakedown itself is linear-time in the number of evaluation points (equiv., the number of coefficients) of our multilinear polynomial. In Spartan, we commit to $2\log(n)$-variate polynomials. Applying Brakedown directly would yield an $O(n^2)$ time commitment scheme, where $n$ is the size of our witness and public I/Os, which is superlinear in the size of our circuit. However, the polynomials we commit to (representing $A, B, C$ R1CS matrices) are sparse, meaning only $O(n)$ entries are nonzero. The Brakedown and Spartan papers detail how to go from dense polynomial commitments to sparse polynomial commitments using a "memory-checking" technique, which would bring the commitment time (and thus proving time) down to $O(n)$.

#### Orion

### Lattice-based
#### Greyhound

## Security Assumptions

## References
[^plonk]: PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge https://eprint.iacr.org/2019/953.pdf
[^zkproof-standards]: ZKProof Standards: Plonkish Constraint System Working Group https://github.com/zkpstandard/wg-plonkish/
[^zk-jargon-decoder]: ZK Jargon Decoder https://zkjargon.github.io/definitions/polynomial_commitment.html
[^brakedown]: Brakedown: Linear-time and field-agnostic SNARKs for R1CS https://eprint.iacr.org/2021/1043.pdf
[^spartan]: Setty, S. (2020, August). Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In Annual International Cryptology Conference (pp. 704-737). Cham: Springer International Publishing.
[^gkr]: https://65610.csail.mit.edu/2024/lec/l12-gkr.pdf