Try   HackMD

Optimizing Plookup: The Alternating Method

Multiplicative Subgrup:

H={ω,...,ωn1,ωn=1}

Involved Vectors:

\boldsymbolf=(f1,f2,,fn)Fn

\boldsymbolt=(t1,t2,,tn)Fn

\boldsymbols=(s1,s2,,s2n)F2n

We want to prove:

\boldsymbolf\boldsymbolt.

\boldsymbols is (\boldsymbolf,\boldsymbolt) sorted by \boldsymbolt

Let's define the vectors

\boldsymbolh1,\boldsymbolh2Fn by:

\boldsymbolh1:=(s1,s3,....,s2n1)

\boldsymbolh2:=(s2,s4....,s2n)

Taking

γ=0 (to visualize an overview), the objective is to define a vector
\boldsymbolZ
such that:
H={ωω2ω3ωn}\boldsymbolZ=[1,(1+β)f1(t1+βt2)(s1+βs2)(s2+βs3),(1+β)2f1f2(t1+βt2)(t2+βt3)(s1+βs2)(s2+βs3)(s3+βs4)(s4+βs5),,(1+β)n1f1fn1(t1+βt2)(t2+βt3)(tn1+βtn)(s1+βs2)(s2+βs3)(s2n3+βs2n2)(s2n2+βs2n1)]

Z(ωi)={1,if  i=1(1+β)i1j=1i1(γ+fj)j=1i1(γ(1+β)+tj+βtj+1)j=1i1(γ(1+β)+s2j1+βs2j)(γ(1+β)+s2j+βs2j+1),if  i=2,,n

Z(Xω)=Z(X)(1+β)(γ+f(X))(γ(1+β)+t(X)+βt(Xω))(γ(1+β)+h1(X)+βh2(X))(γ(1+β)+h2(X)+βh1(Xω))

Protocol

  1. Prover sends the polynomials
    h1(X),h2(X)
    to the idealizer.
  2. Verifier sends random
    γ,βF
    to the prover.
  3. Prover sends
    Z(X)
    to the idealizer.
  4. Verifier asks to the idealizer for the following checks:

L1(X)(Z(X)1)=0

Z(ωX)(γ(1+β)+h1(X)+βh2(X))(γ(1+β)+h2(X)+βh1(Xω))Z(X)(1+β)(γ+f(X))(γ(1+β)+t(X)+βt(Xω))=0

Example

H={ω,ω2,ω3}

\boldsymbolf=(f1,f2,f3)\boldsymbolt=(t1,t2,t3)\boldsymbols=(s1,s2,s3,s4,s5,s6)\boldsymbolh1=(s1,s3,s5)\boldsymbolh2=(s2,s4,s6)

By the alternating method:

Z(ω)=1Z(ω2)=(1+β)(γ+f1)(γ(1+β)+t1+βt2)(γ(1+β)+s1+βs2)(γ(1+β)+s2+βs3)Z(ω3)=(1+β)2(γ+f1)(γ+f2)(γ(1+β)+t1+βt2)(γ(1+β)+t2+βt3)(γ(1+β)+s1+βs2)(γ(1+β)+s2+βs3)(γ(1+β)+s3+βs4)(γ(1+β)+s4+βs5)

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

Z(ω4)=Z(ω)), we only need the factor
(γ+f3)
in the numerator, and
(γ(1+β)+s5+βs6)
in the denominator.

Usign the relation:

Z(Xω)=Z(X)(1+β)(γ+f(X))(γ(1+β)+t(X)+βt(Xω))(γ(1+β)+h1(X)+βh2(X)(γ(1+β)+h2(X)+βh1(Xω))
we obtain more than these two factors:
Z(ω4)=(1+β)3(γ+f1)(γ+f2)(γ+f3)(γ(1+β)+t1+βt2)(γ(1+β)+t2+βt3)(γ(1+β)+t3+βt1)(γ(1+β)+s1+βs2)(γ(1+β)+s2+βs3)(γ(1+β)+s3+βs4)(γ(1+β)+s4+βs5)(γ(1+β)+s5+βs6)(γ(1+β)+s6+βs1)=(1+β)3(γ+f1)(γ+f2)(γ+f3)(γ(1+β)+t1+βt2)(γ(1+β)+t2+βt3)(γ(1+β)+s1+βs2)(γ(1+β)+s2+βs3)(γ(1+β)+s3+βs4)(γ(1+β)+s4+βs5)(γ(1+β)+s5+βs6),

where we have used that
t3=s6
and
t1=s1
, i.e., the last element of
\boldsymbolt
is equal to the last element of
\boldsymbols
and the same happens for the first element.

In general, in the case that

deg(t(X))=deg(f(X)) there will be one more factor
(γ+fj)
than the rest in the definition of
Z(X)
.
This is the reason why in Plookup
deg(t(X))=deg(f(X))+1
.

tags: Plookup