KZG变体：第四部分，基于Gemini的多线性承诺 - ZK/SEC季刊

KZG 变体 · 第 4 部分，共 4 部分

KZG 变体：第四部分，使用 Gemini 的多线性承诺

KZG 变体

1. 1 KZG 变体：第一部分，单变量
2. 2 KZG 变体：第二部分，使用 PST 的多线性承诺
3. 3 KZG 变体：第三部分，使用 Zeromorph 的多线性承诺
4. 4 KZG 变体：第四部分，使用 Gemini 的多线性承诺

在第二部分和第三部分中，我们研究了 PST 和 Zeromorph，它们都是基于多线性商恒等式来构造多线性多项式承诺方案的。在这篇文章中，我们将探索一条不同的路径，即基于 split-and-fold 的技术。类似的技术也用于 FRI、Bulletproofs 和 Sumcheck。结合本系列前几篇文章的思想，我们将研究 Gemini。

符号说明。 我们继续使用第三部分中的符号。我们用 $\mathbb{F}[X_0,\ldots,X_{n-1}]^{\preceq 1}$ 表示 $n$ 元多线性多项式的集合，用 $\mathbb{F}[X]{<d}$ 表示次数至多为 $d-1$ 的单变量多项式的集合。单变量多项式用帽子符号表示，而多线性多项式不带帽子。我们用 $\vec{u}=(u_0,\ldots,u{n-1})$ 表示 $\mathbb{F}^n$ 中的一个点，用 $U_m$ 表示 $m$ 元多线性多项式的单变量化映射。

下面我们研究 Gemini 中使用的 split-and-fold 技术。

拆分与折叠多线性多项式

考虑一个 $n$ 元多线性多项式 $f(X_0,\ldots,X_{n-1})$。假设我们要证明

$$ f(u_0,\ldots,u_{n-1})=v. $$

Gemini 通过一次对一个变量进行部分求值来归约这个多线性求值声明。验证者使用一个单变量恒等式来检查相邻部分求值之间的一致性，我们接下来推导这个恒等式。

通过固定前 $i$ 个变量，定义第 $i$ 个部分求值 $f^{(i)}$：

$$ f^{(i)}(X_i,\ldots,X_{n-1})=f(u_0,\ldots,u_{i-1},X_i,\ldots,X_{n-1}). $$

这里，$f^{(i)}$ 是关于 $X_i,\ldots,X_{n-1}$ 的多线性多项式，并且与 $X_0,\ldots,X_{i-1}$ 无关。

因此，

$$ f^{(0)}(X_0,\ldots,X_{n-1})=f(X_0,\ldots,X_{n-1}) $$

且

$$ f^{(n)}=f(u_0,\ldots,u_{n-1})=v. $$

在第 $i$ 步，$f^{(i)}$ 由 $f^{(i-1)}$ 代入 $X_{i-1}=u_{i-1}$ 得到。由于 $f^{(i-1)}$ 关于 $X_{i-1}$ 是线性的，它由在 $X_{i-1}=0$ 和 $X_{i-1}=1$ 处的求值决定。因此，

$$ f^{(i-1)}(X_{i-1},X_i,\ldots,X_{n-1})=(1-X_{i-1})\cdot f^{(i-1)}(0,X_i,\ldots,X_{n-1})+X_{i-1}\cdot f^{(i-1)}(1,X_i,\ldots,X_{n-1}). $$

令 $X_{i-1}=u_{i-1}$，即可得到下一个部分求值：

$$ f^{(i)}(X_i,\ldots,X_{n-1})=f^{(i-1)}(u_{i-1},X_i,\ldots,X_{n-1})=(1-u_{i-1})\cdot f^{(i-1)}(0,X_i,\ldots,X_{n-1})+u_{i-1}\cdot f^{(i-1)}(1,X_i,\ldots,X_{n-1}). $$

我们把 $f^{(i-1)}$ 在 $X_{i-1}=0$ 和 $X_{i-1}=1$ 处的两个限制分别称为其偶数部分和奇数部分：

$$ f_{\mathrm{even}}^{(i-1)}(X_i,\ldots,X_{n-1}):=f^{(i-1)}(0,X_i,\ldots,X_{n-1}),\quad f_{\mathrm{odd}}^{(i-1)}(X_i,\ldots,X_{n-1}):=f^{(i-1)}(1,X_i,\ldots,X_{n-1}). $$

