Skip to content

[sumcheck] modify batched sumcheck final opening point alignment #867

Closed
@hero78119

Description

@hero78119

This issue was initiative along with reviewing PR #864 , the first scenario we kick of the batched of sumcheck in different number of variables.

Basically due to the invesigation for why num_thread > 1 not work in this test case https://github.com/scroll-tech/ceno/blob/master/sumcheck/src/test.rs#L29-L30

In current design, batched sumcheck with different num_vars are implemented by times a scalar, see docs in code comment

ceno/sumcheck/src/prover.rs

Lines 414 to 425 in a0b719d

// Step 2: generate sum for the partial evaluated polynomial:
// f(r_1, ... r_m,, x_{m+1}... x_n)
//
// To deal with different num_vars, we exploit a fact that for each product which num_vars < max_num_vars,
// for it evaluation value we need to times 2^(max_num_vars - num_vars)
// E.g. Giving multivariate poly f(X) = f_1(X1) + f_2(X), X1 \in {F}^{n'}, X \in {F}^{n}, |X1| := n', |X| = n, n' <= n
// For i round univariate poly, f^i(x)
// f^i[0] = \sum_b f(r, 0, b), b \in {0, 1}^{n-i-1}, r \in {F}^{n-i-1} chanllenge get from prev rounds
// = \sum_b f_1(r, 0, b1) + f_2(r, 0, b), |b| >= |b1|, |b| - |b1| = n - n'
// = 2^(|b| - |b1|) * \sum_b1 f_1(r, 0, b1) + \sum_b f_2(r, 0, b)
// same applied on f^i[1]
// It imply that, for every evals in f_1, to compute univariate poly, we just need to times a factor 2^(|b| - |b1|) for it evaluation value

The methodology works by starting binding variable on all polys, so some poly with smaller num_var will be ended earlier.
In another word, giving the final opening point $\vec{r}$ , the final reduce opening point for each polynomial will be $\vec{r}$[..num_var_i], so are aligned on "prefix"

However, batch different num of variable in prefix alignment, doesn't fit in devirgo style sumcheck, due to we break down sumcheck into 2 phase. In first phase, we break down evaluation into #threads section, and all polynomial bind as "constant" right at the last round of phase 1. This prefix-alignment works well when all poly are in same num_var. However, when poly are in different number of variable, some poly with less num_var in prefix alignment will be end much earlier, which break the rule for all polynomial should be end together in phase 1.

To address the issue, we need to modify the sumcheck design to be right alignment. Thus, giving same opening point $\vec{r}$, each poly will be $\vec{r}$[r.len() - num_var_i..], where we call right alignment. With that, poly with less num_var will start to bind lately, and they can end together at the last round of phase 1 sumcheck.

cc @Jiangkm3

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

Status

Done

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions