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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.