等价地，若 $f^{(i-1)}$ 用其在布尔超立方体上的求值来表示，则 $f_{\mathrm{even}}^{(i-1)}$ 由偶数索引的求值组成，$f_{\mathrm{odd}}^{(i-1)}$ 由奇数索引的求值组成。偶数索引对应 $X_{i-1}=0$，奇数索引对应 $X_{i-1}=1$。使用这个符号，下一个部分求值为

$$ f^{(i)}(X_i,\ldots,X_{n-1})=(1-u_{i-1})\cdot f_{\mathrm{even}}^{(i-1)}(X_i,\ldots,X_{n-1})+u_{i-1}\cdot f_{\mathrm{odd}}^{(i-1)}(X_i,\ldots,X_{n-1}) $$

注意

每个部分求值步骤首先将上一步的求值拆分为偶数部分和奇数部分，然后使用当前的求值点 $u_{i-1}$ 折叠这些部分，得到下一个部分求值。这就是为什么这种技术被称为 split-and-fold。

上面的恒等式仍然是在多变量多项式之间成立的，而 Gemini 使用单变量 KZG 承诺。为了将折叠恒等式表示成可以使用单变量 KZG 承诺的形式，我们应用第三部分中的单变量化映射。

由于单变量化映射 $U_{n-i}$ 是线性的，我们得到：

$$ U_{n-i}(f^{(i)})=(1-u_{i-1})\cdot U_{n-i}(f_{\mathrm{even}}^{(i-1)})+u_{i-1}\cdot U_{n-i}(f_{\mathrm{odd}}^{(i-1)}) \tag{1} $$

$$ \hat{f}^{(i)}(X)=(1-u_{i-1})\cdot \hat{f}{\mathrm{even}}^{(i-1)}(X)+u{i-1}\cdot \hat{f}_{\mathrm{odd}}^{(i-1)}(X) $$

其中：

• $\hat{f}^{(i)}(X)=U_{n-i}(f^{(i)})$ 是单变量多项式，其系数是 $f^{(i)}$ 在剩余布尔超立方体 ${0,1}^{n-i}$ 上的求值；
• $\hat{f}{\mathrm{even}}^{(i-1)}(X)=U{n-i}(f_{\mathrm{even}}^{(i-1)})$ 是单变量多项式，其系数是 $f^{(i-1)}$ 的偶数索引求值，对应 $X_{i-1}=0$；
• $\hat{f}{\mathrm{odd}}^{(i-1)}(X)=U{n-i}(f_{\mathrm{odd}}^{(i-1)})$ 是单变量多项式，其系数是 $f^{(i-1)}$ 的奇数索引求值，对应 $X_{i-1}=1$。

这正是多线性部分求值恒等式的单变量形式。剩下的唯一问题是，证明者没有承诺 $\hat{f}{\mathrm{even}}^{(i-1)}$ 和 $\hat{f}{\mathrm{odd}}^{(i-1)}$。证明者只对前一步完整部分求值的单变量化结果 $\hat{f}^{(i-1)}(X)$ 进行了承诺。因此，下面我们将 $\hat{f}{\mathrm{even}}^{(i-1)}$ 和 $\hat{f}{\mathrm{odd}}^{(i-1)}$ 用 $\hat{f}^{(i-1)}(X)$ 表示出来，再代入方程 (1)。

根据定义，$\hat{f}^{(i-1)}(X)$ 的系数是 $f^{(i-1)}$ 的所有求值，其中偶数索引和奇数索引的求值交替出现。假设

$$ \hat{f}_{\mathrm{even}}^{(i-1)}(X)=e_0+e_1X+e_2X^2+\cdots $$

且

$$ \hat{f}_{\mathrm{odd}}^{(i-1)}(X)=o_0+o_1X+o_2X^2+\cdots. $$

那么完整的单变量多项式的系数会交错为

$$ \hat{f}^{(i-1)}(X)=e_0+o_0X+e_1X^2+o_1X^3+e_2X^4+o_2X^5+\cdots. $$

