# Final Plookup Protocol, Rolled Out

## Terminology \& Notation

We consider $\mathbb{F}$ a finite field of prime order $p$, i.e., $\mathbb{F} = \mathbb{Z}_p$.
For a given integer $n$, we denote by $[n]$ the set of integers $\{1,...,n\}$.
We explicitly define the multiplicative subgroup $H\subset\mathbb{F}$ as the subgroup containing the $n$-th roots of unity in $\mathbb{F}$, where $\omega$ is a primitive $n$-th root of unity and a generator of $H$. That is,
$$
H = \{\omega, \dots, \omega^{n-1}, \omega^n = 1\}.
$$

We denote by $\mathbb{F}_{<n}[X]$ the set of univariate polynomials over $\mathbb{F}$ of degree strictly smaller than $n$.

For a polynomial $f(x) \in \mathbb{F}_{<n}[X]$ and $i \in [n]$, we sometimes denote $f_i := f(\omega^i)$. For a vector $\boldsymbol{f} \in \mathbb{F}^n$, we also denote by $f(x)$ the polynomial in $\mathbb{F}_{<n}[X]$ with $f(\omega^i) = f_i$.

The Lagrange polynomial $L_i(X) \in \mathbb{F}_{<n}[X]$ for $i \in [n]$ has the form
$$
L_i(X) = \frac{\omega^i\:(X^n - 1)}{n\:(X - \omega^i)}.
$$

Thus, the zero polynomial $Z_H(X) \in \mathbb{F}_{<n+1}[X]$ is defined as
$$
Z_H(X) = (X - \omega) \cdots (X - \omega^{n-1})(X - \omega^n) = X^n - 1.
$$

## Protocol

**Common Preprocessed Input**

\begin{align}
&n, \quad \left([1]_1, [x]_1, \dots, [x^{n+3}]_1\right).
\end{align}

<!--
**Public Input**: The vector $\boldsymbol{t} = (t_1, t_2, \dots, t_n)$ describing the lookup values.
-->

### Prover Algorithm

**Prover Input**: A vector $\boldsymbol{f} = (f_1, f_2, \dots, f_n)$ describing the query values and a vector $\boldsymbol{t} = (t_1, t_2, \dots, t_n)$ describing the lookup values.

**Round 1:**

1. Generate random blinding scalars $b_1, b_{2}, \dots, b_{12}\in \mathbb{F}$.

1. Compute the query polynomial $f(X) \in \mathbb{F}_{<n+2}[X]$ and the lookup polynomial $t(X) \in \mathbb{F}_{<n+2}[X]$:
\begin{align*}
f(X) &= (b_1X+b_2)Z_H(X)+\sum_{i=1}^{n} f_iL_i(X), \\
t(X) &= (b_3X+b_4)Z_H(X)+\sum_{i=1}^{n} t_iL_i(X).
\end{align*}

1. Let $\boldsymbol{s} \in \mathbb{F}^{2n}$ be the vector that is $(\boldsymbol{f}, \boldsymbol{t})$ sorted by $\boldsymbol{t}$. We represent $\boldsymbol{s}$ by the vectors $\boldsymbol{h_1}, \boldsymbol{h_2} \in \mathbb{F}^n$ as follows:
\begin{align*}
\boldsymbol{h_1} &= (s_1, s_3, \dots, s_{2n-1}), \\
\boldsymbol{h_2} &= (s_2, s_4, \dots, s_{2n}).
\end{align*}

1. Compute the polynomials $h_1(X)\in \mathbb{F}_{<n+3}[X]$, and $h_2(X) \in \mathbb{F}_{<n+2}[X]$:
\begin{align*}
h_1(X) &= (b_5X^2+b_{6}X+b_7)Z_H(X) + \sum_{i=1}^{n} s_{2i-1}L_i(X), \\
h_2(X) &= (b_{8}X+b_{9})Z_H(X) + \sum_{i=1}^{n} s_{2i}L_i(X).
\end{align*}

1. Compute $[f(x)]_1$, $[t(x)]_1$, $[h_1(x)]_1$ and $[h_2(x)]_1$.

The first output of the prover is $\left([f(x)]_1, [t(x)]_1, [h_1(x)]_1, [h_2(x)]_1\right)$.
:::success
Open question: can the proof size in Round 1 be improved?
:::

**Round 2:**

1. Compute the permutation challenges $\beta, \gamma \in \mathbb{F}_p$:
$$
\beta = \mathsf{Hash}(\mathsf{transcript}, 0), \quad \gamma = \mathsf{Hash}(\mathsf{transcript}, 1).
$$

1. Compute the permutation polynomial $z(X) \in \mathbb{F}_{<n+3}[X]$:
\begin{align*}
z(X) = &~(b_{8}X^2 + b_{9}X + b_{10})Z_H(X) + L_1(X) \\
& + \sum_{i=1}^{n-1} \left( L_{i+1}(X)\prod_{j=1}^{i} \frac{(1+\beta)(\gamma+f_j)(\gamma(1+\beta)+t_j+\beta t_{j+1})}{(\gamma(1+\beta)+s_{2j-1}+\beta s_{2j})(\gamma(1+\beta)+s_{2j}+\beta s_{2j+1})} \right).
\end{align*}

