Optimizing Plookup: The Alternating Method

Multiplicative Subgrup:

$$H=\{\omega ,...,{\omega }^{n-1},{\omega }^n=1\}$$

Involved Vectors:

$$\mathit{f}=(f_1,f_2,\dots ,f_n)\in {\mathbb{F}}^n$$

$$\mathit{t}=(t_1,t_2,\dots ,t_n)\in {\mathbb{F}}^n$$

$$\mathit{s}=(s_1,s_2,\dots ,s_{2n})\in {\mathbb{F}}^{2n}$$

We want to prove:

$$\mathit{f}\subset \mathit{t}.$$

$$\mathit{s}\text{ is }(\mathit{f},\mathit{t})\text{ sorted by }\mathit{t}$$

Let's define the vectors

${\mathit{h}}_{\mathbf{1}},{\mathit{h}}_{\mathbf{2}}\in {\mathbb{F}}^n$ by:

$${\mathit{h}}_{\mathbf{1}}:=(s_1,s_3,....,s_{2n-1})$$

$${\mathit{h}}_{\mathbf{2}}:=(s_2,s_4....,s_{2n})$$

Taking

$\gamma =0$ (to visualize an overview), the objective is to define a vector

$\mathit{Z}$ such that:

$$\begin{array}{rcccccl}{\displaystyle H=\{}& \omega & {\omega }^2& {\omega }^3& \dots & {\omega }^n& \}\\ & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \\ \mathit{Z}=[& 1,& \frac{(1+\beta )f_1(t_1+\beta t_2)}{(s_1+\beta s_2)(s_2+\beta s_3)},& \frac{(1+\beta {)}^2{f}_1{f}_2(t_1+\beta t_2)(t_2+\beta t_3)}{(s_1+\beta s_2)(s_2+\beta s_3)(s_3+\beta s_4)(s_4+\beta s_5)},& \dots ,& \frac{(1+\beta {)}^{n-1}{f}_1\dots f_{n-1}(t_1+\beta t_2)(t_2+\beta t_3)\dots (t_{n-1}+\beta t_n)}{(s_1+\beta s_2)(s_2+\beta s_3)\dots (s_{2n-3}+\beta s_{2n-2})(s_{2n-2}+\beta s_{2n-1})}& ]\end{array}$$