将 $X^2$ 代入 $\hat{f}{\mathrm{even}}^{(i-1)}$ 会将其系数置于 $X$ 的偶数次幂上。类似地，将 $X^2$ 代入 $\hat{f}{\mathrm{odd}}^{(i-1)}$ 并乘以 $X$ 会将其系数置于奇数次幂上。因此，这些多项式之间的关系为

$$ \hat{f}^{(i-1)}(X)=\hat{f}{\mathrm{even}}^{(i-1)}(X^2)+X\cdot \hat{f}{\mathrm{odd}}^{(i-1)}(X^2). $$

将上述关系中的 $X$ 替换为 $-X$，得到

$$ \hat{f}^{(i-1)}(-X)=\hat{f}{\mathrm{even}}^{(i-1)}(X^2)-X\cdot \hat{f}{\mathrm{odd}}^{(i-1)}(X^2). $$

将 $X$ 和 $-X$ 处的关系分别相加、相减，得到

$$ \hat{f}_{\mathrm{even}}^{(i-1)}(X^2)=\frac{\hat{f}^{(i-1)}(X)+\hat{f}^{(i-1)}(-X)}{2}, $$

和

$$ \hat{f}_{\mathrm{odd}}^{(i-1)}(X^2)=\frac{\hat{f}^{(i-1)}(X)-\hat{f}^{(i-1)}(-X)}{2X}. $$

在 $X^2$ 处对方程 (1) 中的单变量折叠恒等式求值，得到

$$ \hat{f}^{(i)}(X^2)=(1-u_{i-1})\cdot \hat{f}{\mathrm{even}}^{(i-1)}(X^2)+u{i-1}\cdot \hat{f}_{\mathrm{odd}}^{(i-1)}(X^2). $$

将偶数部分和奇数部分代入该方程，得到以下对 $X\neq 0$ 成立的恒等式：

$$ \hat{f}^{(i)}(X^2)=(1-u_{i-1})\frac{\hat{f}^{(i-1)}(X)+\hat{f}^{(i-1)}(-X)}{2}+u_{i-1}\frac{\hat{f}^{(i-1)}(X)-\hat{f}^{(i-1)}(-X)}{2X}. $$

在证明者完成对中间多项式的承诺后，验证者随机采样一个非零点 $r\in\mathbb{F}^*$，并利用在 $r$、$-r$ 和 $r^2$ 处的声称求值，检查以下对每个 $i\in{1,\ldots,n}$ 都成立的恒等式：

$$ \hat{f}^{(i)}(r^2)\stackrel{?}{=}(1-u_{i-1})\frac{\hat{f}^{(i-1)}(r)+\hat{f}^{(i-1)}(-r)}{2}+u_{i-1}\frac{\hat{f}^{(i-1)}(r)-\hat{f}^{(i-1)}(-r)}{2r}. $$

注意

这里介绍的结构是 HyperKZG，它是 Gemini 的一个变体。Gemini 以系数形式表示多线性多项式，而 HyperKZG 直接以点求值形式工作。这通常更实用，因为 SNARK 协议中的 witness 通常被编码为布尔超立方体上的求值。

若使用 Gemini 的这种表示形式，证明者需要通过 FFT 将布尔超立方体上的求值转换为多线性多项式的系数。这需要 $O(N\log N)$ 时间，其中 $N=2^n$。HyperKZG 通过直接使用点求值表示来避免这种转换。

下面来看打开协议的最终构造。

端到端协议

公共输入是 $\hat{f}^{(0)}=U_n(f)$ 的承诺 $C$，求值点 $\vec{u}=(u_0,\ldots,u_{n-1})$ 以及声称的求值 $v$。证明者的 witness 是多线性多项式 $f$。完整的端到端协议如下：

1. 计算并承诺中间折叠。 证明者设置 $f^{(0)}=f$，并对每个 $i\in{1,\ldots,n}$ 计算 $f^{(i)}(X_i,\ldots,X_{n-1})=(1-u_{i-1})\cdot f_{\mathrm{even}}^{(i-1)}(X_i,\ldots,X_{n-1})+u_{i-1}\cdot f_{\mathrm{odd}}^{(i-1)}(X_i,\ldots,X_{n-1})$。对每个 $i\in{1,\ldots,n-1}$，它计算单变量编码 $\hat{f}^{(i)}(X)=U_{n-i}(f^{(i)})(X)$，并将其对应的单变量 KZG 承诺 $C_i=\mathrm{KZG.Com}(\hat{f}^{(i)})=[\hat{f}^{(i)}(\tau)]_1$ 发送给验证者。不需要对 $\hat{f}^{(n)}$ 进行承诺，因为 $\hat{f}^{(n)}=v$ 是声称的常量求值。我们将原始的 KZG 承诺记为 $C_0=C$。

