Plookup

definition

Plookup was described by the original authors in [GW20] as a protocol for checking whether values of a committed polynomial, over a multiplicative subgroup $\mathrm{H}$ of a finite field $\mathbb{F}$, are contained in a vector $\mathrm{t}\in {\mathbb{F}}^d$ that represents values of a table $\mathcal{T}$. More precisely, Plookup is used to check if certain evaluations of some committed polynomial are part of some row $\mathrm{t}$ of a lookup table $\mathcal{T}$.

One particular use case of this primitive is: checking whether all evaluations of a polynomial $f(x)$, restricted to values of a multiplicative subgroup $\mathrm{H}\in \mathbb{F}$, fall in a given range $\{0,1,\dots ,M\}$. i.e., proving that, for every $\mathrm{z}\in \mathrm{H}$, we have $f(\mathrm{z})\in \{0,1,\dots ,M\}$.

Plookup’s strategy for soundness depends on a few basic mathematical concepts described below.

Notations and preliminaries

Sets and multisets

Recall that a set is a collection of distinct objects, called elements, where repetitions and order of elements are disregarded. That is, the set $\{1,3,7\}$ is the same set as $\{3,7,1,7,1,1\}$.

Yet, as multisets, $\{1,3,7\}$ is not the same as $\{3,7,1,7,1,1\}$. It is because multisets take into consideration all instances of an element.

Given a multiset s, we define multiplicity to be the number of all instances of an element.

So, in the multiset $\{3,7,1,7,1,1\}$; the element 3 has multiplicity 1, while 7 is of multiplicity 2 , and lastly, 1 has multiplicity 3.

A set can therefore be described as a collection of distinct objects where multiplicity and ordering of objects have no significance.

Multisets are similar to sets in that they also do not respect the ordering of elements. That is, $\{1,3,1,7\}$ and $\{1,7,1,3\}$ represent the same multiset, because they both contain the same elements, each with the same multiplicity.

Given multisets $\mathrm{t}=\{1,3,7\}$ and $\mathrm{s}=\{3,7,1,7,1,1\}$, s can be sorted by t as follows, $\mathrm{s}=\{1,1,1,3,7,7\}$. That is, “$\mathrm{s}$ sorted by $\mathrm{t}$” means the elements of $\mathrm{s}$ are ordered according to the order they appear in $\mathrm{t}$, without losing their multiplicity.

Sorted multisets and set differences

Unless otherwise stated, all sorted multisets are henceforth sorted by $\mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers $\{1,2,3,\dots \}$.

For any given sorted multiset $\mathrm{s}=\{{\mathrm{s}}_1,{\mathrm{s}}_2,\cdots ,{\mathrm{s}}_n\}$, define the set of differences of s as the set of non-zero differences $\{{\mathrm{s}}_2-{\mathrm{s}}_1,{\mathrm{s}}_3-{\mathrm{s}}_2,\dots ,{\mathrm{s}}_n-{\mathrm{s}}_{n-1}\}$. That is, zero-differences, ${\mathrm{s}}_i-{\mathrm{s}}_{i-1}=0$, are discarded.

Take as examples the following sorted multisets: $\mathrm{t}=\{1,3,7\},\mathrm{s}=\{1,1,1,3,7,7\}$ and $\mathrm{r}=\{2,6,6,6,8\}$. These three multisets have the same set of differences, which is $\{2,4\}$.

Although $\mathrm{r}$ has the same set of differences as $\mathrm{s}$ and $\mathrm{t}$, note that the differences appear in a different order; 4 appeared first then 2.

Testing for containment

Let $\mathrm{s}$ and $\mathrm{t}$ be ordered multisets, $\mathrm{s}=\{{\mathrm{s}}_1,{\mathrm{s}}_2,\cdots ,{\mathrm{s}}_d\}$ and none of the elements of $\mathrm{t}=\{{\mathrm{t}}_1,{\mathrm{t}}_2,\cdots ,{\mathrm{t}}_n\}$ are repeated.

It can be observed that:

• If $\mathrm{s}\subset \mathrm{t}$ and ${\mathrm{s}}_d={\mathrm{t}}_n$, then $\mathrm{s}$ and $\mathrm{t}$ have the same set of differences and the differences appear in the same order.

• If $\mathrm{s}$ and $\mathrm{t}$ have the same set of differences except for the differences’ order of appearance, then $\mathrm{s}\not\subset \mathrm{t}$.

• If $\mathrm{s}$ and $\mathrm{t}$ have the same set of differences and the differences appear in the same order, then $\mathrm{s}\subset \mathrm{t}$.

It follows from these three observations that the criteria for testing containment $\mathrm{s}\subset \mathrm{t}$ boils down to checking:

1. The equality of the sets of differences, and
2. The order in which the differences $(a_j-a_{j-1})$ appear in both multisets are the same.

Testing for repeated elements

Consider again the ordered multisets: $\mathrm{s}=\{{\mathrm{s}}_1,{\mathrm{s}}_2,\cdots ,{\mathrm{s}}_d\}$ and $\mathrm{t}=\{{\mathrm{t}}_1,{\mathrm{t}}_2,\cdots ,{\mathrm{t}}_n\}$.

If $\mathrm{s}$ has some repeated elements, ${\mathrm{s}}_i-{\mathrm{s}}_{i-1}=0$ for some $1\le i\le n$, then these can be tested by comparing randomized sets of differences.

A randomized set of differences related to $\mathrm{s}$ is created by selecting a random field element $\beta \in \mathbb{F}$ and defined as the set $\{s_i+\beta \cdot s_{i+1}|1\le i<d\}$.

