# Sumcheck And Its Distributed Version

> Written by Tim

## 1. Classic Sumcheck

Sumcheck protocol is a useful cryptographic primitive which allows us to achieve linear prover in a proving system. The goal of sumcheck protocol is to prove the sum of a multivariate (say $n$) polynomial $f(X_1, \dots,X_n)$ over a finite field $\mathbb{F}$ equal to a claimed value $s$ over the boolean hypercube $B_n=\{0,1\}^n$: $\sum_{(X_1,\dots,X_n)\in B_n}f(X_1,\dots,X_n)=s$.

> Note that sumcheck does not require $f$ to be multilinear. If you are not very familar with polynomial and its extension, you'd better review it firstly. :)

The full sumcheck protocol workflow is shown in the following figure:


The protocol runs in $n$ rounds where $n$ stands for the number of variable of the multivariate poly $f$. In the first round, Prover generates a univariate poly $f_1(X_1)$ which only related the first variable $X_1$ and sends it to Verifier. Verifier checks if $f_1(0)+f_1(1)\overset{?}{=}s$ holds and if true then generates a random challenge $r_1\in\mathbb{F}$ and send it to Prover. In the rest rounds, Prover similarly generates a univariate poly $f_k(X_k)$ which only related the k-th variable $X_k$ and sends it to Verifier. Verifier checks if $f_k(0)+f_k(1)\overset{?}{=}f_{k-1}(r_{k-1})$ holds and if true then generates a random challenge $r_k\in\mathbb{F}$ and send it to Prover. Specially, in the last round (aka n-th round), Verifier needs to additional check $f_n(r_n)\overset{?}{=}f(r_1,\dots,r_n)$. If any check fails during the protocol, the protocol will exit execution.

WLOG, assump the order of $f$ is $d$, then, in each round of the protocol, Prover only need to send $d+1$ points to the Verifier. Specially, if the multivariate poly is multilinear, then prover can just send 2 points to Verifier each round. This is because the univariate poly sent by Prover in each round is a linear function, we just need 2 points to recover it.

> About multilinear sumcheck, I recommend to read the paper: [A Time-Space Tradeoff for the Sumcheck Prover](https://eprint.iacr.org/2024/524.pdf)

## 2. Distributed Sumcheck

In a single Prover setting, regardless of how developers apply concurrent programming, the Prover must compute the sum of an n-variate polynomial.

**It is time to use the power of distribution.** Assuming we have M (where $M=2^m$) machines as Prover, and we assign each of them a Prover id from 0 to M.

The distributed Sumcheck protocol enhances efficiency by assigning each prover a unique ID. Rather than a single prover summing an n-variate polynomial $f(X_1,\dots,X_n)$, the protocol fixes the last $m$ variables of $f$ to the prover's ID (identified $\mathcal{P}_{id}$): $f(X_1, \dots, X_{n-m}, \mathbf{bin}(id))$.


In the very first $n−m$ rounds, $M$ provers collaboratively compute univariate polynomials, aggregated by $\mathcal{P}_0$. In round $n-m+1$, they jointly calculate the sum $v$ over the last $m$ variables. $\mathcal{P}_0$ then runs a classic single-prover Sumcheck with the Verifier on an m-variate polynomial, with minimal overhead.

**Leveraging single-machine parallelism, this distributed approach greatly boosts parallelization, providing significant advantages for large-scale circuit processing.**