2. 采样求值挑战。 在收到所有中间承诺后，验证者采样一个随机的非零挑战 $r \xleftarrow{$} \mathbb{F}^*$ 并将其发送给证明者。

3. 对折叠多项式求值并证明打开。 对于每个 $i\in{1,\ldots,n}$，证明者计算 $a^{(i)}=\hat{f}^{(i)}(r^2)$，其中 $\hat{f}^{(n)}(X)=v$。对于每个 $i\in{0,\ldots,n-1}$，它还计算 $b_+^{(i)}=\hat{f}^{(i)}(r)$ 和 $b_-^{(i)}=\hat{f}^{(i)}(-r)$。证明者将这些声称的求值全部发送给验证者。同时，它发送一个批量的单变量 KZG 打开证明，用于声明 $\hat{f}^{(i)}(r)=b_+^{(i)}$ 和 $\hat{f}^{(i)}(-r)=b_-^{(i)}$，$i\in{0,\ldots,n-1}$，以及 $\hat{f}^{(i)}(r^2)=a^{(i)}$，$i\in{1,\ldots,n-1}$。这些声明通过第一部分中的批量单变量 KZG 打开协议组合在一起。

4. 检查折叠关系。 对于每个 $i\in{1,\ldots,n}$，验证者检查

$$ a^{(i)}\stackrel{?}{=}(1-u_{i-1})\frac{b_+^{(i-1)}+b_-^{(i-1)}}{2}+u_{i-1}\frac{b_+^{(i-1)}-b_-^{(i-1)}}{2r}. $$

它还检查批量 KZG 打开证明是否有效，以及最终折叠是否等于声称的多线性求值：$a^{(n)}\stackrel{?}{=}v$。

每个通过检查的折叠关系都会将一个中间多项式的求值与上一步多项式的求值联系起来。因此，最终检查 $a^{(n)}=v$ 将原始承诺 $C$ 与声称的求值 $f(\vec{u})=v$ 联系起来。下面来看协议的效率。

协议的复杂度

对于一个具有 $2^n$ 个系数的 $n$ 元多线性多项式，打开协议的主要成本如下：

• 证明大小： 证明者发送 $n-1$ 个中间承诺、$O(n)$ 个声称的求值以及一个常数大小的批量 KZG 打开证明。假设每个群元素由常数个域元素编码，则总证明大小为 $O(n)$ 个域元素。

• 证明者成本： 中间折叠的大小构成几何级数 $2^{n-1}+2^{n-2}+\cdots+1=O(2^n)$。因此，计算折叠和批量打开证明需要 $O(2^n)$ 次域运算。承诺中间折叠和计算批量 KZG 证明总共需要 $O(2^n)$ 次群标量乘法。

• 验证者成本： 检查 $n$ 个折叠关系需要 $O(n)$ 次域运算。为了验证批量 KZG 打开，验证者构造原始承诺和 $n-1$ 个中间承诺的线性组合。这是一个大小为 $n$ 的 MSM，需要 $O(n)$ 次群标量乘法。最终的 KZG 检查使用两个配对项。

等价地，打开成本可以总结如下：

组件	成本
证明大小	$O(n)$ 个域元素
证明者工作量	$O(2^n)$ 次域运算，$O(2^n)$ 次群标量乘法
验证者工作量	$O(n)$ 次域运算，$O(n)$ 次群标量乘法，两个配对项

结论

Gemini 通过一次对一个变量进行部分求值来归约多线性求值声明。证明者承诺每一个中间折叠，这使得证明者工作量为线性，打开证明的大小也随变量数量线性增长。

在下一部分中，我们将研究 Mercury 如何一次折叠多个变量，并将这个打开证明归约到常数大小。

• 原文链接： blog.zksecurity.xyz/post...
• 鸿途知科网 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～