Sum-Check Protocol

Suppose we are given a $v\text{-variate}$ polynomial $g$ defined over a finite field $F$. The purpose of the sum-check protocol is for the prover to provide the verifier with the following sum:

$$H = \sum_{b_1 \in \{0, 1\}} \sum_{b_2 \in \{0, 1\}} ... \sum_{b_v \in \{0, 1\}} g(b_1, ..., b_v).$$

Note: In full generality, the sum-check protocol can compute the sum $\sum_{b \in B^v} g(b)$ for any $B ⊆ F$.

Protocol Description

1. At the start of the protocol, the prover sends a value $C_1$ claimed to equal the value $H$

2. In the first round, $P$ sends the univariate polynomial $g_1(X_1)$ claimed to equal

$$g_1(X_1) = \sum_{(x_2,...,x_v) \in \{0, 1\}^{v-1}} g(X_1, x_2, ..., x_v).$$

$V$ checks that $C_1 = g_1(0) + g_1(1)$ and that $g_1$ is a univariate polynomial of degree at most $deg_1(g)$, rejecting if not. Here $deg_j(g)$ denotes the degree of $g(X_1,...,X_v)$ in variable $X_j$.

1. $V$ chooses a random element $r_1 \in F$, and sends $r_1$ to $P$

2. In the $j\text{th}$ round, for $1 < j < v$, $P$ sends a univariate polynomial $g_j(X_j)$ claimed to equal

$$g_j(X_j) = \sum_{(x_{j+1},...,x_v) \in \{0,1\}^{v-j}} g(r_1,...,r_{j-1}, X_j, x_{j+1}, ..., x_v)$$

$V$ checks that $g_j$ is a univariate polynomial of degree at most $deg_j(g)$ and that $g_{j-1}(r_{j-1}) = g_j(0) + g_j(1)$, rejecting if not.

1. $V$ chooses a random element $r_j \in F$, and sends $r_j$ to $P$.

2. In Round $v$, $P$ sends to $V$ a univariate polynomial $g_v(X_v)$ claimed to equal

$$g_v(X_v) = g(r_1, ..., r_{v-1}, X_v).$$

$V$ checks that $g_v$ is a univariate polynomial of degree at most $deg_v(g)$, rejecting if not, and also checks that $g_{v-1}(r_{v-1}) = g_v(0) + g_v(1)$.

1. $V$ chooses a random element $r_v \in F$ and somehow (by their own efforts or with some polynomial commitment scheme) evaluates $g(r_1,...,r_v)$. $V$ checks that $g_v(r_v) = g(r_1,...,r_v)$, rejecting if not.

2. If $V$ has not yet rejected, $V$ halts and accepts.

Properties

• perfect completeness

• soundness

Costs

Costs of the sum-check protocol when applied to a $v\text{-variate}$ polynomial $g$ over $F$. Here, $deg_i(g)$ denotes the degree of variable $i$ in $g$, and $T$ denotes the cost of an oracle query to $g$.

Communication	Rounds	V time	P time
$O(\sum_{i=1}^v deg_i(g))$ field elements	$v$	$O(v + \sum_{i=1}^v deg_i(g)) + T$	$O(2^v·T)\\\text{if }deg_i(g) = O(1) \\ \text{for all }i$