# Sumcheck Protocol 101

Sumcheck protocol was first introduced in paper[1] by Carsten Lund et.al in 1992, described below, the purpose of Sumcheck protocol is to prove the P know vector {w_1, …, w_l}, s.t.

where `u` is claimed sum, l is the number of variables, and H is subset of R.

picture from Sumcheck Arguments and their Applications[2].

Easy to prove the protocol’s correctness.

In the first round, P calculates:

and sends the univariate polynomial q_1 to V, and V checks whether

If not, V rejects the proof.

Then, in the (i+1)th round, V sends r_i to P, and P calculates

univariate polynomial

, and send it to V, V checks that:

And if all the above checks pass, V calculates:

and output tuple:

as the final proof.

The soundness can also be proved by Vanna-Pat Shink Game in paper[3].

So we conclude the communications and time complexity as below:

where T is the time cost of a single query to p, and deg_i(q) is the degree of variable `i` in polynomial p.

Sumcheck protocol is widely used in probabilistic proof、Sumcheck-based succinct arguments. Next post, We will introduce how to apply this protocol for Pedersen commitment to achieve an arguemnt.

- Algebraic Methods for Interactive Proof Systems, https://users.cs.fiu.edu/~giri/teach/5420/f01/LundIPS.pdf
- https://eprint.iacr.org/2021/333.pdf, https://youtu.be/tazkY_CaLK0