Recap and First Protocol

We now have the tools to define a preliminary validation protocol for computing the squared 4th Fibonacci number. Here's an outline of each party's steps:

1. Setup

1. (Both) Fix a working field ${\mathbb{F}}_p$ and note that we will interpolate polynomials of degree $\le 3$.
2. (Both) Compute selector polynomials $qL,qR,qM$ corresponding to this circuit.

2. Prover Computation

1. (Prover $P$) Computes the 4th Fibonacci number squared $F_4^2$ by forming a table of intermediate values, then interpolates them as 3rd-degree polynomials:

   $$a(x),b(x),c(x).$$

   as well as selectors $qL(x),qR(x),qM(x)$.

2. (Prover $P$) Computes

   $$t(x)=qL(x)\cdot a(x)+qR(x)\cdot b(x)+qM(x)\cdot (a(x)\cdot b(x))-c(x)$$

   as well as the quotient polynomial $Q(x)$ satisfying

   $$t(x)=Q(x)\cdot Z(x).$$

3. (Prover $P$) Similarly constructs

   $$f_1(x)=a(x+1)-b(x),f_2(x)=b(x+1)-c(x),$$

   along with their quotient polynomials

   $$Q_1(x),Q_2(x)$$

   using $Z_1(x)$ for the domain $\{1,2\}$.

3. Prover → Verifier Communication

1. (Prover $P$) Sends the polynomials$$a(x),b(x),c(x),Q(x),Q_1(x),Q_2(x)$$to the Validator $V$.

4. Verifier Checks

1. (Verifier $V$) Checks the base conditions:

   $$a(1)=0,b(1)=1.$$

2. (Verifier $V$) Computes $t(x)=qL(x)\cdot a(x)+qR(x)\cdot b(x)+qM(x)\cdot (a(x)\cdot b(x))-c(x)$ and verifies

   $$t(x)=Q(x)\cdot Z(x).$$

   That is, $t(x)$ is indeed divisible by $Z(x)$.

3. (Verifier $V$) Checks the recursive constraints:

   $$f_1(x)=Q_1(x)\cdot Z_1(x),f_2(x)=Q_2(x)\cdot Z_1(x).$$

4. (Verifier $V$) Checks the square gate constraints:

   $$f_3(4)=c(3)-b(4)=0,f_4(4)=a(4)-b(4)=0.$$

5. (Verifier $V$) If all checks pass, the Verifier concludes

   $$c(4)\text{is the correct value of }{F}_4^2.$$

This protocol is correct but seems quite inefficient: instead of doing only 3 additions and one multiplication, we end up performing polynomial multiplications of polynomials of degree 3 over a very large prime field ${\mathbb{F}}_p$. We will now consider a more efficient version.