New Protocol Version

We divide the protocol into Setup, Prover Computation, Verifier Challenge, and Proof & Verification phases.

1. Setup Phase

1. (Both) Agree on the public parameters $(S_1,S_2)$.
2. (Verifier) Publicly specifies the maximum polynomial degree $d$, if needed.
3. (Trusted Ceremony / Setup) Generates a secret $\tau$ and produces $(S_1,S_2)$.
   After this step, $\tau$ (the toxic waste) must be discarded to maintain security.

2. Prover Computation Phase

1. (Prover) Interpolates the column polynomials $a(x),b(x),c(x)$.
2. (Prover) Constructs quotient polynomials $Q(x),Q_1(x),Q_2(x)$ with respect to the vanishing polynomials $Z(x),Z_1(x)$.
3. (Prover) Commits to each polynomial by computing$$c_a=\text{commit}(a),c_b=\text{commit}(b),c_c=\text{commit}(c),c_Q=\text{commit}(Q),\dots$$and sends these commitments to the Verifier.

3. Verifier Challenge Phase

1. (Verifier) Samples random challenges ${\gamma }_1,{\gamma }_2,{\gamma }_3$.
2. (Verifier) Sends the challenges to the Prover.

4. Proof & Verification Phase

1. (Prover) Evaluates each committed polynomial at its corresponding challenge. For example,

   $$a({\gamma }_1),b({\gamma }_1),c({\gamma }_1),Q({\gamma }_1).$$

   Then constructs proofs ${\pi }_a,{\pi }_b,{\pi }_c,{\pi }_Q$ via the KZG evaluation method. The Prover sends

   $$(a({\gamma }_1),b({\gamma }_1),c({\gamma }_1),Q({\gamma }_1))$$

   and

   $$({\pi }_a,{\pi }_b,{\pi }_c,{\pi }_Q)$$

   to the Verifier.

2. (Verifier) Uses the commitments $(c_a,c_b,c_c,c_Q)$ and the proofs ${\pi }_a,{\pi }_b,{\pi }_c,{\pi }_Q$ to verify each polynomial evaluation.
   It then checks the constraint

   $$a({\gamma }_1)+b({\gamma }_1)-c({\gamma }_1)=Q({\gamma }_1)\cdot Z({\gamma }_1).$$

   Since the Verifier can construct $Z(x)$ itself, it only needs to check $t({\gamma }_1)=Q({\gamma }_1)Z({\gamma }_1)$, where $t(x)=qL(x)\cdot a(x)+qR(x)\cdot b(x)+qM(x)\cdot (a(x)\cdot b(x))-c(x)$.

3. (Verifier) Repeats a similar check for the recursive constraints:

   $$a({\gamma }_2+1)-b({\gamma }_2)=Q_1({\gamma }_2)\cdot Z_1({\gamma }_2),$$$$b({\gamma }_3+1)-c({\gamma }_3)=Q_2({\gamma }_3)\cdot Z_1({\gamma }_3).$$

4. (Verifier) If all these checks pass, the Verifier accepts. Otherwise, it rejects.

As you can see, both the number of message exchanges and the operations performed by the Verifier are now almost constant. In other words, the Verifier can ask the Prover to compute $F_6^2$ or $F_{1000}^2$ and still carry out about the same number of computations. The only operation dependent on the number of rows of the circuit on the verifier's side is the computation of the vanishing polynomials $Z$ and $Z_1$.

Protocol Diagram

The following diagram visually represents the four main phases of the protocol:

1. Phase 1: Setup

   • Both parties agree on the public parameters $(S_1,S_2)$.
   • The Verifier may specify the maximum polynomial degree $d$.
   • A trusted ceremony generates the secret $\tau$, then discards it, while producing the public parameters $(S_1,S_2)$.

2. Phase 2: Prover Computation

   • The Prover interpolates the circuit columns (e.g., Fibonacci) into polynomials $a(x),b(x),c(x)$.
   • Constructs the quotient polynomials $Q(x),Q_1(x),Q_2(x)$ relative to vanishing polynomials $Z,Z_1$.
   • Commits to these polynomials (e.g., $c_a,c_b,c_c,c_Q,\dots$) and sends the commitments to the Verifier.

3. Phase 3: Verifier Challenge

   • The Verifier randomly samples challenges ${\gamma }_1,{\gamma }_2,{\gamma }_3$.
   • Sends these challenges to the Prover.

4. Phase 4: Proof & Verification

   • The Prover evaluates each committed polynomial at the corresponding $\gamma$ value and constructs proofs (e.g., ${\pi }_a,{\pi }_b$).
   • Sends the polynomial evaluations and proofs to the Verifier.
   • The Verifier checks that the evaluations match the commitments, confirming equations like$$t({\gamma }_1)=Q({\gamma }_1)\cdot Z({\gamma }_1).$$
   • If all checks pass, the Verifier accepts; otherwise, it rejects.