# Sumcheck

## Overview

The sumcheck protocol is a cryptographic proof protocol designed to efficiently prove and verify whether the sum of a multivariate polynomial over a specified domain equals a claimed value, given :

* A multivariate polynomial $$g(X\_1,X\_2, \dots, X\_{v})$$
* A finite domain $$B^v$$ for any $$B \subseteq \mathbb{F}$$
* A claimed sum 

$$
C\_1 := \sum\_{b\_1 \in B}\sum\_{b\_2 \in B} \dots \sum\_{b\_v \in B} g(b\_1, \dots, b\_v)
$$

or in short $$C\_1 := \sum\_{b \in B^v}g(b)$$. We denote the true correct sum by $$H$$. 

Throughout this article, we assume that $$B = {0,1}$$ which is the case where the evaluation domain is a boolean hypercube. $$\deg\_j(g)$$ denotes the degree of $$g$$ in variable $$X\_j$$. We denote the prover and the verifier by $$\mathcal{P}$$ and $$\mathcal{V}$$. 

The goal is for $$\mathcal{P}$$ to convince $$\mathcal{V}$$ that the claimed $$C\_1 = H$$, without having $$\mathcal{V}$$ evaluate $$g$$ on all $${0,1}^v$$ elements (which would be computationally expensive).

## Protocol

1. In the first round, $$\mathcal{P}$$ sends the univariate polynomial $$g\_1(X\_1)$$ and claims it equals the following:

$$
\sum\_{(x\_2, \dots, x\_v) \in {0,1}^{v-1}}g(X\_1, x\_2, \dots, x\_{v})
$$

Note that $$g\_1(0) + g\_1(1) = C\_1$$ if $$\mathcal{P}$$ is honest. 

2. $$\mathcal{V}$$ checks if $$g\_1(0) + g\_1(1) = C\_1$$. If not, $$\mathcal{V}$$ rejects. 
3. $$\mathcal{V}$$ checks if $$\deg(g\_1) \le \deg\_1(g)$$. If not, $$\mathcal{V}$$ rejects.
4. $$\mathcal{V}$$ chooses a random $$r\_1 \in \mathbb{F}$$  and sends it to $$\mathcal{P}$$. Both $$\mathcal{V}$$ and $$\mathcal{P}$$ set $$C\_2 := g\_1(r\_1)$$. 
5. Now in the $$j$$th round, for $$1\<j\<v$$, $$\mathcal{P}$$ sends the univariate polynomial $$g\_j(X\_j)$$ and claims it equals the following:

$$
\sum\_{(x\_{j+1}, \dots, x\_v) \in {0,1}^{v-j}}g(r\_1,\dots,r\_{j-1}, X\_j, x\_{j+1}, \dots, x\_{v})
$$

Note that $$g\_j(0) + g\_j(1) = C\_j$$ if $$\mathcal{P}$$ is honest.&#x20;

6. $$\mathcal{V}$$ checks if $$g\_j(0) + g\_j(1) = C\_j$$. If not, $$\mathcal{V}$$ rejects.&#x20;
7. $$\mathcal{V}$$ checks if $$\deg(g\_j) \le \deg\_j(g)$$. If not, $$\mathcal{V}$$ rejects.
8. $$\mathcal{V}$$ chooses a random $$r\_j \in \mathbb{F}$$  and sends it to $$\mathcal{P}$$. Both $$\mathcal{V}$$ and $$\mathcal{P}$$ set $$C\_{j+1} := g\_j(r\_j)$$.

This process continues iteratively, reducing the dimension at each step until reaching a single variable.

9. In round $$v$$, $$\mathcal{P}$$ sends $$g\_v(X\_v)$$ to $$\mathcal{V}$$ claiming it equals:

$$
g(r\_1, \dots, r\_{v-1}, X\_v)
$$

10. $$\mathcal{V}$$ checks if $$g\_{v}(0) + g\_{v}(1) = C\_v$$. If not, $$\mathcal{V}$$ rejects.&#x20;
11. $$\mathcal{V}$$ chooses a random $$r\_v \in \mathbb{F}$$ and evaluates $$g(r\_1, \dots, r\_v)$$ with a single oracle query to $$g$$. $$\mathcal{V}$$ checks that $$g\_v(r\_v) = g(r\_1, \dots, r\_v)$$. If not, $$\mathcal{V}$$ rejects.

### Completeness

Let $$s\_i(X)$$ be the polynomial that $$\mathcal{P}$$ would have sent in round $$i$$ if it were honest :

$$
s\_i(X\_i) = \sum\_{(x\_{i+1}, \dots, x\_v) \in {0,1}^{v-i}}g(r\_1,\dots,r\_{i-1}, X\_i, x\_{i+1}, \dots, x\_{v})
$$

If $$C\_1$$ and $$g\_1(X)$$ that $$\mathcal{P}$$ provided in the first round is equal to $$H$$ and $$s\_1(X)$$, respectively, then $$g\_1(0) + g\_1(1)$$ is equal to $$C\_1$$. $$\mathcal{V}$$ checks if this holds, then randomly samples $$r\_1$$ and sends it to $$\mathcal{P}$$. The only remaining part is merely a recursive invocation of another sumcheck protocol on $$s\_1(r\_1)$$ where the claimed value is $$C\_2 := g\_1(r\_1)$$. At the bottom of the recursion, which is the last round of the protocol, $$\mathcal{P}$$ passes the verification as $$g\_v(r\_v) = s\_v(r\_v) = g(r\_1, \dots, r\_v)$$. Thus, the sumcheck protocol has perfect completeness.&#x20;

