加速以太坊精简zkVM的Sumcheck：我们的实现深度解析

lambdaclass
发布于 2025-11-29 20:23
阅读 16

本文深入探讨了Bagad, Dao, Domb和Thaler (BDDT)论文中提出的sumcheck优化算法的实现细节，重点介绍了如何在whir-p3代码库中实现Algorithm 6，该优化旨在延迟扩展域运算，通过Small Value Optimization (SVO)和Eq-Poly优化相结合，在sumcheck协议中实现更高的效率，并减少了通信开销，最终已被合并到whir-p3仓库中。

## 介绍

在这篇文章中，我们将深入探讨我们在 [whir-p3](https://github.com/tcoratger/whir-p3) 仓库中实现的由 Bagad、Dao、Domb 和 Thaler (BDDT) 在他们的 [论文](https://eprint.iacr.org/2025/1117) 中提出的 sumcheck 优化。在之前的文章中，我们已经解释了主要的理论思想（参见 [第一部分](https://blog.lambdaclass.com/optimizing-sumcheck/) 和 [第二部分](https://blog.lambdaclass.com/how-factoring-equality-polynomials-optimizes-sumcheck/)）。在这里，我们将深入研究实现细节，展示我们如何在 [whir-p3](https://github.com/tcoratger/whir-p3) 仓库中准确地实现该论文中的 **算法 6**。

这项工作受到了 Lean Ethereum 团队的推动，该团队使用 Whirlaway，这是一种多线性协议，它依赖 Whir 作为其多项式承诺方案 (PCS)。该团队发现 sumcheck 协议可以从现有的优化中受益（[参见 issue #280](https://github.com/tcoratger/whir-p3/issues/280)）。为了解决这个问题，我们介入并在他们的代码库中实现了 BDDT 优化。

**免责声明：** 本文提供的代码片段对应于合并到此 [PR](https://github.com/tcoratger/whir-p3/pull/322) 中的实现。虽然 whir-p3 仓库正在积极和不断地开发中，但我们选择分析这个特定的快照，因为它提供了最高的教学清晰度。[这个版本](https://github.com/lambdaclass/whir-p3/tree/eec71d03a5ec81f30acc6d591f42f318941c6df5) —— 你可以在我们的仓库 fork 中找到 —— 与 BDDT 论文的理论概念保持着忠实的一对一映射，使其成为在应用进一步的工程优化之前理解核心逻辑的理想参考。

## I. 核心思想：延迟昂贵的字段运算

naive 的 sumcheck prover 过早地强制执行昂贵的扩展字段运算。BDDT 优化的目标很简单：**尽可能长时间地延迟扩展字段运算的引入**。

### 扩展字段计算

在像 Jolt（激发了这篇论文）或 Whir 这样的系统中，底层计算（例如，执行轨迹）对小的基础字段值（32 位或 64 位整数）进行操作。然而，密码学安全性要求 sumcheck 协议使用扩展字段随机挑战。在我们的实现中，我们使用像 **Baby Bear** (31-bit)、**Koala Bear** 或 **Goldilocks** (64-bit) 这样的基础字段以及它们的扩展（例如，`BinomialExtensionField<BabyBear, 4>`）。

这些操作之间的性能差距是巨大的。BDDT 论文引入了一个精确的成本模型：

- **𝔰𝔰 (small-small)**：两个基础字段元素相乘，例如，`BabyBear * BabyBear`。这是最快的 —— 只是一个简单的基础字段乘法。
- **𝔰𝔩 (small-large)**：一个基础字段元素乘以一个扩展字段元素，例如，`BabyBear * BinomialExtensionField<BabyBear, 4>` 需要 4 个基础字段乘法（每个扩展系数一个）。
- **𝔩𝔩 (large-large)**：两个扩展字段元素相乘，例如，`BinomialExtensionField<BabyBear, 4> * BinomialExtensionField<BabyBear, 4>` 速度要慢得多，需要 16 个基础字段乘法加上额外的操作 —— 通常比 𝔰𝔰 慢一个数量级。

### 成本问题

naive（或经典）的 sumcheck prover（论文中的 **算法 1**）存在过早的扩展字段传播：

- **第 1 轮**：prover 计算基础字段值的乘积之和 —— 所有廉价的 𝔰𝔰 运算。
- **第 2 轮及以后**：verifier 发送一个随机挑战 $r_1 \in \mathbb{F}_{ext}$，一个扩展字段元素。这强制所有后续计算使用扩展字段运算。从那时起，prover 必须对所有剩余的轮次执行昂贵的 𝔩𝔩 运算。

**关键见解：** 尽可能长时间地延迟这种转换。执行更多的操作更好，但在基础字段中。这就是全部的想法。

## II. 两个优化：SVO 和 Eq-Poly

**算法 6** 综合了两个互补的优化。单独理解每一个，可以清楚地了解它们如何协同工作。

### A. 小值优化 (SVO)

小值优化（**算法 4**）是一种计算策略：**延迟扩展字段运算**。

一种 naive 的 方法（**算法 3**）会将多项式扩展为 $O(2^{d \cdot \ell_0})$ 项，以保持基础字段和扩展字段分量的分离。对于实际值来说，这是指数级的昂贵且不可行的。

**SVO 的见解：** 使用 **拉格朗日插值** 而不是扩展。这与 Toom-Cook 乘法背后的原理相同。通过将 round 多项式视为要从少量评估点插值的东西，而不是扩展成指数级的单项式，我们将预计算成本从 $O(2^{d \cdot \ell_0})$ 降低到 $O((d+1)\ell_0)$。

你可以在我们的系列 [第一部分](https://blog.lambdaclass.com/optimizing-sumcheck/) 中看到这种优化背后的直觉。

### B. Eq-Poly 优化 (算法 5)

第二个优化（**算法 5**）解决了特定情况

$g(X) = eq(w, X)p(X)$.

它基于 Gruen 的优化，其思想是减少与 $eq$ 多项式相关的 𝔩𝔩 乘法。

该算法没有一次性地对所有剩余变量求和，而是将该求和 "拆分" 成两半。

有关完整说明，请参见我们系列的 [第二部分](https://blog.lambdaclass.com/how-factoring-equality-polynomials-optimizes-sumcheck/)。

## III. 协议架构：两阶段策略

我们的实现本质上封装在函数 [`from_base_evals_svo`](https://github.com/lambdaclass/whir-p3/blob/eec71d03a5ec81f30acc6d591f42f318941c6df5/src/sumcheck/sumcheck_single_svo.rs#L22) 中，prover 调用该函数以按照 **算法 6** 执行 sumcheck 协议。它结合了 SVO 和 Eq-Poly 优化。在我们的实现中，我们选择了：

- $\ell_0 = 3$：我们只进行三个 SVO 轮次，因为正如我们稍后将详细解释的那样，这种优化仅在几个轮次中有效。
- $d = 1$：我们只接受一个多线性多项式，而不是像 BDDT 论文中所示的多项式的乘积。之所以选择这种方式，是因为在我们感兴趣的用例中（即，在 Whir 的上下文中），我们只有一个多项式。

给定超立方体上多线性多项式 $p$ 的基础字段求值 (`evals`) 和一个 eq-poly 约束 (`constraint`)，它应用一定数量的 sumcheck 轮次 (`folding_factor`)，返回一个新的 `SumcheckSingle` 和使用的挑战。

重要的是要指出，此实现设计用于大于 5 的 `folding_factor` 和仅包含**一个相等性语句**的 `constraint`，因为我们想使用 Whir 作为 PCS。

因此，此函数的目标是证明一个相等性约束。

$\sigma = p(w)$,

其中我们可以将求值重写为总和：

$p(w) = \sum_{x \in \{0,1\}^\ell} eq(w,x)p(x)$.

该算法的核心见解：**对不同的阶段使用不同的策略**。以下是高级结构：

```rust
/// 运行遵循算法 6 的 Sumcheck prover。
pub fn from_base_evals_svo<Challenger>(
    evals: &EvaluationsList<F>,
    prover_state: &mut ProverState<F, EF, Challenger>,
    folding_factor: usize,
    pow_bits: usize,
    constraint: &Constraint<F, EF>,
) -> (Self, MultilinearPoint<EF>) {

let mut challenges = Vec::with_capacity(folding_factor);
    // 在这里，我们假设相等性语句只有一个约束。
    let mut sum = constraint.eq_statement.evaluations[0];
    let w = &constraint.eq_statement.points[0];

// 创建统一的相等性多项式评估器
    let mut eq_poly = SumcheckEqState::<_, NUM_SVO_ROUNDS>::new(w);

// --- 阶段 1：前 3 轮的 SVO ---
    let (r_1, r_2, r_3) = svo_three_rounds(prover_state, evals, w, &mut sum, pow_bits);
    challenges.extend([r_1, r_2, r_3]);

// --- 切换：用 3 个挑战折叠多项式 ---
    // 我们进行折叠以获得 p(r1, r2, r3, x)。
    let mut folded_evals = fold_evals_with_challenges(evals, &challenges);

// --- 阶段 2：剩余轮次的算法 5 ---
    algorithm_5(prover_state, &mut folded_evals, w, &mut challenges, &mut sum, pow_bits);

let challenge_point = MultilinearPoint::new(challenges);

// 最终权重：eq(w, r)
    let weights = EvaluationsList::new(vec![w.eq_poly(&challenge_point)]);
    let sumcheck = Self::new(folded_evals, weights, sum);

(sumcheck, challenge_point)
}
```

接下来，让我们详细解释每个阶段。

## IV. 阶段 1：前三轮

前三轮 sumcheck 由 [`svo_three_rounds`](https://github.com/lambdaclass/whir-p3/blob/eec71d03a5ec81f30acc6d591f42f318941c6df5/src/sumcheck/sumcheck_small_value.rs#L220) 实现。在每个轮次 $i$ 中，prover 需要：

- 计算单变量多项式求值 $S_i(0)$ 和 $S_i(\infty)$（即，前导系数）。
- 将这些求值添加到 prover 状态。
- 采样一个新的挑战 $r_i$。
- 折叠多项式 $p$。
-  更新声明的总和 $\sigma$。

唯一繁重的步骤是第一个。我们希望 prover 能够有效地计算 $S_i$。这就是 SVO 发挥作用的地方。

### 分解单变量轮多项式

我们想要证明的声明总和是：

$\sigma = p(w) = \sum_{x \in \{0,1\}^\ell} eq(w,x)p(x)$.

然后，对于每一轮 $i$，prover 需要计算单变量轮多项式 $S_i(u)$，其中：

$S_i(u) = \sum_{x \in \{0,1\}^{\ell-i}} eq(w[1,i-1]; r[1,i-1], u, x) \cdot p(r[1,i-1], u, x)$.

分割 eq-poly，我们可以按以下方式分解 $S_i$，其中 $\ell$ 是容易的部分，$t$ 是困难的部分：

$S_i(u) = \ell_i(u)t_i(u), \quad \ell_i(u) = eq(w[1,i-1]; r[1,i-1]) eq(w_i; u), \quad t_i(u) = \sum_{x \in \{0,1\}^{\ell-i}} eq(w[i+1,\ell]; x) p(r[1,i-1], u, x)$.

其中：

- $\ell_i(u)$ 是**线性部分**：它来自变量 1 到 $i$ 的 eq-poly 部分。这是一个关于 $u$ 的线性多项式，很容易计算。
- $t_i(u)$ 是**繁重部分**：它包含了所有剩余变量 $x$ 上的总和以及多项式 $p$。所有的复杂性都存在于此。

请注意，计算 $\ell_i(0)$ 和 $\ell_i(1)$ 本质上是 "免费的"，但是 naive 地计算 $t_i(0)$ 和 $t_i(1)$ 需要对指数级的许多项求和。这就是**累加器**发挥作用的地方。

### 累加器计算（过程 9）

“重型部分” $t_i(u)$ 是 SVO（**算法 4**）和 Eq-Poly（**算法 5**）相结合的地方。我们通过在挑战 $r[1,i-1]$ 上使用拉格朗日插值和在剩余变量 $x$ 上使用和分割见解来应用 Toom-Cook 见解。

这使我们能够根据预先计算的累加器 $A_i(v,u)$ 重构 $t_i(u)$：

$t_i(u) = \sum_{v \in \{0,1\}^{i-1}} L_v(r[1,i-1]) \cdot \underbrace{\left( \sum_{x_L} eq(w[i+1,\ell/2]; x_L) \sum_{x_R} eq(w[\ell/2+1,\ell]; x_R) \cdot p(v,u,x_L,x_R) \right)}_{A_i(v,u)}$

这里，$L_v$ 是拉格朗日基多项式。这个公式是 **算法 6** 预计算的核心。计算这些 $A_i(v,u)$ 累加器的 "方式" 是 **过程 9**。

我们可以通过以下方式重写先前方程式的内部部分：

$A_i(v,u) = \sum_{y \in {0,1}^{\ell_0-i}} \sum_{x_{out} \in {0,1}^{\ell/2-\ell_0}} eq((w[(i+1):\ell_0], w[(\ell/2+\ell_0+1):]), (y,x_{out})) \cdot \sum_{x_{in} \in \{0,1\}^{\ell/2}} eq(w[(\ell_0+1):(\ell_0+\ell/2)], x_{in}) \cdot p(v,u,y,,x_{in},x_{out})$

在本文中，我们可以看到 **过程 9** 巧妙地反转了循环：它不是通过累加器 $A_i(v,u)$ 迭代，而是迭代数据 $(x_{out},x_{in},\beta)$ 并将每个结果 "分配" 到正确的 $A_i(v,u)$ bin。这是分两个阶段完成的：

1. **时间累积** ($tA[\beta]$)：对于固定的 $x_{out}$，该算法计算每个前缀 $\beta \in \{0,1\}^{\ell_0}$ 的整个内部和。该循环包含主要的 𝔰𝔩 运算：`e_in_value * poly_evals[index]`。

$tA[\beta] = \sum_{x_{in} \in \{0,1\}^{\ell/2}} E_{in}[x_{in}] \cdot p(\beta, x_{in}, x_{out})$

$E_{in}[x_{in}] = eq(w[(\ell_0+1):(\ell_0+\ell/2)], x_{in})$

2. **分布**：一旦计算出 $tA$ 向量，该算法就将这些值 "分布" 到正确的最终累加器 $A_i(v,u)$，并将它们乘以各自的 $E_{out}$ 权重。

让我们深入研究我们的实现。

首先，我们有一个 `Accumulators` 结构，我们在其中存储这些值，以及几个用于创建、修改和读取它们的基本方法：

```rust
#[derive(Debug, Clone, Eq, PartialEq)]
pub struct Accumulators<F: Field> {
    /// 每个 SVO 轮次一个累加器向量。
    /// - `accumulators[0]` 有 2^1 = 2 个元素，用于 A_0(u)
    /// - `accumulators[1]` 有 2^2 = 4 个元素，用于 A_1(v, u)
    /// - `accumulators[2]` 有 2^3 = 8 个元素，用于 A_2(v, u)
    pub accumulators: [Vec<F>; NUM_SVO_ROUNDS],
}

impl<F> Accumulators<F>
where
    F: Field,
{
    #[must_use]
    pub fn new_empty() -> Self {
        Self {
            // 在第 0 轮中，我们有 2 个累加器：A_0(u)，其中 u 在 {0, 1} 中。
            // 在第 1 轮中，我们有 4 个累加器：A_1(v, u)，其中 v 在 {0, 1} 中，u 在 {0, 1} 中。
            // 在第 2 轮中，我们有 8 个累加器：A_2(v, u)，其中 v 在 {0, 1}^2 中，u 在 {0, 1} 中。
            // 我们不需要任何数字为无穷大的累加器。
            accumulators: [F::zero_vec(2), F::zero_vec(4), F::zero_vec(8)],
        }
    }

/// 将值添加到特定的累加器。
    pub fn accumulate(&mut self, round: usize, index: usize, value: F) {
        self.accumulators[round][index] += value;
    }
    /// 获取给定轮次的累加器切片。
    #[must_use]
    pub fn get_accumulators_for_round(&self, round: usize) -> &[F] {
        &self.accumulators[round]
    }
}
```

请注意，即使最初我们应该有三个求值：在 $0$、$1$ 和 $\infty$ 处，因为 $S(u)$ 的度数为 2，但在代码中，我们仅计算 $u \in \{0,1\}$ 的累加器。稍后我们将对此进行解释。

因此，让我们来看一下我们如何将 **过程 9** 适应于我们的特定用例。

```rust
/// 过程 9。第 37 页。
/// 我们只计算我们将要使用的累加器，即，
/// A_i(v, u)，适用于 {0, 1, 2} 中的 i、{0, 1}^{i} 中的 v 和 {0, 1} 中的 u。
fn compute_accumulators<F: Field, EF: ExtensionField<F>>(
    poly: &EvaluationsList<F>,
    e_in: &[EF],
    e_out: &[Vec<EF>; NUM_SVO_ROUNDS],
) -> Accumulators<EF> {
    [...]
}
```

该函数接收 $p(x)$、$E_{in}$ 和 $E_{out}$ 的求值作为输入。

我们可以在论文中看到这些计算如下：

$E_{in} := (eq(w[\ell_0+1:(\ell_0+\ell/2)], x_{in})) \quad \text{with} \quad x_{in} \in \{0,1\}^{\ell/2}$

$E_{out,i} := (eq((w[(i+1):\ell_0], w[(\ell/2+\ell_0+1):]), (y,x_{out}))) \quad \text{with} \quad (y,x_{out}) \in \{0,1\}^{\ell_0} \times \{0,1\}^{\ell/2-\ell_0}$

这些值仅取决于我们的挑战 $w$，因此我们可以如下预先计算它们：

```rust
/// 过程 9（compute_accumulators）所需的预计算。
/// 计算所有 x in {0,1}^l/2 的求值 eq(w_{l0 + 1}, ..., w_{l0 + l/2} ; x)
fn precompute_e_in<F: Field>(w: &MultilinearPoint<F>) -> Vec<F> {
    let half_l = w.num_variables() / 2;
    let w_in = &w.0[NUM_SVO_ROUNDS..NUM_SVO_ROUNDS + half_l];
    eval_eq_in_hypercube(w_in)
}

/// 过程 9（compute_accumulators）所需的预计算。
/// 计算三个 E_out 向量，每个轮次 i 在 {0, 1, 2} 中一个。
/// 对于每个 i，E_out = eq(w_{i+1}, ..., l0, w_{l/2 + l0 + 1}, ..., w_l ; x)
fn precompute_e_out<F: Field>(w: &MultilinearPoint<F>) -> [Vec<F>; NUM_SVO_ROUNDS] {
    let half_l = w.num_variables() / 2;
    let w_out_len = w.num_variables() - half_l - 1;

std::array::from_fn(|round| {
        let mut w_out = Vec::with_capacity(w_out_len);
        w_out.extend_from_slice(&w.0[round + 1..NUM_SVO_ROUNDS]);
        w_out.extend_from_slice(&w.0[half_l + NUM_SVO_ROUNDS..]);
        eval_eq_in_hypercube(&w_out)
    })
}
```

一旦我们计算出这些值，我们就可以返回到我们的 `compute_accumulators` 函数。

我们做的第一件事是计算 $x_{out}$ 中变量的数量为 $\ell/2 - \ell_0$，其中 $\ell$ 是 $p(X)$ 的变量数，$\ell_0$ 是 SVO 轮次数，同时考虑到 $\ell$ 为奇数的情况。

```rust
    [...]
    let l = poly.num_variables();
    let half_l = l / 2;

let x_out_num_vars = half_l - NUM_SVO_ROUNDS + (l % 2);
    let x_num_vars = l - NUM_SVO_ROUNDS;
    debug_assert_eq!(half_l + x_out_num_vars, x_num_vars);

let poly_evals = poly.as_slice();
    [...]
```

现在我们可以运行外部循环，其中对于 $x_{out}$ 的每个值，我们将：

1. 初始化临时累加器并计算 $x_{in}$ 中的变量数：

```rust
    (0..1 << x_out_num_vars)
        .into_par_iter()
        .map(|x_out| {
            // 每个线程将计算其自己的一组本地累加器。
            // 这避免了可变状态共享和对锁的需求。
            let mut local_accumulators = Accumulators::<EF>::new_empty();

let mut temp_accumulators = [EF::ZERO; 1 << NUM_SVO_ROUNDS];

let num_x_in = 1 << half_l;
        })
```

2. 对于 $x_{in}$ 的每个值，我们使用以下公式计算 $tA$ 值：

$tA(x_{out}) = \sum_{\beta \in \{0,1\}^3} E_{in}[x_{in}] \cdot p(\beta, x_{in}, x_{out})$

```rust
            for (x_in, &e_in_value) in e_in.iter().enumerate().take(num_x_in) {
                // 对于 {0,1}^3 中的每个 beta，我们更新 tA(beta) += e_in[x_in] * p(beta, x_in, x_out)
                #[allow(clippy::needless_range_loop)]
                for i in 0..(1 << NUM_SVO_ROUNDS) {
                    let beta = i << x_num_vars;
                    let index = beta | (x_in << x_out_num_vars) | x_out; // beta | x_in | x_out
                    temp_accumulators[i] += e_in_value * poly_evals[index]; // += e_in[x_in] * p(beta, x_in, x_out)
                }
            }
```

3.  一旦我们获得了所有临时累加器，我们就解压它们并收集我们将需要的所有 $E_{out}$ 值。

请记住，$E_{out}$ 仅取决于 $y$。因此，在第一轮中，$y$ 有 2 个变量，这给了我们 4 个可能的 $E_{out}$ 值。在第二轮中，$y$ 有 1 个变量，因此有 2 个可能的 $E_{out}$ 值。在第三轮中，它不依赖于 $y$，因此我们有单个 $E_{out}$ 值。

```rust
    // 解构 things，因为我们稍后会多次访问它们
    let [t0, t1, t2, t3, t4, t5, t6, t7] = temp_accumulators;
    // 获取此 x_out 的 E_out(y, x_out)
    // 第 0 轮 (i=0) -> y=(b1,b2) -> 2 位
    let e0_0 = e_out[0][x_out]; // y=00
    let e0_1 = e_out[0][(1 << x_out_num_vars) | x_out]; // y=01
    let e0_2 = e_out[0][(2 << x_out_num_vars) | x_out]; // y=10
    let e0_3 = e_out[0][(3 << x_out_num_vars) | x_out]; // y=11
    // 第 1 轮 (i=1) -> y=(b2) -> 1 位
    let e1_0 = e_out[1][x_out]; // y=0
    let e1_1 = e_out[1][(1 << x_out_num_vars) | x_out]; // y=1
    // 第 2 轮 (i=2) -> y=() -> 0 位
    let e2 = e_out[2][x_out]; // y=()
```

4.  一旦我们获得了所有这些值，我们就可以开始将它们添加到相应的累加器中。在 **过程 9** 中，这是通过迭代 $(i,v,u,y) \in idx_4(\beta)$ 完成的，但是由于我们只需要计算 3 轮，并且计算 $u=0$ 和 $u=1$ 的值，我们可以使用以下总和直接完成它：

$\sum_{\beta \in U_{\ell_0}^d} \sum_{(i',v',u',y) \in idx_4(\beta)} i'=i, v'=v, u'=u E_{out,i'}[y,x_{out}] \cdot tA[\beta]$
```rust
     // 第 0 轮 (i=0)
     // A_0(u=0) = Σ_{y} E_out_0(y) * tA( (u=0, y), x_out )
     local_accumulators.accumulate(0, 0, e0_0 * t0 + e0_1 * t1 + e0_2 * t2 + e0_3 * t3);
     // A_0(u=1) = Σ_{y} E_out_0(y) * tA( (u=1, y), x_out )
     local_accumulators.accumulate(0, 1, e0_0 * t4 + e0_1 * t5 + e0_2 * t6 + e0_3 * t7);
     // 第 1 轮 (i=1)
     // A_1(v, u) = Σ_{y} E_out_1(y) * tA( (v, u, y), x_out )
     // v=0, u=0
     local_accumulators.accumulate(1, 0, e1_0 * t0 + e1_1 * t1);
     // v=0, u=1
     local_accumulators.accumulate(1, 1, e1_0 * t2 + e1_1 * t3);
     // v=1, u=0
     local_accumulators.accumulate(1, 2, e1_0 * t4 + e1_1 * t5);
     // v=1, u=1
     local_accumulators.accumulate(1, 3, e1_0 * t6 + e1_1 * t7);
     // 第 2 轮 (i=2)
     // A_2(v, u) = E_out_2() * tA( (v, u), x_out )
     #[allow(clippy::needless_range_loop)]
     for i in 0..8 {
          local_accumulators.accumulate(2, i, e2 * temp_accumulators[i]);
          }
```

最后，唯一剩下的是对 ($x_{\mathrm{out}}$) 执行最终求和。

```rust
        .par_fold_reduce(
            || Accumulators::<EF>::new_empty(),
            |a, b| a + b,
            |a, b| a + b,
        )
```

## V. 阶段 2：切换到算法 5

切换策略至关重要。SVO 仅在前几轮中更便宜。这就是为什么在前三轮之后，我们需要将我们收集到的挑战 "应用" 到剩余的多项式求值。此过程在形式上称为**折叠**或部分求值。我们通过绑定前三个变量，将原始多项式 $p(x_1,…,x_\ell)$ 转换为较小的多项式 $p^{(3)}(x_4,…,x_\ell)$：

$p^{(3)}(x_4,…,x_\ell)=\sum_{b\in\{0,1\}^3}eq((r_1,r_2,r_3),b) \cdot p(b,x_4,…,x_\ell)$

多项式折叠在以下行中完成：

```rust
// 进行折叠以获得 p(r1, r2, r3, x)
let mut folded_evals = fold_evals_with_challenges(evals, &challenges);
```

此操作将我们的求值域从 $2^\ell$ 缩小到 $2^{\ell-3}$。在我们的实现中，函数 `fold_evals_with_challenges` 并行处理此折叠操作。

由于多线性求值以字典顺序存储，因此固定前 3 个变量在概念上会将超立方体切成 $2^3=8$ 个大的连续块。为了计算较小的新域中点 $i$ 的值，我们需要从这 8 个块中的每一个块中收集偏移量 $i$ 处的值。

索引逻辑 `(j * num_remaining_evals) + i` 允许我们跳到正确的块 $j$ 并访问特定的元素 $i$，将加权和累加到结果中。

```rust
pub fn fold_evals_with_challenges<F, EF>(
    evals: &EvaluationsList<F>,
    challenges: &[EF],
) -> EvaluationsList<EF> {
    let n = evals.num_vars();
    let k = challenges.len(); // 在我们的案例中 k = 3
    // 较小的新超立方体的大小 (2^{l-3})
    let num_remaining_evals = 1 << (n - k);

// 1. 预先计算 {0,1}^3 中所有 8 个前缀 b 的权重 eq(r, b)
    let eq_evals: Vec<EF> = eval_eq_in_hypercube(challenges);
``````markdown
// 2. 并行 Fold
    let folded_evals_flat: Vec<EF> = (0..num_remaining_evals)
        .into_par_iter()
        .map(|i| {
             // 对于目标域中的每个点 'i'，对 8 个源前缀求和。
            eq_evals
                .iter()
                .enumerate()
                .fold(EF::ZERO, |acc, (j, &eq_val)| {
                    // 重构索引：前缀 (j) + 后缀 (i)
                    let original_eval_index = (j * num_remaining_evals) + i;

let p_b_x = evals.as_slice()[original_eval_index];
                    acc + eq_val * p_b_x
                })
        })
        .collect();

EvaluationsList::new(folded_evals_flat)
}
```

### SVO 到标准算法的切换

为什么我们要在 **这里** 停止 SVO？这个决定是由字段乘法的成本决定的，正如论文中分析的那样：

1. **Folding 之前 (ssss Regime):** 我们的多项式求值在基本域中（小）。SVO 利用这一点，通过在小值上使用高效的插值，避免了昂贵的扩展域算术。

2. **Folding 操作:** Folding 操作本身是一个线性组合，涉及到挑战值 $r_i$。由于 $r_i \in F_{ext}$，fold 的输出必须在扩展域中。

3. **Folding 之后 (llll Regime):** 一旦我们的求值提升到扩展域，SVO 的好处就会消失。SVO 引入了 $O(d^2)$ 操作的开销，以节省乘法运算。

在三轮之后，折叠后的多线性多项式足够小，以至于标准的线性时间证明器 (**算法 5**) 比 SVO 更有效。通过在 fold 后立即切换，我们确保使用 SVO 处理基本域值，并使用标准方法处理扩展域值，从而在整个协议执行过程中保持最佳性能。

### 算法 5

一旦我们折叠了多项式，我们继续使用 **算法 5** 来执行剩余的 $\ell-\ell_0$ 轮。你可以在名为 [`algorithm_5`](https://github.com/lambdaclass/whir-p3/blob/eec71d03a5ec81f30acc6d591f42f318941c6df5/src/sumcheck/sumcheck_small_value.rs#L402) 的函数中找到我们的实现。

```rust
pub fn algorithm_5<Challenger, F: Field, EF: ExtensionField<F>>(
    prover_state: &mut ProverState<F, EF, Challenger>,
    poly: &mut EvaluationsList<EF>,
    w: &MultilinearPoint<EF>,
    challenges: &mut Vec<EF>,
    sum: &mut EF,
    pow_bits: usize,
) where
    Challenger: FieldChallenger<F> + GrindingChallenger<Witness = F>,
{
    [...]
}
```

在每一轮 $j$ 中，证明者的目标与前三轮相同。我们需要：

- 计算并发送单变量多项式求值 $S_j(u)$，对于 $u\in\{0,∞\}$。
- 更新下一轮的变量。

为此，我们将继续使用 $S_j$ 的分解式：

$S_j(u)=\ell_j(u) \cdot t_j(u)$

其中，回想一下，

$\ell_j(u)=eq(w[1,j-1];r[1,j-1]) \cdot eq(w_j;u)$
$t_j(u)=\sum_{x\in\{0,1\}^{\ell-j}}eq(w[j+1,\ell];x) \cdot p(r[1,j-1],u,x)$

然而，为了计算 $t_j$，我们不会像以前那样使用 SVO 和累加器。相反，我们将简单地将其 eq-poly 分成两半，利用其中一部分可以预先计算的事实，从而避免在每一轮中重新计算。

让我们逐步分解 `algorithm_5` 函数。在轮循环之前，你会看到这段代码：

```rust
let num_vars = w.num_variables();
let half_l = num_vars / 2;

// Precompute eq_R = eq(w_{l/2+1..l}, x_R)
let eq_r = eval_eq_in_hypercube(&w.0[half_l..]);
let num_vars_x_r = eq_r.len().ilog2() as usize;

// The number of variables of x_R is: l/2 if l is even and l/2 + 1 if l is odd.
debug_assert_eq!(num_vars_x_r, num_vars - half_l);

// start_round should be NUM_SVO_ROUNDS.
let start_round = challenges.len();
challenges.reserve(num_vars - start_round);
```

在这里，我们定义了几个参数，例如变量的总数 ($\ell$) 和我们当前所在的轮数 ($\ell_0$)。但是，最重要的是，我们预先计算 eq-poly 的右半部分（或最后一部分）：

$eq_R=eq(w_{\ell/2+1},…,w_\ell;x_{\ell/2+1},…,x_\ell)$.

之后，我们开始循环。在每一轮 $j$ 中，我们需要计算 $t_j(0)$ 和 $t_j(1)$。为此，我们考虑两种情况：一方面，直到轮数 $\ell/2-1$ 的前几轮，另一方面，从轮数 $\ell/2$ 开始的后几轮。

**免责声明：** 你会看到在代码中，循环从 i=$\ell_0$ 开始，但应该计算的第一轮是 $\ell_0+1$。这就是为什么我们在代码中有变量 `round = i + 1`。在本文中，为了简化符号，我们调用 j=j=`round`。

```rust
// Compute the remaining rounds, from l_0 + 1 to the end.
for i in start_round..num_vars {
    // `i` is the 0-indexed variable number, so `round = i + 1`.
    let round = i + 1;
    let num_vars_poly_current = poly.num_variables();
    let poly_slice = poly.as_slice();

[...]
```

#### 前半部分轮次

对于 $j<\ell/2$ 的情况，我们使用 `compute_t_evals_first_half` 函数并行获得 $t_j(0)$ 和 $t_j(1)$。这些值使用以下求和拆分计算：

$t(0)=\sum_{x_R}eq(w[\ell/2+1,\ell],x_R)\sum_{x_L}eq(w[j+1,\ell/2],x_L) \cdot p(r[1,j-1],0,x_L,x_R)$
$t(1)=\sum_{x_R}eq(w[\ell/2+1,\ell],x_R)\sum_{x_L}eq(w[j+1,\ell/2],x_L) \cdot p(r[1,j-1],1,x_L,x_R)$

```rust
// Compute t(u) for u in {0, 1}.
let t_evals: [EF; 2] = if round <= half_l {
    // Case i+1 <= l/2: Compute eq_L = eq(w_{i+2..l/2}, x_L)
    let eq_l = eval_eq_in_hypercube(&w.0[round..half_l]);
    let (t_0, t_1) = join(
        || compute_t_evals_first_half(&eq_l, &eq_r, poly_slice, num_vars_x_r, 0),
        || {
            compute_t_evals_first_half(
                &eq_l,
                &eq_r,
                poly_slice,
                num_vars_x_r,
                1 << (num_vars_poly_current - 1), // offset for u=1
            )
        },
    );
    (t_0, t_1).into()

[...]
```

#### 后半部分轮次

类似地，在 $j\geq\ell/2$ 的情况下，我们使用 `compute_t_evals_second_half` 计算 $t_j(0)$ 和 $t_j(1)$。请注意，由于 $j\geq\ell/2$，我们没有涉及 $eq_L$ 多项式的求和。所以：

$t(0)=\sum_x eq(w[j+1,\ell],x) \cdot p(r[1,j-1],0,x)$
$t(1)=\sum_x eq(w[j+1,\ell],x) \cdot p(r[1,j-1],1,x)$

```rust
} else {
    // Case i+1 > l/2: Compute eq_tail = eq(w_{i+2..l}, x_tail)
    let eq_tail = eval_eq_in_hypercube(&w.0[round..]);
    let half_size = 1 << (num_vars_poly_current - 1);
    let (t_0, t_1) = join(
        || compute_t_evals_second_half(&eq_tail, &poly_slice[..half_size]),
        || compute_t_evals_second_half(&eq_tail, &poly_slice[half_size..]),
    );
    (t_0, t_1).into()
};
```

#### 发送、采样和更新

一旦我们有了 $t_j(0)$ 和 $t_j(1)$，我们计算 $\ell_j(0)$ 和 $\ell_j(1)$ 并得到：

$S_j(0)=\ell_j(0) \cdot t_j(0)$
$S_j(∞)=(\ell_j(1)-\ell_j(0)) \cdot (t_j(1)-t_j(0))$

然后我们将这些求值添加到证明者状态并采样一个扩展域元素 $r_j$。之后，我们 fold 多项式并获得：

$p(r_1,…,r_j,x_{j+1},…,x_\ell)$.

最后，我们更新声明的和：

$\sigma_{j+1}=S_j(r_j)$.

```rust
// Compute S_i(u) = t_i(u) * l_i(u) for u in {0, inf}:
let linear_evals = compute_linear_function(&w.0[..round], challenges);
let [s_0, s_inf] = get_evals_from_l_and_t(&linear_evals, &t_evals);

// Send S_i(u) to the verifier.
prover_state.add_extension_scalars(&[s_0, s_inf]);

prover_state.pow_grinding(pow_bits);

// Receive the challenge r_i from the verifier.
let r_i: EF = prover_state.sample();
challenges.push(r_i);

// Fold and update the poly.
poly.compress_svo(r_i);

// Update claimed sum
let eval_1 = *sum - s_0;
*sum = s_inf * r_i.square() + (eval_1 - s_0 - s_inf) * r_i + s_0;
```

## VI. 通信优化

独立于证明者的计算 (SVO)，我们还优化了通信。在标准的 sumcheck 中，证明者每轮发送三个字段元素（因为需要发送的多项式是 2 次的）。但是，我们只发送两个，从而减少了证明大小。

诀窍是验证者可以推导出第三个值。对于任何轮次 $i$，证明者发送：

- $S_i(0)$ — 在零处的求值。
- $S_i(∞)$ — 领先系数。

验证者从前一轮知道声明的和 $\sigma_i=S_{i-1}(r_{i-1})$，从而推导出第三个求值：

$S_i(1)=\sigma_i-S_i(0)$

这成立的原因是由于求和约束 $S_i(0)+S_i(1)=\sigma_i$。

你可以在 `svo_three_rounds` 和 `algorithm_5` 函数中找到针对证明者的实现。例如，对于第一轮，你会看到：

```rust
// Prover side

// [...]

// Round 1
prover_state.add_extension_scalars(&[s_0, s_inf]); // Send 2 values.
let r_1: EF = prover_state.sample(); // Sample a random challenge.
let s_1 = *sum - s_0; // Derive 3rd value.
*sum = s_inf * r_1.square() + (s_1 - s_0 - s_inf) * r_1 + s_0; // Update sum.

// [...]
```

验证者的工作更简单：它读取证明，导出缺失的值，并验证一致性。你可以在 [`verify_sumcheck_round_svo`](https://github.com/lambdaclass/whir-p3/blob/eec71d03a5ec81f30acc6d591f42f318941c6df5/src/whir/verifier/sumcheck.rs#L144) 中找到实现：

```rust
// Verifier Side

// [...]

for _ in 0..rounds {
    // Extract the first and third evaluations of the sumcheck polynomial
    // and derive the second evaluation from the latest sum.
    let c0 = verifier_state.next_extension_scalar()?;

let c1 = *claimed_sum - c0;

let c2 = verifier_state.next_extension_scalar()?;

// PoW interaction (grinding resistance)
    verifier_state.check_pow_grinding(pow_bits)?;

// Sample the next verifier folding randomness rᵢ.
    let rand: EF = verifier_state.sample();

// Update sum.
    *claimed_sum = c2 * rand.square() + (c1 - c0 - c2) * rand + c0;

randomness.push(rand);
}

// [...]
```

验证者从不计算累加器或直接评估多项式。它只从证明中读取两个字段元素并导出第三个值。这比经典的 sumcheck 验证者有效得多，后者需要读取三个元素并显式验证求和约束。

## VII. 结论

在这篇文章中，我们用 Rust 展示了 BDDT 论文中 **算法 6** 的完整实现，将两种优化技术（SVO 和 Eq-Poly）整合到一个工作证明器中。

作为奖励，我们还通过每轮仅发送两个字段元素来减少证明大小，从而利用求和约束让验证者导出缺失的值。

这些优化现在是我们 [whir-p3 分支](https://github.com/lambdaclass/whir-p3) 的一部分，并且已 [合并到原始存储库中](https://github.com/tcoratger/whir-p3/pull/322)。

## 参考文献

- [小值优化论文](https://eprint.iacr.org/2025/1117)
- [优化 Sumcheck (第一部分)](https://blog.lambdaclass.com/optimizing-sumcheck/)
- [分解等式多项式如何优化 Sumcheck (第二部分)](https://blog.lambdaclass.com/how-factoring-equality-polynomials-optimizes-sumcheck/)
- [Whirlaway：使用 WHIR 的多线性 STARK](https://learnblockchain.cn/article/23005/)
- [whir-p3 仓库](https://github.com/tcoratger/whir-p3)
- [我们分叉的 whir-p3 仓库](https://github.com/lambdaclass/whir-p3)
```

>- 原文链接： [blog.lambdaclass.com/spe...](https://blog.lambdaclass.com/speeding-up-sumcheck-an-in-depth-walkthrough-of-our-implementation)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

介绍

在这篇文章中，我们将深入探讨我们在 whir-p3 仓库中实现的由 Bagad、Dao、Domb 和 Thaler (BDDT) 在他们的论文中提出的 sumcheck 优化。在之前的文章中，我们已经解释了主要的理论思想（参见第一部分和第二部分）。在这里，我们将深入研究实现细节，展示我们如何在 whir-p3 仓库中准确地实现该论文中的 算法 6。

这项工作受到了 Lean Ethereum 团队的推动，该团队使用 Whirlaway，这是一种多线性协议，它依赖 Whir 作为其多项式承诺方案 (PCS)。该团队发现 sumcheck 协议可以从现有的优化中受益（参见 issue #280）。为了解决这个问题，我们介入并在他们的代码库中实现了 BDDT 优化。

免责声明： 本文提供的代码片段对应于合并到此 PR 中的实现。虽然 whir-p3 仓库正在积极和不断地开发中，但我们选择分析这个特定的快照，因为它提供了最高的教学清晰度。这个版本 —— 你可以在我们的仓库 fork 中找到 —— 与 BDDT 论文的理论概念保持着忠实的一对一映射，使其成为在应用进一步的工程优化之前理解核心逻辑的理想参考。

I. 核心思想：延迟昂贵的字段运算

naive 的 sumcheck prover 过早地强制执行昂贵的扩展字段运算。BDDT 优化的目标很简单：尽可能长时间地延迟扩展字段运算的引入。

扩展字段计算

在像 Jolt（激发了这篇论文）或 Whir 这样的系统中，底层计算（例如，执行轨迹）对小的基础字段值（32 位或 64 位整数）进行操作。然而，密码学安全性要求 sumcheck 协议使用扩展字段随机挑战。在我们的实现中，我们使用像 Baby Bear (31-bit)、Koala Bear 或 Goldilocks (64-bit) 这样的基础字段以及它们的扩展（例如，BinomialExtensionField<BabyBear, 4>）。

这些操作之间的性能差距是巨大的。BDDT 论文引入了一个精确的成本模型：

𝔰𝔰 (small-small)：两个基础字段元素相乘，例如，BabyBear * BabyBear。这是最快的 —— 只是一个简单的基础字段乘法。
𝔰𝔩 (small-large)：一个基础字段元素乘以一个扩展字段元素，例如，BabyBear * BinomialExtensionField<BabyBear, 4> 需要 4 个基础字段乘法（每个扩展系数一个）。
𝔩𝔩 (large-large)：两个扩展字段元素相乘，例如，BinomialExtensionField<BabyBear, 4> * BinomialExtensionField<BabyBear, 4> 速度要慢得多，需要 16 个基础字段乘法加上额外的操作 —— 通常比 𝔰𝔰 慢一个数量级。

成本问题

naive（或经典）的 sumcheck prover（论文中的 算法 1）存在过早的扩展字段传播：

第 1 轮：prover 计算基础字段值的乘积之和 —— 所有廉价的 𝔰𝔰 运算。
第 2 轮及以后：verifier 发送一个随机挑战 $r1 \in \mathbb{F}{ext}$，一个扩展字段元素。这强制所有后续计算使用扩展字段运算。从那时起，prover 必须对所有剩余的轮次执行昂贵的 𝔩𝔩 运算。

关键见解： 尽可能长时间地延迟这种转换。执行更多的操作更好，但在基础字段中。这就是全部的想法。

II. 两个优化：SVO 和 Eq-Poly

算法 6 综合了两个互补的优化。单独理解每一个，可以清楚地了解它们如何协同工作。

A. 小值优化 (SVO)

小值优化（算法 4）是一种计算策略：延迟扩展字段运算。

一种 naive 的方法（算法 3）会将多项式扩展为 $O(2^{d \cdot \ell_0})$ 项，以保持基础字段和扩展字段分量的分离。对于实际值来说，这是指数级的昂贵且不可行的。

SVO 的见解： 使用 拉格朗日插值 而不是扩展。这与 Toom-Cook 乘法背后的原理相同。通过将 round 多项式视为要从少量评估点插值的东西，而不是扩展成指数级的单项式，我们将预计算成本从 $O(2^{d \cdot \ell_0})$ 降低到 $O((d+1)\ell_0)$。

你可以在我们的系列第一部分中看到这种优化背后的直觉。

B. Eq-Poly 优化 (算法 5)

第二个优化（算法 5）解决了特定情况

$g(X) = eq(w, X)p(X)$.

它基于 Gruen 的优化，其思想是减少与 $eq$ 多项式相关的 𝔩𝔩 乘法。

该算法没有一次性地对所有剩余变量求和，而是将该求和 "拆分" 成两半。

有关完整说明，请参见我们系列的第二部分。

III. 协议架构：两阶段策略

我们的实现本质上封装在函数 from_base_evals_svo 中，prover 调用该函数以按照 算法 6 执行 sumcheck 协议。它结合了 SVO 和 Eq-Poly 优化。在我们的实现中，我们选择了：

$\ell_0 = 3$：我们只进行三个 SVO 轮次，因为正如我们稍后将详细解释的那样，这种优化仅在几个轮次中有效。
$d = 1$：我们只接受一个多线性多项式，而不是像 BDDT 论文中所示的多项式的乘积。之所以选择这种方式，是因为在我们感兴趣的用例中（即，在 Whir 的上下文中），我们只有一个多项式。

给定超立方体上多线性多项式 $p$ 的基础字段求值 (evals) 和一个 eq-poly 约束 (constraint)，它应用一定数量的 sumcheck 轮次 (folding_factor)，返回一个新的 SumcheckSingle 和使用的挑战。

重要的是要指出，此实现设计用于大于 5 的 folding_factor 和仅包含一个相等性语句的 constraint，因为我们想使用 Whir 作为 PCS。

因此，此函数的目标是证明一个相等性约束。

$\sigma = p(w)$,

其中我们可以将求值重写为总和：

$p(w) = \sum_{x \in {0,1}^\ell} eq(w,x)p(x)$.

该算法的核心见解：对不同的阶段使用不同的策略。以下是高级结构：

/// 运行遵循算法 6 的 Sumcheck prover。
pub fn from_base_evals_svo&lt;Challenger>(
    evals: &EvaluationsList&lt;F>,
    prover_state: &mut ProverState&lt;F, EF, Challenger>,
    folding_factor: usize,
    pow_bits: usize,
    constraint: &Constraint&lt;F, EF>,
) -> (Self, MultilinearPoint&lt;EF>) {

    let mut challenges = Vec::with_capacity(folding_factor);
    // 在这里，我们假设相等性语句只有一个约束。
    let mut sum = constraint.eq_statement.evaluations[0];
    let w = &constraint.eq_statement.points[0];

    // 创建统一的相等性多项式评估器
    let mut eq_poly = SumcheckEqState::&lt;_, NUM_SVO_ROUNDS>::new(w);

    // --- 阶段 1：前 3 轮的 SVO ---
    let (r_1, r_2, r_3) = svo_three_rounds(prover_state, evals, w, &mut sum, pow_bits);
    challenges.extend([r_1, r_2, r_3]);

    // --- 切换：用 3 个挑战折叠多项式 ---
    // 我们进行折叠以获得 p(r1, r2, r3, x)。
    let mut folded_evals = fold_evals_with_challenges(evals, &challenges);

    // --- 阶段 2：剩余轮次的算法 5 ---
    algorithm_5(prover_state, &mut folded_evals, w, &mut challenges, &mut sum, pow_bits);

    let challenge_point = MultilinearPoint::new(challenges);

    // 最终权重：eq(w, r)
    let weights = EvaluationsList::new(vec![w.eq_poly(&challenge_point)]);
    let sumcheck = Self::new(folded_evals, weights, sum);

    (sumcheck, challenge_point)
}

接下来，让我们详细解释每个阶段。

IV. 阶段 1：前三轮

前三轮 sumcheck 由 svo_three_rounds 实现。在每个轮次 $i$ 中，prover 需要：

计算单变量多项式求值 $S_i(0)$ 和 $S_i(\infty)$（即，前导系数）。
将这些求值添加到 prover 状态。
采样一个新的挑战 $r_i$。
折叠多项式 $p$。
更新声明的总和 $\sigma$。

唯一繁重的步骤是第一个。我们希望 prover 能够有效地计算 $S_i$。这就是 SVO 发挥作用的地方。

分解单变量轮多项式

我们想要证明的声明总和是：

$\sigma = p(w) = \sum_{x \in {0,1}^\ell} eq(w,x)p(x)$.

然后，对于每一轮 $i$，prover 需要计算单变量轮多项式 $S_i(u)$，其中：

$Si(u) = \sum{x \in {0,1}^{\ell-i}} eq(w[1,i-1]; r[1,i-1], u, x) \cdot p(r[1,i-1], u, x)$.

分割 eq-poly，我们可以按以下方式分解 $S_i$，其中 $\ell$ 是容易的部分，$t$ 是困难的部分：

$S_i(u) = \ell_i(u)t_i(u), \quad \ell_i(u) = eq(w[1,i-1]; r[1,i-1]) eq(w_i; u), \quad ti(u) = \sum{x \in {0,1}^{\ell-i}} eq(w[i+1,\ell]; x) p(r[1,i-1], u, x)$.

其中：

$\ell_i(u)$ 是线性部分：它来自变量 1 到 $i$ 的 eq-poly 部分。这是一个关于 $u$ 的线性多项式，很容易计算。
$t_i(u)$ 是繁重部分：它包含了所有剩余变量 $x$ 上的总和以及多项式 $p$。所有的复杂性都存在于此。

请注意，计算 $\ell_i(0)$ 和 $\ell_i(1)$ 本质上是 "免费的"，但是 naive 地计算 $t_i(0)$ 和 $t_i(1)$ 需要对指数级的许多项求和。这就是累加器发挥作用的地方。

累加器计算（过程 9）

“重型部分” $t_i(u)$ 是 SVO（算法 4）和 Eq-Poly（算法 5）相结合的地方。我们通过在挑战 $r[1,i-1]$ 上使用拉格朗日插值和在剩余变量 $x$ 上使用和分割见解来应用 Toom-Cook 见解。

这使我们能够根据预先计算的累加器 $A_i(v,u)$ 重构 $t_i(u)$：

$ti(u) = \sum{v \in {0,1}^{i-1}} Lv(r[1,i-1]) \cdot \underbrace{\left( \sum{x_L} eq(w[i+1,\ell/2]; xL) \sum{x_R} eq(w[\ell/2+1,\ell]; x_R) \cdot p(v,u,x_L,xR) \right)}{A_i(v,u)}$

这里，$L_v$ 是拉格朗日基多项式。这个公式是 算法 6 预计算的核心。计算这些 $A_i(v,u)$ 累加器的 "方式" 是 过程 9。

我们可以通过以下方式重写先前方程式的内部部分：

$Ai(v,u) = \sum{y \in {0,1}^{\ell0-i}} \sum{x_{out} \in {0,1}^{\ell/2-\ell_0}} eq((w[(i+1):\ell_0], w[(\ell/2+\ell0+1):]), (y,x{out})) \cdot \sum{x{in} \in {0,1}^{\ell/2}} eq(w[(\ell_0+1):(\ell0+\ell/2)], x{in}) \cdot p(v,u,y,,x{in},x{out})$

在本文中，我们可以看到 过程 9 巧妙地反转了循环：它不是通过累加器 $Ai(v,u)$ 迭代，而是迭代数据 $(x{out},x_{in},\beta)$ 并将每个结果 "分配" 到正确的 $A_i(v,u)$ bin。这是分两个阶段完成的：

时间累积 ($tA[\beta]$)：对于固定的 $x_{out}$，该算法计算每个前缀 $\beta \in {0,1}^{\ell_0}$ 的整个内部和。该循环包含主要的 𝔰𝔩 运算：e_in_value * poly_evals[index]。

$tA[\beta] = \sum{x{in} \in {0,1}^{\ell/2}} E{in}[x{in}] \cdot p(\beta, x{in}, x{out})$

$E{in}[x{in}] = eq(w[(\ell_0+1):(\ell0+\ell/2)], x{in})$

分布：一旦计算出 $tA$ 向量，该算法就将这些值 "分布" 到正确的最终累加器 $Ai(v,u)$，并将它们乘以各自的 $E{out}$ 权重。

让我们深入研究我们的实现。

首先，我们有一个 Accumulators 结构，我们在其中存储这些值，以及几个用于创建、修改和读取它们的基本方法：

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct Accumulators&lt;F: Field> {
    /// 每个 SVO 轮次一个累加器向量。
    /// - `accumulators[0]` 有 2^1 = 2 个元素，用于 A_0(u)
    /// - `accumulators[1]` 有 2^2 = 4 个元素，用于 A_1(v, u)
    /// - `accumulators[2]` 有 2^3 = 8 个元素，用于 A_2(v, u)
    pub accumulators: [Vec&lt;F>; NUM_SVO_ROUNDS],
}

impl&lt;F> Accumulators&lt;F>
where
    F: Field,
{
    #[must_use]
    pub fn new_empty() -> Self {
        Self {
            // 在第 0 轮中，我们有 2 个累加器：A_0(u)，其中 u 在 {0, 1} 中。
            // 在第 1 轮中，我们有 4 个累加器：A_1(v, u)，其中 v 在 {0, 1} 中，u 在 {0, 1} 中。
            // 在第 2 轮中，我们有 8 个累加器：A_2(v, u)，其中 v 在 {0, 1}^2 中，u 在 {0, 1} 中。
            // 我们不需要任何数字为无穷大的累加器。
            accumulators: [F::zero_vec(2), F::zero_vec(4), F::zero_vec(8)],
        }
    }

    /// 将值添加到特定的累加器。
    pub fn accumulate(&mut self, round: usize, index: usize, value: F) {
        self.accumulators[round][index] += value;
    }
    /// 获取给定轮次的累加器切片。
    #[must_use]
    pub fn get_accumulators_for_round(&self, round: usize) -> &[F] {
        &self.accumulators[round]
    }
}

请注意，即使最初我们应该有三个求值：在 $0$、$1$ 和 $\infty$ 处，因为 $S(u)$ 的度数为 2，但在代码中，我们仅计算 $u \in {0,1}$ 的累加器。稍后我们将对此进行解释。

因此，让我们来看一下我们如何将 过程 9 适应于我们的特定用例。

/// 过程 9。第 37 页。
/// 我们只计算我们将要使用的累加器，即，
/// A_i(v, u)，适用于 {0, 1, 2} 中的 i、{0, 1}^{i} 中的 v 和 {0, 1} 中的 u。
fn compute_accumulators&lt;F: Field, EF: ExtensionField&lt;F>>(
    poly: &EvaluationsList&lt;F>,
    e_in: &[EF],
    e_out: &[Vec&lt;EF>; NUM_SVO_ROUNDS],
) -> Accumulators&lt;EF> {
    [...]
}

该函数接收 $p(x)$、$E{in}$ 和 $E{out}$ 的求值作为输入。

我们可以在论文中看到这些计算如下：

$E_{in} := (eq(w[\ell_0+1:(\ell0+\ell/2)], x{in})) \quad \text{with} \quad x_{in} \in {0,1}^{\ell/2}$

$E_{out,i} := (eq((w[(i+1):\ell_0], w[(\ell/2+\ell0+1):]), (y,x{out}))) \quad \text{with} \quad (y,x_{out}) \in {0,1}^{\ell_0} \times {0,1}^{\ell/2-\ell_0}$

这些值仅取决于我们的挑战 $w$，因此我们可以如下预先计算它们：

/// 过程 9（compute_accumulators）所需的预计算。
/// 计算所有 x in {0,1}^l/2 的求值 eq(w_{l0 + 1}, ..., w_{l0 + l/2} ; x)
fn precompute_e_in&lt;F: Field>(w: &MultilinearPoint&lt;F>) -> Vec&lt;F> {
    let half_l = w.num_variables() / 2;
    let w_in = &w.0[NUM_SVO_ROUNDS..NUM_SVO_ROUNDS + half_l];
    eval_eq_in_hypercube(w_in)
}

/// 过程 9（compute_accumulators）所需的预计算。
/// 计算三个 E_out 向量，每个轮次 i 在 {0, 1, 2} 中一个。
/// 对于每个 i，E_out = eq(w_{i+1}, ..., l0, w_{l/2 + l0 + 1}, ..., w_l ; x)
fn precompute_e_out&lt;F: Field>(w: &MultilinearPoint&lt;F>) -> [Vec&lt;F>; NUM_SVO_ROUNDS] {
    let half_l = w.num_variables() / 2;
    let w_out_len = w.num_variables() - half_l - 1;

    std::array::from_fn(|round| {
        let mut w_out = Vec::with_capacity(w_out_len);
        w_out.extend_from_slice(&w.0[round + 1..NUM_SVO_ROUNDS]);
        w_out.extend_from_slice(&w.0[half_l + NUM_SVO_ROUNDS..]);
        eval_eq_in_hypercube(&w_out)
    })
}

一旦我们计算出这些值，我们就可以返回到我们的 compute_accumulators 函数。

我们做的第一件事是计算 $x_{out}$ 中变量的数量为 $\ell/2 - \ell_0$，其中 $\ell$ 是 $p(X)$ 的变量数，$\ell_0$ 是 SVO 轮次数，同时考虑到 $\ell$ 为奇数的情况。

    [...]
    let l = poly.num_variables();
    let half_l = l / 2;

    let x_out_num_vars = half_l - NUM_SVO_ROUNDS + (l % 2);
    let x_num_vars = l - NUM_SVO_ROUNDS;
    debug_assert_eq!(half_l + x_out_num_vars, x_num_vars);

    let poly_evals = poly.as_slice();
    [...]

现在我们可以运行外部循环，其中对于 $x_{out}$ 的每个值，我们将：

初始化临时累加器并计算 $x_{in}$ 中的变量数：

    (0..1 &lt;&lt; x_out_num_vars)
        .into_par_iter()
        .map(|x_out| {
            // 每个线程将计算其自己的一组本地累加器。
            // 这避免了可变状态共享和对锁的需求。
            let mut local_accumulators = Accumulators::&lt;EF>::new_empty();

            let mut temp_accumulators = [EF::ZERO; 1 &lt;&lt; NUM_SVO_ROUNDS];

            let num_x_in = 1 &lt;&lt; half_l;
        })

对于 $x_{in}$ 的每个值，我们使用以下公式计算 $tA$ 值：

$tA(x{out}) = \sum{\beta \in {0,1}^3} E{in}[x{in}] \cdot p(\beta, x{in}, x{out})$

            for (x_in, &e_in_value) in e_in.iter().enumerate().take(num_x_in) {
                // 对于 {0,1}^3 中的每个 beta，我们更新 tA(beta) += e_in[x_in] * p(beta, x_in, x_out)
                #[allow(clippy::needless_range_loop)]
                for i in 0..(1 &lt;&lt; NUM_SVO_ROUNDS) {
                    let beta = i &lt;&lt; x_num_vars;
                    let index = beta | (x_in &lt;&lt; x_out_num_vars) | x_out; // beta | x_in | x_out
                    temp_accumulators[i] += e_in_value * poly_evals[index]; // += e_in[x_in] * p(beta, x_in, x_out)
                }
            }

一旦我们获得了所有临时累加器，我们就解压它们并收集我们将需要的所有 $E_{out}$ 值。

请记住，$E{out}$ 仅取决于 $y$。因此，在第一轮中，$y$ 有 2 个变量，这给了我们 4 个可能的 $E{out}$ 值。在第二轮中，$y$ 有 1 个变量，因此有 2 个可能的 $E{out}$ 值。在第三轮中，它不依赖于 $y$，因此我们有单个 $E{out}$ 值。

    // 解构 things，因为我们稍后会多次访问它们
    let [t0, t1, t2, t3, t4, t5, t6, t7] = temp_accumulators;
    // 获取此 x_out 的 E_out(y, x_out)
    // 第 0 轮 (i=0) -> y=(b1,b2) -> 2 位
    let e0_0 = e_out[0][x_out]; // y=00
    let e0_1 = e_out[0][(1 &lt;&lt; x_out_num_vars) | x_out]; // y=01
    let e0_2 = e_out[0][(2 &lt;&lt; x_out_num_vars) | x_out]; // y=10
    let e0_3 = e_out[0][(3 &lt;&lt; x_out_num_vars) | x_out]; // y=11
    // 第 1 轮 (i=1) -> y=(b2) -> 1 位
    let e1_0 = e_out[1][x_out]; // y=0
    let e1_1 = e_out[1][(1 &lt;&lt; x_out_num_vars) | x_out]; // y=1
    // 第 2 轮 (i=2) -> y=() -> 0 位
    let e2 = e_out[2][x_out]; // y=()

一旦我们获得了所有这些值，我们就可以开始将它们添加到相应的累加器中。在 过程 9 中，这是通过迭代 $(i,v,u,y) \in idx_4(\beta)$ 完成的，但是由于我们只需要计算 3 轮，并且计算 $u=0$ 和 $u=1$ 的值，我们可以使用以下总和直接完成它：

$\sum{\beta \in U{\ell0}^d} \sum{(i',v',u',y) \in idx4(\beta)} i'=i, v'=v, u'=u E{out,i'}[y,x_{out}] \cdot tA[\beta]$

     // 第 0 轮 (i=0)
     // A_0(u=0) = Σ_{y} E_out_0(y) * tA( (u=0, y), x_out )
     local_accumulators.accumulate(0, 0, e0_0 * t0 + e0_1 * t1 + e0_2 * t2 + e0_3 * t3);
     // A_0(u=1) = Σ_{y} E_out_0(y) * tA( (u=1, y), x_out )
     local_accumulators.accumulate(0, 1, e0_0 * t4 + e0_1 * t5 + e0_2 * t6 + e0_3 * t7);
     // 第 1 轮 (i=1)
     // A_1(v, u) = Σ_{y} E_out_1(y) * tA( (v, u, y), x_out )
     // v=0, u=0
     local_accumulators.accumulate(1, 0, e1_0 * t0 + e1_1 * t1);
     // v=0, u=1
     local_accumulators.accumulate(1, 1, e1_0 * t2 + e1_1 * t3);
     // v=1, u=0
     local_accumulators.accumulate(1, 2, e1_0 * t4 + e1_1 * t5);
     // v=1, u=1
     local_accumulators.accumulate(1, 3, e1_0 * t6 + e1_1 * t7);
     // 第 2 轮 (i=2)
     // A_2(v, u) = E_out_2() * tA( (v, u), x_out )
     #[allow(clippy::needless_range_loop)]
     for i in 0..8 {
          local_accumulators.accumulate(2, i, e2 * temp_accumulators[i]);
          }

最后，唯一剩下的是对 ($x_{\mathrm{out}}$) 执行最终求和。

        .par_fold_reduce(
            || Accumulators::&lt;EF>::new_empty(),
            |a, b| a + b,
            |a, b| a + b,
        )

V. 阶段 2：切换到算法 5

切换策略至关重要。SVO 仅在前几轮中更便宜。这就是为什么在前三轮之后，我们需要将我们收集到的挑战 "应用" 到剩余的多项式求值。此过程在形式上称为折叠或部分求值。我们通过绑定前三个变量，将原始多项式 $p(x1,…,x\ell)$ 转换为较小的多项式 $p^{(3)}(x4,…,x\ell)$：

$p^{(3)}(x4,…,x\ell)=\sum_{b\in{0,1}^3}eq((r_1,r_2,r_3),b) \cdot p(b,x4,…,x\ell)$

多项式折叠在以下行中完成：

// 进行折叠以获得 p(r1, r2, r3, x)
let mut folded_evals = fold_evals_with_challenges(evals, &challenges);

此操作将我们的求值域从 $2^\ell$ 缩小到 $2^{\ell-3}$。在我们的实现中，函数 fold_evals_with_challenges 并行处理此折叠操作。

索引逻辑 (j * num_remaining_evals) + i 允许我们跳到正确的块 $j$ 并访问特定的元素 $i$，将加权和累加到结果中。

pub fn fold_evals_with_challenges&lt;F, EF>(
    evals: &EvaluationsList&lt;F>,
    challenges: &[EF],
) -> EvaluationsList&lt;EF> {
    let n = evals.num_vars();
    let k = challenges.len(); // 在我们的案例中 k = 3
    // 较小的新超立方体的大小 (2^{l-3})
    let num_remaining_evals = 1 &lt;&lt; (n - k);

    // 1. 预先计算 {0,1}^3 中所有 8 个前缀 b 的权重 eq(r, b)
    let eq_evals: Vec&lt;EF> = eval_eq_in_hypercube(challenges);
``````markdown
// 2. 并行 Fold
    let folded_evals_flat: Vec&lt;EF> = (0..num_remaining_evals)
        .into_par_iter()
        .map(|i| {
             // 对于目标域中的每个点 'i'，对 8 个源前缀求和。
            eq_evals
                .iter()
                .enumerate()
                .fold(EF::ZERO, |acc, (j, &eq_val)| {
                    // 重构索引：前缀 (j) + 后缀 (i)
                    let original_eval_index = (j * num_remaining_evals) + i;

                    let p_b_x = evals.as_slice()[original_eval_index];
                    acc + eq_val * p_b_x
                })
        })
        .collect();

    EvaluationsList::new(folded_evals_flat)
}

SVO 到标准算法的切换

为什么我们要在这里停止 SVO？这个决定是由字段乘法的成本决定的，正如论文中分析的那样：

Folding 之前 (ssss Regime): 我们的多项式求值在基本域中（小）。SVO 利用这一点，通过在小值上使用高效的插值，避免了昂贵的扩展域算术。
Folding 操作: Folding 操作本身是一个线性组合，涉及到挑战值 $r_i$。由于 $ri \in F{ext}$，fold 的输出必须在扩展域中。
Folding 之后 (llll Regime): 一旦我们的求值提升到扩展域，SVO 的好处就会消失。SVO 引入了 $O(d^2)$ 操作的开销，以节省乘法运算。

在三轮之后，折叠后的多线性多项式足够小，以至于标准的线性时间证明器 (算法 5) 比 SVO 更有效。通过在 fold 后立即切换，我们确保使用 SVO 处理基本域值，并使用标准方法处理扩展域值，从而在整个协议执行过程中保持最佳性能。

算法 5

一旦我们折叠了多项式，我们继续使用 算法 5 来执行剩余的 $\ell-\ell_0$ 轮。你可以在名为 algorithm_5 的函数中找到我们的实现。

pub fn algorithm_5&lt;Challenger, F: Field, EF: ExtensionField&lt;F>>(
    prover_state: &mut ProverState&lt;F, EF, Challenger>,
    poly: &mut EvaluationsList&lt;EF>,
    w: &MultilinearPoint&lt;EF>,
    challenges: &mut Vec&lt;EF>,
    sum: &mut EF,
    pow_bits: usize,
) where
    Challenger: FieldChallenger&lt;F> + GrindingChallenger&lt;Witness = F>,
{
    [...]
}

在每一轮 $j$ 中，证明者的目标与前三轮相同。我们需要：

计算并发送单变量多项式求值 $S_j(u)$，对于 $u\in{0,∞}$。
更新下一轮的变量。

为此，我们将继续使用 $S_j$ 的分解式：

$S_j(u)=\ell_j(u) \cdot t_j(u)$

其中，回想一下，

$\ell_j(u)=eq(w[1,j-1];r[1,j-1]) \cdot eq(w_j;u)$ $tj(u)=\sum{x\in{0,1}^{\ell-j}}eq(w[j+1,\ell];x) \cdot p(r[1,j-1],u,x)$

让我们逐步分解 algorithm_5 函数。在轮循环之前，你会看到这段代码：

let num_vars = w.num_variables();
let half_l = num_vars / 2;

// Precompute eq_R = eq(w_{l/2+1..l}, x_R)
let eq_r = eval_eq_in_hypercube(&w.0[half_l..]);
let num_vars_x_r = eq_r.len().ilog2() as usize;

// The number of variables of x_R is: l/2 if l is even and l/2 + 1 if l is odd.
debug_assert_eq!(num_vars_x_r, num_vars - half_l);

// start_round should be NUM_SVO_ROUNDS.
let start_round = challenges.len();
challenges.reserve(num_vars - start_round);

$eqR=eq(w{\ell/2+1},…,w\ell;x{\ell/2+1},…,x_\ell)$.

免责声明： 你会看到在代码中，循环从 i=$\ell_0$ 开始，但应该计算的第一轮是 $\ell_0+1$。这就是为什么我们在代码中有变量 round = i + 1。在本文中，为了简化符号，我们调用 j=j=round。

// Compute the remaining rounds, from l_0 + 1 to the end.
for i in start_round..num_vars {
    // `i` is the 0-indexed variable number, so `round = i + 1`.
    let round = i + 1;
    let num_vars_poly_current = poly.num_variables();
    let poly_slice = poly.as_slice();

    [...]

前半部分轮次

对于 $j<\ell/2$ 的情况，我们使用 compute_t_evals_first_half 函数并行获得 $t_j(0)$ 和 $t_j(1)$。这些值使用以下求和拆分计算：

$t(0)=\sum_{x_R}eq(w[\ell/2+1,\ell],xR)\sum{x_L}eq(w[j+1,\ell/2],x_L) \cdot p(r[1,j-1],0,x_L,xR)$ $t(1)=\sum{x_R}eq(w[\ell/2+1,\ell],xR)\sum{x_L}eq(w[j+1,\ell/2],x_L) \cdot p(r[1,j-1],1,x_L,x_R)$

// Compute t(u) for u in {0, 1}.
let t_evals: [EF; 2] = if round &lt;= half_l {
    // Case i+1 &lt;= l/2: Compute eq_L = eq(w_{i+2..l/2}, x_L)
    let eq_l = eval_eq_in_hypercube(&w.0[round..half_l]);
    let (t_0, t_1) = join(
        || compute_t_evals_first_half(&eq_l, &eq_r, poly_slice, num_vars_x_r, 0),
        || {
            compute_t_evals_first_half(
                &eq_l,
                &eq_r,
                poly_slice,
                num_vars_x_r,
                1 &lt;&lt; (num_vars_poly_current - 1), // offset for u=1
            )
        },
    );
    (t_0, t_1).into()

    [...]

后半部分轮次

类似地，在 $j\geq\ell/2$ 的情况下，我们使用 compute_t_evals_second_half 计算 $t_j(0)$ 和 $t_j(1)$。请注意，由于 $j\geq\ell/2$，我们没有涉及 $eq_L$ 多项式的求和。所以：

$t(0)=\sum_x eq(w[j+1,\ell],x) \cdot p(r[1,j-1],0,x)$ $t(1)=\sum_x eq(w[j+1,\ell],x) \cdot p(r[1,j-1],1,x)$

} else {
    // Case i+1 > l/2: Compute eq_tail = eq(w_{i+2..l}, x_tail)
    let eq_tail = eval_eq_in_hypercube(&w.0[round..]);
    let half_size = 1 &lt;&lt; (num_vars_poly_current - 1);
    let (t_0, t_1) = join(
        || compute_t_evals_second_half(&eq_tail, &poly_slice[..half_size]),
        || compute_t_evals_second_half(&eq_tail, &poly_slice[half_size..]),
    );
    (t_0, t_1).into()
};

发送、采样和更新

一旦我们有了 $t_j(0)$ 和 $t_j(1)$，我们计算 $\ell_j(0)$ 和 $\ell_j(1)$ 并得到：

$S_j(0)=\ell_j(0) \cdot t_j(0)$ $S_j(∞)=(\ell_j(1)-\ell_j(0)) \cdot (t_j(1)-t_j(0))$

然后我们将这些求值添加到证明者状态并采样一个扩展域元素 $r_j$。之后，我们 fold 多项式并获得：

$p(r_1,…,rj,x{j+1},…,x_\ell)$.

最后，我们更新声明的和：

$\sigma_{j+1}=S_j(r_j)$.

// Compute S_i(u) = t_i(u) * l_i(u) for u in {0, inf}:
let linear_evals = compute_linear_function(&w.0[..round], challenges);
let [s_0, s_inf] = get_evals_from_l_and_t(&linear_evals, &t_evals);

// Send S_i(u) to the verifier.
prover_state.add_extension_scalars(&[s_0, s_inf]);

prover_state.pow_grinding(pow_bits);

// Receive the challenge r_i from the verifier.
let r_i: EF = prover_state.sample();
challenges.push(r_i);

// Fold and update the poly.
poly.compress_svo(r_i);

// Update claimed sum
let eval_1 = *sum - s_0;
*sum = s_inf * r_i.square() + (eval_1 - s_0 - s_inf) * r_i + s_0;

VI. 通信优化

诀窍是验证者可以推导出第三个值。对于任何轮次 $i$，证明者发送：

$S_i(0)$ — 在零处的求值。
$S_i(∞)$ — 领先系数。

验证者从前一轮知道声明的和 $\sigmai=S{i-1}(r_{i-1})$，从而推导出第三个求值：

$S_i(1)=\sigma_i-S_i(0)$

这成立的原因是由于求和约束 $S_i(0)+S_i(1)=\sigma_i$。

你可以在 svo_three_rounds 和 algorithm_5 函数中找到针对证明者的实现。例如，对于第一轮，你会看到：

// Prover side

// [...]

// Round 1
prover_state.add_extension_scalars(&[s_0, s_inf]); // Send 2 values.
let r_1: EF = prover_state.sample(); // Sample a random challenge.
let s_1 = *sum - s_0; // Derive 3rd value.
*sum = s_inf * r_1.square() + (s_1 - s_0 - s_inf) * r_1 + s_0; // Update sum.

// [...]

验证者的工作更简单：它读取证明，导出缺失的值，并验证一致性。你可以在 verify_sumcheck_round_svo 中找到实现：

// Verifier Side

// [...]

for _ in 0..rounds {
    // Extract the first and third evaluations of the sumcheck polynomial
    // and derive the second evaluation from the latest sum.
    let c0 = verifier_state.next_extension_scalar()?;

    let c1 = *claimed_sum - c0;

    let c2 = verifier_state.next_extension_scalar()?;

    // PoW interaction (grinding resistance)
    verifier_state.check_pow_grinding(pow_bits)?;

    // Sample the next verifier folding randomness rᵢ.
    let rand: EF = verifier_state.sample();

    // Update sum.
    *claimed_sum = c2 * rand.square() + (c1 - c0 - c2) * rand + c0;

    randomness.push(rand);
}

// [...]

VII. 结论

在这篇文章中，我们用 Rust 展示了 BDDT 论文中 算法 6 的完整实现，将两种优化技术（SVO 和 Eq-Poly）整合到一个工作证明器中。