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

KZG 的变体 · 第 3 部分，共 3 部分

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

KZG 的变体

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

在第二部分中，我们研究了 PST，它直接利用多元公共参数来检查多线性商恒等式。PST 需要一种包含多个隐藏值交叉乘积的专用设置，并且其配对成本随变量数量线性增长。

Zeromorph 则将多线性商恒等式编码为单变量恒等式。这是一种通用构造，它利用加法同态的单变量 PCS 与次数检查协议来构建多线性 PCS。该构造适用于任意加法同态的单变量 PCS，但我们将重点讨论其与单变量 KZG 的实例化。

符号。 我们继续使用第二部分中的符号。我们用 $\mathbb{F}[X_0,\ldots,X_{n-1}]{\preceq 1}$ 表示 $n$ 元多线性多项式的集合，用 $\mathbb{F}[X]{<d}$ 表示次数至多为 $d-1$ 的单变量多项式的集合。单变量多项式用帽子符号标记，多线性多项式则不带帽子。对单变量多项式 $\hat{p}(X)=\sum_j p_j X^j$，记 $\hat{p}{<d}(X)=\sum{j=0}^{d-1} p_j X^j$，即 $\hat{p}(X)$ 截断至次数小于 $d$ 的部分。

Zeromorph 的出发点与 PST 相同。检查 $f(u_0,\ldots,u_{n-1})\stackrel{?}{=}v$ 等价于检查以下多线性商恒等式：

$$ f(X_0,\ldots,X_{n-1})-v \stackrel{?}{=} \sum_{k=0}^{n-1} (X_k-u_k)\cdot q_k(X_0,\ldots,X_{k-1}). $$

与我们在第二部分中通过 PST 在多元多项式上检查该恒等式不同，Zeromorph 是在单变量多项式上检查该恒等式。这需要一种从多线性多项式到单变量多项式的编码，我们接下来就来研究这种编码。

单变量化映射

从 $n$ 元多线性多项式到次数至多为 $2^n-1$ 的单变量多项式的线性映射定义如下：

$$ U_n:\mathbb{F}[X_0,\ldots,X_{n-1}]{\preceq 1}\to\mathbb{F}[X]{<2^n}. $$

对于多线性多项式 $f$，其单变量编码定义为

$$ \hat{f}(X)=U_n(f)(X)=\sum_{\vec{b}\in{0,1}^n} f(\vec{b})\cdot X^{\sum_{i=0}^{n-1} b_i 2^i}. $$

换句话说，$f$ 在布尔超立方体上的全部求值组成了单变量多项式的系数。例如当 $n=2$ 时，

$$ U_2(f)(X)=f(0,0)+f(1,0)X+f(0,1)X^2+f(1,1)X^3. $$

映射 $U_n$ 具有以下性质：

1. 线性性： 对于多线性多项式 $f,g$ 和标量 $\alpha,\beta\in\mathbb{F}$，

   $$ U_n(\alpha\cdot f+\beta\cdot g)(X)=\alpha\cdot U_n(f)(X)+\beta\cdot U_n(g)(X). $$

2. 一一对应： $f$ 的每个求值 $f(\vec{b})$ 都作为 $U_n(f)$ 的一个独立系数被存储。因此，读取 $U_n(f)$ 的系数即可恢复 $f$ 的全部求值。这些求值唯一确定多线性多项式 $f$，因而不会丢失任何信息。反过来，任何次数小于 $2^n$ 的单变量多项式的系数，都恰好对应唯一一个多线性多项式在布尔超立方体上的求值。具有这种性质的映射称为双射。

因此，$U_n$ 既是线性的又是双射的。同时具有这两种性质的映射称为线性同构。

在下一节中，我们将把这个单变量化映射 $U_n$ 应用于多线性商恒等式，得到单变量恒等式。

多线性到单变量恒等式

将单变量化映射 $U_n$ 应用于多线性商恒等式得到

