Sum-check protocol - Sum-check protocol

Introduction¶

These notes replicate Thaler’s elegant presentation 1 of the sum-check protocol by Lund, Fortnow, Karloff, and Nisan 2, enriched with additional background information and interactive examples.

Definitions, conventions, and notation¶

Let $\mathbb{F}$ be a finite field, $v$ a positive integer, and $g$ a $v$ -variate polynomial with coefficients in $\mathbb{F}$ :

g(X_0,\ldots,X_{v - 1}) = \sum_{e \, \in \, \mathbb{N}^{v}} a_{e} X_0^{e_0}\cdots X_{v - 1}^{e_{v - 1}}, \quad a_e \in \mathbb{F}, \quad e = (e_0,\ldots,e_{v-1}),

(1)

where $a_e = 0$ for all but finitely many $e$ . The ring of all such polynomials is denoted $\mathbb{F}[X_0,\ldots,X_{v - 1}]$ . We use zero-based indexing throughout for consistency with the code and to minimize confusion, and define

\mathbb{N} := \{0,1,2,\ldots\}.

Definition 1

Referring to (1) above, we call each $a_e$ a coefficient of $g$ . If $a_e = 0$ for all $e \in \mathbb{N}^v$ , we call $g$ the zero polynomial. Suppose $g$ is not the zero polynomial. The total degree of $g$ is

\mathrm{deg}(g) = \max \left\{ e_0 + \cdots + e_{v-1} : a_e \ne 0 \right\},

(2)

i.e. the highest sum of the exponents of the indeterminates in any single term with a nonzero coefficient. The degree of indeterminate $X_j$ in $g$ is

\mathrm{deg}_{X_j}(g) = \max \left\{ e_j : a_e \ne 0 \right\},

(3)

i.e. the highest power of $X_j$ that appears in any single term with a nonzero coefficient. As the indeterminates are indexed we may denote this by $\mathrm{deg}_j(g)$ . We call $g$ multilinear if each $e_j$ in (1) is either 0 or 1. In other words, $g$ is multilinear if it is linear in each of its indeterminates individually.

Remark 1

(i) The total degree of a univariate polynomial ( $v = 1$ ) is just its degree. We may use the terms degree and total degree interchangeably.

(ii) The zero polynomial is denoted by 0. Context will always make clear whether 0 denotes the zero polynomial or the zero element of $\mathbb{F}$ . The nonzero constant polynomials are precisely those of total degree 0. We leave the degree of the zero polynomial undefined. Some authors, however, define it as $-\infty$ for convenience, which simplifies statements like $\mathrm{deg}(g_1 + g_2) \le \max\{\mathrm{deg}(g_1),\mathrm{deg}(g_2)\}$ and $\mathrm{deg}(g_1g_2) = \mathrm{deg}(g_1) + \mathrm{deg}(g_2)$ , without needing to exclude the zero polynomial as a special case. (iii) On the other hand, if we consider $g$ as a $v$ -variate polynomial in $\mathbb{F}[X_0,\ldots,X_{v-1}]$ , then $\mathrm{deg}_{j}(X_j)$ is defined and nonnegative for every $j$ , $0 \le j \le v - 1$ . Some authors might say, for instance, that the degree of $X_2$ in $X_0X_1 + X_1^2$ , is undefined. In our case, if we understand the polynomial as belonging to $\mathbb{F}[X_0,X_1,X_2]$ , then we note that we can multiply each term by $X_2^0$ without affecting the polynomial, whence the degree of $X_2$ in this polynomial is 0. This convention ensures that $\mathrm{deg}_j(g)$ is defined for all $j$ , which will be important when tracking degree bounds variable-by-variable in the sum-check protocol.

In the RHS of (1), we may replace a subset of $w$ indeterminates $X_j$ with field elements $r_j$ , resulting in a $(v - w)$ -variate polynomial in the remaining indeterminates, with their original indices preserved, and which we denote by substituting the corresponding $r_j$ for each replaced $X_j$ in the LHS. For instance, if $v > 1$ then $g(X_0,r_1,\ldots,r_{v-1})$ denotes the univariate polynomial in the indeterminate $X_0$ , obtained by substituting $X_1,\ldots,X_{v - 1}$ with $r_1,\ldots,r_{v - 1}$ in the RHS. For a more explicit example: if $g(X_0,X_1,X_2) = X_0X_1X_2 + X_0X_1^2 + X_2$ then $g(X_0,1,1) = 2X_0 + 1$ .

Formally, substituting field elements for indeterminates defines a ring homomorphism

\mathbb{F}[X_0,\ldots,X_{v - 1}] \mapsto \mathbb{F}[X_{i_1},\ldots,X_{i_{v - w}}].

The expression $g(r_0,\ldots,r_{v - 1})$ therefore denotes a constant polynomial in 0 indeterminates, which we identify with the corresponding field element. We call this the evaluation of $g$ at the point $(r_0,\ldots,r_{v - 1})$ . We call $(r_0,\ldots,r_{v-1})$ a root or zero of $g$ in $\mathbb{F}^v$ if $g(r_0,\ldots,r_{v-1}) = 0$ . For example, over $\mathbb{F} = \mathbb{Z}/2\mathbb{Z}$ , the evaluation of $g(X_0,X_1,X_2) = X_0X_1X_2 + X_0X_1^2 + X_2$ at the point $(1,1,1)$ is $g(1,1,1) = 1$ , so $(1,1,1)$ is not a root of $g$ , but $g(0,0,0) = 0$ , so $(0,0,0)$ is a root of $g$ , as are $(0,1,0)$ and $(1,0,0)$ .

Remark 2

The distinction between constant polynomials and constants, and between polynomials and polynomial functions, may seem pedantic but are particularly important for polynomials over finite fields. Over a finite field, a polynomial function may be represented by many distinct polynomials. In fact, every function $f : \mathbb{F}^v \to \mathbb{F}$ is a polynomial function, a consequence of the finiteness of $\mathbb{F}$ .

If $\mathbb{F}$ has order $q$ , then $X^q - X$ is certainly not the zero polynomial in $\mathbb{F}[X]$ , but $x \mapsto x^q - x$ is the zero function on $\mathbb{F}$ , by Fermat’s little theorem (equivalently, the Frobenius endomorphism). Polynomials are really just sequences of coefficients that we add and multiply in a certain way. Indeterminates $X_j$ serve as placeholders—not variables—to encode formal algebraic operations independently of evaluation. If this remark seems opaque, consider that a univariate polynomial can be represented as a sequence of coefficients $(a_0, a_1, a_2, \ldots)$ , where only finitely many $a_i$ are nonzero. Given two polynomials $g = (a_0, a_1, a_2, \ldots)$ and $h = (b_0, b_1, b_2, \dots)$ , their product $g \cdot h$ is another sequence of coefficients $(c_0, c_1, c_2, \ldots)$ defined by $c_k = \sum_{i=0}^k a_i b_{k-i}$ .

Example 1

For simplicity, the demo below uses $\mathbb{F}_p$ with prime $p$ . The same degree notions work over any finite field $\mathbb{F}_{p^k}$ .

