Lookup Argument

The Lookup Argument establishes that all elements of list $A=(a_0,\dots ,a_{\ell })$ also occur in list $B=(b_0,\dots ,b_n)$. In this context, $A$ contains the values that are being looked up, while $B$ is the lookup table.¹ Both lists $A$ and $B$ may contain duplicates. However, it is inefficient if $B$ does, and is therefor assumed not to.

The example at the end of this section summarizes the necessary computations for the Lookup Argument. The rest of the section derives those computations. The first step is to interpret both lists' elements as the roots of polynomials $f_A(X)$ and $f_B(X)$, respectively:

$$\begin{array}{rl}{f}_A(X)& =\prod _{i=0}^{\ell }X-a_i\\ f_B(X)& =\prod _{i=0}^{n}X-b_i\end{array}$$

By counting the number of occurrences $m_i$ of unique elements $a_i\in A$ and eliminating duplicates, $f_A(X)$ can equivalently be expressed as:

$$f_A(X)=\prod _{i=0}^n(X-a_i{)}^{m_i}$$

The next step uses

• the formal derivative $f_A^{\prime }(X)$ of $f_A(X)$, and
• the multiplicity-weighted formal derivative $f_B^{\prime (m)}(X)$ of $f_B(X)$.

The former is the familiar formal derivative:

$$f_A^{\prime }(X)=\sum _{i=0}^n{m}_i(X-a_i{)}^{m_i-1}\prod _{j\ne i}(X-a_j{)}^{m_j}$$

The multiplicity-weighted formal derivative uses the lookup-multiplicities $m_i$ as additional factors:

$$f_B^{\prime (m)}(X)=\sum _{i=0}^n{m}_i\prod _{j\ne i}(X-b_j)$$

Let $g(X)$ the greatest common divisor of $f_A(X)$ and $f_A^{\prime }(X)$. The polynomial $f_A(X)/g(X)$ has the same roots as $f_A(X)$, but all roots have multiplicity 1. This polynomial is identical to $f_B(X)$ if and only if all elements in list $A$ also occur in list $B$.

A similar property holds for the formal derivatives: The polynomial $f_A^{\prime }(x)/g(X)$ is identical to $f_B^{\prime (m)}(X)$ if and only if all elements in list $A$ also occur in list $B$. By solving for $g(X)$ and equating, the following holds:

$$f_A(X)\cdot f_B^{\prime (m)}(X)=f_A^{\prime }(X)\cdot f_B(X)$$

Optimization through Logarithmic Derivatives

The logarithmic derivative of $f(X)$ is defined as $f^{\prime }(X)/f(X)$. Furthermore, the equality of monic polynomials $f(X)$ and $g(X)$ is equivalent to the equality of their logarithmic derivatives.² This allows rewriting above equation as:

$$\frac{f_A^{\prime }(X)}{f_A(X)}=\frac{f_B^{\prime (m)}(X)}{f_B(X)}$$

Using logarithmic derivatives for the equality check decreases the computational effort for both prover and verifier. Concretely, instead of four running products – one each for $f_A$, $f_A^{\prime }$, $f_B$, and $f_B^{\prime (m)}$ – only two logarithmic derivatives are needed. Namely, considering once again list $A$ containing duplicates, above equation can be written as:

$$\sum _{i=0}^{\ell }\frac{1}{X-a_i}=\sum _{i=0}^n\frac{m_i}{X-b_i}$$

To compute the sums, the lists $A$ and $B$ are base columns in the two respective tables. Additionally, the lookup multiplicity is recorded explicitly in a base column of the lookup table.

Example

In Table A:

And in Table B:

It is possible to establish a subset relation by skipping over certain elements when computing the logarithmic derivative. The logarithmic derivative must incorporate the same elements with the same multiplicity in both tables. Otherwise, the Lookup Argument will fail.

An example for a Lookup Argument can be found between the Program Table and the Processor Table.