$$ U_n(f(X_0,\ldots,X_{n-1})-v) \stackrel{?}{=} U_n\left(\sum_{k=0}^{n-1}(X_k-u_k)q_k(X_0,\ldots,X_{k-1})\right). $$

利用 $U_n$ 的线性性，

$$ U_n(f)-U_n(v) \stackrel{?}{=} \sum_{k=0}^{n-1}\left(U_n(X_kq_k)-u_k U_n(q_k)\right). $$

接下来我们看如何进一步分解 $U_n(v)$、$U_n(q_k)$ 和 $U_n(X_k\cdot q_k)$。

$v$ 的单变量化

考虑如下定义的常数 $n$ 元多线性多项式

$$ g(X_0,\ldots,X_{n-1})=v. $$

它与 $X_0,\ldots,X_{n-1}$ 无关，在 $n$ 维布尔超立方体上取值恒为 $v$。

下面借助表格来理解。表格前两列列出布尔超立方体上的点以及 $g$ 在各点的求值，最后两列则列出单变量编码中对应的单项式和系数。

多线性多项式		单变量编码
$X_{n-1},\ldots,X_2,X_1,X_0$	$g(X_0,X_1,X_2,\ldots,X_{n-1})$	单项式	系数
$0,\ldots,0,0,0$	$v$	$X^0$	$v$
$0,\ldots,0,0,1$	$v$	$X^1$	$v$
$0,\ldots,0,1,0$	$v$	$X^2$	$v$
$0,\ldots,0,1,1$	$v$	$X^3$	$v$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$1,\ldots,1,1,1$	$v$	$X^{2^n-1}$	$v$

因此，$v$ 的单变量化结果是

$$ U_n(v)=v\cdot X^0+v\cdot X^1+\ldots+v\cdot X^{2^n-1}=v\cdot(X^0+X^1+\ldots+X^{2^n-1})=v\cdot\Phi_n(X), $$

其中 $\Phi_n(X)=1+X+\cdots+X^{2^n-1}$。

$q_k$ 的单变量化

下面以 $k=2$ 为例来说明。$q_2(X_0,X_1)$ 是 $X_0,X_1$ 上的多线性多项式，与变量 $X_2,\ldots,X_{n-1}$ 无关。

假设 $q_2(X_0,X_1)$ 的求值如下：

$$ q_2(0,0)=a,\quad q_2(1,0)=b,\quad q_2(0,1)=c,\quad q_2(1,1)=d. $$

结果如下表所示：

多线性多项式		单变量编码
$X_{n-1},\ldots,X_2,X_1,X_0$	$q_2(X_0,X_1)$	单项式	系数
$0,\ldots,0,0,0$	$a$	$X^0$	$a$
$0,\ldots,0,0,1$	$b$	$X^1$	$b$
$0,\ldots,0,1,0$	$c$	$X^2$	$c$
$0,\ldots,0,1,1$	$d$	$X^3$	$d$
$0,\ldots,1,0,0$	$a$	$X^4$	$a$
$0,\ldots,1,0,1$	$b$	$X^5$	$b$
$0,\ldots,1,1,0$	$c$	$X^6$	$c$
$0,\ldots,1,1,1$	$d$	$X^7$	$d$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$1,\ldots,1,0,0$	$a$	$X^{2^n-4}$	$a$
$1,\ldots,1,0,1$	$b$	$X^{2^n-3}$	$b$
$1,\ldots,1,1,0$	$c$	$X^{2^n-2}$	$c$
$1,\ldots,1,1,1$	$d$	$X^{2^n-1}$	$d$

因此，$q_2$ 的单变量化结果是

$$ U_n(q_2)(X)=a+bX+cX^2+dX^3+aX^4+bX^5+cX^6+dX^7+\cdots+aX^{2^n-4}+bX^{2^n-3}+cX^{2^n-2}+dX^{2^n-1} $$

