Sum-Check Protocol

Paper

Algebraic Methods for Interactive Proof Systems
Authors: Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan
Date: 1992

• One of the most important Interactive Proofs for verifying the sum of a multi-variate polynomial over the Boolean Hypercube
• Prover’s perspective: allows the Prover to prove to the Verifier that the sum is correct
• Verifier’s perspective: allows the Verifier to reduce its computation when calculating the sum by trustlessly delegating the computation to a Prover

Overview

• Allows the Prover to convince the Verifier that a multivariate polynomial sum over the Boolean Hypercube with a claimed sum $C_1$. i.e.:
  • $C_1\stackrel{?}{=}H:=\sum _{b_1\dots b_k\in \{0,1\}}g(b_1,\dots ,b_v)$
    • Where:
      • $C_1$ is the claimed sum
      • $H$ is the true sum
      • $g$ is a $v$-variate polynomial defined over a finite field $\mathbb{F}$
  • Alternatively: $\sum _{x\in \{0,1{\}}^n}g(x)=0$
  • Reduces the claim to a form $f(r)=v$ for random $r\in {\mathbb{F}}^n$
• Prover doesn’t need to perform FFT or commit to other polynomials
• $v$ rounds are needed for a $v$-variate polynomial
• The protocol is unconditionally secure without any crypto assumption $⟺$ $g$ is low-degree (which defines the soundness error)

Sum-Check works for any $B$

Sum-Check actually works for any $B\subseteq \mathbb{F}$. But we are mostly just concerned with $B=0,1$ and thus the degree of each variable is 2 (i.e. $deg(b)=2$)

Purpose

• reduce the Verifier’s work from $2^v\cdot T$ to $T$

Notation: T

$T=$ time for 1 evaluation of $g$

Applications

Zero Testing

• in ZKP, a typical example is:
  • Prover has multilinear polynomial $f_1,f_2,f_3$
  • Verfier has $com(f_1),com(f_2),com(f_3)$
  • Prover wants to prove:

$$f_1(x)f_2(x)-f_3(x)=0,\forall x\in \{0,1{\}}^v$$

• rather than using univariate Zero Quotient testing, Prover doesn’t have to perform FFT or commit to other polynomials

Protocol

Round $0$

Intuition

Prover calculates and send the claimed sum.

1. Prover:
   • send value $C_1$
   • claimed $C_1=H$

Round $1$

Overview

The prover computes $g$ over the Boolean Hypercube except leaving the 1st variable $X_1$ open. Then let the Verifier evaluate $g_1(X_1)$.

1. Prover:

• sends $g_1(X_1)$, which is a univariate polynomial
• claims $g_1(X_1)=s_1(X_1)$
  • where:
    • $s_1(X_1):=\sum _{(x_2,\dots ,x_v)\in \{0,1{\}}^{v-1}}g(X_1,x_2,\dots ,x_v)$
    • $s_1(X_1)$ is defined such that $H=s_1(0)+s_1(1)$
      • i.e. $s_1(X_1)$ is the summation of $g$ over Boolean Hypercube for all variables except $x_1$ which is equal to $X_1$

Implementation Optimization

1. Prover can send $g_1$ in a few ways:

1. send the coefficients of the polynomials (i.e. send $de{g}_1(g)+1$ coefficients)
2. (more efficient) send evaluations of the polynomial at $de{g}_1(g)+1$ points (e.g. -1, 0, 1) so that the verifier can evaluate $g_1(r_1)$ efficiently

2. Prover doesn’t need to send $g_1(1)$ since it can be inferred $g_1(1)=C_1-g_1(0)$

Verifier: - checks: 1. $C_1\stackrel{?}{=}{g}_1(0)+g_1(1)$ 2. $g_1$ is a univariate polynomial of degree $\le de{g}_1(g)$ - sends a random element $r_1\in \mathbb{F}$

Round $j$ where $j=2\dots v-1$

Overview

Prover replace $X$ from previous round with random numbers given by the Verifier. Then the Prover leave the current $X$ open and computes $g$ over the Boolean Hypercube with the rest of $X$. The Verifier evaluate the current $X$.

1. Prover:
   • sends $g_j(X_j)$
   • claims $g_j(X_j)=s_j(X_j)$
     • where $s_j(X_j):=\sum _{(x_{j+1},...,x_v)\in \{0,1{\}}^{v-j}}g(r_1,\dots ,r_{j-1},X_j,x_{j+1},\dots ,x_v)$
