Sum-Check: The Backbone of ZK Proofs

Huge thanks to Oba, Ziemann and Nico for their help and feedback! ❤️

The Sum-Check Protocol is a fundamental tool in cryptographic proofs, particularly in zero-knowledge proofs (ZKPs) and verifiable computation. It allows a verifier to efficiently check that a prover has correctly summed up evaluations of a polynomial over a boolean hypercube without computing every evaluation explicitly.

If that sounds confusing, don't worry, that’s exactly why this article exists.

We’ll break down the key concepts needed to understand the Sum-Check Protocol and then walk through the protocol itself in an easy-to-follow manner.

To assist you, I wrote a few scripts with Sage: ‣

Building Blocks for Sum-Check

Before diving into the Sum-Check Protocol, we need to understand some fundamental mathematical concepts.

1. Multivariate and multilinear polynomials

A multivariate polynomial is a polynomial with more than one variable. For example:

$$ f(x,y)=3x^3y^4+2xy^2+5y+7 $$

<aside> 💡

A multivariate polynomial is typically written as: $f(\vec{x})$

where $\vec{x}$ is a vector of variables, ex: $\vec{x} = (x_1, x_2, \dots, x_n)$. Its length corresponds to the number of input variables in the function.

</aside>

Key things to note:

• Degree of each variable: The highest exponent of each variable. Here, x has degree 3 and y has degree 4
• Degree of the polynomial: The term with the maximum combined degree, which is 7 (3+4) for the previous example

Other examples:

• $x *y^2$ has degree 3 (since x has 1 and y has 2)
• $xyz$ also has degree 3
• $x*z$ has degree 2