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

$\text{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{array}{rl}& n,([1{]}_1,[x{]}_1,\dots ,[x^{n+3}{]}_1).\end{array}$$

Prover Algorithm

Prover Input: A vector

$\text{boldsymbol}f=(f_1,f_2,\dots ,f_n)$ describing the query values and a vector

$\text{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}$.

2. 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{array}{rl}f(X)& =(b_{1}X+b_2)Z_H(X)+\sum _{i=1}^n{f}_i{L}_i(X),\\ t(X)& =(b_{3}X+b_4)Z_H(X)+\sum _{i=1}^n{t}_i{L}_i(X).\end{array}$$

3. Let

   $\text{boldsymbol}s\in {\mathbb{F}}^{2n}$ be the vector that is
   $(\text{boldsymbol}f,\text{boldsymbol}t)$ sorted by
   $\text{boldsymbol}t$. We represent
   $\text{boldsymbol}s$ by the vectors
   $\text{boldsymbol}{h}_1,\text{boldsymbol}{h}_2\in {\mathbb{F}}^n$ as follows:
   
   $$\begin{array}{rl}\text{boldsymbol}{h}_1& =(s_1,s_3,\dots ,s_{2n-1}),\\ \text{boldsymbol}{h}_2& =(s_2,s_4,\dots ,s_{2n}).\end{array}$$

4. Compute the polynomials

   $h_1(X)\in {\mathbb{F}}_{<n+3}[X]$, and
   $h_2(X)\in {\mathbb{F}}_{<n+2}[X]$:
   
   $$\begin{array}{rl}{h}_1(X)& =(b_5{X}^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{array}$$

5. Compute

   $[f(x){]}_1$,
   $[t(x){]}_1$,
   $[h_1(x){]}_1$ and
   $[h_2(x){]}_1$.

The first output of the prover is

$([f(x){]}_1,[t(x){]}_1,[h_1(x){]}_1,[h_2(x){]}_1)$.

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),\gamma =\mathsf{Hash}(\mathsf{transcript},1).$$

2. Compute the permutation polynomial

   $z(X)\in {\mathbb{F}}_{<n+3}[X]$:
   
   $$\begin{array}{rl}z(X)=& (b_8{X}^2+b_{9}X+b_{10})Z_H(X)+L_1(X)\\ & +\sum _{i=1}^{n-1}(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})}).\end{array}$$

3. Compute

   $[z(x){]}_1$.

The second output of the prover is

$([z(x){]}_1)$.

Round 3:

1. Compute the quotient challenge

   $\alpha \in {\mathbb{F}}_p$
   
   $$\alpha =\mathsf{Hash}(\mathsf{transcript}),$$

2. Compute the quotient polynomial

   $q(X)\in {\mathbb{F}}_{<2n+7}[X]$:
   
   $$\begin{array}{r}q(X)=\frac{1}{Z_H(x)}(\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}\end{array}$$

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).$$

2. Compute

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

The third output of the prover is

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

Round 4:

1. Compute the evaluation challenge

   ${\displaystyle \mathfrak{z}\in {\mathbb{F}}_p}$:
   
   $$\mathfrak{z}=\mathsf{Hash}(\mathsf{transcript}),$$

2. Compute the opening evaluations:
   

   $$\begin{array}{rl}& f(\mathfrak{z}),t(\mathfrak{z}),h_2(\mathfrak{z}),\\ t(\mathfrak{z}& \omega ),z(\mathfrak{z}\omega ),h_1(\mathfrak{z}\omega ).\end{array}$$

The fourth output of the prover is

$(f(\mathfrak{z}),t(\mathfrak{z}),h_2(\mathfrak{z}),t(\mathfrak{z}\omega ),z(\mathfrak{z}\omega ),h_1(\mathfrak{z}\omega ))$.

Round 5:

1. Compute the opening challenge

   $v\in {\mathbb{F}}_p$:
   
   $$v=\mathsf{Hash}(\mathsf{transcript}),$$

2. Compute the linearisation polynomial

   $r(X)\in {\mathbb{F}}_{<n+4}[X]$:
   
   $$\begin{array}{rl}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{array}$$

3. 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{array}{rl}{W}_{\mathfrak{z}}(X)& =\frac{1}{X-\mathfrak{z}}[r(X)+v(f(X)-f(\mathfrak{z}))+v^2(t(X)-t(\mathfrak{z}))+v^3(h_2(X)-h_2(\mathfrak{z}))]\\ W_{\mathfrak{z}\omega }(X)& =\frac{1}{X-\mathfrak{z}\omega }[(t(X)-t(\mathfrak{z}\omega ))+v(z(X)-z(\mathfrak{z}\omega ))+v^2(h_1(X)-h_1(\mathfrak{z}\omega ))]\end{array}$$

4. Compute

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

The fifth output of the prover is

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

The complete proof is:

$$\pi =\left(\begin{array}{rl}[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\\ & f(\mathfrak{z}),t(\mathfrak{z}),h_2(\mathfrak{z}),t(\mathfrak{z}\omega ),z(\mathfrak{z}\omega ),h_1(\mathfrak{z}\omega )\end{array}\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$.

2. 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}$.

3. Validate that

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

4. 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$.

5. Compute the zero polynomial evaluation

   $Z_H(\mathfrak{z})={\mathfrak{z}}^n-1$.

6. Compute the Lagrange polynomial evaluation

   $L_1(\mathfrak{z})=\frac{\omega ({\mathfrak{z}}^n-1)}{n(\mathfrak{z}-\omega )}$.

7. 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{array}{r}-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{array}$$
   and let
   $r^{\prime }(X):=r(X)-r_0$.

9. Compute the first part of the batched polynomial commitment

   ${\left[D\right]}_1:=[r^{\prime }(x)]+u(v[z(x){]}_1+v^2[h_1(x){]}_1)$:
   
   $$\begin{array}{rl}{\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 ))+u{v}^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{array}$$

10. Compute the full batched polynomial commitment

    $[F{]}_1$:
    
    $$\begin{array}{rl}[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{array}$$

11. Compute the group-encoded batch evaluation

    $[E{]}_1$:
    
    $$[E{]}_1:=[-r_0+vf(\mathfrak{z})+v^{2}t(\mathfrak{z})+v^3{h}_2(\mathfrak{z})+u(t(\mathfrak{z})+vz(\mathfrak{z})+v^2{h}_1(\mathfrak{z})){]}_1$$

12. Finally, batch validate all evaluations:
    

    $$e([W_{\mathfrak{z}}(x){]}_1+u\cdot [W_{\mathfrak{z}\omega }(x){]}_1,[x{]}_2)\stackrel{?}{=}e(\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).$$

tags: Plookup