Univariate polynomial zero check requires O(n \log(n)) prover and O(1) verifier complexity.
Here we propose another univariate zero check protocol, which is based on the same idea as Sangria protocol, but with a different folding object.
We will split and fold execution trace polynomials, twice decreasing the degree of polynomials in each step.
The prover complexity of this method is O(n) and the verifier complexity is O(\log(n)).
Split and fold
Let’s consider the polynomial expression
where a_i, b_j, c_k, d_i, e_j, f_i are polynomials with degree less than n=2^m over a field \mathbb{F},
and p(x)=0 if x \in \mathbb{H}, where \mathbb{H} is a multiplicative subgroup of \mathbb{F}, and |\mathbb{H}| = n.
We represent here a protocol, using additive-homomorphic polynomial commitments (KZG10, IPA),
using O(n) prover complexity and O(m) commitment openings.
Protocol
Let’s consider g is generator of H,
\mathbb{H}_0 = \{g^0, g^1, g^2, \dots, g^{n-1}\},
\mathbb{H}_1 = \{g^0, g^2, g^4, \dots, g^{n-2}\},
\dots
\mathbb{H}_m = \{g^0\}.
Let’s consider the relaxed polynomial expression
Where y_i is any variable in the constraint system: a_i, b_i, c_i, d_i, e_i\ \text{or}\ f_i.
We will perform split and fold method:
y_{i, (0), L}(x) equals y_{i, (0)}(x) on x \in \mathbb{H}_1,
y_{i, (0), R}(x) equals y_{i, (0)}(gx) on x \in \mathbb{H}_1.
We can prove these polynomial checks with linear time:
y_{i, (0)}(x) - y_{i, (0), L}(x) = q_{i, (0), L}(x) Z_{\mathbb{H}_1},
y_{i, (0)}(x) - y_{i, (0), R}(g^{-1}x) = q_{i, (0), R}(x) Z_{g^{-1}\mathbb{H}_1},
because \deg(q_{i, (0), L}) < n/2,
\deg(Z_{g\mathbb{H}_1}) < n/2,
\deg(y_{i, (0)}(x)) < n.
Next, apply the Sangria protocol and perform folding.
t_1= {a_R} {b_L} {c_L} + {a_L} {b_R} {c_L} + {a_L} {b_L} {c_R} + {d_L} {e_L} {u} + {d_R} {e_L} {u} + {d_L} {e_R} {u} + 2 \, {f_L} {u}^{2} + {f_R} {u}^{2}
t_2= {a_R} {b_R} {c_L} + {a_R} {b_L} {c_R} + {a_L} {b_R} {c_R} + {d_R} {e_L} {u} + {d_L} {e_R} {u} + {d_R} {e_R} {u} + {f_L} {u}^{2} + 2 \, {f_R} {u}^{2}
\lambda \xleftarrow{\$} \mathbb{F}
y_{i, (1)} = y_{i, (0), L} + \lambda y_{i, (0), R},
u_{(1)} = (1+\lambda) u_{(0)},
\text{err}_{(1)} = \text{err}_{(0), L} - \lambda t_1 - \lambda^2 t_2 + \lambda^3 \text{err}_{(0), R},
C(\{y_{i,(1)}\}, u_{(1)}, \text{err}_{(1)}) = C(\{y_{i, (0), L}(x)\}, u_{(0)}, \text{err}_{(0), L}) + \lambda^3 C(\{y_{i, (0), R}(x)\}, u_{(0)}, \text{err}_{(0), R}),
Performing iteratively m foldings, we get just scalar expression, which can be easily verified.