本文系统阐述了如何将多类常见约束规约到 Multivariate Sumcheck Protocol。核心思想是通过随机线性组合与对数导数技巧，将“逐点验证”的全称断言转化为“全局求和”形式，再调用 sumcheck 高效验证。主要方法包括：ZeroCheck：利用等值核函数，把“在布尔超立方体上恒等为零”的断言规约为单一求和断言。Rational Sumcheck：通过辅助函数与零检验，将有理函数求和转化为多项式求和。Multiset Equality Check：基于对数导数恒等式，把集合相等性检验规约为有理函数求和。Permutation Check：在元素附加索引后，转化为多重集相等性检查，再由 Rational Sumcheck 处理。LogUp Lookup Argument：通过有理函数形式验证查表约束，避免高开销的乘积表达。这些方法在 Plonk/HyperPlonk/Halo2 等现代零知识证明系统中得到广泛应用，用于范围检查、布线检验、置换约束和查表验证。

1. ZeroCheck

证明在布尔超立方体 ${0,1}^n$ 上，某个多项式/函数 $f(\vec{x})$ 对所有点都为零，即$\forall \vec{x}\in{0,1}^n,\quad f(\vec{x})=0.$把“逐点为零”的全称断言，转化为一个“单一求和为零”的等式检查，从而用 Multivariate Sumcheck 做交互/非交互验证：

• 通过“等值核” $\mathrm{eq}(\vec{x},\vec{r})$（布尔立方体上的拉格朗日基/多线性等值多项式）把对所有点的断言收敛成 一次 全局求和；
• 对随机点评价（或随机掩码）得到的 求和值 运行 sumcheck，避免枚举 $2^n$ 个点；
• 完整性显然成立（真命题使求和恒为 0）；可靠性由 Schwarz–Zippel（随机点零测集）保证。

把 $f$ 在立方体上的点值看成“权重”，再用 $\mathrm{eq}(\vec{x},\vec{r})$ 作为“插值核”在随机点 $\vec{r}$ 上做一次“抽样评估”（其实就是 $f$ 的多线性扩展 $\tilde f$ 在 $\vec{r}$ 的取值）。若 $f$ 非零，则 $\tilde f$ 是非零多项式，在大域上随机取 $\vec{r}$ 几乎不会恰好使其为 0。

验证 $f(\vec{x}) = 0$ 使得任意 $\vec{x} \in {0,1}^n$均成立

1. 取 $r \leftarrow \mathbb{F}_M$，构造 $\hat{f}(\vec{x}) := f(\vec{x}) \cdot \text{eq}(\vec{x}, r)$，其中 $\text{eq}(\vec{x}, r)$ 是多变量多项式的拉格朗日基，当且仅当$\vec{x}=r$，取值为1，其余取值为0
2. 使用 multivariate sumcheck 验证等式：$\sum_{\vec{x} \in {0,1}^n} \hat{f}(\vec{x}) = 0$

Batch Proof：验证 $f(\vec{x}) = 0 \land g(\vec{x}) = 0$

1. 随机选取 $\alpha \leftarrow \mathbb{F}$；
2. 在$f(\vec{x}) + \alpha g(\vec{x})$上调用ZeroCheck。

1.1 规约方式（到 Multivariate Sumcheck）

1. 随机掩码：取 $\vec{r}\leftarrow\mathbb{F}^n$，构造 $\hat f(\vec{x})=f(\vec{x})\mathrm{eq}(\vec{x},\vec{r})$。

2. 单一求和断言：把“全称为零”化为

   $$ S\;:=\;\sum_{\vec{x}\in{0,1}^n}\hat f(\vec{x})\stackrel{?}{=}0. $$

3. 运行 sumcheck：证明者与验证者对 $S$ 运行多变量 sumcheck（$n$ 轮）；每轮递归地把高维求和降一维，最后只需在随机点处做少量一致性检查（结合承诺/多项式开放等原语）。

复杂度：若 $f$ 是多线性，则 $\hat f$ 在每个变量上的次数 $\le 2$（或保持低度），sumcheck 的往返通信/验证时间是 $O(n)$ 轮、每轮处理 $O(1)$-度的多项式，整体高效。

1.2 典型用途

• Vanishing / 约束消失性检查：验证电路/约束在布尔域上处处成立（如门约束、选择子 gating 后的等式）。
• Rational 检查的子步骤：在有理关系中，常先用 ZeroCheck 验证“分母为 0 时分子也为 0”（守护条件），或把分子消失性转成求和断言。
• 批量约束：大量约束通过随机线性组合合一为单次 sumcheck，通信与验证成本基本与单约束同阶。
• 一致性/边界条件：例如表格/轨迹在立方体边界上的约束（$x_i\in{0,1}$ 条件下的端点关系）也能以 ZeroCheck 形式编码。

