Prerequisite:

  • multilinear polynomials
  • low degree extension

Sumcheck protocol

To Prove:

Univariate sumcheck

Introduced in Aurora Paper, univariate sumcheck proves relation for a univariate polynomial of degree and subset :

Properties of protocol:

  1. rounds:
  2. proof complexity:
  3. query complexity:
  4. prover operations:
  5. verifier operations:

Uses theorem stated by Byott and Chapman BC99 that iff has degree less than . Prove this using FRI protocol by BBHR18b which has proof complexity and proof length . For case when degree : we observe that we can split any polynomial into two polynomials and such that with and ; in particular, and agree on , and thus so do their sums on .

GKR

and agrees to a circuit. proves , the output of the circuit.

Resources