# 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="/files/3rO645Ly5Plf3Yy1Ax9Y" 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](/intro/primitives/commitment-scheme.md)).

## 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](mailto:undefined) and [Carson Lee](mailto:undefined) of Fractalyze


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://fractalyze.gitbook.io/intro/primitives/sumcheck.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.