$$ =(a+bX+cX^2+dX^3)\cdot(1+X^4+X^8+\cdots+X^{2^n-4})=\hat{q}2(X)\cdot\Phi{n-2}(X^4). $$

这里 $\hat{q}2(X)=U_n(q_2){<4}(X)=a+bX+cX^2+dX^3$，即 $U_n(q_2)$ 截断至次数小于 $4$ 的部分。

对一般的 $k\in{0,\ldots,n-1}$，定义 $\hat{q}k(X)=U_n(q_k){<2^k}(X)$。$U_n(q_k)$ 的前 $2^k$ 个系数正是 $\hat{q}_k(X)$ 的系数，并且这组系数在 $U_n(q_k)$ 中重复 $2^{n-k}$ 次。因此，

$$ U_n(q_k)(X)=\hat{q}_k(X)\cdot(1+X^{2^k}+X^{2\cdot 2^k}+\cdots+X^{2^n-2^k})=\hat{q}k(X)\cdot\Phi{n-k}(X^{2^k}), $$

其中 $\Phi_n(X)=1+X+\cdots+X^{2^n-1}$。

$X_k\cdot q_k$ 的单变量化

仍以 $k=2$ 为例。由于 $q_2(X_0,X_1)$ 与 $X_2$ 无关，乘上 $X_2$ 之后，当 $X_2=0$ 时求值恒为零；当 $X_2=1$ 时，求值保持与 $q_2$ 相同。如下表所示：

多线性多项式		单变量编码
$X_{n-1},\ldots,X_2,X_1,X_0$	$X_2\cdot q_2(X_0,X_1)$	单项式	系数
$0,\ldots,0,0,0,0$	$0$	$X^0$	$0$
$0,\ldots,0,0,0,1$	$0$	$X^1$	$0$
$0,\ldots,0,0,1,0$	$0$	$X^2$	$0$
$0,\ldots,0,0,1,1$	$0$	$X^3$	$0$
$0,\ldots,0,1,0,0$	$a$	$X^4$	$a$
$0,\ldots,0,1,0,1$	$b$	$X^5$	$b$
$0,\ldots,0,1,1,0$	$c$	$X^6$	$c$
$0,\ldots,0,1,1,1$	$d$	$X^7$	$d$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$1,\ldots,1,0,0,0$	$0$	$X^{2^n-8}$	$0$
$1,\ldots,1,0,0,1$	$0$	$X^{2^n-7}$	$0$
$1,\ldots,1,0,1,0$	$0$	$X^{2^n-6}$	$0$
$1,\ldots,1,0,1,1$	$0$	$X^{2^n-5}$	$0$
$1,\ldots,1,1,0,0$	$a$	$X^{2^n-4}$	$a$
$1,\ldots,1,1,0,1$	$b$	$X^{2^n-3}$	$b$
$1,\ldots,1,1,1,0$	$c$	$X^{2^n-2}$	$c$
$1,\ldots,1,1,1,1$	$d$	$X^{2^n-1}$	$d$

因此，$X_2\cdot q_2$ 的单变量化结果是

$$ U_n(X_2\cdot q_2)(X)=aX^4+bX^5+cX^6+dX^7+aX^{12}+bX^{13}+cX^{14}+dX^{15}+\cdots+aX^{2^n-4}+bX^{2^n-3}+cX^{2^n-2}+dX^{2^n-1} $$

$$ =X^4\cdot\hat{q}_2(X)\cdot(1+X^8+X^{16}+\cdots+X^{2^n-8})=X^4\cdot\hat{q}2(X)\cdot\Phi{n-3}(X^8). $$

对一般的 $k\in{0,\ldots,n-1}$，乘上 $X_k$ 后，当 $X_k=0$ 时求值为零。$\hat{q}_k$ 的系数在 $X_k=1$ 时出现：从次数 $2^k$ 开始，之后每隔 $2^{k+1}$ 次出现一次。因此，

