Sumcheck Protocol 101

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

where `u` is claimed sum.

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 argument.




Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store