This a short post explaining the multivariate sum-check: a fundamental subprotocol used throughout multivariate succinct arguments (e.g. Spartan, HyperPlonK, etc). Roughly speaking, it often serves the same role as the divisibility check in the univariate contexts.

This post assumes familiarity with finite fields, polynomials and lagrange interpolation/basis.

Introduction

The multivariate sum-check enables a prover to convince a verifier that a particular multivariate polynomial f(X1,X2,…,Xk)∈F[X1,…,Xk] f(X_1, X_2, \ldots, X_k) \in \FF[X_1, \ldots, X_k] sums to a particular value y y over a product of sets: H=S1×S2×…×Sk H = S_1 \times S_2 \times \ldots \times S_k , i.e.

y=∑x1∈S1∑x2∈S2…∑xk∈Skf(x1,x2,…,xk) y = \sum_{x_1 \in S_1} \sum_{x_2 \in S_2} \ldots \sum_{x_k \in S_k} f(x_1, x_2, \ldots, x_k)

Normally H H is a tensor space (hypercube) S1=S2=…=Sk S_1 = S_2 = \ldots = S_k ; most commonly the Boolean hypercube H={0,1}k H = \bin^k :

y=∑x1∈{0,1}∑x2∈{0,1}…∑xk∈{0,1}f(x1,x2,…,xk) y = \sum_{x_1 \in \bin} \sum_{x_2 \in \bin} \ldots \sum_{x_k \in \bin} f(x_1, x_2, \ldots, x_k)

Goal

Computing y y is expensive: taking O(∣H∣) O(|H|) time, even with some clever memoization tricks. The goal of the sum-check protocol is for the verifier to outsource this computation to an untrusted prover.

Communication

In the multivariate sum-check protocol the prover sends ∑∣Si∣ \sum |S_i| field elements to the verifier and the verifier sends k k field elements to the prover. This is logarithmic in the size of the hypercube H H since ∣H∣=∏i∣Si∣ |H| = \prod_i |S_i| .

End of the Protocol

At the end of the protocol the verifier will need to evaluate the polynomial f(X1,…,Xk) f(X_1, \ldots, X_k) at a single point (r1,…,rk)∈F (r_1, \ldots, r_k) \in \FF to check the prover’s claim. The verifier can either evaluate f(r1,…,rk) f(r_1, \ldots, r_k) themselves (which may/may not be expensive) or delegate this computation to the prover using a multivariate polynomial commitment (relying on cryptography).

Hence, with logarithmic communication and computation in the size of H H , the sum-check allows the verifier to reduce the problem of summing a polynomial over H H to checking the value of that polynomial at a single point (r1,…,rk) (r_1, \ldots, r_k) .

The Sum-Check Protocol

Recall the claim we want to verify:

y=∑x1∈S1,…,xk∈Skf(x1,x2,…,xk) y = \sum_{x_1 \in S_1, \ldots, x_k \in S_k} f(x_1, x_2, \ldots, x_k)

Define the polynomial “summing away” X2,…,Xk X_2, \ldots, X_k :

g1(X1)=∑x2∈S2,…,xk∈Skf(X1,x2,…,xk) g_1(X_1) = \sum_{x_2 \in S_2, \ldots, x_k \in S_k} f(X_1, x_2, \ldots, x_k)

Obviously if we also “sum away” the last variable we get y y :

y=∑x1∈S1g1(x1)=∑x1∈S1(∑x2∈S2,…,xk∈Skf(x1,x2,…,xk)) \begin{aligned} y &= \sum_{x_1 \in S_1} g_1(x_1) \\ &= \sum_{x_1 \in S_1} \left( \sum_{x_2 \in S_2, \ldots, x_k \in S_k} f(x_1, x_2, \ldots, x_k) \right) \end{aligned}

At this point the sum-check protocol is straightforward:

  • The (untrusted) prover sends a polynomial g1(X1) g_1(X_1)
  • The verifier checks: y=∑x1∈S1g1(x1) y = \sum_{x_1 \in S_1} g_1(x_1)

At this point the verifier needs to check that g1(X1) g_1(X_1) is indeed the correct polynomial, i.e.

g1(X1)=∑x2∈S2,…,xk∈Skf(X1,x2,…,xk) g_1(X_1) = \sum_{x_2 \in S_2, \ldots, x_k \in S_k} f(X_1, x_2, \ldots, x_k)

To do so, the verifier samples r1←$F r_1 \sample \FF and evaluating both sides at this point:

g1(r1)=∑x2∈S2,…,xk∈Skf(r1,x2,…,xk) \color{green}{g_1(r_1) } = \color{red}{\sum_{x_2 \in S_2, \ldots, x_k \in S_k} f(r_1, x_2, \ldots, x_k)}

