Second Protocol Version (Succinct, Probabilistic Check)

This improved protocol builds on our earlier version by using:

1. Random challenges sampled by the validator ${\gamma }_1,{\gamma }_2,{\gamma }_3$,
2. Single-point polynomial evaluations to check $t({\gamma }_1)=Q({\gamma }_1)Z({\gamma }_1),f_1({\gamma }_2)=Q_1({\gamma }_2)Z_1({\gamma }_2),f_2({\gamma }_3)=Q_2({\gamma }_3)Z_1({\gamma }_3)$.

This lowers the verification cost from a full polynomial multiplication ($O(d^2)$) to an $O(d)$ evaluation, making verification more succinct.

Protocol Flow

1. Compute Fibonacci & Circuit Polynomials

   • (Prover) Generates $F_4^2$ by building the full circuit table.
   • (Prover) Encodes the circuit columns as polynomials $a(x),b(x),c(x)$.

2. Compute Constraint Polynomials

   • (Prover) Defines $t(x)=qL(x)\cdot a(x)+qR(x)\cdot b(x)+qM(x)\cdot (a(x)\cdot b(x))-c(x)$ and finds $Q(x)$ such that $t(x)=Q(x)\cdot Z(x)$.
   • (Prover) Similarly, for the recursive constraints: $f_1(x)=a(x+1)-b(x),$$f_2(x)=b(x+1)-c(x),$ with quotient polynomials $Q_1(x),Q_2(x)$ satisfying $f_1(x)=Q_1(x)\cdot Z_1(x)$ and $f_2(x)=Q_2(x)\cdot Z_1(x)$.

3. Send Polynomials

   • (Prover) Sends $a(x),b(x),c(x),Q(x),Q_1(x),Q_2(x)$ to the validator.

4. Verification (Random Challenge & Single-Point Check)

   • (Validator) Samples random values ${\gamma }_1,{\gamma }_2,{\gamma }_3\in {\mathbb{F}}_p$.

   • (Valdiator) Computes on its own: $t({\gamma }_1),f_1({\gamma }_2),f_2({\gamma }_3)$

   • (Validator) Checks:

     $$t({\gamma }_1)\stackrel{?}{=}Q({\gamma }_1)Z({\gamma }_1),f_1({\gamma }_2)\stackrel{?}{=}{Q}_1({\gamma }_2)Z_1({\gamma }_2),f_2({\gamma }_3)\stackrel{?}{=}{Q}_2({\gamma }_3)Z_1({\gamma }_3).$$

   • By the Schwartz–Zippel Lemma, if $t(x)\ne Q(x)Z(x)$ (etc.) the probability it also coincides at a random $\gamma$ is at most $\frac{d}{p}$.

5. Accept or Reject

   • (Validator) If all checks pass, the proof is accepted; otherwise, it is rejected.

Diagram of Protocol

Below is a simplified diagram illustrating these steps:

With this approach, the validator does a constant amount of final checks (polynomial evaluations), regardless of the polynomial degree $d$, achieving succinct verification.