$$Z({\omega }^i)=\{\begin{array}{ll}1,& \text{if }i=1\\ \frac{{\displaystyle (1+\beta {)}^{i-1}\prod _{j=1}^{i-1}(\gamma +f_j)\prod _{j=1}^{i-1}(\gamma (1+\beta )+t_j+\beta t_{j+1})}}{{\displaystyle \prod _{j=1}^{i-1}(\gamma (1+\beta )+s_{2j-1}+\beta s_{2j})(\gamma (1+\beta )+s_{2j}+\beta s_{2j+1})}},& \text{if }i=2,\dots ,n\end{array}$$

$$\begin{array}{r}Z(X\omega )=Z(X)\frac{(1+\beta )(\gamma +f(X))(\gamma (1+\beta )+t(X)+\beta t(X\omega ))}{(\gamma (1+\beta )+h_1(X)+\beta h_2(X))(\gamma (1+\beta )+h_2(X)+\beta h_1(X\omega ))}\end{array}$$

Protocol

1. Prover sends the polynomials
   $h_1(X),h_2(X)$ to the idealizer.
2. Verifier sends random
   $\gamma ,\beta \in \mathbb{F}$ to the prover.
3. Prover sends
   $Z(X)$ to the idealizer.
4. Verifier asks to the idealizer for the following checks:

$$L_1(X)(Z(X)-1)=0$$

$$\begin{gathered} Z(\omega X)(\gamma (1+\beta )+h_1(X)+\beta h_2(X))(\gamma (1+\beta )+h_2(X)+\beta h_1(X\omega ))- \\ -Z(X)(1+\beta )(\gamma +f(X))(\gamma (1+\beta )+t(X)+\beta t(X\omega ))=0 \end{gathered}$$

Example

$$H=\{\omega ,{\omega }^2,{\omega }^3\}$$

$$\begin{array}{l}\mathit{f}=(f_1,f_2,f_3)\\ \mathit{t}=(t_1,t_2,t_3)\\ \mathit{s}=(s_1,s_2,s_3,s_4,s_5,s_6)\\ {\mathit{h}}_{\mathbf{1}}=(s_1,s_3,s_5)\\ {\mathit{h}}_{\mathbf{2}}=(s_2,s_4,s_6)\end{array}$$

By the alternating method:

$$\begin{array}{l}Z(\omega )=1\\ Z({\omega }^2)={\displaystyle \frac{(1+\beta )(\gamma +f_1)(\gamma (1+\beta )+t_1+\beta t_2)}{(\gamma (1+\beta )+s_1+\beta s_2)(\gamma (1+\beta )+s_2+\beta s_3)}}\\ Z({\omega }^3)={\displaystyle \frac{(1+\beta {)}^2(\gamma +f_1)(\gamma +f_2)(\gamma (1+\beta )+t_1+\beta t_2)(\gamma (1+\beta )+t_2+\beta t_3)}{(\gamma (1+\beta )+s_1+\beta s_2)(\gamma (1+\beta )+s_2+\beta s_3)(\gamma (1+\beta )+s_3+\beta s_4)(\gamma (1+\beta )+s_4+\beta s_5)}}\end{array}$$

So, to complete the grand-product (which is intended to be completed at

$Z({\omega }^4)=Z(\omega )$), we only need the factor

$(\gamma +f_3)$ in the numerator, and

$(\gamma (1+\beta )+s_5+\beta s_6)$ in the denominator.

Usign the relation:

$$\begin{array}{rl}Z(X\omega )& =Z(X)\frac{(1+\beta )(\gamma +f(X))(\gamma (1+\beta )+t(X)+\beta t(X\omega ))}{(\gamma (1+\beta )+h_1(X)+\beta h_2(X)(\gamma (1+\beta )+h_2(X)+\beta h_1(X\omega ))}\end{array}$$
we obtain more than these two factors:

$$\begin{array}{rl}Z({\omega }^4)& ={\displaystyle \frac{(1+\beta {)}^3(\gamma +f_1)(\gamma +f_2)(\gamma +f_3)(\gamma (1+\beta )+t_1+\beta t_2)(\gamma (1+\beta )+t_2+\beta t_3)(\gamma (1+\beta )+t_3+\beta t_1)}{(\gamma (1+\beta )+s_1+\beta s_2)(\gamma (1+\beta )+s_2+\beta s_3)(\gamma (1+\beta )+s_3+\beta s_4)(\gamma (1+\beta )+s_4+\beta s_5)(\gamma (1+\beta )+s_5+\beta s_6)(\gamma (1+\beta )+s_6+\beta s_1)}}\\ & ={\displaystyle \frac{(1+\beta {)}^3(\gamma +f_1)(\gamma +f_2)(\gamma +f_3)(\gamma (1+\beta )+t_1+\beta t_2)(\gamma (1+\beta )+t_2+\beta t_3)}{(\gamma (1+\beta )+s_1+\beta s_2)(\gamma (1+\beta )+s_2+\beta s_3)(\gamma (1+\beta )+s_3+\beta s_4)(\gamma (1+\beta )+s_4+\beta s_5)(\gamma (1+\beta )+s_5+\beta s_6)},}\end{array}$$
where we have used that

$t_3=s_6$ and

$t_1=s_1$, i.e., the last element of

$\mathit{t}$ is equal to the last element of

$\mathit{s}$ and the same happens for the first element.

In general, in the case that

$\mathrm{deg}(t(X))=\mathrm{deg}(f(X))$ there will be one more factor

$(\gamma +f_j)$ than the rest in the definition of

$Z(X)$.
This is the reason why in Plookup

$\mathrm{deg}(t(X))=\mathrm{deg}(f(X))+1$.

tags: Plookup