The green part the verifier can compute directly, by evaluating the polynomial g1(X1) g_1(X_1) at r r . The red part requires a large summation, but the dimension of the hypercube has been reduced by one (we got rid of X1 X_1 ). Rather than computing this summation themselves, the verifier recursively use the sum-check protocol, asking the prover to show new the claim:

y′=∑x2∈S2,…,xk∈Skf′(x2,…,xk) \color{blue}{ y' = \sum_{x_2 \in S_2, \ldots, x_k \in S_k} f'(x_2, \ldots, x_k) }

Where f′(X2,…,Xk)=f(r1,X2,…,Xk) f'(X_2, \ldots, X_k) = f(r_1, X_2, \ldots, X_k) and y′=g(r1) y' = g(r_1) .

End of the Protocol

After recursively applying the sum-check protocol above k k times, replacing each variable one-by-one, the verifier will be left with the claim:

y=f(r1,r2,…,rk) y = f(r_1, r_2, \ldots, r_k)

At which point the verifier can either evaluate the polynomial herself (as in GKR) or delegate this computation to the prover using a polynomial commitment (as in e.g. Spartan).

Soundness

If g1(X1)≠∑x2∈S2,…,xk∈Skf(X1,x2,…,xk) g_1(X_1) \neq \sum_{x_2 \in S_2, \ldots, x_k \in S_k} f(X_1, x_2, \ldots, x_k) then:

Pr1←$F[g1(r1)=∑x2∈S2,…,xk∈Skf(r1,x2,…,xk)] \prob_{r_1 \sample \FF} \left[ g_1(r_1) = \sum_{x_2 \in S_2, \ldots, x_k \in S_k} f(r_1, x_2, \ldots, x_k) \right]

Is at most deg(g1(X1)) / ∣F∣ \deg(g_1(X_1)) \ / \ |\FF| and the degree of g1(X1) g_1(X_1) is the maximal degree of X1 X_1 in the polynomial f(X1,X2,…,Xk) f(X_1, X_2, \ldots, X_k) – usually a small constant: in the most common case of multilinear polynomials it is just 1. This follows from the Schwartz-Zippel lemma.

To get a soundness analysis for all rounds (after recursively applying the sum-check) one can apply a union bound over each recursion step and arrive at a soundness error of:

∑i=1kdegXi(f(X1,…,Xk))∣F∣ \frac{\sum_{i = 1}^k \deg_{X_i}(f(X_1, \ldots, X_k))}{|\FF|}

In the multilinear case this is just k/∣F∣ k / |\FF| .

Addendum: Efficiency via Lagrange Basis

Having the prover compute:

g1(X1)=∑x2∈S2,…,xk∈Skf(X1,x2,…,xk) g_1(X_1) = \sum_{x_2 \in S_2, \ldots, x_k \in S_k} f(X_1, x_2, \ldots, x_k)

Directly is expensive in most applications.

Instead the prover can compute smaller sums and combine them using Lagrange interpolation. Recall the Lagrange basis polynomials for S1 S_1 : for each x1∈S1 x_1 \in S_1 we define the unique degree ∣S1∣−1 |S_1| - 1 polynomial L(x1)(X1) L^{(x_1)}(X_1) such that:

  • It evaluates to 1 1 at x1 x_1 : L(x1)(x1)=1 L^{(x_1)}(x_1) = 1
  • It evaluates to 0 0 on the rest of S1 S_1 : ∀x1′∈S1∖{x1}.L(x1)(x1′)=0 \forall x_1' \in S_1 \setminus \{ x_1 \}. L^{(x_1)}(x_1') = 0

We can write the polynomial f(X1,X2,…,Xn) f(X_1, X_2, \ldots, X_n) in X1X_1 -Lagrange basis:

f(X1,X2,…,Xn)=∑x1∈S1L(x1)(X1)⋅f(x1,X2,…,Xn) \begin{aligned} f(X_1, X_2, &\ldots, X_n) = \\ &\sum_{x_1 \in S_1} L^{(x_1)}(X_1) \cdot f(x_1, X_2, \ldots, X_n) \end{aligned}

With this rewrite the prover can compute the polynomial g1(X1) g_1(X_1) as:

g1(X1)=∑x1L(x1)(X1)⋅y(x1) g_1(X_1) = \sum_{x_1} L^{(x_1)}(X_1) \cdot y^{(x_1)}

wherey(x1)=∑x2∈S2,…,xk∈Skf(x1,x2,…,xk)\quad \text{where} \quad y^{(x_1)} = \sum_{x_2 \in S_2, \ldots, x_k \in S_k} f(x_1, x_2, \ldots, x_k)

This assumes that ∣S1∣>degX1(f(X1,X2,…,Xk)) |S_1| > \deg_{X_1}(f(X_1, X_2, \ldots, X_k)) which is usually the case in applications, e.g. in the common case of multilinear polynomials summed over the Boolean hypercube. Otherwise the prover needs to compute the sum for a larger S1′⊇S1 S_1' \supseteq S_1 .