COSC 544 Probabilistic Proof Systems - Assignment: The Sum-Check Protocol
COSC 544 Probabilistic Proof Systems 9/14/17 The Sum-Check Protocol
Lecturer: Justin Thaler
1 The Sum-Check Protocol
Suppose we are given a v-variate polynomial g defined over a finite field F. The purpose of the sum-check protocol [LFKN92] is to compute the sum:
H := ∑ ∑ ... ∑ g(b1,...,bv). b1 ∈{0,1} b2 ∈{0,1} bv ∈{0,1}
In applications, this sum will often be over a very large number of terms, so the verifier may not have the resources to compute the sum without help. Instead, she uses the sum-check protocol to force the prover to compute the sum for her.
Remark 1. In full generality, the sum-check protocol can compute the sum ∑b∈Bm g(b) for any B ⊆ F, but most of the applications covered in this survey will only require B = {0, 1}.
For presentation purposes, we assume here that the verifier has oracle access to g, i.e., V can evaluate g(r1,...,rv) for a randomly chosen vector (r1,...,rv) ∈ Fv with a single query to an oracle, though this will not be the case in applications. In our applications, V will either be able to efficiently evaluate g(r1,...,rv) unaided, or if this is not the case, V will ask the prover to tell her g(r1,...,rv), and P will subsequently prove this claim is correct via further applications of the sum-check protocol.
The protocol proceeds in v rounds. In the first round, the prover sends a polynomial g1(X1), and claims that g1(X1) = ∑(x2,...,xv)∈{0,1}v−1 g(X1,x2,...,xv). If g1 is as claimed, then H = g1(0)+g1(1).
Throughout, let degi(p) denote the degree of variable i in variable p. The polynomial g1(X1) has degree deg1(g). Hence g1 can be specified with deg1(g)+1 field elements, for example by sending the evaluation of g1 at each point in the set {0,1,...,deg1(g)}.
Then, in round j > 1, V chooses a value rj−1 uniformly at random from F and sends rj−1 to P. We refer to this step by saying that variable j−1 gets bound to value rj−1. In return, the prover sends a polynomial gj(Xj), and claims that
gj(Xj) = ∑ g(r1,...,rj−1,Xj,xj+1,...,xv). (1) (x j+1 ,...,xv )∈{0,1}v− j
The verifier compares the two most recent polynomials by checking gj−1(rj−1) = gj(0) + gj(1), and rejecting otherwise. The verifier also rejects if the degree of gj is too high: each gj should have degree degj(g), the degree of variable xj in g.
In the final round, the prover has sent gv(Xv) which is claimed to be g(r1,...,rv−1,Xv). V now checks that gv(rv) = g(r1,...,rv) (recall that we assumed V has oracle access to g). If this test succeeds, and so do all previous tests, then the verifier is convinced that H = g1 (0) + g1 (1).
The protocol is summarized below.
1
Description of Sum-Check Protocol.
-
FixanH∈F.
-
In the first round, P sends the univariate polynomial
g1(X1) := ∑ g(X1,x2,...,xv).
(x2 ,...,xv )∈{0,1}v−1
V checks that g1 is a univariate polynomial of degree at most deg1 (g), and that H = g1 (0) +
g1(1), rejecting if not.
-
V chooses a random element r1 ∈ F, and sends r1 to P.
-
In the jth round, for 1 < j < v, P sends to V the univariate polynomial
gj(Xj) = ∑ g(r1,...,rj−1,Xj,xj+1,...,xv). (x j+1 ,...,xv )∈{0,1}v− j
V checks that gj is a univariate polynomial of degree at most degj(g), and that gj−1(rj−1) = gj(0)+gj(1), rejecting if not.
-
V chooses a random element rj ∈ F, and sends rj to P.
-
In Round v, P sends the univariate polynomial
gv(Xv) = g(r1,...,rv−1,Xv)
to V. V checks that gv is a univariate polynomial of degree at most degv(g), rejecting if not, andalso checks that gv−1(rv−1) = gv(0)+gv(1).
-
V chooses a random element rv ∈ F and evaluates g(r1,...,rv) with a single oracle query to g.
V checks that gv(rv) = g(r1,...,rv), rejecting if not.
-
If V has not yet rejected, V halts and accepts.
The following proposition formalizes the completeness and soundness properties of the sum-check pro- tocol.
Proposition 1.1. Let g be a v-variate polynomial of total degree at most d in each variable, defined over a finite field F. For any H ∈ F, let L be the language of of polynomials g (given as an oracle) such that
H = ∑ ∑ ... ∑ g(b1,...,bv). b1 ∈{0,1} b2 ∈{0,1} bv ∈{0,1}
The sum-check protocol is an interactive proof system for L with completeness error δc = 0 and sound- ness error δs ≤ vd/|F|.
Proof. Completeness is evident: if the prover sends the prescribed polynomial gj(Xj) at all rounds j, then V will accept with probability 1.
The proof of soundness is by induction on v. In the case v = 1, P’s only message specifies a degree d univariate polynomial g1(X1). If g1(X1) ̸= g(X1), then because any two distinct degree d univariate polyno- mials can agree at most d inputs, g1(r1) ̸= g(r1) with probability at least 1−d/|F| over the choice of r1, and hence V’s final check will cause V to reject with probably at least 1−d/|F|.
Assume by way of induction that for all v − 1-variate polynomials, the sum-check protocol has soundness error at most (v−1)d/|F|. Let h1(X1) = ∑x2,...,xv∈{0,1}v−1 g(X1,x2,...,xv). Suppose P sends a polynomial
2
Communication Rounds V time P time
O (∑vi=1 degi (g)|) field elements v at most O (∑vi=1 degi (g)) + T at most O (2v · T )
Table 1: Costs of sum-check protocol when applied to a v-variate polynomial g over F. degi(g) denotes the degree of variable i in g, and T denotes the cost of an oracle query to g.
g1(X1) ̸= h1(X1) in Round 1. Then because any two distinct degree d univariate polynomials can agree at most d inputs, h1(r1) ̸= g1(r1) with probability at least 1 − d/|F|. Conditioned on this event, P is left to prove the false claim in Round 2 that g1(r1)=∑(x2,...,xv)∈{0,1}v−1 g(r1,x2,...,xv). Since g(r1,x2,...,xv) is a v−1- variate polynomial of total degree d, the inductive hypothesis implies that V will reject at some subsequent round of the protocol with probability at least 1 − d(v − 1)/|F|. Therefore, V will reject with probability at least
1 − Pr[h1(r1) ̸= g1(r1)] − (1 − Pr[V rejects in some Round j > 1|h1(r1) ̸= g1(r1)]) ≥1− d −d(v−1)=1−dv.
|F| |F| |F|
Discussion of costs. There is one round in the sum-check protocol for each of the v variables of g. The total communication is ∑vi=1 degi (g) + 1 = v + ∑vi=1 degi (g) field elements. In particular, if degi (g) = O(1) for all j, then the communication cost is O(v) field elements.
The running time of the verifier over the entire execution of the protocol is proportional to the total communication, plus the cost of a single oracle query to g to compute g(r1,...,rv).
Determining the running time of the prover is less straightforward. Recall that P can specify gj by sending for each i ∈ {0,...,degj(g)} the value:
gj(i) = ∑ g(r1,...,rj−1,i,xj+1,...,xv). (2) (x j+1 ,...,xv )∈{0,1}v− j
An important insight is that the number of terms defining the value gj(i) in Equation (2) falls geo- metrically with j: in the jth sum, there are only 2v−j terms, each corresponding to a Boolean vector in {0,1}v−j. Thus, the total number of terms that must be evaluated over the course of the protocol is ∑vj=1 degj(g)2v−j = O(2v) if degj(g) = O(1) for all j. Consequently, if P is given oracle access to g, then P will require just O(2v) time.
In all of the applications covered in this survey, P will not have oracle access to the truth table of g, and the key to many of the results in this survey is to show that P can nonetheless evaluate g at all of the necessary points in close to O(2v) total time.
The costs of the sum-check protocol are summarized in Table 1. Since P and V will not be given oracle access to g in applications, the table makes the number of oracle queries to g explicit.
Preview: Why multilinear extensions are useful. We will see several scenarios where it is useful to compute H = ∑x∈{0,1}v f (x) for some function f : {0, 1}v → F derived from the verifier’s input. We can
compute H by applying the sum-check protocol to any low-degree extension g of f . When g = f , or is derived from fe in some way, then Lemma 1.6 from the previous lecture (which gave an explicit expression
3
e
for fe in terms of Lagrange basis polynomials) can often be exploited to ensure that enormous cancellations occur in the computation of the prover’s messages, allowing fast computation.
Preview: Why using multilinear extensions is not always possible. Although the use of the MLE fe typically ensures fast computation for the prover, fecannot be used in all applications. The reason is that the verifier has to be able to evaluate fe at a random point r ∈ Fv to perform the final check in the sum-check protocol, and in some settings, this computation would be too costly.
Lemma 1.8 from the previous lecture gives a way for V to evaluate f ̃(r) in time O ̃(2v), given all evalua- tions of f at Boolean inputs. This might or might not be an acceptable runtime, depending on the relationship between v and the verifier’s input size n. If v = log n + poly(log log n), then O ̃ (2v ) = O ̃ (n), and the verifier runs in quasilinear time. But we will see some applications where v = c log n for some constant c > 1, and others where v = n (cf. the #SAT protocol in the next lecture). In these settings, O ̃(2v) runtime for the verifier is unacceptable, and we will be forced to use an extension g of f that has a succinct representation, enabling V to compute g(r) in o(2v) time. Sometimes feitself has such a succinct representation, but other times we will be forced to use a higher-degree extension of f .
References
[LFKN92] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for inter- active proof systems. J. ACM, 39:859–868, October 1992.
4
