# Succinct proof of evaluation of known polynomial

Consider the zeroes polynomial $$zeroes_n(X) = \prod_{0\leq i< n} (X-i) .$$ Fix a large prime $$p$$, and fix some $$n$$ that is less than $$p$$ but which may still be very large (e.g. $$p\approx 2^{256}$$ and $$n\approx 2^{64}$$).

Question: What is the state of the art for a prover to succinctly prove to a verifier that $$zeroes_n(x) = y \quad (mod\ p) .$$ In more detail:

1. The verifier sends $$n$$, $$p$$, and $$x$$ to the prover.
2. The prover (if honest) computes $$y=zeroes_n(x)\ (mod\ p)$$ and returns this value to the verifier, along with a succinct proof $$C$$ that $$y$$ is correct.
3. The verifier can, without too much computation (e.g. $$O(1)$$ or $$O(log(n))$$ or similar) use $$C$$ to verify that indeed $$zeroes_n(x)=y\ (mod\, p)$$, without having to compute $$zeroes_n(x)$$ itself.

Note that:

• Both prover and verifier know the polynomial $$zeroes_n(X)$$. In particular, the verifier knows that the roots of $$zeroes_n(X)$$ are $$\{0,\dots,n-1\}$$.
• Both prover and verifier know $$n$$, $$p$$, and $$x$$. Nothing is hidden here.
• Even though the verifier has full knowledge of the above, the verifier may be limited in computational power or memory space, so it cannot compute $$zeroes_n(x)$$ itself.
• This setup is similar to a polynomial commitment of course, but if we look at it like that then note that the prover is being asked to commit to an evaluation of a known polynomial. Thus something like KZG as described in https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html#verifying-an-evaluation-proof does not obviously help, so far as I can tell, because in this verification the verifier only knows that some polynomial evaluates as described, but cannot force the prover to use a particular one (such as $$zeroes_n(X)$$).

Thank you.