jagged sumcheck

[kunxian-xia]

main idea

This sumcheck is used to reduce the evaluations $v_i = p_i(r)$ to a single evaluation of $q = \textrm{concat}(p_0, \ldots, p_N)$ at point $(r, z_c)$.

To be more specific, the sumcheck has the following form $v = \sum_i eq(z_c, i)*v_i = \sum_b q(b) * f(b)$ where

$$f(b) = \textrm{eq}(r, \textrm{row}(b)) * \textrm{eq}(z_c, \textrm{col}(b)).$$

The linear space algorithm (VSBW13) we use in crate sumcheck needs to have dense representation of $q(x) \in F, f(x) \in E$. In the case that $q(x)$ has around 31 variables, it's impossible to fit $f(x)$ in 24G GPU VRAM (which requires 32G).

The main constraint: $f(b)$ is too large to materialize in memory. We can only treat it as an oracle.

BlendySC

Fortunately the blendy paper perfectly solves this problem.

• we currently use the linear time algorithm VSBW13 (with linear space).
• try the blendy algorithm with $k = 2$ which runs in $O(k*N)$ and takes $O(\sqrt{N})$ space (see the blendy paper)

We describes blendy algorithm for $k = 2$ below.

1. The prover runs in 2 stages (each stage has $n/2$ rounds).

2. In the stage 1, for round $j < n/2$, the prover needs to output $h_j(x) = \sum_b p(R_j, x, b)$ where $p(b) = f(b)*g(b)$, $R_j = (r_1, \ldots, r_{j-1})$.
   a. We can unroll the above expression to $h_j(x) = \sum_B \textrm{eq}([R_j, x], B[..j]) * p(B)$;

   b. If we split $B$ into three parts $B = (a, c, d)$ with $|a| = j, |b| = n/2 - j, |c| = n/2$), then above expression becomes $h_j(x) = \sum_{a, b} \textrm{eq}([R_j, x], a) * \sum_c p(a, b, c)$.

   c. If we condense/accumulate $p(a, b, c)$ that shares same $(a,b)$, we get a new function $\text{Aux} (a, b) = \sum_c p(a, b, c)$;

   d. Then the expression in step b becomes $h_j(x) = \sum_{a} \textrm{eq}([R_j, x], a) * \sum_b \text{Aux}(a, b) = \sum_b \text{Aux}(R_j, x, b)$;

   e. from the expression in step d, this directly translates to run VSBW13 sumcheck prover for function $\text{Aux}(a,b)$ with expected sum equals to $v$.

3. At the end of stage 2, the sumcheck reduce the original sumcheck to the validity of $\text{Aux}(r_1, \ldots, r_{n/2}) = \sum_c p(r_1, \ldots, r_{n/2}, c)$, then in stage 2, we just run another VSBW13 sumcheck prover for the function $p(r_1, \ldots, r_{n/2}, c)$ with expected sum equals to $\text{Aux}(r_1, \ldots, r_{n/2})$.

We can move one step further, by allowing the number of rounds in stage 1 to be configurable.

Implementation details

1. By definition, $\text{Aux}(b) = \sum_c p(b, c) = \sum_c g(b, c) * f(b, c)$;
2. For each c, we have $p(r_1, \ldots, r_{n/2}, c) = \sum_b \textrm{eq}([r_1, \ldots, r_{n/2}], b) * p(b, c)$.

It's easy to see the oracle for $f(b, c)$ is queried twice for each point.

[kunxian-xia]

The blendy paper only works for p is a multilinear polynomial not $p(b) = f(b)*g(b)$.

Instead we need to use the algorithm in https://eprint.iacr.org/2025/1473.

[kunxian-xia]

Let me describe the main idea behind "Time-Space Trade-Offs for Sumcheck" paper.

To prove the sumcheck $v = \sum_b q(b) * f(b)$ in $O(\sqrt{N})$ space, the prover computes several tables

$$M_{j'}[\beta_1, \beta_2] = \sum_{b \in H_{n-2*j'+1}} q(R_{j'}, \beta_1, b) * f(R_{j'}, \beta_2, b)$$

where $\beta_1, \beta_2 \in H_{j'}$(each table can be built in time $O(N)$, $j' = 1, 2, 4, 8, \ldots$), then the prover will compute the round $j$ uni-variate polynomial in a very short time.

Here is the math to compute $h_j(x)$ given the table $M_{j'}$ ($j' \le j < 2*j'$). For $x = 0$ or $x = 1$, we have

$$\begin{align} h_j(x) &=& \sum_{b \in H_{n-j}} q(R_j, x, b) * f(R_j, x, b) \\\ & = & \sum_b \sum_{a, c} \textrm{eq}(r_{j'..j},a) * \textrm{eq}(r_{j'..j}, c) * q(R_{j'}, a, x, b) * f(R_{j'}, c,x, b) \\\ & = & \sum_{a, c} \textrm{eq}(r_{j'..j},a) * \textrm{eq}(r_{j'..j}, c) * M_{j'}[(a, x, \vec{0}), (c, x, \vec{0})] \end{align}$$

For other $x$, letting

$$\begin{align} g_x(a,c) & = & (1-x)^2 * M_{j'}[(a,0, \vec{0}), (c, 0, \vec{0})] \\\ & & + x*(1-x) * M_{j'}[(a,1, \vec{0}), (c, 0, \vec{0})] \\\ & & + x*(1-x) * M_{j'}[(a,0, \vec{0}), (c, 1, \vec{0})] \\\ & & + x^2 * M_{j'}[(a,1, \vec{0}), (c, 1, \vec{0})] \end{align}$$

then we have $h_j(x) = \sum_{a,c} g_x(a,c)$.

Therefore, we have the following algorithm:

1. In round $j = 1$, we precompute the table $M_1$ according to the above formula and then use it to compute the $h_1(x)$;
2. In round $j= 2$, we precompute the table $M_2$, then use it to compute $h_2(x), h_3(x)$;
3. In round $j = 4$, we precompute the table $M_4$, then use it to compute $h_4(x), h_5(x), h_6(x), h_7(x)$;
4. In round $j = 8$, we precompute the table $M_8$, then use it to compute $h_8(x), \ldots, h_15(x)$; (the space to store is $M_8$ is around 1M.
5. Start from this round, we first fixes the first 15 variables for $q(b)$ and $f(b)$, then run the CTY11 sumcheck prover (in our sumcheck crate) for $h_{15}(r_{15}) = \sum_b q(R_{16}, b) * f(R_{16}, b)$.

[kunxian-xia]

Already solved by scroll-tech/gkr-backend#32.