本文展示了如何将零检验、有理约束、集合相等、置换与查表等多类约束统一规约到 Multivariate Sumcheck Protocol，实现高效验证。该方法已广泛应用于 Plonkish 与 STARK 系统中的范围检查、布线与查表约束。

本文系统阐述了如何将多类常见约束规约到 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}), ..., g_k(\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, 随后令 $v_1=\sum_{\vec{x}\in{{0,1}^n}} \frac{1}{\beta + F(\vec{x})}$

$$
v_1=\sum_{\vec{x}\in{{0,1}^n}} \frac{1}{\beta + F(\vec{x})},\ 
v_2=\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 + S_i} = \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, T_N) \in \mathbb{F}^N$。
若 $S \subseteq T$，则存在一个向量 $m \in \mathbb{F}^N$，使得：
$$
\sum_{i \in [P]} \frac{1}{X + S_i} = \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.
$$
并定义：
$$
A_i := \prod_{j=1}^{t} \frac{1}{\beta + S_j(i)}, \qquad
B_j := \prod_{j=1}^{t} \frac{1}{\beta + T_j(i)},
$$
其中 $\beta \in \mathbb{F}$ 是一个随机挑战。最终要验证的核心约束为：
$$
\sum_{i \in [P]} A_i = \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

| 编号 | Relation 类型 | 数学形式或目标描述 | 归约方式 | 用途说明 |
| --- | --- | --- | --- | --- |
| ① | **ZeroCheck** | 验证 $f(\vec{x})=0$ 使得任意 $\vec{x} \in \{0,1\}^n$均成立 | $\sum_{\vec{x} \in \{0,1\}^n} \hat{f}(\vec{x}) = 0$ | 约束消失性校验，如 vanishing 或 rational 检查 |
| ② | **Multiset Equality Check** | ${f_0(\vec{x}), ..., f_k(\vec{x})} = {g_0(\vec{x}), ..., g_k(\vec{x})}$ | 转换为乘积等式 + sumcheck | 验证集合相等，例如 Plonk wiring |
| ③ | **Rational Relation** | $\sum_{\vec{x}} \frac{p(\vec{x})}{q(\vec{x})} = v$  | 1. ZeroCheck on ( $q=0 \Rightarrow g=0$ )  <br> 2. sumcheck on ( $f q = g$ ) | 统一建模除法、压缩、多项式关系 |
| ④ | **Permutation Check** | $(s_{\text{id}}(\vec{x}), f(\vec{x})),(s_\sigma(\vec{x}), g(\vec{x}))$ | 转换为乘积表达式 + rational + sumcheck | Plonk permutation argument |
| ⑤ | **Lookup Check** |  $f(\vec{x}) \in \text{table} \subseteq \mathbb{F}$  | 转换为 multiset check 或 rational equality | Lookup argument 验证 |

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

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(\vec{x}) = 0$ 使得任意 $\vec{x} \in {0,1}^n$均成立

取 $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
使用 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$

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

1.1 规约方式（到 Multivariate Sumcheck）

随机掩码：取 $\vec{r}\leftarrow\mathbb{F}^n$，构造 $\hat f(\vec{x})=f(\vec{x})\mathrm{eq}(\vec{x},\vec{r})$。
单一求和断言：把“全称为零”化为

$$ S\;:=\;\sum_{\vec{x}\in{0,1}^n}\hat f(\vec{x})\stackrel{?}{=}0. $$
运行 sumcheck：证明者与验证者对 $S$ 运行多变量 sumcheck（$n$ 轮）；每轮递归地把高维求和降一维，最后只需在随机点处做少量一致性检查（结合承诺/多项式开放等原语）。

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 协议本身只适用于多项式求和，而有理函数包含分母，因此需要一个规约策略，将“分式求和”化为多项式求和与 零检验 的组合：

把分母 $q(\vec{x})$ 的倒数表示为一个多项式 $f(\vec{x})$（需要保证构造的 $f$ 确实等于 $1/q$）。
在 $p(\vec{x})\cdot f(\vec{x})$ 上直接运行 Sumcheck，验证其和为 $v$。
再用 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 . $$

规约步骤：

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

$$ f(\vec{x}) = \frac{1}{q(\vec{x})},\qquad \forall \vec{x}\in{0,1}^n. $$
核心求和 检查

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

通过 Multivariate Sumcheck Protocol 实现。
一致性验证 通过 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。

关键技巧

引入随机权重 $\gamma$，将多元集合压缩为单一多项式 $F(\vec{x}), G(\vec{x})$。
再采样随机挑战 $\beta$，将乘积等式转换为分式求和。
最终得到一个形如 $\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})} $$

定理（对数导数推导）：假设两个集合${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 $$

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 已成为现代零知识证明系统中 查表约束 的主流技术，典型应用包括：

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

6. 对比

编号	Relation 类型	数学形式或目标描述	归约方式	用途说明
①	ZeroCheck	验证 $f(\vec{x})=0$ 使得任意 $\vec{x} \in {0,1}^n$均成立	$\sum_{\vec{x} \in {0,1}^n} \hat{f}(\vec{x}) = 0$	约束消失性校验，如 vanishing 或 rational 检查
②	Multiset Equality Check	${f_0(\vec{x}), ..., f_k(\vec{x})} = {g_0(\vec{x}), ..., g_k(\vec{x})}$	转换为乘积等式 + sumcheck	验证集合相等，例如 Plonk wiring
③	Rational Relation	$\sum_{\vec{x}} \frac{p(\vec{x})}{q(\vec{x})} = v$	1. ZeroCheck on ( $q=0 \Rightarrow g=0$ ) <br> 2. sumcheck on ( $f q = g$ )	统一建模除法、压缩、多项式关系
④	Permutation Check	$(s{\text{id}}(\vec{x}), f(\vec{x})),(s\sigma(\vec{x}), g(\vec{x}))$	转换为乘积表达式 + rational + sumcheck	Plonk permutation argument
⑤	Lookup Check	$f(\vec{x}) \in \text{table} \subseteq \mathbb{F}$	转换为 multiset check 或 rational equality	Lookup argument 验证

结论

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

学分: 3
分类: Layer2
标签: zkVM zkMIPS

zkMIPS解读

Multivariate Sumcheck Protocol规约