No-fft O(n) univariate polynomial zero check with O(log(n)) verifier

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

p(x) = C(\{a_i\}, \{b_i\}, \{c_i\}, \{d_i\}, \{e_i\}, \{f_i\}) = \\\sum a_i b_j c_k + \sum d_i e_j + \sum f_i,

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.


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}\},


\mathbb{H}_m = \{g^0\}.

Let’s consider the relaxed polynomial expression

C(\{y_i\}, u, \text{err}) = C(\{a_i\}, \{b_i\}, \{c_i\}, \{d_i\}, \{e_i\}, \{f_i\}, u, \text{err}) =\\ \sum a_i b_j c_k + u\sum d_i e_j + u^2\sum f_i + \text{err},

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.