The recursive function z

Now that we have both the numerator and denominator functions, and the partial accumulators we can proceed to spell out the interactive protocol that allows the (potentially malicious) prover to prove that the permutation holds over the three columns $a$,$b$,$c$ in an efficient way. Note that the following function has an interesting property, which is that it can be defined recursively:

$$z(i+1)=\frac{\mathsf{acc}\mathsf{\_}\mathsf{numerator}(i+1)}{\mathsf{acc}\mathsf{\_}\mathsf{denominator}(i+1)}=z(i)\cdot \frac{\mathsf{numerator}(i)}{\mathsf{denominator}(i)}$$

Moreover, the base case is $z(1)=1$. We would like also to be able to prove that $z(n+1)=1$, given that this represents the grand product argument when considering all indexes.

We can develop a succinct argument using polynomials by following these steps:

• We assume the prover has already commited to $a,b,c$.
• The verifier challenges the prover with random $\beta$ and $\gamma \in {\mathbb{F}}_p$.
• The prover interpolates $z$ over $\mathrm{\Omega }$ by computing each of the points for $i=1,\dots ,n$.
• The prover interpolates polynomials $N$ and $D$ corresponding to the $\mathsf{numerator}$ and $\mathsf{denominator}$ functions.
• The prover computes the quotient polynomial $Q_z$ for the polynomial $z\cdot N-D\cdot z(x\cdot \omega )$ and commits to it.
• The verifier checks the following two properties
  • $z(\omega )=1$
  • $z\cdot N-D\cdot z(x\cdot \omega )=0$

It is interesting to note that in the multiplicative domain, $z(\omega )=1$ automatically implies $z({\omega }^{n+1})=1$. This follows from:

$$z({\omega }^{n+1})=z({\omega }^n\cdot \omega )=z(\omega )=1$$

Exercise 17

Compute a function that receives as parameters the three polynomials $a,b,c$ , the challenges $\beta ,\gamma$ and the domain $\mathrm{\Omega }$ and returns the interpolation fo the $z$, $N$ and $D$ polynomials.

def interpolate_z_N_D(a,b,c, beta, gamma, Ω):
#TBD
    return z,N,D

z,N,D = interpolate_z_N_D(a,b,c,42,42,Ω)

If computed correctly, the interpolated functions should pass the $z(\omega )=1$ check as follows.

L1 = prod((x - ω**m)//(ω - ω**m) for m in range(2,n+1))
L1=R(L1)
ZH = R(x^n-1)
(ZH).divides(L1*(z-1))

Moreover it should pass the following check, which proves the recursive constraint.

(ZH).divides( z*N -D*z(x*ω))

The polynomial $z(x)\cdot N(x)-D(x)\cdot z(x\ast \omega )$ is:

$$\begin{array}{rl}z(x)\cdot N(x)-D(x)\cdot z(x\cdot \omega )=& 19088033315219631021107812019832839306780395371633216223270161982137379434783x^6\\ & +9442345120481651903520919226899454023736002770233426083846080860317389062734x^5\\ & +21082329243894486516657209903907612685168280090308035096051805040844722189074x^4\\ & +2800209556619644201138593725424435781767969028782818120428042204438429060834x^2\\ & +12445897751357623318725486518357821064812361630182608259852123326258419432883x\\ & +805913627944788705589195841349662403380084310107999247646399145731086306543\end{array}$$

show(z*N -D*z(x*ω))