Zero-Integral and Sum-Check

Let be a table of 1 column and rows, and let be any polynomial that agrees with when evaluated on , where is a generator of the subgroup of order . Group theory lets us prove and efficiently verify if .

Decompose into , where is the zerofier over , and where has degree at most . The table sums to zero if and only if integrates to zero over because

and this latter proposition is true if and only if the constant term of is zero.

Theorem. for a subgroup of order .

Let be a subgroup of . If then and also because the elements of come in pairs: . Therefore .

The map is a morphism of groups with . Therefore we have:

The polynomial has only one term whose exponent is , which is the constant term.

This observation gives rise to the following Polynomial IOP for verifying that a polynomial oracle integrates to 0 on a subgroup of order some power of 2.

Protocol Zero-Integral

  • Prover computes and .
  • Prover computes .
  • Prover sends , of degree at most , and , of degree at most to Verifier.
  • Verifier queries , , in z \xleftarrow{$} \mathbb{F} and receives .
  • Verifier tests .

This protocol can be adapted to show instead that a given polynomial oracle integrates to on the subgroup , giving rise to the well-known Sum-Check protocol. The adaptation follows from the Verifier's capacity to simulate from , where . This simulated polynomial is useful because

In other words, integrates to on iff integrates to on , and we already a protocol to establish the latter claim.