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

Variants of KZG · 共 4 部分中的第 3 部分

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

Variants of KZG

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

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

Zeromorph 则把多线性商恒等式编码为单变量恒等式。它是一个通用构造，使用加法同态的单变量 PCS 和一个次数检查协议来构建多线性 PCS。它可以与任何加法同态的单变量 PCS 配合使用，但我们将专门考察它与单变量 KZG 的实例化。

记号。 我们继续使用第二部分中的记号。我们用 $F[X_0,\ldots,X_{n-1}]{\preceq 1}$ 表示 $n$ 元多线性多项式的集合，用 $F[X]{<d}$ 表示次数至多为 $d-1$ 的单变量多项式的集合。单变量多项式用带帽符号表示，而多线性多项式不带帽。对于单变量多项式 $\hat{p}(X)=\sum_j p_jX^j$，我们写 $\hat{p}{<d}(X)=\sum{j=0}^{d-1} p_jX^j$ 表示其截断到次数小于 $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$ 的单变量多项式的线性映射定义如下：

$$ \mathrm{Un}\colon F[X_0,\ldots,X_{n-1}]{\preceq 1}\to F[X]{<2^n}. $$

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

$$ \hat{f}(X)=\mathrm{Un}(f)(X)=\sum_{\vec{b}\in{0,1}^n} f(\vec{b})\cdot X^{\sum_{i=0}^{n-1} b_i2^i}. $$

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

$$ \mathrm{U}_2(f)(X)=f(0,0)+f(1,0)X+f(0,1)X^2+f(1,1)X^3. $$

映射 $\mathrm{Un}$ 具有以下性质：

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

$$ \mathrm{Un}(\alpha\cdot f+\beta\cdot g)(X)=\alpha\cdot \mathrm{Un}(f)(X)+\beta\cdot \mathrm{Un}(g)(X). $$

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

因此，$\mathrm{Un}$ 是线性和双射的。同时具有这两种性质的映射称为线性同构。

在下一节中，我们将把这个单变量化映射 $\mathrm{Un}$ 应用到多线性商恒等式上，得到单变量恒等式。

从多线性到单变量的恒等式

将单变量化映射 $\mathrm{Un}$ 应用到多线性商恒等式上，得到

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

利用 $\mathrm{Un}$ 的线性性，

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