2. Rational Sumcheck

在许多证明系统里，需要验证涉及有理函数的全局求和关系，例如： $\sum_{\vec{x}\in{0,1}^n}\frac{p(\vec{x})}{q(\vec{x})} = v.$ 这类约束经常出现在 除法约束（denominator）、lookup argument、压缩多项式 等场景中。 由于 Sumcheck 协议本身只适用于多项式求和，而有理函数包含分母，因此需要一个规约策略，将“分式求和”化为多项式求和与 零检验 的组合：

1. 把分母 $q(\vec{x})$ 的倒数表示为一个多项式 $f(\vec{x})$（需要保证构造的 $f$ 确实等于 $1/q$）。
2. 在 $p(\vec{x})\cdot f(\vec{x})$ 上直接运行 Sumcheck，验证其和为 $v$。
3. 再用 ZeroCheck 验证 $f(\vec{x})\cdot q(\vec{x}) - 1 \equiv 0$，以确保证明者没有伪造 $f$。

这样就把“有理求和”安全地降解为“纯多项式求和 + 零检验”。

目标断言： $$ \sum_{\vec{x}\in{0,1}^n}\frac{p(\vec{x})}{q(\vec{x})} \stackrel{?}{=} v . $$

规约步骤：

1. 引入辅助函数 证明者声明存在一个函数 $f(\vec{x})$，使得

   $$ f(\vec{x}) = \frac{1}{q(\vec{x})},\qquad \forall \vec{x}\in{0,1}^n. $$

2. 核心求和 检查

   $$ \sum_{\vec{x}\in{0,1}^n} p(\vec{x}) \cdot f(\vec{x}) \stackrel{?}{=} v , $$

   通过 Multivariate Sumcheck Protocol 实现。

3. 一致性验证 通过 ZeroCheck 验证以下恒等式：

   $$ f(\vec{x})\cdot q(\vec{x}) - 1 \equiv 0 ,\qquad \forall \vec{x}\in{0,1}^n. $$

   若成立，则 $f(\vec{x})$ 必然是 $q(\vec{x})$ 的倒数。

2.1 规约方式

• 把“分式求和”规约为两部分：
  1. Sumcheck 部分：验证分子与分母倒数的乘积求和；
  2. ZeroCheck 部分：保证分母倒数的正确性。
• 若需要批量处理多个分式，可以通过随机线性组合把多个 $p_i/q_i$ 合并为一个统一的 Rational Sumcheck。

2.2 典型用途

• 除法约束：在证明系统中直接表达“某约束多项式除以选择子不为零”。
• 压缩关系：将多个多项式合并时，经常需要引入分母（随机组合 / 压缩技术）。
• Lookup argument：验证查表约束时，分母形式自然出现，可以通过 Rational Sumcheck 统一建模。
• Permutation / wiring checks：一些排列检查也能转化为有理形式，然后用该方法处理。

3 Multiset Equality Check via Rational Sumcheck

验证两个函数集合在布尔超立方体 ${0,1}^n$ 上的取值是否相等：${f_0(\vec{x}),\dots,f_k(\vec{x})}\;=\;{g_0(\vec{x}),\dots,g_k(\vec{x})}.$ 这类约束在证明系统里很常见，例如 Plonk wiring check。经典做法是用 ProdCheck（乘积校验）验证两边生成多项式是否相同，但 ProdCheck 在分布式场景下需要额外辅助多项式和交互，不够高效。 解决思路 通过 对数导数恒等式： $$ \prod_i (a_i+X)=\prod_i(b_i+X)\quad\Longleftrightarrow\quad \sum_i\frac{1}{a_i+X}=\sum_i\frac{1}{b_i+X}, $$ 可以把乘积等式规约为一个有理函数求和等式。这样一来，就能利用 Rational Sumcheck Protocol 处理，而无需构造额外的 helper polynomial。

关键技巧

1. 引入随机权重 $\gamma$，将多元集合压缩为单一多项式 $F(\vec{x}), G(\vec{x})$。
2. 再采样随机挑战 $\beta$，将乘积等式转换为分式求和。
3. 最终得到一个形如 $\sum p(\vec{x})/q(\vec{x})=0$ 的关系，可直接用 Rational Sumcheck 验证。

原理如下：验证 ${f_0(\vec{x}), ..., f_k(\vec{x})} = {g_0(\vec{x}), ..., gk(\vec{x})}$，其中$\vec{x} \in {0,1}^n$。选择随机 $\beta,\gamma$，构造线性组合： $$ F(\vec{x}) = \sum{j} \gamma^j \cdot{f_j(\vec{x})} , \quad G(\vec{x}) = \sum_j \gamma^j \cdot{g_j(\vec{x})} $$

