# Lookup argument and its tweaks

# Abstract

This document contains techniques that we implemented as a part of Placeholder proof system. All these algorithms were originally developed for SHA-256 PLONK component design and now they provide an important tool that is actively used in zkEVM circuits for zkSharding.

Some of these methods were already described in Plookup paper[[3](#refPlookup)]. However, during the implementation of Plookup and its practical use, we encountered many technical issues that were not mentioned in the original paper. Here, we describe them and summarize our experience in improving Plookup.

# Preliminaries

## PLONK

### Basic concepts

PLONK is a protocol, which allows the prover to prove that they know some table over a prime field $\mathbb F$ (hereafter $A$, the **assignment table**) that satisfies some constraints on its cells. Some table columns are public — both prover and verifier know them, others are known only by prover. We will call the latter **witness columns**. We will call public columns with cells with $0$ and $1$ values **selector columns**.

PLONK is typically used to prove that some program was executed correctly. Prover proves that the assignment table contains specially encoded program execution trace. The constraints ensure that assignment table cells encode execution trace correctly and that this trace corresponds to the program and its input data.

There are interactive and non-interactive versions of the protocol. In interactive version prover and verifier may exchange messages. Messages from verifier are just random **challenges**. For a non-interactive protocol this kind of interaction is simulated by the Fiat-Shamir transformation.

Assignment table rows amount should be a power of $2$ (denote it $N=2^\nu$).

The zero-knowledge condition for PLONK means that the verifier cannot get any information about witness columns after proof verification. One of the possible ways to achieve this is to append multiple rows to assignment tables that are filled with random values in witness columns, without proving constraints on these padding rows. Another reason for padding usage may be non-power-of-two circuit size. We will denote $N_u$ the smallest index such that no cells placed in rows with index $\ge N_u$ are involved in any constraints. Rows with index $< N_u$ are called **used rows**, with index $\ge N_u$ are called **unused rows**.

### Short prover and verifier algorithms description

Prover does $B$ rounds:

- commits to some columns, sends commitments to verifier,
- gets challenges,
- generates some additional columns that are necessary to prove constraints.

Polynomials that are committed during one round may be computed together in one **commitment batch** that may be much more effective than committing to them separately. Our current Placeholder proof system supports batched versions of FRI based and KZG commitment schemes.

Let **evaluation domain** $\Omega$ be a multiplicative subgroup of $\mathbb F$ with order $N$ and generator $\omega$. Each table column or additional column $f$ may be interpreted as a polynomial $f(X)$ of degree $N-1$ over $\mathbb F$ via interpolation:

$$
f(\omega ^ i) = f[i], ~~ 0 \le i < N.
$$

$N$ polynomial values uniquely define a polynomial at most $N-1$.

We suppose that all original constraints correspond to some multivariate polynomials (**expressions**) over table columns and additional columns constructed by prover in such a way. The prover substitutes the expressions’ variables with table column and additional column polynomials in the expressions and obtains a certain number of univariate polynomials: $\{F_j(X)\}$.

:::success

💡 **Example**

If $j$-th constraint on witness columns $w_0, w_1, w_2$ requires that for all assignment table rows $w_2[i] = w_0[i]\cdot w_1[i]$ will be transformed to multivariate polynomial $F_j(w_0, w_1, w_2) = w_2 - w_1 \cdot w_0$. Polynomial $F_j(x) = F_j(w_0(x), w_1(x), w_2(X))$ will have degree $2N-2$.
:::

The **final polynomial** $F(X) = \sum_i \alpha^i F_i(X)$ is computed as their random linear combination, using a challenge $\alpha$ that comes from the verifier.

The final polynomial degree may be greater than $N-1$.

Expressions are constructed from original constraints so that constraints’ fulfillment is equivalent to the condition that $F(\omega^i) = 0 \forall i$. It means that $\omega^i$ are roots of $F(X)$.

To prove it the prover computes **quotient polynomial:**

$$
Q(X) = \frac {F(X)}{Z(X)}, Z(X) = \prod_{i = 0}^{N-1}(X-\omega^i).
$$

Its degree may be also greater than $N-1$, so prover splits $Q(X)$ into $(N-1)$-degree chunks and sends their commitments to verifier.

The final prover step is to get a random evaluation point $\xi$. Then prover constructs a proof that contains commitments of table polynomials, commitments of additional polynomials and commitments of quotient polynomial chunks, these polynomials evaluations on point $\xi$, evaluation proofs for this evaluations.

Knowing polynomial commitments, the verifier can generate all challenges itself. Knowing polynomials evaluations, verifier computes $F(\xi), Q(\xi), Z(\xi)$ and checks that $F(\xi) = \frac{Q(\xi)}{Z(\xi)}$

Formal proofs and soundness estimations may be found in [[1](#refPLONK)].

### What parameters affect the prover and verifier performance

Prover performance is mostly affected by the degrees of polynomials that are needed for the final polynomial computation. Main parameters are:

- assignment table rows amount $N$ — that’s why circuit developers try to design the smallest possible assignment tables for their tasks.
- constraint’s expression maximum degree $D$.

Verifier performance is defined by commitment scheme parameters:

- Verifier performance depends on $B$, the number of commitment batches.
- Amount of committed polynomials $P$.

It also depends sub-linearly on $N$ ($O(\log^2 N)$ for FRI and $O(\log N)$ for KZG), and linearly on the number of public inputs.

## Lookup argument

A lookup argument is a part of the PLONK protocol that provides **lookup constraints,** i.e. that some column $C$ cells (**lookup inputs**) are present in some list $T$ of values (**lookup values**). Lookup inputs and lookup values are computed from assignment table $A$.

A lookup argument may be used in different ways according to the task it solves. In its basic form it checks that the value from a certain assignment cell is contained in a predefined lookup table that is also placed in assignment table columns. But this basic setting can be enhanced with some adjustments of the lookup argument:

- We can [lookup tuples of values](#Support-for-lookup-tuples-using-a-random-linear-combination).
- [Multiple lookup constraints](#Multiple-lookup-constraints) may be used at once.
- [Lookup inputs and lookup values may be expressed by polynomials](#Using-expressions-as-lookup-input-and-lookup-values) instead of being simple witness values. Lookup tables may also be defined via expressions. This allows efficient use of the assignment table space rather than storing intermediate calculation results.
- Moreover, we can [pack lookup table values](#Zero-first-row-condition) in a way that fits best our assignment table size and even have [several lookup tables](#Using-multiple-tables) packed into the same assignment table columns or same assignment table rows. This approach allows circuit designers more possibilities for effective assignment table space usage, which is important for prover and verifier performance.

All these features may be implemented by adjusting standard lookup methods. In this document we describe their tailoring for different settings, from the simplest to the most complex, by improving the Plookup technique. Our adjustments make lookup tables an extremely flexible and convenient tool for circuit building.

All these Plookup extensions are supported by the lookup argument of =nil;’s Placeholder proof system. It is an important tool for circuit design. The most common applications are:

- **Range checks** — lookup table contains all numbers from given range.
- **Bitwise operations** — lookup table contains all possible operand values and operation result.
- **Dynamic lookups** — a tool for connecting different circuits. Some assignment table columns may be present in other assignment tables for other circuits. Similar columns may play different roles for different circuits. Some circuits prove that these columns are constructed correctly and others use them as lookup tables.
- **Circuits for hash functions computation** — lookup tables are used in SHA2-256 and Keccak circuits to constrain operations that hardly may be expressed by usual polynomial constraints.

## Notation

- $N = 2^\nu$ — assignment table rows amount.
- $N_u$ — amount of used rows in the assignment table.
- $q_{last}$ is a column of height $N: q_{last}[N_u] = 1, q_{last}[i] = 0 ~~ \forall i \ne N_u$. It is the indicator of the first unused row.
- $mask$ is a column of height $N : mask[i] = 1\; \forall i < N_u, mask[i] = 0 \forall i \ge N_u$. It is the indicator of used rows.
- $L_0$ is a column of height $N: L_0[0] = 1, L_0[i] = 0 ~~ \forall i > 0$. It is the indicator of the table’s first row.
- $\Omega$ — evaluation domain: a multiplicative subgroup of order $N$of a field $\mathbb F$.
- $\omega$ — evaluation domain generator.
- $f[i]$ for polynomial $f(X)$ means $f(\omega^i)$.

# The simplest problem statement

In the simplest setting we expect the prover to prove that:

$$
\forall i \exists j: f[i] = t[j], \quad 0 \le i,j < N_u
$$

for some columns $f,t$ in assignment table, i.e. that every element from the column $f$ appears somewhere in the column $t$.


We will denote this kind of lookup constraint $f \rightarrow t$.

Creating a proof for this statement may be carried out as follows.

## Join and split

Take the usable parts of columns $f$ and $t$ as vectors of length $N_u$ and create a vector $s$ of length $2N_u$ by inserting values from $f$ into the vector $t$. Every value from $f$ should be placed next to some equal element in $t$. Thus, the sequence of different elements from $t$ is preserved in $s$, but the lengths of same-element subsequences might increase. Next we split vector $s$ into two sub-vectors $s_0$ and $s_1$ of length $N_u$ and add one value to each vector, letting $s_0[N_u]=s_1[0]$ and $s_1[N_u] = t[N_u]$.

If $s_0, s_1$ are constructed correctly, they satisfy the following conditions:

1. <a id = "cond1"></a> The set of non-equal sequential values in all $s_i$’s , i.e.
$\{(s_i[j], s_i[j+1]): s_i[j]\ne s_i[j+1], 0 \le j < N_u, 0 \le i \le 1\}$
is equal to the set of non-equal sequential values in $t$, i.e.
$\{(t[j], t[j+1]): t[j]\ne t[j+1], 0 \le j < N_u\}$.
2. <a id = "cond2"></a> For each value $a$ the amount of pairs $(s_i[j], s_i[j+1])$ where $s_i[j] = s_i[j+1] = a$, equals the sum of total $a$ occurrences in $f$ and the amount of pairs $(t[j], t[j+1])$ where $t[j] = t[j+1] = a$:

$$
|\{j: s_i[j]= s_i[j+1] = a, 0 \le j < N_u, i = \overline{0,1}\}| =
$$

$$
= |\{j: f[j] = a, 0 \le j < N_u\}| + |\{j: t[j]= t[j+1] = a, 0 \le j < N_u\}|.
$$

3. <a id = "cond3"></a> $s_0, s_1$ continuity: $s_0[N_u] = s_1[0]$

These conditions are equivalent to the original lookup constraint statement if $t[N_u] = t[i]$ for some $i < N_u$.


If $t$ is placed in public columns and the verifier knows that $t[N_u] = t[i]$, or this condition is proven by other constraints, prover may prove the conditions list above. But this kind of padding is not convenient for PLONK. We should modify the list of conditions to exclude the case in which

$$
\exists i < N_u:f[i] = 0 \land \forall j < N_u \,\,\, t[j] \ne 0
$$


This issue with padding $t$ may be fixed by using lookup tuples as described in the following section.

Hereafter we allow repetitions in lookup table values. One might wonder why this may be useful. This has at least two applications.

1. The amount of lookup values (size of $t$) may be smaller than $N_u$, but our algorithm works with vectors of length $N_u$. In such a case, extra cells in assignment table columns reserved for lookup tables may be easily filled by valid lookup values.
2. Sometimes lookup table columns are also witness columns and are involved in other PLONK relations. Hence assuring value uniqueness would require excessive efforts from the circuit designer.

Here is an example of how join-and-split algorithm will work on a non-sorted lookup table with repetitions.


## Grand product technique

To prove conditions [1](#cond1), [2](#cond2) and [3](#cond3), the prover commits to polynomials $s_0, s_1$, and gets two challenges $\beta$ and $\gamma$. Using $\beta, \gamma$, the prover constructs an additional column $V$ according to the following definition (formulas are written with the assumption that $t$ is padded by random values):

$$
V[0] = 1
$$

$$
V[i+1] = V[i] \times \frac {(1+\beta)(\gamma + f[i]) (\gamma + \beta\gamma + t[i+1]+ \beta t[i])}{(\gamma + \beta\gamma + s_0[i+1] + \beta s_0[i])(\gamma + \beta\gamma + s_1[i+1] + \beta s_1[i])}
$$

If the claimed statement is true, then $V[N_u] = 1$ (except for cases with negligible probability when$V[N_u] = 0$ due to an extremely unlucky choice of $\beta$ and $\gamma$ by the prover).

Now the prover constructs the polynomials for the final checks:

- $F_1(X) = L_0(X) \cdot (V(X) - 1)$
- $F_2(X) = q_{last}(X) \cdot V(X) \cdot (V(X) - 1)$
- $F_3(X) = mask(X)\cdot( V(X)\cdot g(X) - V(\omega X)\cdot h(X))$, where
$g(X) = (1+\beta)(\gamma + f(X) ) (\gamma + \beta\gamma + t(\omega X) + \beta t(X) )$
$h(X) = {(\gamma + \beta\gamma + s_0(\omega X) + \beta s_0(X))(\gamma + \beta\gamma + s_1(\omega X) + \beta s_1(X))}$
- $F_4(X) = L_0(X)\cdot (s_1(x) - s_0(x\omega^{N_u}))$ — guarantees that $s_0, s_1$ satisfy statement [3](#cond3).

The statements above are equivalent to $F_1(X), \dots, F_4(X)$ being $0$ on all points of the evaluation domain $\Omega$.

In this simplest setting, the lookup argument requires committing to 3 additional polynomials, namely $s_0, s_1, V_L$. While polynomials $s_0$ and $s_1$ may be committed in a single batch, $V$ should be committed in a separate batch, because random challenges $\beta, \gamma$ should be independent from $s_0, s_1$.

Eventually, for verification we use a random linear combination of the polynomials $F_1,\dots,F_4$. This final polynomial has degree $4(N-1)$.

## Support for lookup tuples using a random linear combination

Consider now a lookup table $T$ with multiple columns $\{t_0 \dots t_{m-1} \}$. A lookup constraint is then a list $\{f_0 \dots f_{n-1}\}$ of assignment table’s columns. Lookup constraint will be written as $\{f_0,\dots f_{m-1}\} \rightarrow \{t_0,\dots t_{m-1}\}.$The statement to be proven is:

$$
\forall i ~\exists j ~\forall k ~~t_k[i]=f_k[j].
$$

At the beginning prover gets a random challenge $\theta$ and compress multiple columns into one by computing:

- $t = \sum_{i=0}^{(n-1)} \theta^i t_i$,
- $f = \sum_{i=0}^{(n-1)} \theta^if_i$.

This reduces the problem to our previous setting. For the sake of clarity in the images below we represent the compressed values as pairs of initial values and not the values of random linear combinations.


But, as in the previous scenario, we also have issues with zero padding for $t_i$. To prevent it, we just append a mask to the random linear combination above.

- $t = mask + \sum_{i=0}^{n-1} \theta^{i + 1} t_{i}$,
- $f = mask + \sum_{i=0}^{(n-1)} \theta^{i+1} f_i$.

Zero tuples appear in the lookup inputs with negligible probability because
$\forall i < N_u: mask[i] = 1$.


Polynomials $V$ and $F_i$ are constructed in the same way as described in the [previous section](https://hackmd.io/kpn5x5O3RKqR9yLZy0PB4Q?both#Grand-product-technique).

:::success
💡 **Our contribution**
We modified the reordering algorithm to have full support of repetitions inside lookup table columns and various paddings of lookup table columns.
:::

# Using expressions as lookup input and lookup values

## Changes in polynomial degrees

Let $\{c_k(w_0 \dots w_{m-1})\}$ and $\{t_k(w_0 \dots w_{m-1})\}$ where $0\le i \le n$ are same-size tuples of expressions degrees over columns of the assignment table degrees $\{d_{c_k}\}$ and $\{d_{t_k}\}$ respectively. Lookup constraint will be written as:

$$
\{c_0,\dots c_{n-1}\} \rightarrow \{t_0,\dots t_{n-1}\}
$$

We are now set out to prove that:

$$
\forall i \exists j \forall k: c_k[i] = t_k[j], 0 \le i,j < N_u, 0 \le k < m
$$

i.e. that every value in $c$ has a matching value in $t$. For this case we just have to use polynomial expressions instead of ordinary columns. Remember that the $c_k(X)$ and $t_k(X)$ polynomials may have degree bigger than $N-1$ and that $c_k[i] = c_k(\omega^i)$.


Compressed polynomials will be constructed as:

- $c(X) = mask(X) + \sum_{i = 0}^{n-1}\theta^{i+1} c_i(w_0(X), \dots, w_m(X))$ :
it has degree $\max(d_{c_k})(N-1)$,
- $t(X) = mask(X) + \sum_{i=0}^{n-1}\theta^{i+1} t_i(w_0(X),\dots, w_m(X))$ that has degree $\max(d_{t_k})(N-1)$

The polynomials for the final checks will be:

- $F_1(X) = L_0(X) \cdot (V(X) - 1)$
- $F_2(X) = q_{last}(X) \cdot V(X) \cdot (V(X) - 1)$
- $F_3(X) = mask(X)\cdot(V(X)\cdot g(X) - V(\omega X)\cdot h(X))$, where
$g(X) = (1+\beta)(\gamma + c(X) ) (\gamma + \beta\gamma + t(\omega X) + \beta t(X))$
$h(X) = {(\gamma + \beta\gamma + s_0(\omega X) + \beta s_0(X))(\gamma + \beta\gamma + s_1(\omega X) + \beta s_1(X))}$
- $F_4(X) = L_0(X) (s_1(x) - s_0(x\omega^{N_u}))$

This modification increases the degree of $F_3$ to $(\deg(c) + \deg(t) + 2)(N-1)$.

If we use a non-trivial expression for some of the lookup table columns, such that $t_k(0 \dots 0) \ne 0$, it is necessary to multiply $t(X)$ by $mask(X)$, even if the assignment table is padded with zeros.

If the assignment table is padded with zeros and $\forall k: 0 \le k < m,~~ t_k(0, \dots 0) = 0$ then we need not multiply $t(X)$ by $mask(X)$. In this case the degree of $F_3$ will be $(\deg(c) + \deg(t) + 2)(N-1)$.

## Selector columns usage

Using expressions in lookup constraints, we can solve a slightly more complex, but practical problem.

Assume that prover wants to prove that lookup values contain only those lookup input cells that are marked by a selector $q$ (public column with 0 and 1 values). Also assume that the list of possible values are placed only in rows that are marked by selector $p$.

We want the prover to assert that:

$$
\forall i: p[i] = 1 ~\exists j: q[j] = 1, \forall k \quad c_k[i] = t_k[j],
$$

i.e. for every selected row in the lookup input there is indeed a row in the selected part of the lookup table, that contains the same values. We will denote this kind of lookup constraint by:

$$
(p,\{c_0 \dots c_{n-1}\})\rightarrow(q,\{t_0 \dots t_{n-1}\}).
$$

This problem is reduced to the previous one using following tuples:

$$
\{p,p\times c_0 \dots p\times c_{n-1}\}\rightarrow\{q,q\times t_0 \dots q \times t_{n-1}\}.
$$

Since $p,q$ are public polynomials, they are padded by zeros, so there is no more need to add the $mask$ polynomial to these tuples.


Compressed polynomials will have following form:

- $c(X) = p(X)\left(1 + \sum_{i = 0}^{n-1}\theta^{i+1} c_i(X) \right)$ — has degree $(max(d_{c_i}) + 1)(N-1)$
- $t(X) = q(X)\left(1 + \sum_{i=0}^{n-1}\theta^{i+1} t_i(X)\right)$ has degree $(max(d_{t_i}) + 1)(N-1)$

Final polynomial degree in this case is defined by $\deg(F_3) = (\max_i(\deg(c_i)) + \max_i(\deg(t_i)) + 4) (N-1)$.

## Multiple lookup constraints

Suppose now we want to have $L$ different lookup constraints using the same lookup table to be satisfied simultaneously:

$(p^{(0)},\{c^{(0)}_0, \dots , c^{(0)}_{n-1}\} )\rightarrow (q, \{t_0, \dots t_{n-1}\})$,

$(p^{(1)},\{c^{(1)}_0, \dots , c^{(1)}_{n-1}\} )\rightarrow (q, \{t_0, \dots t_{n-1}\})$,

$\dots$

$(p^{(l-1)},\{c^{(L-1)}_0, \dots , c^{(L-1)}_{n-1}\} )\rightarrow (q, \{t_0, \dots t_{n-1}\})$.

The statement to prove will be:

$$
\forall l,i: 0 \le l < L, 0 \le i < n,~~ p^{(l)}[i]=1 \quad \exists j:q[j]=1, \quad \forall k ~ c^{(l)}_k[i] = t_k[j].
$$

From the lookup constraints we compute compressed columns $c^{(0)} \dots c^{(L-1)}$ and from the lookup table we compute the compressed column $t$. Joining and splitting these compressed columns as described previously will produce $L+1$ specially ordered columns $s_0 \dots s_L$.


The statements of the lookup argument are transformed into:

1. <a id="newcond1"></a> The set of non-equal sequential values in all $s_i$’s , i.e.
$\{(s_i[j], s_i[j+1]): s_i[j]\ne s_i[j+1], 0 \le j < N_u, 0 \le i < L\}$
is equal to the set of non-equal sequential values in $t$, i.e.
$\{(t[j], t[j+1]): t[j]\ne t[j+1], 0 \le j < N_u\}$.

2. <a id="newcond2"></a> For each value $a$ the amount of pairs $(s_i[j], s_i[j+1])$ where $s_i[j] = s_i[j+1] = a$, equals the sum of total $a$ occurrences in $f$ and the amount of pairs $(t[j], t[j+1])$ where $t[j] = t[j+1] = a$:

$$
|\{j: s_i[j]= s_i[j+1] = a, 0 \le j < N_u, 0 \le l < L\}| =
$$

$$=|\{j: f[j] = a, 0 \le j < N_u\}| + |\{j: t[j]= t[j+1] = a, 0 \le j < N_u\}|.
$$

3. <a id="newcond3"></a> $\{s_i\}$ continuity: $s_i[N_u] = s_{i+1}[0]$ for $0 \le i < L-1$

Now define the column $V$ as follows:

$$
V[i+1] = V[i] \times \frac
{(\gamma + \beta\gamma + t[i+1] + \beta t[i]) \prod_{j=0}^{L-1}(1+\beta)(\gamma + c^{(j)}[i])}
{\prod_{j=0}^{L}(\gamma + \beta\gamma + s_j[i+1] + \beta s_j[i])}
$$

The following polynomials should be zero on all points of the evaluation domain:

- $F_1(X) = L_0(X) \cdot (V(X) - 1)$
- $F_2(X) = q_{last}(X) \cdot V(X) \cdot (V(X) - 1)$
- $F_3(X) = mask(X)\cdot(V(X)\cdot g(X) - V(\omega X)\cdot h(X))$ where
$g(X) = (\gamma + \beta\gamma + t(\omega X) + \beta t(X)) \prod_{i=0}^{L-1}(1+\beta)(\gamma + c^{(i)}(X))$
$h(X) = \prod_{i = 0} ^ L{(\gamma + \beta\gamma + s_i(\omega X) + \beta s_i(X))}$
- $F_{4+i}(X) = L_0(X) (s_{i+1}(x) - s_i(x\omega^{N_u}))$, where $0 \le i < L-1$

In this case we should commit to $L+2$ polynomials in 2 different batches. The polynomial degree will be:

$\deg(F_3) = (3 + \max_j(\deg(t_j)) + (N-1)\sum_i(\max_j( \deg(c^{(i)}_j))+1))$

:::success
💡 **Our contribution**
We clarified and explained selector column usage, which is extremely important for circuit design. Selector columns for lookup input allows to distribute lookup table rows between different sub-circuits.

Selector columns for lookup tables provide for an effective use of assignment table space and allow to fill unused cells of lookup table columns with significant data instead of useless padding.

For example, we may use this space for storing [another lookup table](#Using-multiple-tables).
:::

# Using large lookup tables

## Zero first row condition

Suppose now that the table $T$ has many more rows than the assignment table does. In this case, we can try to “cut” the table $T$ into sections of no more than $N_u$ rows, and pack them horizontally into the assignment table. These section are further called *options*. Suppose that the table $T$ with columns $\{t_0,\dots,t_{n-1}\}$ is split into $m$ options $T\langle 0\rangle ,\dots,T\langle m-1\rangle$. We denote their columns as $\{t_0\langle i\rangle,\dots,t_{n-1}\langle i\rangle\}$ for $i = 0,\dots,m-1$.

Lookups into an optioned table assume that each lookup input coincides with one of the options. We denote such lookups as follows (as usual, $q$ is the lookup table selector):

$(p^{(0)},\{c^{(0)}_0, \dots , c^{(0)}_{n-1}\} )\rightarrow (q, \{t_0\langle 0\rangle, \dots t_{n-1}\langle 0\rangle\}, \dots, \{t_0\langle m-1\rangle, \dots t_{n-1}\langle m-1\rangle \})$,

$(p^{(1)},\{c^{(1)}_0, \dots , c^{(1)}_{n-1}\} )\rightarrow (q, \{t_0\langle 0 \rangle, \dots t_{n-1}\langle 0 \rangle \}, \dots, \{t_{0}\langle m-1 \rangle, \dots t_{n-1}\langle m-1 \rangle \})$ ,

$\dots$

$(p^{(L-1)},\{c^{(L-1)}_0, \dots , c^{(L-1)}_{n-1}\} )\rightarrow\\ (q, \{t_0\langle 0 \rangle, \dots t_{n-1}\langle 0 \rangle \}, \dots, \{t_0\langle m-1 \rangle, \dots t_{n-1}\langle m-1\rangle\})$

We intend to prove that:

$$
\forall i,l:p^{(l)}[i]=1~~ \exists j,u:q[j]=1 ~~\forall k ~ c^{(l)}_k[i] = t_k\langle u\rangle[j],
$$$$
0 \le i < N_u, 0\le l < L, 0 \le j < N_u, 0 < u < m
$$

i.e. for every selected lookup input there is an option in the selected part of the table with a row that matches the lookup input’s values.

We compute compressed input columns $c^{(0)} \dots c^{(L-1)}$ from lookup constraints. We also compute compressed columns $t\langle 0\rangle \dots t\langle m-1\rangle$ for options, one per option. Our join-and-split procedure produces $L + m$ specially ordered columns.

To work with multiple table options, we need more restrictions on the structure of table columns. The join-and-split algorithm will fail if the first row is selected by $q$.


The problem arises because, in the original masked lookup table columns, the value $t\langle0\rangle[N_{u-1}-1]$ is followed by zero, while in the joint vector $s$ it is followed by $t\langle 1 \rangle[0]$. To ensure that the joint vector has the correct sequence of elements, and thus the join-and-split algorithm works correctly, we require lookup table columns to have the first row unselected by the selector $q$.


$$
V[i+1] = V[i] \times \frac
{\prod_{j=0}^{m-1}(\gamma + \beta\gamma + t\langle j\rangle[i+1] + \beta t\langle j\rangle[i]) \prod_{j=0}^{L-1}(1+\beta)(\gamma + c^{(j)}[i])}
{\prod_{j=0}^{L + m-1}(\gamma + \beta\gamma + s_j[i+1] + \beta s_j[i])}
$$

The following polynomials will have to be combined for the final check:

- $F_1(X) = L_0(X) \cdot (V(X) - 1)$
- $F_2(X) = q_{last}(X) \cdot V(X) \cdot (V(X) - 1)$
- $F_3(X) = mask(X)\cdot(V(X)\cdot g(X) - V(\omega X)\cdot h(X))$
$g(X) = \prod_{j=0}^{m-1}(\gamma + \beta\gamma + t\langle j\rangle(\omega X) + \beta t\langle j\rangle(X)) \prod_{j=0}^{L-1}(1+\beta)(\gamma + c^{(j)}(X))$
$h(X) = \prod_{i = 0} ^ {m+L-1}{(\gamma + \beta\gamma + s_i(\omega X) + \beta s_i(X))}$
- $F_{4+i}(X) = L_0(X) (s_{i+1}(x) - s_i(x\omega^{N_u}))$, where $0 \le i < L + m - 1$.

The degree of the final polynomial matches the degree of $F_3$:

$$
\deg(F_3) = \left(2 +\sum_i( \max_j(\deg(t\langle j \rangle^{(i)}) + 1) + \sum_i (\max_j(\deg(c^{(i)}_j))+1\right)\\ \times (N-1)
$$

This technique allows us to use lookup tables that are larger than assignment table size. Note that for correct processing of non-selected rows, we need condition $q[0] = 0$ to be satisfied.

## Using multiple tables

Sometimes we have to check multiple conditions described in the previous section independently with completely different lookup tables and lookup constraints. We can just run the lookup argument multiple times. But it is more effective to run it only once using lookup tables unique identifiers.

Suppose that $T_1 \dots T_r$ are lookup tables having column amounts $n_1\dots n_r$ and option amounts $m_1\dots m_r$, respectively. Assume that table $T_i$ has selector $q^{(i)}$ and option columns $\{t_0^{(i)}\langle 0\rangle, \dots t_{n_i-1}^{(i)}\langle 0\rangle\}, \dots, \{t_0^{(i)}\langle m_i-1\rangle , \dots t_{n_i-1}^{(i)}\langle m_i-1\rangle\}$.

Let $L$ be the number of lookup constraints.

Suppose that table number $r_i$, $1 \le r_i \le r$, is used for $i$-th lookup constraint (table identifiers may be repeated in different lookup constraints). The constraint system has the following format:

$(p^{(0)},\{c^{(0)}_0, \dots , c^{(0)}_{n_{r_0}-1}\} )\rightarrow \\(q^{(r_0)}, \{t_0^{(r_0)}\langle 0\rangle, \dots t_{n_{r_0}-1}^{(r_0)}\langle 0 \rangle \}, \dots, \{t_0^{(r_0)}\langle m_{r_0}-1\rangle, \dots t_{n_{r_0}-1}^{(r_0)}\langle m_{r_0}-1\rangle\})$

$\dots$

$(p^{(i)},\{c^{(i)}_0, \dots , c^{(i)}_{n_{r_i}-1}\} )\rightarrow \\(q^{(r_i)}, \{t_0^{(r_i)}\langle 0\rangle, \dots t_{n_{r_i}-1}^{(r_i)}\langle 0 \rangle\}, \dots, \{t_0^{(r_i)}\langle m_{r_i}-1\rangle, \dots t_{n_{r_i}-1}^{(r_i)}\langle m_{r_i}-1\rangle\})$

$\dots$

$(p^{(L-1)},\{c^{(L-1)}_0, \dots , c^{(L-1)}_{n_{r_{l-1}}-1}\} )\rightarrow \\(q_{(r_{L-1})}, \{t_0^{(r_{L-1})}\langle 0\rangle, \dots t_{n_{r_{L-1}}-1}^{(r_{L-1})}\langle 0\rangle\}, \dots, \{t_0^{(r_{L-1})}\langle m_{r_{L-1}}-1\rangle, \dots t_{n_{r_{L-1}}-1}^{(r_{L-1})}\langle m_{r_{l-1}}-1\rangle\})$

The prover needs to prove that:

$$
\forall i,l:p^{(l)}[i]=1~~ \exists j,u:q^{(r_i)}[j]=1 \quad \forall k ~ c^{(l)}_k[i] = t_k^{(r_l)}\langle u\rangle[j]
$$

Using the selector as an additional lookup value is insufficient to distinguish different tables. If the previous compression algorithm is used for lookup tables compressing, we will actually prove a weaker statement, namely:

$$
\forall i,l:p^{(l)}[i]=1~~ \exists j,u,\mu:q^{(\mu)}[j]=1 \quad \forall k ~ c^{(l)}_k[i] = t_k^{(\mu)}\langle u\rangle[j],
$$

i.e. that the $i$-th lookup constraint value is in *some* of $T_1,\dots,T_r$, but not exactly in $T_{r_i}$.

We use the index of each table as a unique non-zero identifier to fix this problem. This allows the lookup argument to run with the following constraints:

$$
(\{p^{(0)} \times r_0, p^{(0)} \times c^{(0)}_0, \dots , p^{(0)} \times c^{(0)}_{n_{r_0}-1}\} )\rightarrow
$$$$
(\{q^{(r_0)}\times r_0, q^{(r_0)} \times t_0^{(r_0)}\langle 0 \rangle, \dots, q^{(r_0)}\times t_{n_{r_0}-1}^{(r_0)}\langle 0\rangle\}, \\
\dots
$$$$
\{q^{(r_0)}\times r_0, q^{(r_0)} \times t_0^{(r_0)}\langle m_{r_0}-1\rangle, \dots q_{r_0} \times t_{n_{r_0}-1}^{(r_0)}\langle m_{r_0}-1\rangle\}),
$$$$
\dots
$$$$
(\{p^{(L-1)} \times r_{L-1}, p^{(L-1)} \times c^{(L-1)}_0, \dots , p^{(l-1)} \times c^{(L-1)}_{n_{r_{L-1}}-1}\} )
\rightarrow
$$$$
(\{q^{(r_{L-1})}\times r_{L-1}, q^{(r_{L-1})} \times t_0^{(r_{L-1})}\langle 0\rangle, \dots q^{(r_0)}\times t_{n_{r_{L-1}}-1}^{(r_{L-1})}\langle 0\rangle\}, \\
$$$$
\dots, \\
\{q^{(r_{L-1})}\times r_{L-1}, q^{(r_{L-1})} \times t_0^{(r_{L-1})}\langle m_{r_{L-1}}-1\rangle, \dots q^{(r_{L-1})} \times t_{n_{r_{L-1}}-1}^{(r_{L-1})}\langle m_{r_{L-1}}-1\rangle\})
$$

Let $m = \sum_{i=1}^r m_i$ be the total amount of lookup options. After compressing, joining and splitting the lookup input and option columns the usual way, we will have $L + m$ specially ordered columns.`


$$
V[i+1] = V[i] \times \frac
{\prod_{j=1}^{r}\prod_{k=0}^{m_j-1}(\gamma + \beta\gamma + t^{(j)}\langle k\rangle[i+1] + \beta t^{(j)}\langle k\rangle[i]) \prod_{j=0}^{l-1}(1+\beta)(\gamma + c^{(j)}[i])}
{\prod_{j=0}^{l + m-1}(\gamma + \beta\gamma + s_j[i+1] + \beta s_j[i])}
$$

The polynomials that make up the final polynomial are:

- $F_1(X) = L_0(X) \cdot (V(X) - 1)$
- $F_2(X) = q_{last}(X) \cdot V(X) \cdot (V(X) - 1)$
- $F_3(X) = mask(X)\cdot(V(X)\cdot g(X) - V(\omega X)\cdot h(X))$ where

$$
g(X) = \prod_{j=1}^{r}\prod_{k=0}^{m_j-1}(\gamma + \beta\gamma + t^{(j)}\langle k \rangle (\omega X) + \beta t^{(j)}\langle k \rangle(X)) \prod_{j=0}^{L-1}(1+\beta)(\gamma + c^{(j)}\langle X\rangle)
$$

$$
h(X) = \prod_{i = 0} ^{L + m-1}{(\gamma + \beta\gamma + s_i(\omega X) + \beta s_i(X))}
$$

- $F_{4+i}(X) = L_0(X) (s_{i+1}(x) - s_i(x\omega^{N_u}))$, where $0 \le i < L + n - 1$.

The number of committed polynomials for the lookup argument is $L+n+1$. The degree of the final polynomial is determined by:

$$
\deg(F_3) = \left(2 +\sum_k\sum_{i=0}^{m_k-1}( \max_j(\deg(t^{(r_k)}_j\langle i\rangle)) + 1) + \sum_i (\max_j( \deg(c^{(i)}_j))+1\right)\\ \times (N-1).
$$

:::success

💡 **Our contribution**
We improved the join-and-split algorithm to be able to work with multiple option columns $t\langle i \rangle$. This allows us to use large lookup tables without growth in the amount of assignment table rows. This may improve the prover performance and decrease memory consumption.

This technique also allows us to use multiple lookup tables that may be placed in the same assignment table rows. Our approach is more effective than re-running the lookup argument for each lookup table.

A circuit designer may use different strategies for lookup table storage according to given restrictions.

:::

# Final polynomial degree optimization

One of the main drawbacks for the product arguments we use is the high degree of the final polynomial. It leads to a growing evaluation domain, slows down operations with polynomials, and increases memory consumption.

To optimize the prover performance we use partition products.

Let $d$ be the degree bound for the final polynomial $F$. We split the factors of $g(X)$ into $K$ groups, with products:

$$
g_k(X): \deg(g_k(X))=d_k, d_k < d, \sum_k d_k = \deg(g(X)), \prod_k g_k(X) = g(X)
$$

And $h_k(X)$ is corresponding $h$(X) factors split.

Define partition product columns that may be interpreted as degree $N-1$ polynomials

$$
\pi_0(X) = V(X)\\
$$$$
\pi_{k+1}[i] = \pi_k[i] \cdot \frac{ g_k[i] }{ h_k[i]}
$$

Commit $\pi_i(X)$ polynomials.

These polynomials should be added to the final polynomial checks:

- $F_1(X) = L_0(X) \cdot (V(X) - 1)$
- $F_2(X) = q_{last}(X) \cdot V(X) \cdot (V(X) - 1)$
- $F_{3+k}(X) = (\pi_k(X)\cdot g_k(X) - \pi_{k+1}(X)\cdot h_k(X))$ where $0\le k < K$
- $F_{3+K}(X) = mask(X) \cdot (V(\omega X)\cdot g_K(X) - \pi_{K}(x) \cdot h_K(X))$
- $F_{4+K+i}(X) = L_0(X) (s_{i+1}(X) - s_i(X\omega^{N_u}))$, where $0 \le i < L + n - 1$.

Thus, $n+L+K$ polynomials will be committed. The polynomials $\pi_i$ may be committed along with $V(X),$ so two batches will be enough. The final polynomial will in this case have a degree $\deg(F) < d$, which is lower than in the original algorithm, so processing the final polynomial will be cheaper. The prover will work with smaller polynomials on smaller evaluation domains, which may be more efficient. So, this optimization involves a trade-off between the number of committed polynomials on the one hand, and their degree and evaluation domain size on the other.

This is similar to the grand product optimization described in the [Plonky2 documentation](https://github.com/0xPolygonZero/plonky2/blob/main/plonky2/plonky2.pdf) for permutation arguments.

# References

1. <a id="refPLONK"></a> Gabizon A., Williamson Z. J., Ciobotaru O. PLONK: Permutations over Lagrange--bases for Oecumenical Noninteractive arguments of Knowledge. — 2019. — [https://ia.cr/2019/953](https://ia.cr/2019/953). Cryptology ePrint Archive, Report 2019/953.
2. <a id="refHalo2"></a> [https://zcash.github.io/halo2/design/proving-system/lookup.html](https://zcash.github.io/halo2/design/proving-system/lookup.html) — Halo2 lookup argument
3. <a id="refPlookup"></a> Gabizon A., Williamson Z.J., Plookup: A simplified polynomial protocol for lookup tables. — 2020. — [https://eprint.iacr.org/2020/315.pdf](https://eprint.iacr.org/2020/315.pdf)

# RFC

The lookup argument described in this document is quite generic. It can be optimized in various ways for specific applications. Some approaches to the lookup argument may be more efficient than Plookup.

If you find any of the above ideas useful or if you know better ways of dealing with the settings described above, please share them in comments!

---

**Links**
[Website](https://nil.foundation/)
[Documentation](https://docs.nil.foundation/)
[Other our research on HackMD](https://hackmd.io/MPkGZS0NSBGZstB6FsvNtA)

**Connect**
Email: [[e-mail]](mailto:[e-mail]?subject=HackMD_Test)
Twitter: [@nil_foundation](https://x.com/nil_foundation)