$$ U_n(X_kq_k)(X)=X^{2^k}\cdot\hat{q}k(X)\cdot\sum{j=0}^{2^{n-k-1}-1}X^{j2^{k+1}}=X^{2^k}\cdot\hat{q}k(X)\cdot\Phi{n-k-1}(X^{2^{k+1}}), $$

其中 $\Phi_n(X)=1+X+\cdots+X^{2^n-1}$，并且对于 $k=n-1$，$\Phi_0(X)=1$。

单变量恒等式

现在我们已经得到了 $U_n(v)$、$U_n(q_k)$ 和 $U_n(X_k\cdot q_k)$ 的分解。将它们代入下面的恒等式：

$$ U_n(f)-U_n(v) \stackrel{?}{=} \sum_{k=0}^{n-1}\left(U_n(X_k\cdot q_k)-u_k U_n(q_k)\right). $$

于是得到单变量恒等式

$$ \hat{f}(X)-v\cdot\Phi_n(X) \stackrel{?}{=} \sum_{k=0}^{n-1}\left(X^{2^k}\cdot\Phi_{n-k-1}(X^{2^{k+1}})-u_k\cdot\Phi_{n-k}(X^{2^k})\right)\cdot\hat{q}_k(X), $$

其中 $\hat{f}(X)=U_n(f)(X)$ 且 $\hat{q}k(X)=U_n(q_k){<2^k}(X)$。

注意

我们用 $\Phi_n(X)=1+X+\cdots+X^{2^n-1}$ 来表达上述恒等式，是因为验证者可以高效地在随机点处计算 $\Phi_n(X)$ 的值。由 $(X-1)\cdot\Phi_n(X)=X^{2^n}-1$ 可知，计算 $\Phi_n(x)=\frac{x^{2^n}-1}{x-1}$ 只需要 $n+1$ 次乘法、$2$ 次加法和 $1$ 次求逆。

定义以下单变量多项式：

$$ Z(X)=\hat{f}(X)-v\cdot\Phi_n(X)-\sum_{k=0}^{n-1}\left(X^{2^k}\cdot\Phi_{n-k-1}(X^{2^{k+1}})-u_k\cdot\Phi_{n-k}(X^{2^k})\right)\cdot\hat{q}_k(X). $$

根据 Schwartz-Zippel 引理，如果验证者检查到 $Z(\tau)=0$ 在随机采样的秘密设置值 $\tau$ 处成立，那么 $Z(X)$ 以高概率为零多项式，单变量恒等式随之成立。然而，验证者不能直接检查 $Z(\tau)\stackrel{?}{=}0$，因为 $\tau$ 是秘密的，验证者无法计算下面这个配对检查中需要的项：

$$ \tau^{2^k}\cdot\Phi_{n-k-1}(\tau^{2^{k+1}})-u_k\cdot\Phi_{n-k}(\tau^{2^k}). $$

为解决这个问题，验证者随机采样一个点 $x\in\mathbb{F}$，并让证明者证明 $Z(x)=0$。为此，证明者构造多项式 $Z_x(X)$：其中与各商多项式相乘的系数都在 $x$ 处求值。

$$ Z_x(X)=\hat{f}(X)-v\cdot\Phi_n(x)-\sum_{k=0}^{n-1}\left(x^{2^k}\cdot\Phi_{n-k-1}(x^{2^{k+1}})-u_k\cdot\Phi_{n-k}(x^{2^k})\right)\cdot\hat{q}_k(X). $$

注意这里 $Z(x)=Z_x(x)$，因此证明者只需证明 $Z_x(x)=0$。由于 $\hat{f}$ 和 $\hat{q}_k$ 的承诺是加法同态的，验证者可以用这些承诺直接计算出 $Z_x$ 的承诺。

然而，仅检查 $Z_x(x)\stackrel{?}{=}0$ 是不够的。KZG 打开只会验证 $Z_x(x)=0$，无法确保每个被承诺的多项式 $\hat{q}_k$ 具备在前 $k$ 个变量上编码多线性商所需的次数。缺少这一检查，证明者就可以使用次数大于 $2^k-1$ 的多项式。因此，协议还必须额外检查每个 $k$ 都满足 $\deg(\hat{q}_k)<2^k$。