from gkr import total_degree_example
total_degree_example(interactive=False)


EXAMPLE 1. The polynomial 

g(X_0, X_1, X_2) = X_0*X_1 + 4*X_0*X_2 + 4*X_1**2 + X_1*X_2 

is a non-multilinear polynomial in GF(5)[X_0, X_1, X_2].


The total degree of g is deg(g) = 2


The degree of X_0 in g is deg_X_0(g) = 1.


The degree of X_1 in g is deg_X_1(g) = 2.


The degree of X_2 in g is deg_X_2(g) = 1.

In the sum-check protocol we will repeatedly substitute random field elements for some variables, so tracking $\mathrm{deg}_j(g)$ is useful because it bounds the degree of the univariate polynomials sent in each round.

DeMillo–Lipton–Schwartz–Zippel Lemma¶

This result, commonly referred to as the Schwartz-Zippel lemma, tells us that the roots of a multivariate polynomial over a field are sparse. This insight has useful implications; for instance, it suggests that two multivariate polynomials over a field are unlikely to agree at a randomly selected point, which is the crux of the soundness error in the sum-check protocol.

The lemma was first proved jointly by DeMillo and Lipton 3, preceding the independent discoveries by both Schwartz 4 and Zippel 5 around the late 1970s. In fact, for the special case of finite fields—which is the only case relevant here—the result was originally established by Ore in 1922 6.

To set up the proof of the Schwartz-Zippel lemma, we begin by stating a foundational proposition upon which the proof relies.

Proof outline

Let $r_0 \in \mathbb{F}$ be a root of $g$ . By the division algorithm, we may write

g(X) = (X - r_0)q(X)

for some polynomial $q(X) \in \mathbb{F}[X]$ of degree $d - 1$ . If $r_0$ is a repeated root, then there exists a maximal integer $m_0 \ge 1$ such that

g(X) = (X - r_0)^{m_0}q_0(X), \quad q_0(r_0) \ne 0.

Now let $r_1 \ne r_0$ be another root of $g$ . Since $\mathbb{F}$ is an integral domain, $(r_1 - r_0)^{m_0} \ne 0$ , and hence

0 = g(r_1) = (r_1 - r_0)^{m_0}q_0(r_1)

implies $q_0(r_1) = 0$ . Thus $q_0(X)$ is divisible by $X - r_1$ .

Repeating this process for distinct roots, each new root reduces the degree of the remaining factor by at least one. Since the original polynomial has degree $d$ , the total number of roots, counted with multiplicity, cannot exceed $d$ .

Proof

The proof is by induction on $v$ . The base case $v = 1$ is the previous proposition. Let $v \ge 2$ and assume the statement holds for all nonzero polynomials in $u$ indeterminates, $1 \le u \le v - 1$ .

Writing $g$ as in (1), note that

\begin{align} g(X_0,\ldots,X_{v - 1}) & = \sum_{e \, \in \, \mathbb{N}^{v}} a_{e} X_0^{e_0}\cdots X_{v - 1}^{e_{v - 1}} \\ & = \sum_{e_{v-1} \, \in \, \mathbb{N}} X_{v-1}^{e_{v-1}} \sum_{(e_0,\ldots,e_{v-2}) \, \in \, \mathbb{N}^{v-1}} a_{e} X_0^{e_0}\cdots X_{v - 2}^{e_{v - 2}} \\ & = \sum_{k \, = \, 0}^{d} X_{v-1}^k h_k(X_0,\ldots,X_{v-2}), \end{align}

say, where we have replaced $e_{v - 1}$ by $k$ in the outer sum and truncated it at $k = d$ , because total degree $d$ implies $e_{v - 1} \le d$ for every monomial with nonzero coefficient. We can’t have $h_k \equiv 0$ for every $k$ , for in that case we’d also have $g \equiv 0$ . Let $j = \max\{k: h_k \not\equiv 0\}$ be the largest $k$ for which $h_k$ is a nonzero polynomial.

We now separate the roots of $g$ according to whether the leading coefficient (as a polynomial in $X_{v - 1}$ ) vanishes:

\{\mathbf{r} \in \mathbb{F}^{v} : g(\mathbf{r}) = 0\} \subseteq \{\mathbf{r} \in \mathbb{F}^{v} : h_j(r_0,\ldots,r_{v-2}) = 0\} \cup \{\mathbf{r} \in \mathbb{F}^v : h_j(r_0,\ldots,r_{v-2}) \ne 0 \,\, \text{and} \,\, g(\mathbf{r}) = 0 \}.