我们现在来看如何进一步分解 $\mathrm{Un}(v)$、$\mathrm{Un}(q_k)$ 和 $\mathrm{Un}(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$ 的单变量化为

$$ \mathrm{Un}(v)=v\cdot X^0+v\cdot X^1+\cdots+v\cdot X^{2^n-1} =v\cdot(1+X+\cdots+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$ 的单变量化为

$$ \begin{aligned} \mathrm{Un}(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). \end{aligned} $$

这里，$\hat{q}2(X)=\mathrm{Un}(q_2){<4}(X)=a+bX+cX^2+dX^3$ 是 $\mathrm{Un}(q_2)$ 截断到次数小于 $4$ 的项。

对于一般的 $k\in{0,\ldots,n-1}$，定义 $\hat{q}k(X)=\mathrm{Un}(q_k){<2^k}(X)$。$\mathrm{Un}(q_k)$ 以 $\hat{q}_k(X)$ 的 $2^k$ 个系数开头。这个系数块在 $\mathrm{Un}(q_k)$ 中重复 $2^{n-k}$ 次。因此，

$$ \mathrm{Un}(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$ 的单变量化为

$$ \begin{aligned} \mathrm{Un}(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). \end{aligned} $$

对于一般的 $k\in{0,\ldots,n-1}$，乘以 $X_k$ 使得当 $X_k=0$ 时求值为零。$\hat{q}_k$ 的系数出现在 $X_k=1$ 时，从次数 $2^k$ 开始，并且每 $2^{k+1}$ 次幂重复一次。因此，

$$ \mathrm{Un}(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$。

单变量恒等式

现在我们得到了 $\mathrm{Un}(v)$、$\mathrm{Un}(q_k)$ 和 $\mathrm{Un}(X_k\cdot q_k)$ 的分解式，将它们代入以下恒等式：

$$ \mathrm{Un}(f)-\mathrm{Un}(v)\stackrel{?}{=}\sum_{k=0}^{n-1}\left(\mathrm{Un}(X_k\cdot q_k)-u_k\mathrm{Un}(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)=\mathrm{Un}(f)(X)$ 且 $\hat{q}k(X)=\mathrm{Un}(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)=(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 引理，如果验证者在随机采样的秘密设置值 $\tau$ 处检查 $Z(\tau)=0$，那么以高概率 $Z(X)$ 是零多项式，并且单变量恒等式成立。然而，验证者不能直接检查 $Z(\tau)\stackrel{?}{=}0$，因为 $\tau$ 是秘密的，而且验证者无法计算以下用于配对检查的项：

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

为了解决这个问题，验证者采样一个随机点 $x\in 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$；
• $n$ 个次数检查 $\deg(\hat{q}_k)<2^k$，其中 $k\in{0,\ldots,n-1}$。

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

带次数界的 KZG 打开

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

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

给定一个单变量多项式 $\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 发送 $\mathsf{com}_{\hat{f}}$ 给 V。
2. V 采样 $u\in F^*$ 并请求在 $u$ 处打开。
3. P 发送求值 $v$ 和承诺 $\mathsf{cm}=[\hat{q}_{\mathrm{shift}}(\tau)]1=[\hat{q}(\tau)\tau^{N{\max}-d}]_1$。
4. 当且仅当

$$ e(\mathsf{cm},[\tau]_2-u[1]2)\stackrel{?}{=}e(\mathsf{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$。因此，验证者从 $F^*$ 中采样 $u$。条件 $u\ne0$ 至关重要：如果 $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,\ k\in{0,\ldots,n-1}. $$

其思想是移位每个多项式，使得移位后的多项式具有相同的次数界，然后使用随机挑战将它们组合起来。然后我们可以对这个组合后的多项式运行次数检查。

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

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

注意，如果 $\deg(\hat{q}k)\le d_k$，那么对应的移位后多项式次数至多为 $d*+1$。我们对这些移位后的多项式取随机线性组合：

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

如果每个 $\hat{q}k$ 都满足其次数界，那么 $\deg(\hat{Q})\le d+1$。反之，如果某个 $\hat{q}k$ 违反了其次数界，那么关于随机挑战 $y$，以高概率有 $\deg(\hat{Q})>d+1$。因此，$n$ 个次数检查归约为以下两个检查：

• 对 $\hat{Q}$ 的单个次数检查，即 $\deg(\hat{Q})\le d_*+1$；
• 检查 $\hat{Q}$ 是良构的，即其承诺与各个 $\hat{q}_k$ 的承诺一致。

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

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

然后证明者证明以下两点：

• $\deg(\zeta_x)\le d_+1$：这证明 $\deg(\hat{Q})\le d_+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_*+1$。

在最终的 Zeromorph 打开协议中，我们选择 $d_*=2^n-2$，使得 $\zeta_x$ 和 $Z_x$ 具有相同的次数界 $2^n-1$。然后验证者采样一个随机挑战 $z\in 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$，以高概率，这一次调用同时强制执行两个求值检查和所需的次数界。

现在我们已经有了呈现端到端 Zeromorph 打开协议所需的全部构件。

端到端打开协议

端到端打开协议如下进行：

1. P 计算 $f$ 的单变量编码 $\hat{f}(X)=\mathrm{Un}(f)(X)$，并将承诺 $C=[\hat{f}(\tau)]_1$ 发送给 V。
2. V 采样 $(u_0,\ldots,u_{n-1})\leftarrow_{$}F^n$ 并发送给 P。
3. P 计算多线性商多项式 $q_0,\ldots,q_{n-1}$ 及其单变量编码 $\hat{q}k(X)=\mathrm{Un}(q_k){<2^k}(X)$。它将承诺 $C_k=[\hat{q}_k(\tau)]_1,\ k\in{0,\ldots,n-1}$ 和求值 $v$ 发送给 V。
4. V 采样一个随机挑战 $y\leftarrow_{$}F$（用于批处理次数检查）并发送给 P。
5. P 计算移位后的随机线性组合

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

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

6. V 采样 $x\leftarrow_{$}F^*$（一个非零打开点）和 $z\leftarrow_{$}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$。因此，证明包含 $G_1$ 中的 $n+2$ 个元素。假设每个 $G_1$ 元素由两个域元素编码，则证明大小为 $O(n)$ 个域元素。
• 证明者成本： 主要的证明者成本包括以下操作：
  • 计算并承诺商多项式： 正如第二部分中的 PST 复杂度分析所示，计算商多项式和声称的求值 $v=f(\vec{u})$ 需要 $O(2^n)$ 次域运算。对 $f$ 的承诺需要规模为 $2^n$ 的 MSM，而对所有商多项式做承诺需要总规模为 $2^n-1$ 的 MSM。同样的界也适用于单变量编码 $\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 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～