乍看之下，协议似乎还应该检查 $\deg(\hat{f})<2^n$。不过，这个界可以由商多项式的次数界以及下面的多项式恒等式推出。

$$ \hat{f}(X)-v\cdot\Phi_n(X)\stackrel{?}{=}\sum_{k=0}^{n-1}\left(X^{2^k}\cdot\Phi_{n-k-1}(X^{2^{k+1}})-u_k\cdot\Phi_{n-k}(X^{2^k})\right)\cdot\hat{q}_k(X). $$

如果每个 $k$ 都满足 $\deg(\hat{q}_k)<2^k$，那么右侧每一项的次数至多为 $(2^n-2^k)+(2^k-1)=2^n-1$。由于 $\deg(\Phi_n)=2^n-1$，该恒等式自然蕴含 $\deg(\hat{f})<2^n$，因此无需再对 $\hat{f}$ 单独做次数检查。

至此，我们把声明 $f(u_0,\ldots,u_{n-1})=v$ 归约为以下检查：

• 恒等式检查：$Z_x(x)\stackrel{?}{=}0$；
• 次数检查：对每个 $k\in{0,\ldots,n-1}$，验证 $\deg(\hat{q}_k)<2^k$。

Zeromorph 对这 $n$ 个次数检查做批处理，将它们归约为一次同时强制次数界的 KZG 打开。下面我们研究这个带次数界的 KZG 打开协议。

带次数界的 KZG 打开

设 $N_{\max}$ 是 KZG 承诺方案支持的多项式次数的严格上界。因此，承诺密钥包含

$$ ck=([1]_1,[\tau]_1,[\tau^2]1,\ldots,[\tau^{N{\max}-1}]_1). $$

给定单变量多项式 $\hat{f}(X)$ 和一个声称的次数上界 $d$，目标是要证明

$$ \hat{f}(u)=v \quad\text{且}\quad \deg(\hat{f})\le d. $$

这个协议只是对单变量 KZG 的一个简单改动。我们从下面的 KZG 恒等式出发：

$$ \hat{f}(X)-v \stackrel{?}{=} \hat{q}(X)\cdot(X-u). $$

将两边乘以 $X^{N_{\max}-d}$ 得到

$$ (\hat{f}(X)-v)\cdot X^{N_{\max}-d} \stackrel{?}{=} \hat{q}(X)\cdot X^{N_{\max}-d}\cdot(X-u). $$

证明者对 $\hat{q}{\mathrm{shift}}(X)=\hat{q}(X)\cdot X^{N{\max}-d}$ 进行承诺，验证者则用双线性配对在秘密设置值 $\tau$ 处检查下面的恒等式：

$$ (\hat{f}(X)-v)\cdot X^{N_{\max}-d} \stackrel{?}{=} \hat{q}_{\mathrm{shift}}(X)\cdot(X-u). $$

注意 $\deg(\hat{q}{\mathrm{shift}})\le (d-1)+(N{\max}-d)=N_{\max}-1$，因此 $\hat{q}_{\mathrm{shift}}$ 可以用 KZG 承诺密钥来承诺。

端到端协议流程如下：

1. $P$ 向 $V$ 发送 $com_{\hat{f}}$。
2. $V$ 采样 $u\in\mathbb{F}^{\ast}$，并请求在 $u$ 处打开。
3. $P$ 发送求值 $v$ 和承诺 $cm=[\hat{q}_{\mathrm{shift}}(\tau)]1=[\hat{q}(\tau)\tau^{N{\max}-d}]_1$。
4. 当且仅当 $e(cm,[\tau]_2-u[1]2)\stackrel{?}{=}e(com{\hat{f}}-v[1]1,[\tau^{N{\max}-d}]_2)$ 时，$V$ 接受。