We will show that the sets on the RHS have sizes bounded by $(\#\mathbb{F})^{v - 1}(d - j)$ and $(\#\mathbb{F})^{v - 1}j$ respectively.

Since $X_{v-1}^jh_j(X_0,\ldots,X_{v-2})$ has degree at most $\mathrm{deg} \, (g) = d$ , we have $\mathrm{deg} \, (h_j) \le d - j$ . Therefore, by inductive hypothesis,

\#\{(r_0,\ldots,r_{v - 2}) \in \mathbb{F}^{v - 1} : h_j(r_0,\ldots,r_{v-2}) = 0\} \le (\#\mathbb{F})^{v - 2}(d - j).

Consequently,

\#\{(r_0,\ldots,r_{v - 2},r_{v-1}) \in \mathbb{F}^v : h_j(r_0,\ldots,r_{v-2}) = 0\} \le (\#\mathbb{F})^{v - 1}(d - j).

If $h_j(r_0,\ldots,r_{v - 2}) \ne 0$ , then $g(r_0,\ldots,r_{v-2},X_{v-1})$ is a nonzero univariate polynomial of degree $j$ (its leading term is $X_{v-1}^jh_j(r_0,\ldots,r_{v-2}))$ . There are trivially at most $(\#\mathbb{F})^{v-1}$ tuples $(r_0,\ldots,r_{v-2}) \in \mathbb{F}^{v - 1}$ such that $h_j(r_0,\ldots,r_{v-2}) \ne 0$ , and for each such tuple, there are at most $j$ elements $r_{v - 1}$ of $\mathbb{F}$ such that $g(r_0,\ldots,r_{v-1}) = 0$ . This follows from the univariate case, since such $r_{v-1}$ are roots of a nonzero univariate polynomial of degree $j$ . Hence,

\#\{(r_0,\ldots,r_{v - 1}) \in \mathbb{F}^v : h_j(r_0,\ldots,r_{v-2}) \ne 0 \,\, \text{and} \,\, g(r_0,\ldots,r_{v-1}) = 0 \} \le (\#\mathbb{F})^{v-1}j.

Example 2

from sympy import symbols, Poly, GF
from gkr import roots_example

X = symbols("X_:2")
g_small = Poly(X[0]*X[1] + 1, X, domain=GF(5, symmetric=False))

Y = symbols("X_:3")
g_big = Poly(Y[0]*Y[1] + Y[2]**2, Y, domain=GF(331, symmetric=False))

roots_example(polynomials=[g_small, g_big], time_out=3)


EXAMPLE 1. The polynomial X_0*X_1 + 1 has 4 roots in (GF(5))^(2).


Thus, if each of r_0, r_1 is chosen independently and uniformly at random from GF(5), then g(r_0, r_1) = 0 with probability 4/5**2 = 0.16.


The polynomial has total degree d = 2, and the Schwartz-Zippel bound is 2/5 = 0.4.


Observed probability is below the Schwartz-Zippel upper bound.


Here are the roots:

g(1, 4) = 0

g(2, 2) = 0

g(3, 3) = 0

g(4, 1) = 0


EXAMPLE 2. In 3 seconds, we found 436 roots of X_0*X_1 + X_2**2 in (GF(331))^(3).


There may be more roots, so what follows is not a verification of Schwartz-Zippel.


Thus, if each of r_0, r_1, r_2 is chosen independently and uniformly at random from GF(331), then g(r_0, r_1, r_2) = 0 with probability at least 436/331**3 = 1.2022713774122602e-05 (this is a lower bound). Schwartz-Zippel gives an upper bound.


The polynomial has total degree d = 2, and the Schwartz-Zippel bound is 2/331 = 0.006042296072507553.


Here are 10 of the roots:

g(0, 0, 0) = 0

g(0, 1, 0) = 0

g(0, 2, 0) = 0

g(0, 3, 0) = 0

g(0, 4, 0) = 0

g(0, 5, 0) = 0

g(0, 6, 0) = 0

g(0, 7, 0) = 0

g(0, 8, 0) = 0

g(0, 9, 0) = 0

Sum-check protocol of Lund, Fortnow, Karloff, and Nisan, as described by Thaler¶

This is a description of the sum-check protocol as presented by Lund, Fortnow, Karloff, and Nisan in 2, with the exposition following Thaler’s treatment in 1

Initialization. Given a nonzero $v$ -variate polynomial $g$ over a finite field $\mathbb{F}$ , let

H := \sum_{b_0 \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(b_0,\ldots,b_{v - 1}).

(5)

Although verifier V does not know $g$ , the number of indeterminates $v$ and upper bounds $\mathrm{deg}_{X_j}(g) \le d_j$ are known to V. Prover P claims that

H \overset{\mathsf{P}}{\underset{\text{claim}}{=}} H^*,

sending this claim to V, who needs to verify that this claim is true by interacting with P.

Remark 5 (notation and epistemic status)

We distinguish between ground-truth objects and objects that the prover P merely claims to be ground-truth by using an asterisk. Thus, $H$ denotes the true value of the right-hand side of $(5)$ , whereas $H^{*}$ denotes the value that P claims it to be. Any expression involving asterisked notation may therefore be false, and the verifier V’s goal is to detect such inconsistencies with high probability.

To make the epistemic status of equalities explicit, we use the notation

\overset{\mathsf{P}}{\underset{\text{claim}}{=}}

to denote an equality explicitly asserted by P, which may be false.

Finally, we use the notation

\stackrel{?}{=}, \, \stackrel{?}{\le}

to denote an (in)equality that the verifier checks as part of the sum-check protocol. Such an equality is not asserted outright by P, but is instead forced by the protocol transcript: if P behaves honestly, the equality holds deterministically, whereas if P behaves dishonestly, the verifier accepts a false equality only with negligible probability.

Round 0. Let

g_0(X_0) := \sum_{b_1 \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(X_0,b_1,\ldots,b_{v - 1}).

(6)

P sends polynomial $g^*_0$ to V, claiming that

g^*_0 \overset{\mathsf{P}}{\underset{\text{claim}}{=}} g_0.

(Here, ‘P sends a polynomial’ means P sends an explicit representation, e.g., its coefficients.) If so, then

\mathrm{deg}(g^*_0) \stackrel{?}{=} \mathrm{deg}(g_0) \le \mathrm{deg}_0(g) = d_0.

V verifies this: if $\mathrm{deg}(g^*_0) > d_0$ then V ‘rejects’ and the protocol terminates. Otherwise, we continue. If P’s claims that

H \overset{\mathsf{P}}{\underset{\text{claim}}{=}} H^* \quad \text{and} \quad g^*_0 \overset{\mathsf{P}}{\underset{\text{claim}}{=}} g_0

are both true, then

H^* \stackrel{?}{=} g^*_0(0) + g^*_0(1).

(7)

This is because $H = g_0(0) + g_0(1)$ . V verifies (7), which is easy because $g^*_0$ is explicitly given as a univariate polynomial, even though V cannot compute $g_0$ efficiently from scratch. If (7) does not hold, then V rejects and the protocol terminates. Otherwise, V chooses $r_0$ uniformly at random from $\mathbb{F}$ , and sends it to P.

Round j ( $1 \le j \le v - 1$ ). Let

g_j(X_j) := \sum_{b_{j+1} \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(r_0,r_1,\ldots,r_{j-1},X_j,b_{j+1},\ldots,b_{v - 1}).

(8)

P responds to V’s random challenge $r_{j - 1}$ by sending V a polynomial $g^*_{j}$ , claiming that

g^*_{j} \overset{\mathsf{P}}{\underset{\text{claim}}{=}} g_j.

If so, then

\mathrm{deg}(g^*_j) \stackrel{?}{=} \mathrm{deg}(g_j) \le \mathrm{deg}_j(g) = d_j.

V verifies this: if $\mathrm{deg}(g^*_j) > d_j$ then V ‘rejects’ and the protocol terminates. Otherwise, we continue. If P’s previous claims that

g^*_{j-1} \overset{\mathsf{P}}{\underset{\text{claim}}{=}} g_{j - 1} \quad \text{and} \quad g^*_{j} \overset{\mathsf{P}}{\underset{\text{claim}}{=}} g_{j}

are both true, then

g^*_{j - 1}(r_{j - 1}) \stackrel{?}{=} g^*_j(0) + g^*_j(1).

(9)

This is because $g_{j - 1}(r_{j - 1}) = g_j(0) + g_j(1)$ . To see this, note that by definition (8),

\begin{align*} g_{j - 1}(r_{j - 1}) & = \sum_{b_{j} \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(r_0,r_1,\ldots,r_{j-2},r_{j-1},b_{j},\ldots,b_{v - 1}) \end{align*}

and

\begin{align} g_j(0) + g_j(1) & = \sum_{b_{j+1} \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(r_0,r_1,\ldots,r_{j-1},0,b_{j+1},\ldots,b_{v - 1}) + \sum_{b_{j+1} \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(r_0,r_1,\ldots,r_{j-1},1,b_{j+1},\ldots,b_{v - 1}) \\ & = \sum_{b_{j} \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(r_0,r_1,\ldots,r_{j-1},b_j,b_{j+1},\ldots,b_{v - 1}). \end{align}

V verifies (9), which is easy because $g_{j - 1}$ and $g_{j}$ are explicitly given as univariate polynomials, even though V cannot compute $g_{j - 1}$ and $g_{j}$ efficiently from scratch. If (9) does not hold, V rejects and the protocol terminates. Otherwise, V chooses $r_j$ uniformly at random from $\mathbb{F}$ , independently of $r_0,\ldots,r_{j-1}$ , and sends it to P.

It helps to write out Round $v - 1$ explicitly. In the final round, P sends $g^*_{v - 1}$ to V, claiming that

g^*_{v - 1} \overset{\mathsf{P}}{\underset{\text{claim}}{=}} g_{v - 1},

where

g_{v - 1}(X_{v - 1}) := g(r_0,\ldots,r_{v - 2},X_{v - 1}).

(10)

V verifies that $\mathrm{deg}(g^*_{v-1}) \stackrel{?}{\le} d_{v-1}$ and that $g^*_{v - 2}(r_{v - 2}) \stackrel{?}{=} g^*_{v - 1}(0) + g^*_{v - 1}(1)$ . If either the degree bound or (9) with $j = v - 1$ does not hold, V rejects and the protocol terminates. Otherwise, we continue.

Final check. V chooses $r_{v - 1}$ uniformly at random from $\mathbb{F}$ , independently of $r_0,\ldots,r_{v-2}$ , and verifies that

g^*_{v - 1}(r_{v - 1}) \stackrel{?}{=} g(r_0,\ldots,r_{v - 2},r_{v - 1}),

(11)

which holds if $g^*_{v-1} \overset{\mathsf{P}}{\underset{\text{claim}}{=}} g_{v-1}$ is true, in view of (10). If (11) does not hold, then V rejects. Otherwise, V accepts that $H \overset{\mathsf{P}}{\underset{\text{claim}}{=}} H^*$ is true and P passes the sum-check protocol. The protocol is complete.

Remark 6 (oracle access and evaluation)

In the original interactive-proof setting, the verifier is assumed to have oracle access to the evaluation map induced by the polynomial $g$ . That is, although $g$ is formally an element of $\mathbb{F}[X_0,\ldots,X_{v-1}]$ , the verifier may query the oracle at any point $\mathbf r \in \mathbb{F}^v$ and receive the value $g(\mathbf r)$ . We will freely identify a polynomial with the polynomial function it induces on $\mathbb{F}^v$ , since the verifier only ever interacts with $g$ through such evaluations.

In cryptographic implementations, this oracle access is replaced by a binding commitment to $g$ (or to a witness that uniquely determines $g$ ), together with a separate mechanism that allows the verifier to check claimed point evaluations. Concretely, when the verifier requests the value of $g$ at $(r_0,\ldots,r_{v-1})$ in the final check, the prover supplies both the value $g(r_0,\ldots,r_{v-1})$ and a proof that this value is consistent with the committed polynomial. This evaluation-consistency check is provided by the commitment scheme itself (for example, a polynomial commitment), and is not an invocation of the sum-check protocol.

Although the verifier may have oracle access to evaluations of $g$ , computing $H$ directly from the oracle would require $2^v$ queries. The sum-check protocol shows how to reduce verification of this exponentially large sum to a linear number of oracle queries by exploiting the low-degree structure of $g$ .

Example 3

from gkr import sum_check_example
sum_check_example(interactive=False)


EXAMPLE 1.


==============

INITIALIZATION

==============


Let

g(X_0, X_1, X_2) = X_0*X_1 + 4*X_0*X_2 + 4*X_1**2 + X_1*X_2.


We display g for the reader. In the protocol, V does not receive g explicitly; V only has oracle/committed evaluation access to g.


For soundness, V relies on degree bounds per variable (this is public information): [1, 2, 1].


Let

H := sum g(b_0, b_1, b_2) over (b_0, b_1, b_2) in {0,1}^3.


P claims that H = H*, where H* = 3.


=======

ROUND 0

=======


Let

g_0(X_0) := sum g(X_0, b_1, b_2) over (b_1, b_2) in {0,1}^2


P claims that g_0(X_0) = g*_0(X_0), where 

g*_0(X_0) = 4.


If P's last two claims are true, then deg(g*_0) ≤ deg_0(g) and H* = g*_0(0) + g*_0(1).


V checks the degree bound: deg(g*_0) = 0 ≤ deg_0(g) = 1.


P's claim is that H = H* = 3. V proceeds to compute:

g*_0(0) + g*_0(1) = 3


This is easy because g*_0 is given explicitly, so V can evaluate it at 0 and 1.


V sees that P's claims so far are consistent.


V samples an element uniformly at random from GF(5); here r_0 = 0.


=======

ROUND 1

=======


Let

g_1(X_1) := sum g(0, X_1, b_2) over (b_2) in {0,1}^1


P claims that g_1(X_1) = g*_1(X_1), where 

g*_1(X_1) = 3*X_1**2 + X_1.


If P's last two claims are true, then deg(g*_1) ≤ deg_1(g) and g*_0(0) = g*_1(0) + g*_1(1).


V checks the degree bound: deg(g*_1) = 2 ≤ deg_1(g) = 2.


V proceeds to compute:

          g*_0(0) = 4

g*_1(0) + g*_1(1) = 4


This is easy because both claimed polynomials are given explicitly, and V only needs univariate evaluations at 0 and 1.


V sees that P's claims so far are consistent.


V samples an element uniformly at random from GF(5); here r_1 = 4.


=======

ROUND 2

=======


Let

g_2(X_2) := g(0, 4, X_2)


P claims that g_2(X_2) = g*_2(X_2), where 

g*_2(X_2) = 4*X_2 + 4.


If P's last two claims are true, then deg(g*_2) ≤ deg_2(g) and g*_1(4) = g*_2(0) + g*_2(1).


V checks the degree bound: deg(g*_2) = 1 ≤ deg_2(g) = 1.


V proceeds to compute:

          g*_1(4) = 2

g*_2(0) + g*_2(1) = 2


This is easy because both claimed polynomials are given explicitly, and V only needs univariate evaluations at 0 and 1.


V sees that P's claims so far are consistent.


FINAL CHECK


V samples an element uniformly at random from GF(5); here r_2 = 3.


If all of P's claims are true, then

g*_2(3) = g(0, 4, 3).


V computes

g*_2(3) = 1.


Finally, V queries an oracle for g at r to obtain

g(0, 4, 3) = 1.


P passes the final verification, and V ACCEPTS P's initial claim that H = H*.


Verifier accepted.


============

GROUND TRUTH

============


True polynomial g:

g(X_0, X_1, X_2) = X_0*X_1 + 4*X_0*X_2 + 4*X_1**2 + X_1*X_2


True value of H := sum g(b) over b in {0,1}^3 is: 3


Prover claimed that this is equal to: H* = 3.


Outcome: V ACCEPTED.


This was a TRUE POSITIVE: the claim H = H* was correct.

Why V should be convinced if P passes sum check¶

The sum-check protocol is complete: if P’s claims are true, P will pass the protocol, assuming V’s calculations are accurate. If V rejects, then at least one of P’s claims is inconsistent with the protocol checks.

In terms of soundness, a dishonest P may provide an incorrect value for the initial sum $H$ and still pass sum check. However, we can make the probability of this event—the soundness error—as small as desired by choosing a large field size $\#\mathbb{F}$ relative to $vd$ . The probability of V being convinced of a false value for the initial sum is at most $vd/\#\mathbb{F}$ .

To recap the sum-check protocol, we have

\begin{align} H & := \sum_{b_0 \, \in \, \{0,1\}} \cdots \sum_{b_{v - 1} \, \in \, \{0,1\}} g(b_0,\ldots,b_{v-1}) \\ g_0(X_0) & := \sum_{b_1 \, \in \, \{0,1\}} \cdots \sum_{b_{v - 1} \, \in \, \{0,1\}} g(X_0,b_1,\ldots,b_{v-1}) \end{align}

Also, $r_0,\ldots,r_{v-1}$ are selected independently and uniformly at random from $\mathbb{F}$ , and

\begin{align} g_j(X_j) & := \sum_{b_{j + 1} \, \in \, \{0,1\}} \cdots \sum_{b_{v - 1} \, \in \, \{0,1\}} g(r_0,\ldots,r_{j-1},X_j,b_{j+1},\ldots,b_{v-1}), \quad 0 \le j \le v - 2 \\ g_{v-1}(X_{v-1}) & := g(r_0,\ldots,r_{v-2},X_{v-1}) \end{align}

Letting $d_j := \mathrm{deg}_{j}(g)$ for $0 \le j \le v - 1$ , we have

\mathrm{deg}(g_j) \le d_j, \quad 0 \le j \le v - 1.

Also,

\begin{align} H & = g_0(0) + g_0(1) \\ g_{j-1}(r_{j-1}) & = g_j(0) + g_j(1), \quad 1 \le j \le v - 1 \\ g_{v-1}(r_{v-1}) & = g(r_0,\ldots,r_{v-1}) \end{align}

P claims that $H \overset{\mathsf{P}}{\underset{\text{claim}}{=}} H^*$ and $g_j \overset{\mathsf{P}}{\underset{\text{claim}}{=}} g_j^*$ for $0 \le j \le v - 1$ , passing sum check if and only if the V’s acceptance conditions hold:

\begin{align} \begin{split} \mathrm{deg}(g^*_j) & \stackrel{?}{\le} d_j, \quad 0 \le j \le v - 1, \\ H^* & \stackrel{?}{=} g^*_0(0) + g^*_0(1) \\ g^*_{j-1}(r_{j-1}) & \stackrel{?}{=} g^*_j(0) + g^*_j(1), \quad 1 \le j \le v - 1 \\ g^*_{v-1}(r_{v-1}) & \stackrel{?}{=} g(r_0,\ldots,r_{v-1}) \end{split} \end{align}

(12)

Suppose P’s claim for the value of the initial sum is false, i.e. in fact $H^* \ne H$ , and that P passes sum-check in spite of this, i.e. V’s acceptance conditions (12) all hold. If we had $g^*_0 = g_0$ , then we’d have $g^*_0(0) + g^*_0(1) = g_0(0) + g_0(1) = H \ne H^*$ , and so V would reject in Round 0. Therefore, $g^*_0 \ne g_0$ .

Case 1. $g^*_j \ne g_j$ for all $j$ , $0 \le j \le v - 1$ . In particular, $g^*_{v - 1} \ne g_{v - 1}$ , and by the final acceptance condition,

g^*_{v-1}(r_{v - 1}) = g_{v-1}(r_{v-1}) = g(r_0,\ldots,r_{v-1}).

Case 2. There is a minimal $k$ , $1 \le k \le v - 1$ , such that $g^*_{k-1} \ne g_{k-1}$ and $g^*_k = g_k$ . By the acceptance condition of Round k,

g^*_{k-1}(r_{k-1}) = g^*_k(0) + g^*_k(1) = g_k(0) + g_k(1) = g_{k - 1}(r_{k - 1}).

If Case 1 holds, take $k = v\,$ ; else take $k$ as in Case 2. In either case, there is a sequence of polynomials $g^*_0 \ne g_0,\ldots,g^*_{k-1} \ne g_{k-1}$ , where $1 \le k \le v$ , such that $g^*_{k-1}(r_{k-1}) = g_{k-1}(r_{k-1})$ . Since $g_{k - 1}$ and $g^*_{k-1}$ are fixed after seeing the transcript $(r_0,\ldots,r_{k - 1})$ but before $r_{k - 1}$ is chosen, they are independent of $r_{k - 1}$ . Moreover, by the degree bounds, the (univariate) polynomial $g^*_{k - 1} - g_{k - 1}$ is nonzero and has degree at most $d_{k - 1} \le d := \mathrm{deg}(g)$ . Therefore, since $r_{k - 1}$ is uniform in $\mathbb{F}$ ,

\mathrm{Pr}[(g^*_{k - 1} - g_{k - 1})(r_{k-1}) = 0] \le \frac{d_{k - 1}}{\#\mathbb{F}} \le \frac{d}{\#\mathbb{F}} \tag{12}

by the univariate root bound (equivalently, the $v = 1$ case of Schwartz-Zippel Schwartz-Zippel).

In each round $j \ge 1$ , while V verifies that $g^*_{j-1}(r_{j-1}) = g^*_j(0) + g^*_j(1)$ (which could hold even if $g^*_{j-1}(r_{j-1}) \ne g_{j-1}(r_{j-1})$ ), P can check whether $g^*_{j - 1}(r_{j - 1}) = g_{j-1}(r_{j - 1})$ . (This check is possible because the prover knows [or can compute from a witness defining] the underlying polynomial $g$ and can efficiently evaluate $g$ at arbitrary points. In particular, P can compute the value $g_{j - 1}(r_{j - 1})$ directly as a sum of evaluations of $g$ without ever expanding $g_{j - 1}$ symbolically.) If this equality holds, P can then revert to sending the ‘true’ polynomials $g^*_j = g_j$ for subsequent rounds $j$ and pass the sum-check protocol.

Finally, we note that V will accept a false value for the sum $H$ in the end in the event that the above occurs for any $k$ , $1 \le k \le v$ . Therefore, by the union bound and $(12)$ ,

\mathrm{Pr}[ \text{V accepts} \, | \, H^* \ne H] \le \frac{\sum_{j = 0}^{v - 1}d_j}{\#\mathbb{F}} \le \frac{vd}{\#\mathbb{F}}.

(13)

Remark 7

(i) If P provides a false value $H^*$ for the initial sum, their strategy to pass the sum-check protocol might involve finding a polynomial $g^*_0 \ne g_0$ , of degree at most $d_0$ , such that $g^*_0 - g_0$ has as many roots as possible in $\mathbb{F}$ , while satisfying the condition $g^*_0(0) + g^*_0(1) = H^*$ . This maximizes the likelihood that $g^*_0(r_0) = g_0(r_0)$ . If this coincidence occurs, P can immediately switch to sending the ‘true’ polynomials to V, starting with $g^*_1 = g_1$ , since the acceptance condition $g^*_0(r_0) = g^*_1(0) + g^*_1(1)$ will hold (because $g_0(r_0) = g_1(0) + g_1(1)$ ). Notably, the acceptance condition might still hold even if $g^*_0(r_0) \ne g_0(r_0)$ . In that case, P would seek a polynomial $g^*_1 \ne g_1$ such that $g^*_1 - g_1$ has as many roots as possible in $\mathbb{F}$ , and so on.

For instance, suppose $\mathbb{F}$ is a prime field of order $p$ , and that $g_0$ has degree $d_0$ , where $2 \le d_0 < p$ . If $\{\alpha_0,\ldots,\alpha_{k-1}\}$ is any set of $k$ distinct field elements such that

[(0 - \alpha_0)\cdots (0 - \alpha_{k-1})] + [(1 - \alpha_0)\cdots (1 - \alpha_{k-1})] \ne 0,

and if $\alpha_{k} \in \mathbb{F}$ satisfies

(0 - \alpha_{k}) = \frac{[H^* - H] - [(1 - \alpha_0)\cdots (1 - \alpha_{k-1})]}{[(0 - \alpha_0)\cdots (0 - \alpha_{k-1})] + [(1 - \alpha_0)\cdots (1 - \alpha_{k-1})]},

then

[(0 - \alpha_0)\cdots (0 - \alpha_{k})] + [(1 - \alpha_0)\cdots (1 - \alpha_{k})] = H^* - H \ne 0.

If $\alpha_{k} \not\in \{\alpha_0,\ldots,\alpha_{k - 1}\}$ , then we now have $k + 1$ distinct field elements $\alpha_0,\ldots,\alpha_k$ such that

g^*_0(X_0) := g_0(X_0) + (X_0 - \alpha_0)\cdots (X_0 - \alpha_{k})

satisfies

g^*_0(0) + g^*_0(1) = H^*.

A dishonest prover P may try to generate such a polynomial $g^*_0$ with $k$ as large as possible while not exceeding $d_0 - 1$ . Then $g_0^*$ is distinct from $g_0$ , has degree at most $d_0$ , and $g^*_0(r_0) = g_0(r_0)$ if and only if $r_0 \in \{\alpha_0,\alpha_1,\ldots,\alpha_{k}\}$ . That is, $\mathrm{Pr}[ g^*_0(r_0) = g_0(r_0) ] = (k+1)/\#\mathbb{F}$ . Given that $g^*_0 \ne g_0$ and $\mathrm{deg}(g^*_0) \le \mathrm{deg}(g_0) \le \mathrm{deg}(g)$ , this probability can be at most $d/\#\mathbb{F}$ , by the Schwartz-Zippel lemma.

Alternatively, P could start with a multivariate polynomial $g^*$ different from $g$ , where $\mathrm{deg}(g^*) \le d$ and the sum of $g^*$ over the Boolean hypercube equals $H^* \ne H$ . P would then respond to all of V’s challenges as though $g^*$ were the same as $g$ . For the final check to pass, it would require that $g^*(r_0, \ldots, r_{v-1}) = g(r_0, \ldots, r_{v-1})$ . P could maximize the likelihood of this by choosing a $g^* \ne g$ such that $g^* - g$ has as many roots as possible in $\mathbb{F}^v$ . By the Schwartz-Zippel lemma, the probability that $(r_0, \ldots, r_{v - 1})$ is a root of $g^* - g$ remains at most $vd/\#\mathbb{F}$ .

(ii) If the degree $d$ of $g$ were concealed from V, a dishonest P could inflate the degrees of the $g^*_j$ polynomials, increasing the probability of passing.

(iii) In the sum-check protocol, the degree $d$ of $g$ and the number of indeterminates $v$ are typically known to V beforehand, as they are determined by the structure of the problem being verified. These parameters are either agreed upon during the setup phase or are intrinsic to the function being evaluated (e.g., a multilinear extension or arithmetic circuit). The verifier ensures the prover’s adherence to these parameters by checking that the submitted polynomials meet the degree constraints at each round.

Example 4

from sympy import symbols, Poly, GF
from gkr import sum_check_example

x, y, z = symbols("x y z")
g = Poly(x**2 + 2*x*y*z + y*z**2, x, y, z, domain=GF(331, symmetric=False))

sum_check_example(scenario={"poly": g, "claim": 7, "challenges": [6, 77, 4]})


==============

INITIALIZATION

==============


Let

g(x, y, z) = x**2 + 2*x*y*z + y*z**2.


We display g for the reader. In the protocol, V does not receive g explicitly; V only has oracle/committed evaluation access to g.


For soundness, V relies on degree bounds per variable (this is public information): [2, 1, 2].


Let

H := sum g(b_0, b_1, b_2) over (b_0, b_1, b_2) in {0,1}^3.


P claims that H = H*, where H* = 7.


In this run, P's initial claim H* is intentionally false, and P will try to get away with it.


=======

ROUND 0

=======


Let

g_0(x) := sum g(x, b_1, b_2) over (b_1, b_2) in {0,1}^2


P claims that g_0(x) = g*_0(x), where 

g*_0(x) = 5*x**2 + 1.


If P's last two claims are true, then deg(g*_0) ≤ deg_0(g) and H* = g*_0(0) + g*_0(1).


V checks the degree bound: deg(g*_0) = 2 ≤ deg_0(g) = 2.


P's claim is that H = H* = 7. V proceeds to compute:

g*_0(0) + g*_0(1) = 7


This is easy because g*_0 is given explicitly, so V can evaluate it at 0 and 1.


V sees that P's claims so far are consistent.


V samples an element uniformly at random from GF(331); here r_0 = 6.


=======

ROUND 1

=======


Let

g_1(y) := sum g(6, y, b_2) over (b_2) in {0,1}^1


P claims that g_1(y) = g*_1(y), where 

g*_1(y) = 35*y + 73.


If P's last two claims are true, then deg(g*_1) ≤ deg_1(g) and g*_0(6) = g*_1(0) + g*_1(1).


V checks the degree bound: deg(g*_1) = 1 ≤ deg_1(g) = 1.


V proceeds to compute:

          g*_0(6) = 181

g*_1(0) + g*_1(1) = 181


This is easy because both claimed polynomials are given explicitly, and V only needs univariate evaluations at 0 and 1.


V sees that P's claims so far are consistent.


V samples an element uniformly at random from GF(331); here r_1 = 77.


=======

ROUND 2

=======


Let

g_2(z) := g(6, 77, z)


P claims that g_2(z) = g*_2(z), where 

g*_2(z) = 78*z**2 + 301*z + 36.


If P's last two claims are true, then deg(g*_2) ≤ deg_2(g) and g*_1(77) = g*_2(0) + g*_2(1).


V checks the degree bound: deg(g*_2) = 2 ≤ deg_2(g) = 2.


V proceeds to compute:

         g*_1(77) = 120

g*_2(0) + g*_2(1) = 120


This is easy because both claimed polynomials are given explicitly, and V only needs univariate evaluations at 0 and 1.


V sees that P's claims so far are consistent.


FINAL CHECK


V samples an element uniformly at random from GF(331); here r_2 = 4.


If all of P's claims are true, then

g*_2(4) = g(6, 77, 4).


V computes

g*_2(4) = 171.


Finally, V queries an oracle for g at r to obtain

g(6, 77, 4) = 330.


P fails the final verification, and V REJECTS P's initial claim that H = H*.


Interpretation: P can often keep the transcript locally consistent round-by-round, but the final random evaluation ties the transcript to the true g and typically catches a lie.


============

GROUND TRUTH

============


True polynomial g:

g(x, y, z) = x**2 + 2*x*y*z + y*z**2


True value of H := sum g(b) over b in {0,1}^3 is: 8


Prover claimed that this is equal to: H* = 7.


Outcome: V REJECTED.


This was a TRUE NEGATIVE: V rejected a false claim.

Example 5

from sympy import symbols, Poly, GF
from gkr import sum_check_example

x, y, z = symbols("x y z")
g = Poly(x**2 + 2*x*y*z + y*z**2, x, y, z, domain=GF(331, symmetric=False))

sum_check_example(scenario={"poly": g, "claim": 7, "challenges": [2, 4, 1]})


==============

INITIALIZATION

==============


Let

g(x, y, z) = x**2 + 2*x*y*z + y*z**2.


We display g for the reader. In the protocol, V does not receive g explicitly; V only has oracle/committed evaluation access to g.


For soundness, V relies on degree bounds per variable (this is public information): [2, 1, 2].


Let

H := sum g(b_0, b_1, b_2) over (b_0, b_1, b_2) in {0,1}^3.


P claims that H = H*, where H* = 7.


In this run, P's initial claim H* is intentionally false, and P will try to get away with it.


=======

ROUND 0

=======


Let

g_0(x) := sum g(x, b_1, b_2) over (b_1, b_2) in {0,1}^2


P claims that g_0(x) = g*_0(x), where 

g*_0(x) = 5*x**2 + 1.


If P's last two claims are true, then deg(g*_0) ≤ deg_0(g) and H* = g*_0(0) + g*_0(1).


V checks the degree bound: deg(g*_0) = 2 ≤ deg_0(g) = 2.


P's claim is that H = H* = 7. V proceeds to compute:

g*_0(0) + g*_0(1) = 7


This is easy because g*_0 is given explicitly, so V can evaluate it at 0 and 1.


V sees that P's claims so far are consistent.


V samples an element uniformly at random from GF(331); here r_0 = 2.


=======

ROUND 1

=======


Let

g_1(y) := sum g(2, y, b_2) over (b_2) in {0,1}^1


P claims that g_1(y) = g*_1(y), where 

g*_1(y) = 5*y + 8.


If P's last two claims are true, then deg(g*_1) ≤ deg_1(g) and g*_0(2) = g*_1(0) + g*_1(1).


V checks the degree bound: deg(g*_1) = 1 ≤ deg_1(g) = 1.


V proceeds to compute:

          g*_0(2) = 21

g*_1(0) + g*_1(1) = 21


This is easy because both claimed polynomials are given explicitly, and V only needs univariate evaluations at 0 and 1.


V sees that P's claims so far are consistent.


V samples an element uniformly at random from GF(331); here r_1 = 4.


=======

ROUND 2

=======


Let

g_2(z) := g(2, 4, z)


P claims that g_2(z) = g*_2(z), where 

g*_2(z) = 4*z**2 + 16*z + 4.


If P's last two claims are true, then deg(g*_2) ≤ deg_2(g) and g*_1(4) = g*_2(0) + g*_2(1).


V checks the degree bound: deg(g*_2) = 2 ≤ deg_2(g) = 2.


V proceeds to compute:

          g*_1(4) = 28

g*_2(0) + g*_2(1) = 28


This is easy because both claimed polynomials are given explicitly, and V only needs univariate evaluations at 0 and 1.


V sees that P's claims so far are consistent.


FINAL CHECK


V samples an element uniformly at random from GF(331); here r_2 = 1.


If all of P's claims are true, then

g*_2(1) = g(2, 4, 1).


V computes

g*_2(1) = 24.


Finally, V queries an oracle for g at r to obtain

g(2, 4, 1) = 24.


P passes the final verification, and V ACCEPTS P's initial claim that H = H*.


P HAS DECEIVED V: THE TRUE VALUE OF H IS IN FACT 8.


P GOT LUCKY: the final random check happened not to expose the inconsistency this time. Over a large field, this success event should be rare.


============

GROUND TRUTH

============


True polynomial g:

g(x, y, z) = x**2 + 2*x*y*z + y*z**2


True value of H := sum g(b) over b in {0,1}^3 is: 8


Prover claimed that this is equal to: H* = 7.


Outcome: V ACCEPTED.


This was a FALSE POSITIVE: V accepted a false claim (P got lucky).

Complexity and proof size¶

Verifier’s runtime¶

In Round $j$ of the sum-check protocol, verifier V performs the following steps:

Degree bound check: verify that $\deg(g_j^*) \le d_j$ .
Consistency check: verify that $g^*_{j-1}(r_{j-1}) = g^*_j(0) + g^*_j(1)$ (with $H^*$ substituted for $g^*_{-1}(r_{-1})$ in Round 0, i.e. $H^* = g^*_0(0) + g^*_0(1)$ ).
Sample a random field element $r_j \in \mathbb{F}$ .
Final check: verify that $g^*_{v-1}(r_{v-1}) = g(r_0,\ldots,r_{v-1})$ .

Note that each $d_j := \deg_j(g)$ satisfies $d_j \le d$ , where $d := \deg(g)$ is the total degree. Since each $g^*_j$ is a univariate polynomial, the work in Round $j$ is:

Degree verification: $O(t_j)$ field operations, where $t_j$ is the number of terms used to represent $g_j^*$ (e.g. the number of nonzero coefficients sent as pairs $(i,c_i)$ ). In the dense-coefficient representation this is $O(d)$ .
Evaluation check: $O(d)$ field operations, because evaluating a univariate polynomial of degree at most $d$ can be done with $d$ multiplications and $d$ additions using Horner’s method.
Random field element generation: this is often treated as $O(1)$ in protocol analyses (randomness is assumed available). In bit complexity, sampling a uniform element from $\mathbb{F}_{p^k}$ costs $O(k\log p)$ expected time (e.g. by rejection sampling in $\mathbb{F}_p$ and sampling $k$ coefficients for $\mathbb{F}_{p^k}$ ).
Final round verification: $O(d)$ field operations to compute $g^*_{v-1}(r_{v-1})$ , plus the cost of obtaining and verifying the value $g(r_0,\ldots,r_{v-1})$ (one oracle query in the interactive-proof model, or one commitment opening verification in cryptographic implementations).

Horner’s method is an efficient way to evaluate a polynomial given its coefficients. Rewrite a degree- $d$ polynomial

P(X) = c_0 + c_1X + \cdots + c_d X^d

in nested form:

P(X) = c_0 + X\bigl(c_1 + X\bigl(c_2 + \cdots + X(c_{d-1} + Xc_d)\cdots\bigr)\bigr).

Given $a \in \mathbb{F}$ , set $A_d := c_d$ and compute recursively

A_j = c_j + aA_{j+1}, \quad j = d-1, d-2,\ldots,0.

Then $P(a) = A_0$ .

In practical implementations, $d$ is usually much smaller than $k\log p$ , so random number generation can dominate if done online. To mitigate this, $r_0,\ldots,r_{v-1}$ are typically precomputed. We assume this is the case.

Complexity of evaluating $g$ at a point. A $v$ -variate polynomial of total degree $d$ has at most

\binom{v + d}{d}

monomials (nonzero terms): one for each exponent tuple $(e_0,\ldots,e_{v-1})$ with $e_0 + \cdots + e_{v-1} \le d$ .

Using a monomial-sum representation, one can evaluate $g(r_0,\ldots,r_{v-1})$ by evaluating and summing all monomials. Each monomial evaluation requires $O(v)$ field operations (e.g. multiplying together the $v$ contributions $r_i^{e_i}$ , with $e_i \le d$ ), so the total is

O\!\left(\binom{v + d}{d}\cdot v\right).

Since $\binom{v + d}{d} = \Theta(v^d)$ for constant $d$ , this becomes $O(v^{d+1})$ when $d$ is bounded (in many applications $d$ is 2 or 3).

Verifier’s total runtime. Ignoring randomness generation (or assuming it is done offline), V’s work across all rounds is

O(vd),

plus the cost of a single oracle query / commitment opening verification for $g(r_0,\ldots,r_{v-1})$ in the final check.

Verifier’s space complexity¶

The verifier generates and stores the $v$ random field elements $r_0, \ldots, r_{v-1}$ , all of which must be retained because $g(r_0,\ldots,r_{v-1})$ is compared against $g^*_{v-1}(r_{v-1})$ in the final round.

In each round $j$ ( $0 \le j \le v-1$ ), V receives a univariate polynomial $g_j^*$ of degree at most $d_j \le d$ . If $g_j^*$ is sent in coefficient form, storing it requires $O(d+1)$ field elements (or $O(t_j)$ in sparse form). Evaluating $g_j^*$ at a point via Horner’s method uses only $O(1)$ working memory beyond access to the coefficients (one running accumulator), and each polynomial is needed for at most two consecutive rounds.

Thus, measured in field elements, the total space complexity for the verifier is $O(v + d)$ . If the field is $\mathbb{F}_{p^k}$ and each field element is represented using $O(k\log p)$ bits, then the bit space complexity is $O((v + d)k\log p)$ .

Prover’s runtime¶

In Round 0, an honest prover P computes

g_0(X_0) := \sum_{b_1 \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(X_0,b_1,\ldots,b_{v-1}).

Computing $g_0$ by direct summation requires evaluating $g$ at each point $(X_0,b_1,\ldots,b_{v-1})$ with $(b_1,\ldots,b_{v-1}) \in \{0,1\}^{v-1}$ , i.e. at $2^{v-1}$ points. If $g$ is represented as a sum of monomials, evaluating $g$ at one point takes

O\!\left(\binom{v + d}{d}\cdot v\right)

field operations, so the total cost in Round 0 is

O\!\left(\binom{v + d}{d}\cdot v \cdot 2^{v-1}\right).

In Round $j$ , $1 \le j \le v-1$ , an honest prover P computes

g_j(X_j) := \sum_{b_{j+1} \in \{0,1\}} \cdots \sum_{b_{v-1} \in \{0,1\}} g(r_0,\ldots,r_{j-1},X_j,b_{j+1},\ldots,b_{v-1}),

which involves $2^{v-j-1}$ evaluations of (a specialization of) $g$ . Using the same monomial-sum evaluation model, the work in Round $j$ is at most

O\!\left(\binom{v + d}{d}\cdot v \cdot 2^{v-j-1}\right).

Summing across all rounds gives

\sum_{j=0}^{v-1} O\!\left(\binom{v + d}{d}\cdot v \cdot 2^{v-j-1}\right) = O\!\left(\binom{v + d}{d}\cdot v \cdot 2^v\right),

since $2^{v-1} + 2^{v-2} + \cdots + 1 = 2^v - 1$ .

Equivalently,

O\!\left(\binom{v + d}{d}\cdot v \cdot 2^v\right) = O\!\left(\frac{v(v + d)^d 2^v}{d!}\right).

If $d$ is bounded, this simplifies to $O(v^{d+1}2^v)$ , dominated by the exponential term $2^v$ arising from the Boolean hypercube.

Prover’s space complexity¶

P’s space complexity is dominated by storing the multivariate polynomial $g(X_0,\ldots,X_{v-1})$ . In a monomial-sum representation, $g$ may have up to $\binom{v + d}{d}$ nonzero terms, and each term requires storing a coefficient together with its exponent tuple. Thus the storage for $g$ is $O\!\left(\binom{v + d}{d}\right)$ field elements (up to constant-factor overhead for exponents).

During each round, P computes and sends a univariate polynomial $g_j(X_j)$ of degree at most $d$ , which can be stored using $O(d+1)$ field elements. The working memory needed to sum over the hypercube can be kept small: P can stream through the $2^{v-j-1}$ points, maintaining only an accumulator for each coefficient of $g_j$ (i.e. $O(d+1)$ field elements), plus whatever temporary values are needed to evaluate $g$ at one point. If P precomputes the powers $r_i^0,\ldots,r_i^d$ for the specialized point, this adds $O(vd)$ field elements; otherwise the working memory can be treated as $O(1)$ beyond the accumulator.

Overall, the prover’s space is dominated by the representation size of $g$ , namely $O\!\left(\binom{v + d}{d}\right)$ field elements (or $O(v^d)$ for bounded $d$ ), plus lower-order terms such as $O(vd)$ and $O(d)$ .

Proof size¶

The proof size is the total amount of information communicated from the prover to the verifier during the sum-check protocol.

In each round $j$ , $0 \le j \le v-1$ , P sends a univariate polynomial of degree at most $d_j \le d$ to V. In coefficient form this requires at most $d+1$ field elements per round (or fewer in sparse form). Thus, counting only the sum-check messages, the total proof size is

O(vd)

field elements. In bit terms, since each element of $\mathbb{F}_{p^k}$ can be encoded using $O(k\log p)$ bits, the sum-check proof size is

O(vdk\log p)

bits. (In cryptographic implementations, one must additionally account for the size of the opening proof used in the final check to justify the value $g(r_0,\ldots,r_{v-1})$ .)

References¶

Thaler, J. (2015). A note on the GKR protocol. https://api.semanticscholar.org/CorpusID:16402332
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992). Algebraic methods for interactive proof systems. Journal of the ACM, 39(4), 859–868. 10.1145/146585.146605
DeMillo, R. A., & Lipton, R. J. (1978). A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4), 193–195. 10.1016/0020-0190(78)90067-4
Schwartz, J. T. (1980). Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4), 701–717. 10.1145/322217.322225
Zippel, R. (1979). Probabilistic algorithms for sparse polynomials. In E. W. Ng (Ed.), Symbolic and Algebraic Computation, EUROSAM ’79, An International Symposium on Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings (Vol. 72, pp. 216–226). Springer. 10.1007/3-540-09519-5_73
Ore, Ø. (1922). Über höhere Kongruenzen. Norsk Matematisk Forenings Skrifter, Ser. I, 7, 15.