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.

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

--

--

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
Eigen Network

Eigen Network

Where make transaction secure and private for Web3.0(https://eigen.cash)