注意，验证者密钥中除了 $[1]_2$ 和 $[\tau]2$ 之外，还包含更高次幂项 $[\tau^{N{\max}-d}]_2$。

该协议只能在 $u\ne 0$ 时强制保证 $\hat{f}(u)=v$，因此验证者从 $\mathbb{F}^{\ast}$ 中采样 $u$。条件 $u\ne 0$ 至关重要：如果 $u=0$，$X-u=X$ 就会与 $X^{N_{\max}-d}$ 共享因子，不诚实的证明者便可以声称任意值 $v$，并令

$$ \hat{q}{\mathrm{shift}}(X)=(\hat{f}(X)-v)\cdot X^{N{\max}-d-1}. $$

当 $\deg(\hat{f})\le d$ 时，上面这个多项式的次数至多为 $N_{\max}-1$，并且满足恒等式

$$ \hat{q}{\mathrm{shift}}(X)\cdot X \stackrel{?}{=} (\hat{f}(X)-v)\cdot X^{N{\max}-d} $$

即使 $\hat{f}(0)\ne v$，该恒等式依然成立。因此，配对检查可能会接受 $u=0$ 处不正确的求值声明。

该协议同时还能强制保证 $\deg(\hat{f})\le d$。如果 $\deg(\hat{f})>d$，则 $\deg(\hat{q})\ge d$，于是

$$ \deg(\hat{q}{\mathrm{shift}})\ge d+(N{\max}-d)=N_{\max}. $$

这样一来，证明者无法对 $\hat{q}{\mathrm{shift}}$ 做出承诺，因为承诺密钥只支持次数至多为 $N{\max}-1$ 的多项式。

接下来我们研究批处理次数检查协议。

批处理次数检查协议

对于单变量多项式 $\hat{q}0(X),\ldots,\hat{q}{n-1}(X)$，目标是证明

$$ \deg(\hat{q}_k)\le d_k,\quad\text{其中 } d_k=2^k-1,\quad k\in{0,\ldots,n-1}. $$

基本思路是：先把每个多项式做移位，使移位后的多项式具有相同的次数界，再用一个随机挑战把它们组合起来，最后对这个组合多项式做单一次数检查。

设 $d^{\ast}\ge\max_k d_k$，$y\in\mathbb{F}$ 是随机挑战。对于 $\deg(\hat{q}_k)\le d_k$ 的 $\hat{q}_k$，移位后的多项式为

$$ X^{d^{\ast}-d_k+1}\cdot\hat{q}_k(X). $$

注意，若 $\deg(\hat{q}_k)\le d_k$，对应的移位多项式次数至多为 $d^{\ast}+1$。我们取这些移位多项式的随机线性组合：

$$ \hat{Q}(X)=\sum_{k=0}^{n-1} y^k\cdot X^{d^{\ast}-d_k+1}\cdot\hat{q}_k(X). $$

如果每个 $\hat{q}_k$ 都满足其次数界，那么 $\deg(\hat{Q})\le d^{\ast}+1$。反之，只要某个 $\hat{q}_k$ 违反其次数界，以关于随机挑战 $y$ 的高概率就会有 $\deg(\hat{Q})>d^{\ast}+1$。于是，$n$ 个次数检查归约为下面两个检查：

• 对 $\hat{Q}$ 做单一次数检查：$\deg(\hat{Q})\le d^{\ast}+1$；
• 检查 $\hat{Q}$ 的构造是否正确，即其承诺与各 $\hat{q}_k$ 的承诺一致。

验证者随机采样一个点 $x\in\mathbb{F}$，随后证明者计算

$$ \zeta_x(X)=\hat{Q}(X)-\sum_{k=0}^{n-1} y^k\cdot x^{d^{\ast}-d_k+1}\cdot\hat{q}_k(X). $$

接下来证明者要证明两件事：