So, instead of a pair $({\mathrm{s}}_i,{\mathrm{s}}_{i+1})$ of repeated elements yielding a difference of zero because $({\mathrm{s}}_i\equiv {\mathrm{s}}_{i+1})$, they yield: $${\mathrm{s}}_i+\beta \cdot {\mathrm{s}}_{i+1}=(1+\beta )\cdot$$ in the setting of randomized set of differences.

This property of repeated elements yielding a multiple of $(1+\beta )$, characterizes repeated elements in ordered multisets. Consequently, when computing randomized set of differences, repeated elements can be identified by these multiples of $(1+\beta )$.

A test can therefore be coined using a grand product argument akin to the one used in PLONK’s permutation argument [GWC19].

Vectors

The above concepts defined for multisets apply similarly to vectors, and the Plookup protocol also extends readily to vectors.

A vector is a collection of ordered field elements, for some finite field $\mathbb{F}$, and it is denoted by $a=(a_1,a_2,\cdots ,a_n)$.

A vector $a=(a_1,a_2,\cdots ,a_n)$ is contained in a vector $b=(b_1,b_2,\cdots ,b_d)$, denoted by $a\subset b$, if each $a_i\in \{b_1,b_2,\cdots ,b_d\}$ for $i\in \{1,2,\cdots ,n\}$.

The vector of differences of a given vector $a=(a_1,a_2,\cdots ,a_n)$ is defined as the vector $a^{\prime }=(a_2-a_1,a_3-a_2,\cdots ,a_n-a_{n-1})$, which has one less component (or element) compared to a. That is, $|a^{\prime }|=n-1$ because $|a|=n$.

Given a random scalar $\beta$ in a field F and a vector $a=(a_1,a_2,\cdots ,a_n)$, a randomized vector of differences of $a$ is defined as $a^{\prime }=(a_1+\beta \cdot a_2,a_2+\beta \cdot a_3,\cdots ,a_{n-1}+\beta \cdot a_n)$.

The concatenation of vectors $a=(a_1,a_2,\cdots ,a_n)$ and $b=(b_1,b_2,\cdots ,b_d)$ is the vector $(a,b)=(a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_d)$​, and it has n+d components.

Plookup protocol

The context of Plookup is within a polynomial commitment scheme, where a party $\mathcal{P}$ ,called the prover, seeks to convince the second party $\mathcal{V}$, called the verifier, that it knows a certain polynomial.

The protocol, as described in the Plookup paper, mentions a third party called the Ideal party, denoted by $\mathcal{I}$, which is also called the trusted party.

It is this trusted party who is responsible for generating all the proof-verification system parameters. Among these parameters are the so-called preprocessed polynomials.

In the case of a non-interactive proof-verification system, the trusted party is equipped so as to act as an intermediary between the prover and the verifier.

1. The protocol starts with the generation of preprocessed polynomials {$\mathrm{t}$} and describing them as a Lookup Table.

2. Prover submits messages in the form of polynomials {$\mathrm{f}$} expressed either as multisets or vectors.

3. The verifier also sends randomly selected field elements ${\alpha }_i\subset \mathbb{F}$, called challenges.

4. The prover then evaluates a special polynomial $Z[X]$ on the ${\alpha }_i$’s and sends them to $\mathcal{I}$.

5. The verifier subsequently requests I to check if certain polynomial identities $F\equiv G$ hold true.

6. The verifier accepts the prover’s submissions as true if all identities hold true, otherwise it rejects.

The polynomials F and G in the polynomial identities {F≡G} are bi-variate polynomials in β and γ, related to randomized sets of differences associated with {f} and {t}. They are defined in terms of grand product expressions seen below: $$\begin{gathered} F(\beta ,\gamma )=(1+\beta {)}^n\prod _{i\in [n]}(\gamma +f_i)\prod _{i\in [d-1]}(\gamma (1+\beta )+t_i+\beta t_{i+1}) \\ G(\beta ,\gamma )=\prod _{i\in [n+d+1]}(\gamma (1+\beta )+s_i+\beta \cdot s_{i+1}) \end{gathered}$$

where $\beta$ and $\gamma$ are the randomly selected field elements.

The Plookup protocol boils down to proving that the two polynomials $F$ and $G$ are the same by comparing vectors of their evaluations and multiplicities of elements in those vectors. Simply put, it checks if two polynomials are the same up to multiplicities of elements in their witness vectors.

Plookup in PIL

The test for whether the polynomial identities $F\equiv G$ hold true, is based on the following lemma (viz. Claim 3.1 as stated and proved in pages 4 and 5 of the Plookup paper).

A Plookup applies to Polynomial Commitment Scheme settings, where the polynomials are expressed as vectors; $\mathrm{t}$, $\mathrm{f}$ and $\mathrm{s}=(\mathrm{f},\mathrm{t})$. It is therefore a test of inclusion, denoted by $\mathrm{f}\subset \mathrm{t}$.

In the zkEVM setting, Plookup typically appears in PIL code as: $$\{{\mathrm{f}}_1,\cdots ,{\mathrm{f}}_m\}\text{in}\{{\mathrm{t}}_1,\cdots ,{\mathrm{t}}_m\}$$ where in is a PIL keyword for set inclusion, $\mathrm{f}\subset \mathrm{t}$​.

Plookup in zkProver

The commitment of the Plookup protocol is implemented on round 2 of eSTARK. The prover computes the reducing challenges $\alpha ,\beta \in \mathbb{F}$:

Using $\alpha$ and $\beta$, the prover computes the inclusion polynomials $h_{i,1},h_{i,2}\in {\mathbb{F}}_{<n}[X]$ for each inclusion argument, with $i\in [M]$, and commits to them.