---
# System prepended metadata

title: Sumcheck protocol simplified

---

Sumcheck is interactive protocol between prover P and verifier V. 
The prominent feature of the sumcheck protocol is to offload hard work of computing a sum to P. 
As described by J. Thaler in his [book](https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.html) called "Proofs, Arguments, and Zero-Knowledge", the sumcheck protocol can be described as follows.
**Setup:**
* Let $g$ be n-variate polynomial of degree 3  defined over binary hypercube {0,1}^n^. 
* The protocol runs in n rounds. 
* The complexity of algorithm is logarithmic in terms of circuit size.

**Round 0** 
At the start of the protocol, P sends a claimed answer C.

**Round 1** 
P sends a polynomial S~1~(X) claimed to be equal 
  $h_1(X) = \sum_{(x_2,\ldots,x_n)} g\bigl(X, x_2, \ldots, x_n\bigr)$
  
V performs round 1 consistency check C = S~1~(0) + S~1~(1)
S~1~(0) is a first half of the terms
S~1~(1) is the second half of the terms.
If P is honest, this consistency check will pass.

V would like to ascertain if $h_1(X)$ = $S_1(X)$
V picks random $r_1 \in$ F and sends it to P
By Schwarz-Zippel Lemma, if $h_1(r_1)$ = $S_1(r_1)$ holds, then $h_1$ and $S_1$ are the same polynomials with a high probability.

*Note*
V can compute $S_1(r_1)$ on its own, but he has no idea what $h_1$ is. V can not compute $h_1(r_1)$ on its own. That is what the future rounds for. 

$h_1(r_1) = \sum_{(x_2,\ldots,x_n)} g\bigl(r_1, x_2, \ldots, x_n\bigr)$

In the second round apply sumcheck recursively to compute (n-1)-variate polynomial $g'\bigl(x_2, \ldots, x_n\bigr)$ = $g\bigl(r_1, x_2, \ldots, x_n\bigr)$

**Round 2**
P sends a univariate polynomial $S_2(X)$ claimed to be equal 
  $h_2(X) = \sum_{(x_3,\ldots,x_n)} g\bigl(r_1, X, x_3, \ldots, x_n\bigr)$
  
V performs round 2 consistency check $S_1(r_1)$ = S~2~(0) + S~2~(1)  
This check will pass if p is honest and  $h_2(X)$ = $S_2(X)$ indeed holds.
V picks random $r_2 \in$ F and sends it to P
V checks if $h_2(r_2)$ = $S_2(r_2)$

In the next round apply sumcheck recursively to compute (n-2)-variate polynomial $g''\bigl(x_3, \ldots, x_n\bigr)$ = $g\bigl(r_1, r_2, x_3, \ldots, x_n\bigr)$

**Round i** 
P sends $S_i(X)$ to V to be claimed equal to $h_i(X)$
V checks  S~i-1~(r~i-1~) = S~i~(0)+ S~i~(1) 
V picks r~i~ and send it to P
V checks S~i~(r~i~) = h~i~(r~i~) 


**Final round n** 
P sends $S_n(X)$ claimed to be equal
$h_n(X)$ = g(r~1~ ... r~n-1~,X)
V performs final round n consistency check 
S~n-1~(r~n-1~) = S~n~(0) + S~n~(1)
V picks random $r_n \in$ F and sends it to P
V would like to ascertain if $S_n(r_n)$ = $h_n(r_n)$ 
Note, $h_n(r_n)$ = $g(r_1, r_2,...r_n)$

**Security assessment**
Completeness: if P is honest, all consistency checks will pass
Soundness error <= n*(3/|F|)