1. Compute $[z(x)]_1$.

The second output of the prover is $\left([z(x)]_1\right)$.

**Round 3:**

1. Compute the quotient challenge $\alpha \in \mathbb{F}_p$
$$
\alpha = \mathsf{Hash}(\mathsf{transcript}),
$$

1. Compute the quotient polynomial $q(X) \in \mathbb{F}_{<2n+7}[X]$:
\begin{align}
q(X) =
\frac{1}{Z_H(x)}
\left(
\begin{array}{l}
z(X) (1+\beta) (\gamma+f(X)) (\gamma(1+\beta)+t(X)+\beta t(X\omega)) \\ - z(X\omega)(\gamma(1+\beta)+h_1(X)+\beta h_2(X)) (\gamma(1+\beta)+h_2(X)+\beta h_1(X\omega))\\+ (z(X)-1)L_1(X)\alpha
\end{array}
\right.
\end{align}
:::success
TODO: Add zero-knowledge to $q$ properly.
:::

1. Split $q(X)$ into one polynomial $q_\text{low}(X)$ of degree lower than $n+3$ and another polynomial $q_\text{high}(X)$ of degree at most $n+3$ such that:
$$q(X) = q_{\text{low}}(X) + X^{n+3}q_{\text{high}}(X).$$

1. Compute $[q_{\text{low}}(x)]_1, [q_{\text{high}}(x)]_1$.

The third output of the prover is $\left([q_{\text{low}}(x)]_1, [q_{\text{high}}(x)]_1\right)$.

**Round 4:**

1. Compute the evaluation challenge $\displaystyle \mathfrak{z} \in \mathbb{F}_p$:
$$
\mathfrak{z} = \mathsf{Hash}(\mathsf{transcript}),
$$

1. Compute the opening evaluations:
\begin{align*}
&f(\mathfrak{z}), \quad t(\mathfrak{z}), \quad h_2(\mathfrak{z}), \\[0.1cm]
t(\mathfrak{z}&\omega), \quad z(\mathfrak{z}\omega), \quad h_1(\mathfrak{z}\omega).
\end{align*}

The fourth output of the prover is $\left(f(\mathfrak{z}), t(\mathfrak{z}), h_2(\mathfrak{z}), t(\mathfrak{z}\omega), z(\mathfrak{z}\omega), h_1(\mathfrak{z}\omega)\right)$.

**Round 5:**

1. Compute the opening challenge $v \in \mathbb{F}_p$:
$$
v = \mathsf{Hash}(\mathsf{transcript}),
$$

1. Compute the linearisation polynomial $r(X) \in \mathbb{F}_{<n+4}[X]$:
\begin{align}
r(X) = &~z(X) (1+\beta) (\gamma+f(\mathfrak{z})) (\gamma(1+\beta)+t(\mathfrak{z})+\beta t(\mathfrak{z}\omega)) \\
&- z(\mathfrak{z}\omega)(\gamma(1+\beta)+h_1(X)+\beta h_2(\mathfrak{z})) (\gamma(1+\beta)+h_2(\mathfrak{z})+\beta h_1(\mathfrak{z}\omega)) \\
&+ \alpha(z(X)-1)L_1(\mathfrak{z}) \\
&- Z_H(\mathfrak{z})(q_\text{low}(X) + \mathfrak{z}^{n+3}q_\text{high}(X)).
\end{align}

1. Compute the opening proof polynomials $W_{\mathfrak{z}}(X) \in \mathbb{F}_{<n+3}[X]$ and $W_{\mathfrak{z}\omega}(X) \in \mathbb{F}_{<n+2}[X]$:
\begin{align*}
W_{\mathfrak{z}}(X) &= \frac{1}{X - \mathfrak{z}}\left[r(
X) + v(f(X) - f(\mathfrak{z})) + v^2(t(X)- t(\mathfrak{z})) + v^3(h_2(X) - h_2(\mathfrak{z}))\right] \\
W_{\mathfrak{z}\omega}(X) &= \frac{1}{X - \mathfrak{z}\omega}\left[(t(X) - t(\mathfrak{z}\omega)) + v(z(X) - z(\mathfrak{z}\omega)) + v^2(h_1(X)- h_1(\mathfrak{z}\omega))\right]
\end{align*}

1. Compute $[W_{\mathfrak{z}}(x)]_1, [W_{\mathfrak{z}\omega}(x)]_1$.

The fifth output of the prover is $\left([W_{\mathfrak{z}}(x)]_1, [W_{\mathfrak{z}\omega}(x)]_1\right)$.

The complete proof is:
$$\pi =
\left(
\begin{align*}
[f(x)]_1, [t(x)]_1, [h_1(x)]_1,& [h_2(x)]_1, [z(x)]_1, [q_{\text{low}}(x)]_1, [q_{\text{high}}(x)]_1, [W_{\mathfrak{z}}(x)]_1, [W_{\mathfrak{z}\omega}(x)]_1 \\[0.1cm]
&f(\mathfrak{z}), t(\mathfrak{z}), h_2(\mathfrak{z}), t(\mathfrak{z}\omega), z(\mathfrak{z}\omega), h_1(\mathfrak{z}\omega)
\end{align*}
\right).
$$

Compute multipoint evaluation challenge $u\in \mathbb{F}$:
$$
u = \mathsf{Hash}(\mathsf{transcript}),
$$

### Verifier Algorithm

**Verifier preprocessed input:** The curve element $[x]_2$.

$\mathcal{V}((t_i)_{i \in [n]},\pi):$

1. Validate that $[f(x)]_1$, $[h_1(x)]_1$, $[h_2(x)]_1$, $[z(x)]_1$, $[q_\text{low}(x)]_1$, $[q_\text{high}(x)]$, $[W_\mathfrak{z}(x)]_1$, $[W_{\mathfrak{z}\omega}(x)]_1 \in \mathbb{G}_1$.

1. Validate that $f(\mathfrak{z}), t(\mathfrak{z}), h_2(\mathfrak{z}), t(\mathfrak{z}\omega), z(\mathfrak{z}\omega), h_1(\mathfrak{z}\omega) \in \mathbb{F}$.

1. Validate that $(t_i)_{i\in[n]}\in\mathbb{F}^{n}$.

1. Compute the challenges $\beta, \gamma, \alpha, \mathfrak{z}, v, u \in \mathbb{F}$ as in prover description, from the common preprocessed inputs, public input, and elements of $\pi$.

1. Compute the zero polynomial evaluation $Z_H(\mathfrak{z}) = \mathfrak{z}^n-1$.

1. Compute the Lagrange polynomial evaluation $L_1(\mathfrak{z}) = \frac{\omega\:(\mathfrak{z}^n - 1)}{n\:(\mathfrak{z} - \omega)}$.

1. Compute the lookup commitment $[t(x)]_1$.
> The previous computation be avoided by forcing the prover to send it.

8. To save a verifier scalar multiplication, we split $r(X)$ into its constant and non-constant terms. Compute $r(X)$'s constant term:
\begin{align}
-r_0 := z(\mathfrak{z}\omega)(\gamma(1+\beta)+\beta h_2(\mathfrak{z}))(\gamma(1+\beta)+h_2(\mathfrak{z})+\beta h_1(\mathfrak{z}\omega)) + \alpha L_1(\mathfrak{z}),
\end{align}
and let $r'(X) := r(X) - r_0$.

9. Compute the first part of the batched polynomial commitment $\left[D\right]_1 := [r'(x)] + u(v[z(x)]_1 + v^2[h_1(x)]_1)$:
\begin{align*}
\left[D\right]_1 := &(( 1+\beta) (\gamma+f(\mathfrak{z})) (\gamma(1+\beta)+t(\mathfrak{z})+\beta t(\mathfrak{z}\omega)) + L_1(\mathfrak{z})\alpha + uv)[z(x)]_1 \\
&+ (- z(\mathfrak{z}\omega)(\gamma(1+\beta)+h_2(\mathfrak{z})+\beta h_1(\mathfrak{z}\omega)) + uv^2) [h_1(x)]_1 \\
&- Z_H(\mathfrak{z})([q_\text{low}(x)]_1 + \mathfrak{z}^{n+3} \cdot [q_\text{high}(x)]_1).
\end{align*}

10. Compute the full batched polynomial commitment $[F]_1$:
\begin{align*}
[F]_1 := ~\left[D\right]_1 & + v \cdot [f(x)]_1 + v^2 \cdot [t(x)]_1 + v^3 [h_2(x)] + u[t(x)]_1.
\end{align*}

11. Compute the group-encoded batch evaluation $[E]_1$:
$$
[E]_1 := \bigg[-r_0 +vf(\mathfrak{z}) + v^2t(\mathfrak{z}) + v^3h_2(\mathfrak{z}) + u(t(\mathfrak{z}) + vz(\mathfrak{z}) + v^2h_1(\mathfrak{z}))\bigg]_1
$$

12. Finally, batch validate all evaluations:
$$
e\left([W_\mathfrak{z}(x)]_1+u\cdot[W_{\mathfrak{z}\omega}(x)]_1, [x]_2\right) \stackrel{?}{=} e\left(\mathfrak{z}\cdot [W_\mathfrak{z}(x)]_1+u(\mathfrak{z}\omega)\cdot[W_{\mathfrak{z}\omega}(x)]_1 + [F]_1 - [E]_1, [1]_2\right).
$$

###### tags: `Plookup`