• $\deg(\zeta_x)\le d^{\ast}+1$：由此证明 $\deg(\hat{Q})\le d^{\ast}+1$，进而推出每个 $\deg(\hat{q}_k)\le d_k$。
• $\zeta_x(x)=0$：由此证明 $\hat{Q}$ 的承诺与各 $\hat{q}_k$ 的承诺一致。

至此，声明 $f(u_0,\ldots,u_{n-1})=v$ 被归约为以下检查：

• 恒等式检查：$Z_x(x)\stackrel{?}{=}0$；
• 求值与次数检查：$\zeta_x(x)\stackrel{?}{=}0$，且 $\deg(\zeta_x)\le d^{\ast}+1$。

在最终的 Zeromorph 打开协议中，取 $d^{\ast}=2^n-2$，这样 $\zeta_x$ 和 $Z_x$ 就具有相同的次数界 $2^n-1$。随后验证者采样随机挑战 $z\in\mathbb{F}$，将这两个多项式组合起来：

$$ \hat{H}_x(X)=\zeta_x(X)+z\cdot Z_x(X). $$

最后，证明者和验证者运行带次数界的 KZG 打开协议，证明 $\hat{H}_x(x)=0$ 且 $\deg(\hat{H}_x)\le 2^n-1$。以关于 $z$ 的高概率，这一次调用同时保证了两个求值检查以及所需的次数界。

端到端打开协议

端到端打开协议的具体流程如下：

1. $P$ 计算 $f$ 的单变量编码 $\hat{f}(X)=U_n(f)(X)$，并向 $V$ 发送承诺 $C=[\hat{f}(\tau)]_1$。

2. $V$ 采样 $(u_0,\ldots,u_{n-1})\leftarrow_{$}\mathbb{F}^n$ 并将其发送给 $P$。

3. $P$ 计算多线性商多项式 $q_0,\ldots,q_{n-1}$ 及其单变量编码 $\hat{q}k(X)=U_n(q_k){<2^k}(X)$，并向 $V$ 发送承诺 $C_k=[\hat{q}_k(\tau)]_1$（$k\in{0,\ldots,n-1}$）以及求值 $v$。

4. $V$ 采样随机挑战 $y\leftarrow_{$}\mathbb{F}$（用于批处理各个次数检查），并将其发送给 $P$。

5. $P$ 计算移位后的随机线性组合

   $$ \hat{Q}(X)=\sum_{k=0}^{n-1} y^k X^{2^n-d_k-1}\hat{q}_k(X) $$

   并向 $V$ 发送其承诺 $C_{\hat{Q}}=[\hat{Q}(\tau)]_1$。

6. $V$ 采样 $x\leftarrow_{$}\mathbb{F}^{\ast}$（非零打开点）和 $z\leftarrow_{$}\mathbb{F}$（用于合并 $Z_x$ 与 $\zeta_x$），并把两个挑战发送给 $P$。利用 KZG 承诺的同态性质，$V$ 按如下方式计算 $Z_x$ 和 $\zeta_x$ 的承诺：

   $$ C_{Z_x}=C-v\cdot\Phi_n(x)[1]1-\sum{k=0}^{n-1}\left(x^{2^k}\Phi_{n-k-1}(x^{2^{k+1}})-u_k\Phi_{n-k}(x^{2^k})\right)\cdot C_k, $$

   $$ C_{\zeta_x}=C_{\hat{Q}}-\sum_{k=0}^{n-1}y^k x^{2^n-d_k-1}C_k. $$

   然后 $V$ 将两个承诺组合为 $C_{\hat{H}x}=C{\zeta_x}+z\cdot C_{Z_x}$。

7. $P$ 计算相应的多项式 $Z_x$ 和 $\zeta_x$：

   $$ Z_x(X)=\hat{f}(X)-v\Phi_n(x)-\sum_{k=0}^{n-1}\left(x^{2^k}\cdot\Phi_{n-k-1}(x^{2^{k+1}})-u_k\cdot\Phi_{n-k}(x^{2^k})\right)\cdot\hat{q}_k(X), $$

   $$ \zeta_x(X)=\hat{Q}(X)-\sum_{k=0}^{n-1}y^k x^{2^n-d_k-1}\hat{q}_k(X). $$

   然后 $P$ 将两个多项式组合为

   $$ \hat{H}_x(X)=\zeta_x(X)+z\cdot Z_x(X). $$

