Sum-Check Protocol

Taken from: Oleg Fomenko and Anton Levochko: Understanding Lasso - A Novel Lookup Argument Protocol

---

A sum-check protocol Lund et al., 1992 is an interactive proof protocol used in theoretical computer science to verify the correctness of a sum of values computed by a multivariate polynomial over a finite field, assuming oracle access to the polynomial. It allows a verifier to check a complex computation (like a huge sum over exponentially many values) using only a few rounds of interaction and logarithmic work.

Let $g$ be an $\ell$-variate polynomial over a finite field $\mathbb{F}$. The goal of the sum-check protocol is for the verifier $\mathcal{V}$ to check that the prover $\mathcal{P}$ has correctly computed:

$$H:=\sum _{b\in \{0,1{\}}^{\ell }}g(b)$$

We assume that $\mathcal{V}$ has oracle access to the polynomial $g\in {\mathbb{F}}^{\ell }[x]$. The protocol proceeds as follows:

1. Initialization: $\mathcal{P}$ sends a claimed value $C_1=H$ to $\mathcal{V}$.

2. First Round: $\mathcal{P}$ sends a univariate polynomial:

   $$g_1(X_1)=\sum _{(x_2,\dots ,x_{\ell })\in \{0,1{\}}^{\ell -1}}g(X_1,x_2,\dots ,x_{\ell })$$

   $\mathcal{V}$ checks that:

   • $C_1=g_1(0)+g_1(1)$
   • $\mathrm{deg}(g_1)\le {\mathrm{deg}}_1(g)$

3. Verifier Samples: $\mathcal{V}$ picks a random $r_1\in \mathbb{F}$ and sends it to $\mathcal{P}$.

4. Intermediate Rounds (for $2\le j<\ell$): $\mathcal{P}$ sends:

   $$g_j(X_j)=\sum _{(x_{j+1},\dots ,x_{\ell })\in \{0,1{\}}^{\ell -j}}g(r_1,\dots ,r_{j-1},X_j,x_{j+1},\dots ,x_{\ell })$$

   $\mathcal{V}$ checks:

   • $\mathrm{deg}(g_j)\le {\mathrm{deg}}_j(g)$
   • $g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$

   Then samples $r_j\in \mathbb{F}$ and sends it to $\mathcal{P}$.

5. Final Round: $\mathcal{P}$ sends:

   $$g_{\ell }(X_{\ell })=g(r_1,\dots ,r_{\ell -1},X_{\ell })$$

   $\mathcal{V}$ checks:

   • $\mathrm{deg}(g_{\ell })\le {\mathrm{deg}}_{\ell }(g)$
   • $g_{\ell -1}(r_{\ell -1})=g_{\ell }(0)+g_{\ell }(1)$

6. Final Query and Check: $\mathcal{V}$ picks $r_{\ell }\in \mathbb{F}$ and queries the oracle for $g(r_1,\dots ,r_{\ell })$. Then checks:

   $$g_{\ell }(r_{\ell })=g(r_1,\dots ,r_{\ell })$$

7. Accept: If all checks pass, $\mathcal{V}$ accepts. Otherwise, it rejects.

Sum-Check Protocol (with Commitment)

Oracle Query Procedure

Used to open committed values via any multilinear polynomial commitment protocol commitments.

Query(C_f ∈ 𝔽, x ∈ {0,1}^ℓ)
 
// Executed by both 𝒫 and 𝒱
𝒫 computes (f(x), π) ← Open(C_f, x)
𝒱 executes Verify(C_f, x, f(x), π)
Return f(x)

Algorithm

Executed by both prover $\mathcal{P}$ and verifier $\mathcal{V}$ for polynomial $g$, its commitment $C_g$, and claimed sum $H$:

SumCheckProtocol(H ∈ 𝔽, g: {0,1}^ℓ → 𝔽, C_g ∈ 𝔽)
 
Set g₁(X₁) = ∑_{(x₂,…,x_ℓ) ∈ {0,1}^{ℓ-1}} g(X₁,x₂,…,x_ℓ)
𝒫 shares g₁ with 𝒱
𝒱 evaluates g₁(0), g₁(1)
If H ≠ g₁(0) + g₁(1): 𝒱 rejects
𝒱 samples r₁ ∈ 𝔽, evaluates g₁(r₁)
 
For j = 2 to ℓ:
    Set gⱼ(Xⱼ) = ∑_{(x_{j+1},…,x_ℓ)} g(r₁,…,r_{j−1},Xⱼ,x_{j+1},…,x_ℓ)
    𝒫 shares gⱼ with 𝒱
    𝒱 evaluates gⱼ(0), gⱼ(1)
    If gⱼ₋₁(rⱼ₋₁) ≠ gⱼ(0) + gⱼ(1): 𝒱 rejects
    𝒱 samples rⱼ ∈ 𝔽, evaluates gⱼ(rⱼ)
 
𝒱 calls Query(C_g, (r₁,…,r_ℓ)) to get g(r₁,…,r_ℓ)
If g_ℓ(r_ℓ) ≠ g(r₁,…,r_ℓ): 𝒱 rejects

Remark

Sometimes, $g$ is not committed directly, but rather defined as a known combination of other committed polynomials. In such cases, we override the query/commit methods by committing to and querying these polynomials individually, then combining them according to the predefined structure.