KZG变体系列：第四部分，使用Gemini的多线性承诺 - ZK/SEC季刊

Variants of KZG · 第 4 部分，共 4 部分

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

Variants of KZG

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

在第二部分和第三部分中，我们研究了 PST 和 Zeromorph，它们基于多线性商恒等式构造了多线性多项式承诺方案。在这篇文章中，我们将探索一条基于拆分与折叠技术的不同路径。类似的技术也用于 FRI、Bulletproofs 和 Sumcheck。在本系列前几篇文章的基础上，我们将研究 Gemini。

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

拆分与折叠多线性多项式

考虑一个 $n$ 元多线性多项式 $f(X_0,\ldots,X_{n-1})$。假设我们要证明 $$ f(u_0,\ldots,u_{n-1})=v. $$ Gemini 通过一次对一个变量进行部分求值来归约这个多线性求值声明。验证者使用一个单变量恒等式来检查连续部分求值之间的一致性，我们接下来推导这个恒等式。

定义第 $i$ 个部分求值 $f^{(i)}$，即固定前 $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}) \quad\text{且}\quad f^{(n)}=f(u_0,\ldots,u_{n-1})=v. $$ 在第 $i$ 步，令 $X_{i-1}=u_{i-1}$，即可从 $f^{(i-1)}$ 得到 $f^{(i)}$。由于 $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$ 和 $1$ 得到的两个限制分别称为其偶数部分和奇数部分： $$ f_{\mathrm{even}}^{(i-1)}(X_i,\ldots,X_{n-1}):=f^{(i-1)}(0,X_i,\ldots,X_{n-1}),\qquad 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}$ 折叠这些部分，得到下一个部分求值。这就是该技术被称为拆分与折叠的原因。

上述恒等式仍然是在多变量多项式之间成立的，而 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}^{(i-1)}(X)$ 来表示 $\hat{f}{\mathrm{even}}^{(i-1)}$ 和 $\hat{f}{\mathrm{odd}}^{(i-1)}$，并将它们代入方程 (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}. $$ 在证明者对中间多项式进行承诺之后，验证者从 $F^*$ 中随机采样一个非零点 $r$，并使用在 $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. 采样求值挑战。 在收到所有中间承诺后，验证者从 $F^$ 中随机采样一个非零挑战 $r \xleftarrow{$} 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 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～