8. $P$ 与 $V$ 在 $C_{\hat{H}_x}$ 上运行带次数界的 KZG 打开协议：打开点为 $x$，声明的求值为 $0$，次数界为 $2^n-1$。该协议证明 $\hat{H}_x(x)=0$ 且 $\deg(\hat{H}_x)\le 2^n-1$。

接下来我们分析打开协议的复杂度。

打开协议的复杂度

对于拥有 $2^n$ 个系数的 $n$ 元多线性多项式，打开协议的复杂度分析如下。

• 证明大小： 证明者需要发送 $n$ 个商承诺 $C_0,\ldots,C_{n-1}$、承诺 $C_{\hat{Q}}$ 以及最终的打开证明 $\pi$。因此，证明由 $\mathbb{G}_1$ 中的 $n+2$ 个元素组成。若每个 $\mathbb{G}_1$ 元素用两个域元素来编码，则证明大小为 $O(n)$ 个域元素。
• 证明者成本： 证明者的主要成本包括以下几项：
  • 计算并承诺商多项式： 如第二部分中 PST 的复杂度分析所示，计算商多项式以及声称的求值 $v=f(\vec{u})$ 需要 $O(2^n)$ 次域运算。对 $f$ 做承诺需要规模为 $2^n$ 的 MSM，而对所有商多项式做承诺所需的 MSM 总规模为 $2^n-1$。单变量编码 $\hat{f}$ 和 $\hat{q}_k$ 也适用同样的界，因为它们包含相同数量的系数。
  • 计算批处理多项式： 商编码总共包含 $2^n-1$ 个系数，每个批处理或除法步骤都需要线性扫描一遍至多 $2^n$ 个系数。因此，计算 $\hat{Q}$、$Z_x$、$\zeta_x$、$\hat{H}_x$ 以及最终的打开商多项式，共需要 $O(2^n)$ 次域运算。
  • 对 $\hat{Q}$ 做承诺： 每个移位项 $X^{2^n-d_k-1}\hat{q}k(X)$ 的最高次数至多为 $2^n-1$。因此，计算 $C{\hat{Q}}$ 至多需要 $2^n-1$ 次群标量乘法。
  • 带次数界的 KZG 中的商承诺计算： $\hat{H}_x$ 的次数至多为 $2^n-1$，因此它的打开商多项式至多有 $2^n-1$ 个系数。于是，计算移位后的承诺 $\pi$ 需要规模至多为 $2^n-1$ 的 MSM。
• 验证者成本： 验证者需要接收证明者发来的商承诺 $C_0,\ldots,C_{n-1}$，并计算构造 $C_{Z_x}$ 和 $C_{\zeta_x}$ 所需的域元素，包括 $x$、$y$ 的各个幂次以及 $\Phi_i$ 的取值，这需要 $O(n)$ 次域运算。然后，验证者把 $C_{Z_x}$ 和 $C_{\zeta_x}$ 分别构造为所接收承诺的线性组合，需要 $O(n)$ 次群标量乘法。此外，最终的验证检查包含两个配对项。

等价地，若不计原始承诺 $C$ 的成本，打开协议的开销可总结如下：

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

结论

在上一部分和这一部分中，我们研究了两种基于商的方法，将 KZG 扩展到多线性多项式：PST 直接使用多元公共参数检查多线性商恒等式，而 Zeromorph 则把同一恒等式编码为单变量恒等式，并通过次数检查来强制所需的商结构。

在下一部分中，我们将研究基于折叠的方法。这类构造会反复折叠多线性求值声明，直到可以用单变量 KZG 完成验证。

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