因为ProdCheck在分布式场景下不友好，需要通过多个参与方之间交互来生成额外的helper polynomial来进行运算，从而将其转换为rational sumcheck，并依赖于以下定理：

定理（对数导数推导）：假设两个集合${a_i},{b_i}$的大小为n，那么有以下等式成立：

$$ \prod (a_i + X) = \prod (b_i + X) \Leftrightarrow \sum \frac{1}{a_i + X} = \sum \frac{1}{b_i + X} $$

将问题转换为Rational Sumcheck Protocol（即协议2），具体推导过程如下所示：

令$X=\beta$，作为一个random challenge, 随后令 $v1=\sum{\vec{x}\in{{0,1}^n}} \frac{1}{\beta + F(\vec{x})}$

$$ v1=\sum{\vec{x}\in{{0,1}^n}} \frac{1}{\beta + F(\vec{x})},\ v2=\sum{\vec{x}\in{{0,1}^n}} \frac{1}{\beta + G(\vec{x})} $$

接下来有$v_1=v_2$，即以下等式成立

$$ \sum_{\vec{x}\in{{0,1}^n}} \left( \frac{1}{\beta + F(\vec{x})} - \frac{1}{\beta + G(\vec{x})} \right) = 0 $$

随后将其合并同类项，则有

$$ \sum_{\vec{x}\in{{0,1}^n}}\frac{F(\vec{x})-G(\vec{x})}{(\beta+F(\vec{x}))\cdot{(\beta+G(\vec{x}))}}=0 $$

则令 $p(\vec{x})=F(\vec{x})-G(\vec{x}), q(\vec{x})=(\beta+F(\vec{x}))\cdot{(\beta+G(\vec{x}))}$，并利用Rational Sumcheck Protocol检查$\sum_{\vec{x}\in{{0,1}^n}} \frac{p(\vec{x})}{q(\vec{x})}=0$。

3.1 规约方式

• 利用随机线性组合（$\gamma$）将集合多项式压缩为单一函数。
• 利用对数导数定理与随机挑战（$\beta$），把“乘积等式”转化为“分式求和等式”。
• 调用 Rational Sumcheck，避免了传统 ProdCheck 的辅助多项式开销。

3.2 典型用途

• Plonk wiring check：验证布线约束对应的多集合一致性。
• Permutation check 的子步骤：证明一组值是另一组的排列。
• Lookup argument 的内部检查：验证查找集合与表集合是否相等。
• 一般性的 多集合相等性验证：任何需要证明多集合一致性的场景。

4. Permutation Check via Multiset Equality

Permutation Check via Multiset Equality 的核心目标是验证两个列表 $f(\vec{x})$ 与 $g(\vec{x})$ 是否仅仅是相互的一个排列（即它们的元素相同但顺序可能不同）。 直接比较难以高效实现，因此通过 多重集相等性 (Multiset Equality) 来完成验证。

基本思路是：给每个元素附加一个 索引标签，保证不同位置的元素可以区分。构造两个集合：一个由 $f(\vec{x})$ 与其在 恒等排列 下的位置索引 $s{\text{id}}(\vec{x})$ 组成；另一个由 $g(\vec{x})$ 与其在某一排列 $\sigma$ 下的位置索引 $s\sigma(\vec{x})$ 组成。如果这两个多重集完全一致，则说明 $g$ 确实是 $f$ 的一个排列。原理如下：

设输入空间为 ${0,1}^n$。定义： $$ \mathcal{F} = {(s{\text{id}}(\vec{x}), f(\vec{x})) \mid \vec{x} \in {0,1}^n}, $$ $$ \mathcal{G} = {(s\sigma(\vec{x}), g(\vec{x})) \mid \vec{x} \in {0,1}^n}. $$

其中：$s{\text{id}}(\vec{x})$ 表示 $\vec{x}$ 在恒等排列下的索引；$s\sigma(\vec{x})$ 表示 $\vec{x}$ 在置换 $\sigma$ 下的索引。

Permutation Check 的条件为：

$$ \mathcal{F} = \mathcal{G}. $$

即这两个带索引的多重集完全一致。

4.1 规约方式

为了高效检查多重集相等，常用 Random Linear Combination (RLC) 技巧：随机选取 $\beta \in \mathbb{F}$，构造单变量映射： $$ p(\vec{x}) = s{\text{id}}(\vec{x}) + \beta \cdot f(\vec{x}), $$ $$ q(\vec{x}) = s\sigma(\vec{x}) + \beta \cdot g(\vec{x}). $$ 检查 ${p(\vec{x})} = {q(\vec{x})}$。由于 $\beta$ 的随机性，除非 $\mathcal{F}=\mathcal{G}$，否则相等的概率可以忽略。

