Suppose there is an $\mu$-variate low-degree polynomial, $\mathcal{G}: \mathbb{F}^\mu \rightarrow \mathbb{F}$ where the degree of each variable in $\mathcal{G}$ is at most $\ell$. Suppose that a verifier $\mathcal{V}_{S C}$ is interested in checking a claim of the following form by an untrusted prover $\mathcal{P}_{S C}$ or the computationally bounded verifier wants to delegate the heavy computation to a unbounded prover :
First, we can analyze the cost of the above computation. The number of terms in the above sum is $2^\mu$. The degree of the polynomial $\mathcal{G}$ is $\ell$ in each variable. Therefore, the degree of the polynomial $\mathcal{G}$ is at most $\mu \cdot \ell$. The cost of evaluating the polynomial $\mathcal{G}$ at a point is $O(\mu \cdot \ell)$. Therefore, the cost of evaluating the above sum is $O(2^\mu \cdot \mu \cdot \ell)$. It’s unaffordable to compute the above sum by the verifier $\mathcal{V}_{S C}$ itself.
By using Sum-Check Protocol, the verifier can reduce the cost to just calculate a random point of the polynomial $\mathcal{G}$ and sample some random points. The complexity of the protocol is $O(\mu \cdot \ell)$.
We denote the sum-check protocol as $b \leftarrow\left\langle\mathcal{P}_{S C}, \mathcal{V}_{S C}(r)\right\rangle(\mathcal{G}, \mu, \ell, T)$. For any $\mu$-variate polynomial $\mathcal{G}$ with degree at most $\ell$ in each variable, the following properties hold.
- Completeness. If $T=\sum_{x \in\{0,1\}^\mu} \mathcal{G}(x)$, then for a correct $\mathcal{P}_{S C}$ and for all $r \in\{0,1\}^*$, $\operatorname{Pr}\left\{\left\langle\mathcal{P}_{S C}(\mathcal{G}), \mathcal{V}_{S C}(r)\right\rangle(\mu, \ell, T)=1\right\}=1$.
- Soundness. If $T \neq \sum_{x \in\{0,1\}^\mu} \mathcal{G}(x)$, then for any $\mathcal{P}_{S C}^{\star}$ and for all $r \in\{0,1\}^*$, $\operatorname{Pr}_r\left\{\left\langle\mathcal{P}_{S C}^{\star}(\mathcal{G}), \mathcal{V}_{S C}(r)\right\rangle(\mu, \ell, T)=1\right\} \leq \ell \cdot \mu /|\mathbb{F}|$.
- Succinctness. The communication between $\mathcal{P}_{S C}$ and $\mathcal{V}_{S C}$ is $O(\mu \cdot \ell)$ elements of $\mathbb{F}$.
Proof of Soundness
In this section, we will prove the soundness of the sum-check protocol. We will show that if $T \neq \sum_{x \in\{0,1\}^\mu} \mathcal{G}$, then for any $\mathcal{P}_{S C}^{\star}$ and for all $r \in\{0,1\}^*$, $\operatorname{Pr}_r\left\{\left\langle\mathcal{P}_{S C}(\mathcal{G^\star}), \mathcal{V}_{S C}(r)\right\rangle(\mu, \ell, T)=1\right\} \leq \ell \cdot \mu /|\mathbb{F}|$.
We can prove it by induction.
The base case is $\mu=1$: Prover’s only message is a degree-$\ell$ polynomial $\mathcal{G}_1(x_1)$, and the verifier’s only message is a random point $r_1 \in \mathbb{F}$.
The prover can forge a polynomial satisfy $T=\mathcal{G}_1(0)+\mathcal{G}_1(1)$. But the verifier checks the following equation:
By the Schwartz-Zippel lemma, the probability that the above equation holds is at most $\ell/|\mathbb{F}|$.
Assume the statement holds for $\mu-1$.
Let $h_1\left(X_1\right)=\sum_{x_2, \ldots, x_v \in\{0,1\}^{\nu-1}} \mathcal{G}\left(X_1, x_2, \ldots, x_v\right)$.
Suppose $\mathcal{P}$ sends a polynomial $\mathcal{G}_1$ satisfying $T=\mathcal{G}_1(0)+\mathcal{G}_1(1)$ and $\mathcal{G}_1(X_1)\not =h_1(X_1)$. Then because the degree of the degree of $\mathcal{G}_1-h_1$ is at most $\ell$, $\mathcal{G}_1(r_1)=h_1(r_1)$ with probability at most $\ell/|\mathbb{F}|$.
Conditioned on $\mathcal{G}_1(r_1)=h_1(r_1)$, the verifier need to checks:
By the induction hypothesis, the probability that the above equation holds is at most $\ell \cdot (\mu-1) /|\mathbb{F}|$.
Therefore, the probability that the verifier reject is