### Soundness

What is the soundness error, that is, what is the probability that $$\mathcal{P}$$ passes the protocol even though the first value given in the first step is wrong, i.e. $$C\_1 \neq H$$?&#x20;

If the following occurs at any round of the protocol, $$\mathcal{P}$$ can pass the verification even if the first claimed value is wrong:&#x20;

* For the challenge $$r\_i \stackrel{$}{\leftarrow} \mathbb{F}$$ sampled by $$\mathcal{V}$$, luckily $$g\_i(r\_i) = s\_i(r\_i)$$ for the $$g\_i \neq s\_i$$ that $$\mathcal{P}$$ had sent in the previous round.&#x20;

Once the scenario outlined above occurs, $$\mathcal{P}$$ can proceed onto the  remaining rounds with a valid transcript to deceive $$\mathcal{V}$$. The soundness error $$\delta\_s$$ is bounded by $$vd / |\mathbb{F}|$$, which can be calculated by the Schwartz-Zippel lemma.  In other words, $$\mathcal{V}$$ can be convinced that $$g\_i(X) = s\_i(X)$$ if $$g\_i(r\_i) = s\_i(r\_i)$$ for a random sampled $$r\_i$$.&#x20;

### Cost

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2F5N8YcHPc8PYaTDFqkHgC%2Fimage.png?alt=media&#x26;token=59471fbb-cb07-4cae-a969-9b5777e28571" alt=""><figcaption></figcaption></figure>

We denote the cost of evaluation oracle query to $$g$$ by $$T$$. In reality, $$T$$ is equal to the cost to evaluate $$g$$ at a single input in $$\mathbb{F}^v$$.&#x20;

#### Communication cost.&#x20;

At each round, $$\mathcal{P}$$ generates an univariate polynomial $$g\_i(X)$$ whose degree is at most $$\deg\_i(g)$$. To uniquely satisfy such polynomial, $$\mathcal{P}$$ needs to send $$\deg\_i(g)$$ evaluations on $$g$$.&#x20;

#### Prover cost.

The cost of computing such prescribed messages at each round is equal to evaluating $$g\_i(X)$$ at $$\deg\_i(g)$$ points. Letting the oracle query cost be $$T$$ and assuming $$\deg\_i(g) = O(1)$$, the prover's runtime cost at round $$i$$ is $$O(2^v \cdot T)$$.&#x20;

#### Verifier cost. &#x20;

Also assuming $$\deg\_i(g) = O(1)$$, the total verifier cost is dominated by $$T$$; the cost of evaluating $$g$$ only once.&#x20;

Combining with Fiat-Shamir transform, we have successfully reduced a complicated interactive proof into a simple evaluation task for $$\mathcal{V}$$. Unfortunately, in many real world problems, $$\mathcal{V}$$ does not have access to a constant cost oracle query to $$g$$, or even a single evaluation is prohibitively expensive.&#x20;

The key part of sumcheck-based protocols is about how we will grant $$\mathcal{V}$$ oracle access. There should be either a way $$\mathcal{V}$$ can efficiently evaluate $$g$$, or we should run another protocol for the value $$g(r)$$ (refer to [polynomial commitment scheme](https://fractalyze.gitbook.io/intro/~/revisions/GBuVDfZJZBNDtoleSgnx/primitives/commitment-scheme)).

## Example&#x20;

### #SAT

For a $$n$$-variate boolean formula $$\phi$$, whose size $$S$$ is $$\mathsf{poly} (n)$$, calculate&#x20;

$$
\sum\_{x \in {0,1}^n} \phi(x)
$$

The fastest algorithm ever known to solve $$#\mathsf{SAT}$$ is exponential, which means it's not much better than brute-forcing it.&#x20;

In addition to that, there is no polynomial time deterministic & non-interactive algorithm $$\mathcal{V}$$. This is because even if $$\mathcal{P}$$ provides every valid input it knows as a witness, there is no way $$\mathcal{V}$$ can check in polynomial time whether there are more valid inputs. $$#\mathsf{SAT} \notin \mathsf{NP}$$.&#x20;

However there exists an interactive proof for this, which enables $$\mathcal{V}$$ to verify if the claimed value is correct within polynomial time.  $$#\mathsf{SAT} \in \mathsf{IP}$$.&#x20;

This implies that the interactive proof is more powerful than merely proving an NP statement. It is known that $$\mathsf{NP} \sube \mathsf{PSPACE} = \mathsf{IP}$$, where $$\mathsf{PSPACE}$$ denotes the set of all problems that can be solved by Turing machines with polynomial space complexity.

#### Protocol

Transform $$\phi$$ into an arithmetic circuit $$\psi(x)$$. AND gate can be extended to $$y \cdot z$$, OR gate to $$y + z - y\cdot z$$, NOT gate to $$1-y$$. Now extend circuit $$\psi$$ to a $$n$$-variate polynomial $$g$$, which means that $$\sum\_{x\in{0,1}^{n}} g(x) = \sum\_{x\in{0,1}^{n}} \phi(x)$$.&#x20;

Degree of $$g$$ is $$\mathsf{poly} (S)$$. Run the sumcheck protocol on $$g$$.&#x20;

***

## References

* <https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf>

> Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") and [Carson Lee](https://app.gitbook.com/u/Hm5RHrPlu2fbxwXnpUgxmvXVTwB3 "mention") of Fractalyze