4.2 典型用途

Permutation Check via Multiset Equality 在零知识证明与多项式交互协议中非常常见，主要应用包括：

• 多项式置换检查 (Permutation Argument)： 用于证明两个多项式的值域只是排列关系（如 PLONK 的置换检验）。
• 一致性验证： 验证约束系统中不同表格/列的数据是否为同一集合的重新排列。
• 交叉验证： 确保 witness 的不同部分满足置换约束，例如 cross-column permutation checks。

5 LogUp Lookup Argument（基于对数导数）

LogUp (Logarithmic-Derivative based) Lookup Argument 的目标是验证一个集合（或多重集）$S \subseteq T$，即证明“所有被查表的元素 $S$ 确实来自于查找表 $T$”。 与基于多项式承诺的直接对比不同，LogUp 的思路是利用 有理函数恒等式： $$ \sum_{i \in [P]} \frac{1}{X + Si} = \sum{j \in [N]} \frac{m_j}{X + T_j}, $$

其中 $m_j$ 是表示元素 $T_j$ 出现次数的非负整数。这相当于比较两个多项式分式的对数导数，从而避免了直接构造庞大的乘积约束。原理如下：

给定查表输入集 $S = (S_1, \ldots, S_P) \in \mathbb{F}^P$， 查找表 $T = (T_1, \ldots, TN) \in \mathbb{F}^N$。 若 $S \subseteq T$，则存在一个向量 $m \in \mathbb{F}^N$，使得： $$ \sum{i \in [P]} \frac{1}{X + Si} = \sum{j \in [N]} \frac{m_j}{X + T_j}. $$ 为了压缩多维查表场景，引入随机线性组合参数 $\alpha \in \mathbb{F}$，把多个查表关系合并成一个： $$ X + \alpha \cdot Y \subseteq T_x + \alpha \cdot T_y. $$ 并定义： $$ Ai := \prod{j=1}^{t} \frac{1}{\beta + S_j(i)}, \qquad Bj := \prod{j=1}^{t} \frac{1}{\beta + Tj(i)}, $$ 其中 $\beta \in \mathbb{F}$ 是一个随机挑战。最终要验证的核心约束为： $$ \sum{i \in [P]} Ai = \sum{j \in [N]} m_j \cdot B_j. \tag{1} $$ 同时，还需要确保分母构造的正确性： $$ A(i) \cdot (\text{SC}(i) + \beta) = 1, \tag{2} $$ $$ B(j) \cdot (\text{CT}(j) + \beta) = 1. \tag{3} $$

5.1 规约方式

• 将 (1)、(2)、(3) 三个约束通过随机线性组合合并为一个约束： $$ (1) + \alpha \cdot (2) + \alpha^2 \cdot (3). $$
• 然后规约到 sumcheck 协议：验证一个多项式恒等式在布尔超立方体 ${0,1}^n$ 上成立。
• 这样，整个查表验证问题被高效规约为一个可交互的、多项式层面的 sumcheck。

5.2 典型用途

LogUp Lookup Argument 已成为现代零知识证明系统中 查表约束 的主流技术，典型应用包括：

1. 通用查表约束：高效验证 witness 的某些列是否来自给定表格（例如 range check, boolean check, custom gates）。
2. 多列查表 (cross-column lookup)：通过随机线性组合支持多个列的联合查表。
3. 电路优化：减少电路中的乘法门数量，因为查表可替代复杂约束表达。
4. 现代协议中的应用：Halo 2、Plonkish 系统的查表实现；Starkware 和 zkVM 框架中高效的范围检查与约束表达。

6. 对比

与HyperPlonk类似，HyperPianist对以下的relation规约为Multivariate Sumcheck Protocol，但为了实现非交互式的分布式证明，采用了不同的规约方式将其转换为Sumcheck Protocol

结论

Multivariate Sumcheck Protocol 作为一种统一的归约框架，能够承载 零检验、分式约束、集合一致性、置换与查表 等多种关系验证。其优势在于： 表达力强： 涵盖从单点约束到复杂有理关系的多种场景。 高效性： 避免指数级点值枚举，验证复杂度仅为多项式度与变量数的线性函数。 模块化： 不同约束均可转化为 sumcheck 的标准形式，方便组合与扩展。 实用性： 在 Plonkish 系统、STARK 系统以及 zkVM 框架中均已成为核心构件。 总体而言，Multivariate Sumcheck Protocol 已成为现代零知识证明中最具普适性的规约工具，为设计高效、安全的证明系统提供了坚实的基础。