# Folding for Arbitrary Polynomial Custom Gates and Lookups

[Yan X Zhang](https://twitter.com/krzhang) and [Aard Vark](https://twitter.com/aard_k_vark)

(with thanks to [Yi Sun](https://twitter.com/theyisun), [Jonathan Wang](https://twitter.com/jonathanpwang), [Lev Soukhanov](https://twitter.com/levs57), [Nicolas Mohnblatt](https://github.com/nmohnblatt))

:::warning
This hasn't been checked. Use at your own risk.
:::

[Nova](https://eprint.iacr.org/2021/370) introduced a _folding scheme_ for R1CS circuits. A _folding scheme_ is a way to aggregate multiple satisfying _witnesses_ to a constraint system (in Nova's case, an R1CS circuit), so that multiple verifications can be combined into one. Under the hood, folding works by taking a random linear combination of the witnesses; the R1CS equations need to be generalized to "relaxed R1CS" constraints, which are stable under linear combination.

Our goal here is to show how Nova-style folding can be generalized to any polynomial "custom gate". The idea is sketched in [Sangria](https://geometry.xyz/notebook/sangria-a-folding-scheme-for-plonk) in Section 3.3. In addition, we provide a useful special case that has not yet been done: folding lookups. (We also have a separate writeup of folding lookups at [Origami](https://hackmd.io/Nuwf9Q6yRtSVK7ldKgo9kw).)

## 1. Preliminaries

### A bit of algebra

We'll start with a general algebraic identity.

:::success
Let $p(\mathbf{x})$ be a homogenous polynomial of degree $d$ in $n$ variables (where $\mathbf{x} = (x_1, x_2 \ldots, x_n)$).

Then there are $d-1$ polynomials $\Delta^1 p, \Delta^2 p, \ldots, \Delta^{n-1} p$ of degree at most $d$ in $2n$ variables such that
$$ p(\mathbf{x} + r \mathbf{y}) = p(\mathbf{x}) + r^d p(\mathbf{y}) + \sum_{k=1}^{d-1} r^k \Delta^k p (\mathbf{x}, \mathbf{y}). $$
:::

The construction is simple. Write $p(\mathbf{x})$ as a linear combination of monomials $x_{i_1} x_{i_2} \cdots x_{i_d}$:
$$p(\mathbf{x}) = \sum a_{i_1, i_2, \ldots, i_d} x_{i_1} x_{i_2} \cdots x_{i_d}.$$
(It's OK if some of the indices are equal to each other. For example, the monomial $x_1^2$ has $i_1 = i_2 = 1$. Also, this expression is not unique, and that's OK too. For example, $x_1 x_2$ could be rewritten as $x_2 x_1$ or even $2x_1 x_2 - x_2 x_1$.)

The polynomial $\Delta^k p(\mathbf{x})$ can be computed as follows: for any monomial, $\Delta^k(x_{i_1} x_{i_2} \cdots x_{i_d})$ is the sum of the $\binom{d}{k}$ terms obtained by replacing $k$ of the $d$ variables $x_{i_j}$ with $y_{i_j}$. For example:
\begin{align}
\Delta^1 (x_1 x_2) & = x_1 y_2 + y_1 x_2 \\
\Delta^2 (x_1 x_2 x_3) & = x_1 y_2 y_3 + y_1 x_2 y_3 + y_1 y_2 x_3 \\
\Delta^1 (x_1^3) & = \Delta^1 (x_1 x_1 x_1) = x_1 y_1 y_1 + y_1 x_1 y_1 + y_1 y_1 x_1. \\
\end{align}

What if $p$ is not homogenous? To match the notation in Nova, we'll _homogenize_ by introducing an extra variable.

:::success
For any polynomial $p(\mathbf{x})$ of degree at most $d$ in $n$ variables, we'll define a homogenous polynomial $p^{homog}(\mathbf{x}, u)$ of degree $d$ in $n+1$ variables, as follows.

Write $$p(\mathbf{x}) = \sum_{d' = 0}^{d} p_{d'}(\mathbf{x}), $$ where $p_{d'}(\mathbf{x})$ is homogenous of degree $d'$. In other words, $p_{d'}(\mathbf{x})$ is just the sum of all the degree-$d'$ terms in $p(\mathbf{x})$. Then define $$p^{homog}(\mathbf{x}, u) = \sum_{d' = 0}^{d} u^{d - d'} p_{d'}(\mathbf{x}).$$
:::

In other words, to make $p^{homog}(\mathbf{x}, u)$ from $p(\mathbf{x})$, just multiply each term of $p(\mathbf{x})$ by whatever power of $u$ is needed to make the degree come out to $d$.

For future reference, it's worth noting that
$$p(\mathbf{x}) = p^{homog}(\mathbf{x}, 1).$$

:::info
TODO: an example that reformulates Sangria in this notation.
:::

### Commitments

We'll assume a hiding, binding, additively homomorphic commitment scheme $\mathrm{Com}(pp, x, \rho)$. We'll denote a commitment to a vector $V$ by $\overline{V} = \mathrm{Com}(pp, V, \rho)$. For clarity of notation, sometimes we will write $\mathrm{Com}(V) := \mathrm{Com}(pp, V, \rho)$ when the arguments are obvious from context.

## 2. The Protocol

We'll describe a folding scheme for [AIRs](https://hackmd.io/@aztec-network/plonk-arithmetiization-air), a form of polynomial constraint system. An _AIR_ $P$ is a collection of polynomials $f_1, \ldots, f_\ell$ in $2w$ variables over a finite field $\mathbb{F}$. An _execution trace_ $T$ for $P$ is an array of elements $T_{r, c}$ of $\mathbb{F}$, with $n$ rows, each of width $w$. In order for the trace $T$ to be _valid_, it is required that, when we substitute into any $f_i$ the $2w$ elements of any two consecutive rows of $T$, the result equals zero:
$$ f_i(T_{j, 1}, T_{j, 2}, \ldots, T_{j, w}, T_{j+1, 1}, T_{j+1, 2}, \ldots, T_{j+1, w}) = 0. $$

The folding scheme we're about to describe works for more general polynomial constraint systems as well. All that matters is that a valid trace be defined by some fixed collection of polynomial equations in the entries. It is not necessary that each polynomial only involve entries from two consecutive rows. Nonetheless, we'll continue working within the AIR framework.

To start, we introduce the main object, a _relaxed AIR_, in the style of Sangria. The main idea of a relaxed AIR, like the relaxed R1CS analogue from Nova, is a polynomial constraint that involves a "slack term."

### Relaxed AIR

We'll write $f_i(T)$ for the length-$n$ vector whose $j$-th entry is $f_i$ applied to rows $j$ and $j+1$ of $T$:
$$ f_i(T_{j, 1}, T_{j, 2}, \ldots, T_{j, w}, T_{j+1, 1}, T_{j+1, 2}, \ldots, T_{j+1, w}). $$
(Rows wrap around, so row $n$ is the same as row $0$.)

A _relaxed AIR instance_ is satisfied by a trace $T$ (i.e. an $n$-by-$w$ array of elements of $\mathbb{F}$), vectors $E_1, E_2, \ldots, E_{\ell} \in \mathbb{F}^n$, and a scalar $u \in \mathbb{F}$, if
$$ f_i^{homog}(T_{j, 1}, T_{j, 2}, \ldots, T_{j, w}, T_{j+1, 1}, T_{j+1, 2}, \ldots, T_{j+1, w}, u) = (E_i)_j, $$ for each $i$ and $j$.

We'll write $f_i^{homog}(T, u)$ for the vector whose $j$-th entry is
$$ f_i^{homog}(T_{j, 1}, T_{j, 2}, \ldots, T_{j, w}, T_{j+1, 1}, T_{j+1, 2}, \ldots, T_{j+1, w}, u). $$

Since $f_i^{homog}$ is a polynomial in $2w+1$ variables, the construction at the top of the page defines polynomials $\Delta^k f_i^{homog}$ in $2(2w+1)$ variables. We'll write $\Delta^k f_i^{homog} (T^1, u^1; T^2, u^2)$ for the vector whose $j$-th entry is
$$ \Delta^k f_i^{homog} (T^1_{j, 1}, \ldots, T^1_{j+1, w}, u^1, T^2_{j, 1}, \ldots, T^2_{j+1, w}, u^2). $$

A _relaxed AIR instance_ $(E_i, u)$ consists of slack vectors $E_1, \ldots, E_{\ell} \in \mathbb{F}^n$ and a scalar $u \in \mathbb{F}$. A _witness_ for such an instance is an $n$-by-$w$ matrix $T$ of field elements such that $$f_i^{homog}(T, u) = E_i,$$ for all $i$.

Clearly, any AIR instance can be promoted to a relaxed AIR instance by setting $u = 1$ and $E = 0$. The main idea in folding AIR instances is that by converting them to relaxed AIR instances, the computations can be more easily combined.

### Committed relaxed AIR

A _committed relaxed AIR instance_ $(f_i, \rho, \overline{E_i}, u, \overline{T})$ consists of polynomials $f_1, \ldots, f_{\ell}$, randomness $\rho$ (to be used by the commitment scheme) a commitment to a _slack vector_ $E = (E_1, \ldots, E_{\ell})$, a scalar $u$, and a commitment $\overline{T}$ to an $n$-by-$w$ matrix of scalars. A _witness_ to the committed relaxed AIR instance $(f_i, \overline{E_i}, \overline{T})$ is a tuple $(E, T, \rho)$ of
- a slack vector $E$ and
- an $n$-by-$w$ matrix $T$,

such that $\overline{T} = \operatorname{Com}(pp, T, \rho)$, $\overline{E} = \operatorname{Com}(pp, E, \rho)$, and $f_i^{homog}(T, u) = E_i$.

### The Folding Scheme

We'll describe a folding scheme for relaxed AIR instances. Suppose a prover and a verifier have an AIR $P$, i.e. they both know the collection of polynomials $f_i$. The prover is given two relaxed AIR instances $(T^1, E^1, u^1)$ and $(T^2, E^2, u^2)$. The verifier knows only the scalars $u^1$ and $u^2$.

Let $d_i$ be the degree of the polynomial $f_i$, and let $\Delta^k f_i^{homog}$ be as defined above.

The prover $\mathcal{P}$ and the verifier $\mathcal{V}$ carry out the following protocol.

:::success

**Protocol 1**

1. $\mathcal{P}$ computes commitments $\overline{X}$ for $X \in \{T^1, T^2, E_i^1, E_i^2\}$ and their openings $\rho_X$ (meaning that for all $X$, $\overline{X} = \operatorname{Com}(pp, X, \rho_X)$ holds) and sends them to $\mathcal{V}$.

2. For each constraint polynomial $f_i$, and each degree $1 \leq k \leq d_i - 1$, $\mathcal{P}$ also computes the _cross term_
$$ B_{i, k} = \Delta^k f_i^{homog} (T^1, u^1; T^2, u^2) $$ (a vector of length $n$). $\mathcal{P}$ computes commitments and openings for $\overline{B_{i, k}}$ and sends them to $\mathcal{V}$.

3. $\mathcal{V}$ samples a random _folding challenge_ $r \in \mathbb{F}$, and sends $r$ to $\mathcal{P}$.

4. $\mathcal{P}$ computes $$T = T^1 + r T^2$$ and, for each $i$, $$E_i = E^1_i + r^{d_i} E^2_i + \sum_{k=1}^{d_i-1} r^k B_{i, k}.$$ These values $T$ and $E_i$ give a _folded relaxed AIR witness_.

5. Both $\mathcal{P}$ and $\mathcal{V}$ compute $$u = u^1 + r u^2,$$ $$\overline{T} = \overline{T^1} + r \overline{T^2},$$ and, for each $i$, $$\overline{E_i^1} + r^{d_i} \overline{E_i^2} + \sum_{k=1}^{d_i-1} r^k \overline{B_{i, k}}. $$
:::

Like Nova, this folding process can be iterated. Steps 2-5 allow two committed relaxed AIR instances to be folded into one, at the cost of sending just $4 + \sum_{i=1}^{\ell} d_1-1$ commitments to the verifier. One can iterate the procedure to fold an arbitrary number of committed relaxed AIR instances together, one by one. At the end, the prover only has to convince the verifier that the final $(E, T)$ is a witness to the folded instance.

## 3. Application: Lookups

In [Origami](https://hackmd.io/@aardvark/rkHqa3NZ2), we apply our procedure to Halo2 lookup checks.

<!---
### Brief Review of Halo2 Lookups
First, we recall the setup:

1. As usual, we'll work with a prover $\mathcal{P}$ and a verifier $\mathcal{V}$. $\mathcal{P}$ has a series of $N$ lookup arguments to make, and wants to fold them together so as to be able to convince $\mathcal{V}$ of their correctness with $1$ argument instead of $N$.
2. Suppose $A^1, \ldots, A^N$ and $S^1, \ldots, S^N$ are vectors representing $N$ lookup arguments. Let's call their entries $(A^i)_j$ and $(S^i)_j$. We want to show that, for every $i$ and $j$, there exists $k$, such that $(A^i)_j = (S^i)_k$. In other words, we want to "look up" $A^1$ in $S^1$, $A^2$ in $S^2$, and so forth.
4. The way this is done is by $\mathcal{P}$ constructing permutations encoding auxiliary vectors $A_p$ and $S_p$ and (in response to two random scalars $\beta$ and $\gamma$ sent by the verifier) two "grand product" polynomials / vectors $Z$ and $W$. It then turns out the lookup can be confirmed by polynomial constraints on $A, S, A_p, S_p, Z, W, \beta$, and $\gamma$.

Under the hood, a vector (for example, $(A_1, \ldots, A_n)$) is going to be encoded as a polynomial $A(X)$, such that the values $A_i$ are encoded as the values of $A(X)$ at certain roots of unity. We won't discuss this further.

We now look at our constraint polynomials in depth. The following are the $7$ constraint polynomials corresponding to $f_i$:

1. $(1 - Q^{blind} - Q^{last}) \cdot \left ( Z[-1] (A_p + \beta) - Z (A + \beta) \right ) = 0$
2. $(1 - Q^{blind} - Q^{last}) \cdot \left ( W[-1] (S_p + \gamma) - W (S + \gamma) \right ) = 0$
6. $Q^{last} \cdot (Z^2 - Z) = 0$
7. $Q^{last} \cdot (W^2 - W) = 0$.
3. $Q^0 \cdot (A_p - S_p) = 0$
4. $Q^0 \cdot (Z - 1) = 0$
5. $Q^0 \cdot (W - 1) = 0$,

where we have the constant and public vectors

- $Q^0$: $q^0_0 = 1$ and $q^0_i = 1$ for all $i \neq 0$. (In the Halo2 writeup, this $Q^0$ is denoted $\ell_0$ and called a _Lagrange basis polynomial_ -- which of course is what $Q^0$ becomes when you encode a column as a polynomial.)
- $Q^{blind}$: $q^{blind}_i = 0$ for $n-t \leq i \leq n-1$, and $1$ otherwise (i.e. $Q^{blind}$ selects the last $t$ rows).
- $Q^{last}$: $q^{last}_i = 1$ for $i = n-t-1$, and $0$ otherwise (i.e. $Q^{last}$ selects the $(n-t-1)$-st row, the last row before the "blind" rows).
- Here $t=2$; the role of $Q^{blind}$ and $Q^{last}$ is to allow zero knowledge. We won't discuss this here.

Each capital variable above corresponds to $n$ polynomials of the same form, with shifted indices. As an example, let's consider the third equation $f_3(Z) = Z^2 - Z.$ Since $Z$ is a vector, this is shorthand for $n$ constraints of the form $f_{3, i}(Z) = Z_i^2 - Z_i = 0$ for each $i$. In this notiation, $Z_1[-1]$ means that the individual equations refer to the previous $j$. That is, when we unpack equation $f_{i, j}$, instead of substituting $Z_{1, j}$, we substitute $Z_{1, j-1}$.

Now, when we do relaxed versions of the equations, we obtain the following relaxed analgoues:
1. $(1 - Q^{blind} - Q^{last})\left ( Z[-1] \cdot (A_p + \beta) - Z \cdot (A + \beta) \right ) = E_1$
2. $(1 - Q^{blind} - Q^{last})\left ( W[-1] \cdot (S_p + \gamma) - W \cdot (S + \gamma) \right ) = E_2$
6. $Q^{last} (Z^2 - u Z) = E_3$
7. $Q^{last} (W^2 - u W) = E_4$
3. $Q^0 (A_p - S_p) = 0$
4. $Q^0 (Z - u) = 0$
5. $Q^0 (W - u) = 0$.

Continuing our example with $f_3$, $f_{3, homog}(Z, u) = Z^2 - uZ.$
Note that it is quadratic, so $d = 2$. This means we will have $d-1 = 1$ cross term, which is $B_{3,1}$. We compute

:::danger
Note to the reader: for the below calculation and the remainder of this subsection, $Z_1$ and $Z_2$ are different vectors, not subscripts of a vector. We do this because using superscripts (which would be consistent with the rest of our work to mean different objects to be folded together) would clash with the interpretation of taking powers. In other contexts we would consistently use $Z^1$ and $Z^2$ instead.
:::

$\begin{align}
f_{3, homog}(Z_1 + rZ_2, u_1 + r u_2) & = (Z_1 + rZ_2)^2 - (u_1 + ru_2) (Z_1 + rZ_2) \\
& = (Z_1^2 + 2r Z_1 Z_2 + r^2Z_2^2) - u_1Z_1 - ru_1Z_2 - ru_2Z_1 - r^2 u_2 Z_2 \\
& = (Z_1^2 - u_1Z_1) + r^2(Z_2^2 - u_2Z_2) + r(2Z_1 Z_2 - u_1Z_2 - u_2Z_1) \\
& = f_{3, homog}(Z_1) + r^2 f_{3, homog}(Z_2) + r B_{3, 1}(Z_1, u_1, Z_2, u_2),
\end{align}$

so we found that $B_{3,1}(Z_1, u_1, Z_2, u_2) = Q^{last} \cdot (2Z_1Z_2 - u_1 Z_2 - u_2 Z_1)$. (Since we ignored the constant factor $Q^{last}$, we should multiply it back now).

Again, recall that our capital letters are vectors, not numbers -- so we have $n$ instances of the equation
$$ B_{3, 1, j}(Z_1, u_1, Z_2, u_2) = Q^{last}_j \cdot (2Z_{1, j}, Z_{2, j} - u_1 Z_{2, j} - u_2 Z_{1,j}),$$
one for each $j$, where e.g. $Z_{2, j}$ is the $j$-th element of the vectors $Z_2$.

Similarly, we can obtain the other cross terms:
- $B_{1,1} = (1 - Q^{blind} - Q^{last}) \cdot \left (Z_1[-1] (A_2' + \beta_2) + Z_2[-1] (A_1' + \beta_1) - Z_1 (A_2 + \beta_2) - Z_2 (A_1 + \beta_1) \right )$
- $B_{2,1} = (1 - Q^{blind} - Q^{last}) \cdot \left ( W_1[-1] (S_2' + \gamma_2) + W_2[-1] (S_1' + \gamma_1) - W_1 (S_2 + \gamma_2) - W_2 (S_1 + \gamma_1) \right )$
- $B_{3,1} = Q^{last} \cdot (2 Z_1 Z_2 - u_1 Z_2 - u_2 Z_1$),
- $B_{4,1} = Q^{last} \cdot (2 W_1 W_2 - u_1 W_2 - u_2 W_1$).

### Details of the Protocol (Halo2 lookups)

In this section, we take Protocol 1 and show how it specializes to the particular case of Halo2 lookups. We first look at what happens for a single instance of the folding and then mention some nuances for folding in $N$ steps. The "single folding" protocol following Protocol 1 follows:

1. **$\mathcal{V}$ sends to $\mathcal{P}$ random challenges $\rho_X$ (where $X \in \{T^1, T^2, E_i^1, E_i^2\}$), for commitments. $\mathcal{P}$ computes commitments $\overline{T^1}, \overline{T^2}, \overline{E_i^1}, \overline{E_i^2}$, where for all $X$, $\overline{X} = \operatorname{Com}(pp, X, \rho_X)$, and sends them to $\mathcal{V}$.**
- What is our $T$? Recall that $\mathcal{P}$ takes vectors $A^1, A^2, S^1, S^2$ as input and then computes, for each $i \in \{1, 2\}$, permutations $A_p^i$ and $S_p^i$ of $A^i$ and $S^i$, respectively, such that each $(A_p^i)_j$ is either equal to $(A_p^i)_{j-1}$ or $(S_p^i)_j$. The prover $\mathcal{P}$ is given scalars $\beta_i, \gamma_i$, which $\mathcal{P}$ uses to compute grand products $Z^i$ and $W^i$. We define $T^i$ to be the concatenation of $(\beta_i, \gamma_i, A^i, S^i, A_p^i, S_p^i, Z^i, W^i)$.
- For clarity, instead of writing "$T$" explicitly, we take it to be understood that if we write e.g. $Z$, we are looking at the $Z$ "part" of $T$ in our concatenation. Equivalently, instead of commiting $T^i$ as a single unit, we can also change the protocol so that $\mathcal{P}$ sends to $\mathcal{V}$ commitments $\overline{\beta_i}, \overline{\gamma_i}, \overline{A^i}, \overline{S^i}, \overline{A^i_p}$, etc.
- In fact, since $\beta_i$ and $\gamma_i$ are public scalars, there is no need to send the commitments $\overline{\beta_i}$ or $\overline{\gamma_i}$. (we can think of them as committing themselves)
- As seen in the previous section, $f_5$ through $f_7$ are linear and thus accumulate no slack terms (equivalently, $E_5 = E_6 = E_7 = 0$), and $f_1$ through $f_4$ correspond to error terms $E_1, E_2, E_3, E_4$ respectively.

2. **For each constraint polynomial $f_i$, and each degree $1 \leq k \leq d_i - 1$, $\mathcal{P}$ also computes the _cross term_ $B_{i, k} = \Delta^k f_i^{homog} (T^1, u^1; T^2, u^2)$ (a vector of length $n$). $\mathcal{V}$ sends to $\mathcal{P}$ a random commitment challenge $\rho_{B_{i, k}}$, and $\mathcal{P}$ sends back a commitment $\overline{B_{i, k}}$ to $\mathcal{V}$.**
- Again, $f_5$ through $f_7$ are linear and have no cross terms. The first $4$ are all quadratic so they have exactly one cross term each, of the form $B_{k, 1}$, as we just computed them.

3. **$\mathcal{V}$ samples a random _folding challenge_ $r \in \mathbb{F}$, and sends $r$ to $\mathcal{P}$.**
- Exactly as stated.

4. **$\mathcal{P}$ computes $T = T^1 + r T^2$ and, for each $i$, $E_i = E^1_i + r^{d_i} E^2_i + \sum_{k=1}^{d_i-1} r^k B_{i, k}.$ These values $T$ and $E_i$ give a _folded relaxed AIR witness_.**
- Since our $T$ is a concatenation, the $T = T^1 + rT^2$ computation translates to
- $\beta = \beta^1 + r \beta^2$
- $\gamma = \gamma^1 + r \gamma^2$
- $A = A^1 + rA^2$
- $S = S^1 + rS^2$
- $A_p = A^1_p + rA^2_p$
- $S_p = S^1_p + rS^2_p$
- $Z = Z^1 + rZ^2$
- $W = W^1 + rW^2$.
- Finally, we fold the cross-terms. For each $i \in [4]$, they take the same form $E_i = E^1_i + r^2 E^2_i + r \cdot B_{i, 1}$.

5. **Both $\mathcal{P}$ and $\mathcal{V}$ compute $u = u^1 + r u^2,$ $\overline{T} = \overline{T^1} + r \overline{T^2},$ and, for each $i$, $\overline{E_i^1} + r^{d_i} \overline{E_i^2} + \sum_{k=1}^{d_i-1} r^k \overline{B_{i, k}}.$**
- Exactly as stated. Again, for us it is equivalent to think of $T$'s as "decomposed" into the individual pieces, and the $E$ sums always have only one term for $k=1$ on the summartion side since all the $d_i$'s ($i \in [4]$) are equal to $2$.

The above encodes a single step. We need some overhead for the other variables as well. The entire protocol to fold $N$ entries is the following:
1. To initialize folding, $\mathcal{P}$ creates a "cumulative lookup instance" $I_{cml}$ where $u, \beta, \gamma, \ldots, E$ are all equal to zero.
2. When we fold in a new lookup instance $(\beta^i, \gamma^i, A^i, S^i, A^i_p, S^i_p, Z^i, W^i)$, we construct a *relaxed* lookup instance $I^i = (u^i, \beta^i, \gamma^i, A^i, S^i, A^i_p, S^i_p, Z^i, W^i, E_1^i, E_2^i, E_3^i, E_4^i),$ by defining
- $u^i = 1$,
- $E^1_i = E^2_i = E^3_i = E^4_i = 0$.
3. Using the current $I_{cml}$ as $T^1$ and the new relaxed instance $I^i$ as $T^2$, we peform the $5$ steps in our protocol as before. However, during each step, we need a new $r = r^i$ for our "folding randomness".

After $N$ steps, the folding is complete. All that remains is for $\mathcal{P}$ to convince $\mathcal{V}$ that the final folded tuple $I_{cml}$ is a legitimate committed relaxed lookup instance, which is done as in the usual Halo2.
--->
:::warning
Technically speaking, this is not an exact special case of the protocol since $\beta$ and $\gamma$ play the role of verifier-supplied randomness that does not fit in the framework. Instead, lookups are a special case of a slight generalization of Protocol 1 that includes verifier randomness.
:::

## Appendix

### A.1 Knowledge Soundness

Here we'll argue that the folding procedure satisfies knowledge soundness. In other words, a prover can't convince a verifier to accept a proof (with more than negligible probability) unless the prover itself knows witnesses $(E^1, T^1)$ and $(E^2, T^2)$.

We'll prove this by a "rewinding" argument. Imagine an "extractor" that is allowed to interact with the prover by rewinding it to a previous state. In practice, the extractor will feed the prover different random challenges $r$ and see what response it gives to each.

Let $d$ be the largest of the $d_i$'s, so that all the constraint polynomials $f_i$ have degree at most $d$. Suppose we are given two committed relaxed AIR instances $(f_i, \overline{E^1_i}, u^1, \overline{T^1})$ and $(f_i, \overline{E^2_i}, u^2, \overline{T^2})$ (for the same AIR $P = (f_1, \ldots, f_{\ell})$). We are also given $d+1$ transcripts of the prover-verifier interaction, with $d+1$ different values of $r$, say $r_{(1)}, \ldots, r_{(d+1)}$.

Each transcript contains the same commitments $\overline{B_{i, k}}$. Furthermore, each transcript gives witnesses $E(r_{(j)})$, $T(r_{(j)})$, and $$u(r_{(j)}) = u^1 + r_{(j)} u^2,$$ that satisfy the relaxed AIR condition:
$$ f_i^{homog}(T(r_{(j)}), u(r_{(j)})) = E_i(r_{(j)}). $$

Furthermore, these witnesses are consistent with the commitments $\overline{E^1_i}, \overline{T^1}, \overline{E^2_i}, \overline{T^2}$, in that
$$\overline{T(r_{(j)})} = \overline{T^1} + r_{(j)} \overline{T^2}$$
and
$$\overline{E(r_{(j)})} = \overline{E_i^1} + r_{(j)}^{d_i} \overline{E_i^2} + \sum_{k=1}^{d_i-1} r_{(j)}^k \overline{B_{i, k}}. $$

From this, the extractor needs to extract satisfying witnesses $E^1_i, T^1, E^2_i, T^2$ to the original relaxed AIR. As in Nova, the extractor works by interpolation.

By linear interpolation, the extractor can find $T^1$ and $T^2$ such that
$$T(r_{(j)}) = T^1 + r_{(j)} T^2$$
for $j = 1, 2$. Since the commitment scheme is linear, the $T^1$ the extractor finds will satisfy $\operatorname{Com}(pp, T^1, \rho_{T^1}) = \overline{T^1}$, and similarly for $T^2$. Therefore, for every $j$ we have
$$\overline{T(r_{(j)})} = \overline{T^1} + r_{(j)} \overline{T^2} = \operatorname{Com}(T(r_{(j)})),$$
so by the binding property of commitment, we have (with high probability) that
$$T(r_{(j)}) = T^1 + r_{(j)} T^2$$ for all $j$.

Similarly, we'll recover $E^1_i, E^2_i$ and $B_{i, k}$ by Lagrange interpolation. Recall that the coefficients of any degree-$d$ polynomial in one variable can be recovered from the value of the polynomial at $d+1$ distinct points. (This is purely a question of linear algebra, so the extractor can do it efficiently.) We are looking for $E^1_i, E^2_i$ and $B_{i, k}$ such that
$$E_i(r_{(j)}) = E^1_i + r_{(j)}^{d_i} E^2_i + \sum_{k=1}^{d_i-1} r_{(j)}^k B_{i, k}.$$
Well, this is simply an interpolation problem for a polynomial of degree $d_i \leq d$ in the variable $r$; the unknowns $E^1_i, E^2_i$ and $B_{i, k}$ play the role of coefficients. Thus, for each $i$, we can find $E^1_i, E^2_i$ and $B_{i, k}$ by Lagrange interpolation on the first $d_i+1$ values $r_{(j)}$.

We know that $$\overline{E(r_{(j)})} = \overline{E_i^1} + r_{(j)}^{d_i} \overline{E_i^2} + \sum_{k=1}^{d_i-1} r_{(j)}^k \overline{B_{i, k}}, $$ so by linearity of commitment and linearity of Lagrange interpolation, $\operatorname{Com}(pp, E^1_i, \rho_{E^1_i}) = \overline{E^1_i}$, $\operatorname{Com}(pp, E^2_i, \rho_{E^2_i}) = \overline{E^2_i}$, and $\operatorname{Com}(pp, B_{i, k}, \rho_{B_{i,k}}) = \overline{B_{i, k}}$ -- in other words, the values $E^1_i, E^2_i, B_{i, k}$ that the extractor finds are consistent with the given commitments.

Just like with $T(r_{(j)})$ above, the hiding property of the commitment scheme then guarantees that (with all but negligible probability) we have $$E_i(r_{(j)}) = E^1_i + r_{(j)}^{d_i} E^2_i + \sum_{k=1}^{d_i-1} r_{(j)}^k B_{i, k}.$$ for all $j$.

Finally, we need to show that $(E^1_i, u^1, T^1)$ and $(E^2_i, u^2, T^2)$ are satisfying witnesses for the original AIR. To this end, consider the equality $$ f_i^{homog}(T^1 + r T^2, u^1 + r u^2) = E^1_i + r^{d_i} E^2_i + \sum_{k=1}^{d_i-1} r^k B_{i, k}. $$

This is an equality of polynomials of degree $d_i$ in $r$ that is known to hold for $d_i+1$ values of $r$. Therefore, the equality holds for all $r$. In particular, it holds for $r = 0$, so $$ f_i^{homog}(T^1, u^1) = E^1_i. $$

On the other hand, since $f_i^{homog}$ is homogenous of degree $d_i$, we see that
$$ f_i^{homog}(s T^1 + T^2, s u^1 + u^2) = s^{d_i} E^1_i + E^2_i + \sum_{k=1}^{d_i-1} s^{d_i-k} B_{i, k} $$ holds for $d_i+1$ values of $s$, namely $s = r_{(j)}^{-1}$. Therefore, this equality holds for all $s$, in particular for $s=0$, so $$f_i^{homog}(T^2, u^2) = E^2_i. $$

This shows that the extractor can recover the two satisfying witnesses.

#### Knowledge Soundness for Lookups

It's worth explaining why folded lookup arguments satisfy knowledge soundness as well. Recall the overall shape of the lookup argument:

- $\mathcal{P}$ commits to $A^i$, $S^i$, $A_p^i$, $S_p^i$
- $\mathcal{V}$ sends challenges $\beta$ and $\gamma$ for the grand product
- $\mathcal{P}$ computes grand products $Z^i$ and $W^i$, depending on $\beta^i$ and $\gamma^i$

Then the folding happens. To fold the instance into $I_{cml}$:

- $\mathcal{P}$ commits to cross-terms $B_j$
- $\mathcal{V}$ sends a challenge $r$
- $\mathcal{P}$ updates the folded instance $I_{cml}$.

In the proof of knowledge soundness above, the extractor rewinds to just before $\mathcal{V}$ sends the challenge $r$. The earlier challenges $\beta$ and $\gamma$ remain untouched. The conclusion is that the prover knows a witness $(u^i, \beta^i, \gamma^i, A^i, S^i, A_p^i, S_p^i, Z^i, W^i)$ that satisfies the seven polynomial relations $f_1, \ldots, f_7$.

A separate argument (knowledge soundness for Halo2 lookups) shows that in fact the prover knows $A^i$ and $S^i$ satisfying the lookup condition.

### A.2 Comparing with Nova and Sangria

[Nova](https://eprint.iacr.org/2021/370) is a folding scheme for R1CS circuits. The R1CS structure is a special case of an AIR, where there is a single constraint polynomial $f_1$, of degree 2, having a specific form. Because the polynomial is of degree $d=2$, there is only a single cross-term $B = B_{1, 1}$. The folding scheme described here generalizes Nova: if you apply this scheme to R1CS systems, you recover the original Nova folding scheme.

The idea that Nova-style folding can be generalized to arbitrary custom gates was introduced in Section 3.3 of [Sangria](https://geometry.xyz/notebook/sangria-a-folding-scheme-for-plonk).