Prerequisite:

- multilinear polynomials
- low degree extension

## Sumcheck protocol

To Prove: $∑_{i=0}f=c$

### Univariate sumcheck

Introduced in Aurora Paper, univariate sumcheck proves relation for a univariate polynomial $f(x)$ of degree $d$ and subset $H⊆F$:

$a∈H∑ f(a)=0$Properties of protocol:

- rounds: $O(gd)$
- proof complexity: $O(d)$
- query complexity: $O(gd)$
- prover operations: $O(dg∣H∣)$
- verifier operations: $O(gd+g_{2}∣H∣)$

Uses theorem stated by Byott and Chapman BC99 that $∑_{a∈H}f(a)=0$ iff $f$ has degree less than $∣H∣−1$. Prove this using FRI protocol by BBHR18b which has proof complexity $O(gd)$ and proof length $O(d)$. For case when degree $d>∣H∣−1$: we observe that we can split any polynomial $f$ into two polynomials $g$ and $h$ such that $f(x)≡g(x)+∏_{α∈H}(x−α)⋅h(x)$ with $deg(g)<∣H∣$ and $deg(h)<d−∣H∣$; in particular, $f$ and $g$ agree on $H$, and thus so do their sums on $H$.

$f^ a∈H∑ f^ (a) ≡g^ +Z_{H}⋅h^≡a∈H∑ (g^ (a)+Z_{H}⋅h^(a))=βa∈H∑ a_{∣H∣−1} $## GKR

$P$ and $V$ agrees to a circuit. $P$ proves $V$, the output of the circuit.

## Resources

- recmo’s post about sumcheck
- JThaler’s: unreasonable power of sumcheck
- JThaler’s sumcheck notes
- JThaler’s: Proofs, Args, and ZK, Chapter 3, 4
- JThaler’s small sumcheck
- erhant’s notes on Lecture 4 of ZKP MOOC
- NUS CS6230: The power of IPs
- Berkeley’s CS294: Introduction to IP & Sumcheck
- risencrypto’s sumcheck
- zk sumcheck
- sumcheck arguments and their application
- CPerez’s post about sumcheck
- CPerez’s ideas about GKR