2. Verifier:
   • checks:
     1. $g_{j-1}(r_{j-1})\stackrel{?}{=}{g}_j(0)+g_j(1)$
     2. $g_j$ is a univariate polynomial of degree $\le de{g}_j(g)$
   • sends a random element $r_j\in \mathbb{F}$

What does the Verifier actually know?

Verifier doesn’t actually know that $g_j(X_j)=s_j(X_j)$ at this point. Verifier only knows that the Prover has been consistent with $g$ throughout the rounds.

Round $v$ (last round)

1. Prover:
   1. send $g_v(X_v)$
   2. claim $g_v(X_v)=s_v(X_v)$
      • where $s_v(X_v):=g(r_1,\dots ,r_{v-1},X_v)$
2. Verifier:
   1. checks:
      1. $g_{v-1}(r_{v-1})\stackrel{?}{=}{g}_v(0)+g_v(1)$
      2. $g_v$ is a univariate polynomial of degree $\le de{g}_v(g)$
   2. select a random element $r_v\in \mathbb{F}$
   3. checks $g_v(r_v)\stackrel{?}{=}g(r_1,\dots ,r_v)$

Why does Verifier need the evaluation of $g(r_1,...,r_v)$?

The Verifier only knows the Prover has been consistent with $g$ in previous rounds. By checking the evaluation of $g(r_1,...,r_v)$, the Verifier finally know that $g$ from the Prover is the claimed $g$.

Evaluating $g(r_1,...,r_v)$

For the Verifier to get the evaluation of $g(r_1,...,r_v)$, the Verifier use one of these methods:

1. oracle access to $g$
2. can compute $g(r_1,...,r_v)$ efficiently
3. ask the Prover where the Prover will subsequently prove the claim is correct via further applications of sum-check

Security

Completeness error

• ${\delta }_c=0$

Proof

• If the Prover is honest, then the Verifier will always accept when following the protocol

Soundness error

• ${\delta }_S\le \frac{vdeg(g)}{|\mathbb{F}|}$

Proof

• based on Schwartz-Zippel Lemma
• If the Prover is dishonest, the Prover prove $C_1=H$ but $H\ne \sum _{(x_1,\dots ,x_v)\in \{0,1{\}}^v}g(x_1,\dots ,x_v)$
• To do this, the Prover must send a $g_i(X_i)\ne S_i(X_i)$ yet $g_i(r_i)=s_i(r_i)$.
• For each round, this has the probability $\le \frac{deg(g)}{|F|}$.
• With $v$ rounds in the protocol, the total probability is $\le \frac{v\cdot deg(g)}{|F|}$

Costs

Tip

• for a $v$-variate polynomial, $v=log(Size(g))$
• In SNARK application, $Size(g)$ = number of terms being summed = circuit size
  • Thus $O(v)=O(log(Size(g)))=O(log(|circuit|))$

Prover Time

• $O(2^v\cdot T)=O(2^v)=O(|circuit|)$

Verifier Time

• $O([v+deg(b)]+T)$
• $O(v)=O(log(|circuit|))$, since $deg(b)$ is constant for a multivariate polynomial and $T$ is constant
• O(T), since $O(v+deg(b))$ is usually small and can be ignored

Number of Rounds

• 1 round per variable in $g$
• Total $v$ rounds

Communication / Proof Size

• For each round, Prover sends a univariate polynomials represented by $(de{g}_i(g)+1)$ field elements
• For $v$ rounds, the total is $v\cdot (de{g}_i(g)+1)$
• Thus it is $O(v\cdot deg(g))$
• Since $deg(g)$ is constant for a multilinear polynomial, it is $O(v)$

Non-interactive Implementation

To transform the sum-check protocol to non-interactive often requires applying the Fiat-Shamir transformation, which requires a hash function. Even though this is a $O(log)$ overhead, it can still be a large constant.

Optimization

Prover Doesn’t Send Polynomial to Verifier (HyperPlonk)

Benefits and Characteristics

• no commitments necessary
  • avoid commitment costs which can be high
• $O(polylog(circuit))$ sized proofs
  • although it’s not constant sized, but if using a hashing-based commitment scheme like FRI which is $O(polylog(circuit))$ anyways, then sum-check protocol doesn’t add any extra costs

Sum-Check-Based SNARKs

• Spartan20
• Brakedown21
• Orion22
• HyperPlonk23
• BaseFold24
• Blaze2
• Losum - a KZG-based sum-check scheme

Sum-Check-Based Lookups

• Locq24 - based on Losum

Resources

• Proofs, Arguments and Zero Knowledge by Justin Thaler, Chapter 4.1