KZG变体：第二部分，基于PST的多线性承诺 - ZK/SEC Quarterly

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

KZG 的变体：第二部分，基于 PST 的多线性承诺

KZG 的变体

1. 1 KZG 的变体：第一部分，单变量
2. 2 KZG 的变体：第二部分，基于 PST 的多线性承诺

在第一部分中，我们研究了单变量场景下的 KZG 承诺，即证明者想向验证者证明 $f^{\hat{}}(u)=v$，其中 $f^{\hat{}}$ 是一个单变量多项式。在本部分及本系列的后续部分，我们将探索基于 KZG 的多线性多项式承诺。多线性多项式是一个多元多项式，在每个变量上的次数最多为 1。 我们在本系列剩余部分要研究的关键问题是：

我们能否为一个多线性多项式 $f(X_0,\dots,X_{n-1})$ 在点 $(u_0,\dots,u_{n-1})$ 处构造一个打开论证，证明 $f(u_0,\dots,u_{n-1})=v$？ 此类承诺可与多线性 IOP（例如 Spartan）一起使用，来构建 SNARK。在本部分，我们将研究 Papamanthou-Shi-Tamassia (PST) 承诺方案。 记号。 我们继续使用第一部分中的记号。令 $\vec{X}=(X_0,\dots,X_{n-1})$ 且 $\vec{u}=(u_0,\dots,u_{n-1})$。单变量多项式用带帽符号表示，而多线性多项式则不带帽。 在深入构造细节之前，让我们研究一下多线性场景下的一个多项式恒等式。

多线性多项式恒等式

在第一部分中，我们基于因式定理看到了单变量场景下的一个多项式恒等式。如果 $\hat{f}(u)=v$，则存在一个唯一的商多项式： $\hat{q}(X)=\frac{\hat{f}(X)-v}{X-u}$。 关键思想是在随机采样的隐藏设置值处检查恒等式 $\hat{f}(X)-v=(X-u)\hat{q}(X)$。根据 Schwartz-Zippel 引理，如果该恒等式不成立，则它在随机设置值处成立的概率很小。验证者使用公共参数、$\hat{f}$ 和 $\hat{q}$ 的承诺以及双线性配对来执行此检查。 我们想要在多线性场景中得到一个类似的恒等式。让我们按逆序 $X_{n-1},X_{n-2},\dots,X_0$ 来特化变量。考虑通过设置 $X_{n-1}=u_{n-1}$ 得到的 $f(X_0,\dots,X_{n-1})$ 的局部求值： $f_{n-1}(X_0,\dots,X_{n-2})=f(X_0,\dots,X_{n-2},u_{n-1})$。 现在差值 $f(X_0,\dots,X_{n-1})-f_{n-1}(X_0,\dots,X_{n-2})=f(X_0,\dots,X_{n-1})-f(X_0,\dots,X_{n-2},u_{n-1})$ 在 $X_{n-1}=u_{n-1}$ 时消失。因此，根据多元多项式的因式定理，它可被 $(X_{n-1}-u_{n-1})$ 整除，并且存在一个商 $q_{n-1}$，使得 $q_{n-1}(X_0,\dots,X_{n-2})=\frac{f(X_0,\dots,X_{n-1})-f_{n-1}(X_0,\dots,X_{n-2})}{X_{n-1}-u_{n-1}}$。 因此， (1) $f(X_0,\dots,X_{n-1})-f_{n-1}(X_0,\dots,X_{n-2})=(X_{n-1}-u_{n-1})\cdot q_{n-1}(X_0,\dots,X_{n-2})$ 接下来，考虑 $f_{n-1}(X_0,\dots,X_{n-2})$ 的局部求值， $f_{n-2}(X_0,\dots,X_{n-3})=f_{n-1}(X_0,\dots,X_{n-3},u_{n-2})$， 通过设置 $X_{n-2}=u_{n-2}$ 得到。再次应用因式定理得到 (2) $f_{n-1}(X_0,\dots,X_{n-2})-f_{n-2}(X_0,\dots,X_{n-3})=(X_{n-2}-u_{n-2})\cdot q_{n-2}(X_0,\dots,X_{n-3})$ 将方程 (1) 和 (2) 相加，我们得到 $f(X_0,\dots,X_{n-1})-f_{n-2}(X_0,\dots,X_{n-3})=(X_{n-1}-u_{n-1})\cdot q_{n-1}(X_0,\dots,X_{n-2})+(X_{n-2}-u_{n-2})\cdot q_{n-2}(X_0,\dots,X_{n-3})$。 以相同方式继续直到 $X_0=u_0$，我们得到以下恒等式： $f(X_0,\dots,X_{n-1})-f(u_0,\dots,u_{n-1})=\sum_{k=0}^{n-1}(X_k-u_k)\cdot q_k(X_0,\dots,X_{k-1})$。 这里，$q_k$ 仅依赖于前 $k$ 个变量 $X_0,\dots,X_{k-1}$，并且在这些变量上是多线性的，而 $q_0$ 是常数。对于固定的特化顺序 $X_{n-1},X_{n-2},\dots,X_0$，这些商多项式是唯一的。 因此，证明 $f(u_0,\dots,u_{n-1})\stackrel{?}{=}v$ 简化为证明存在多线性多项式 $q_k$ 满足以下恒等式： $f(X_0,\dots,X_{n-1})-v\stackrel{?}{=}\sum_{k=0}^{n-1}(X_k-u_k)\cdot q_k(X_0,\dots,X_{k-1})$。 我们将以此作为 PST 的起点。基础知识介绍完毕后，现在我们来看构造。

PST 承诺方案

PST 是 KZG 的直接多元推广。原始构造支持一般的多元多项式，但我们专注于其多线性特化，这在实践中更常用。 我们需要检查以下恒等式： $f(X_0,\dots,X_{n-1})-v\stackrel{?}{=}\sum_{k=0}^{n-1}(X_k-u_k)q_k(X_0,\dots,X_{k-1})$。 根据 Schwartz-Zippel 引理，如果上述方程不是一个有效的多项式恒等式，那么它在随机选择的点处成立的概率很小。 因此，在设置阶段，我们随机采样一个点 $\vec{\tau}=(\tau_0,\dots,\tau_{n-1})$，将在该点处检查上述方程。验证者使用公共参数、$f$ 和 $q_k$ 的承诺以及双线性配对来执行此检查。 该构造的算法定义如下。

• $\text{setup}(n)\to pp$
  • 采样 $\tau_0,\dots,\tau_{n-1}\in\mathbb{F}p$ 并令 $\vec{\tau}=(\tau_0,\dots,\tau{n-1})$。
  • 计算承诺密钥 $ck$，其中包含 $\vec{\tau}$ 的所有 $2^n$ 个单项式的编码：$ck=\left(\left{\left[\prod_{i=0}^{n-1}\tau_i^{b_i}\right]_1:\vec{b}\in{0,1}^n\right}\right)$。
  • 计算验证密钥 $vk$，其中包含每个 $\tau_i$ 的编码：$vk=\left([1]_1,[1]_2,[\tau_0]2,\dots,[\tau{n-1}]_2\right)$。
  • 输出 $pp=(ck,vk)$。
  • 丢弃 $\vec{\tau}$。
• $\text{commit}(pp,f)\to \text{com}_f$
  • 写出 $f(\vec{X})=\sum_{\vec{b}\in{0,1}^n}f_{\vec{b}}\prod_{i=0}^{n-1}X_i^{b_i}$。
  • 计算 $\text{com}f=[f(\vec{\tau})]1=\sum{\vec{b}\in{0,1}^n}f{\vec{b}}\left[\prod_{i=0}^{n-1}\tau_i^{b_i}\right]_1$。
• $\text{open}(P,V)\to 0/1$
  • $P$ 将 $\text{com}_f$ 发送给 $V$。
  • $V$ 采样 $\vec{u}=(u_0,\dots,u_{n-1})\in\mathbb{F}_p^n$ 并请求在 $\vec{u}$ 处打开。
  • $P$ 计算 $v=f(\vec{u})$ 和满足 $f(\vec{X})-v=\sum_{k=0}^{n-1}(X_k-u_k)q_k(X_0,\dots,X_{k-1})$ 的商多项式 $q_0,\dots,q_{n-1}$。$P$ 发送 $v$ 以及每个 $k=0,\dots,n-1$ 的 $\pi_k=\text{com}_{q_k}$。
  • 当且仅当 $e(\text{com}_f-v[1]_1,[1]2)\stackrel{?}{=}\prod{k=0}^{n-1}e(\pi_k,[\tau_k]_2-u_k[1]_2)$ 时，$V$ 接受。

打开协议的复杂度

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

• 证明大小： 证明者为每个变量发送一个商承诺 $\pi_k$。因此，打开证明包含 $\mathbb{G}_1$ 中的 $n$ 个元素。假设 $\mathbb{G}_1$ 元素由两个域元素编码，则证明大小为 $O(n)$ 个域元素。
• 证明者开销： 主要的证明者开销包括以下操作：
  • 计算商多项式： 在第 $k$ 步，商多项式为：$q_k(X_0,\dots,X_{k-1})=\frac{f_{k+1}(X_0,\dots,X_k)-f_k(X_0,\dots,X_{k-1})}{X_k-u_k}$，其中 $f_k$ 是通过设置 $X_k=u_k$ 从 $f_{k+1}$ 得到的。由于 $f_{k+1}$ 在 $X_k$ 上次数最多为 1，我们可以将其拆分为 $f_{k+1}(X_0,\dots,X_k)=A_k(X_0,\dots,X_{k-1})+X_kB_k(X_0,\dots,X_{k-1})$。设置 $X_k=u_k$ 得 $f_k=A_k+u_kB_k$。现在将这些代入商多项式得 $q_k=\frac{f_{k+1}-f_k}{X_k-u_k}=\frac{A_k+X_kB_k-(A_k+u_kB_k)}{X_k-u_k}=B_k$。证明者将 $B_k$ 作为商 $q_k$，并计算 $f_k=A_k+u_kB_k$。$A_k$ 和 $B_k$ 最多有 $2^k$ 个系数。计算 $A_k+u_kB_k$ 每个系数需要一次乘法和一次加法，因此 $O(2^k)$ 次域操作。对每个 $k$ 重复此过程，总开销为 $\sum_{k=0}^{n-1}O(2^k)=O(2^n)$ 次域操作。最终的局部求值是 $f_0=f(\vec{u})$，因此相同的计算也产生了声称的值 $v$。
  • 承诺多线性多项式 $f$ 和商多项式 $q_k$： 由于 $f$ 最多有 $2^n$ 个系数，承诺 $f$ 需要大小为 $2^n$ 的 MSM。承诺 $q_k$ 需要大小为 $2^k$ 的 MSM。因此，承诺 $f$ 和所有商多项式需要 $n+1$ 次 MSM，总大小为 $2^n+\sum_{k=0}^{n-1}2^k=2^{n+1}-1$，即 $O(2^n)$ 次群标量乘法。
• 验证者开销： 对于每个 $k=0,\dots,n-1$，验证者计算 $[\tau_k]_2-u_k[1]_2$。这需要 $O(n)$ 次群标量乘法。最终的配对检查有 $n+1$ 个配对项：一个涉及承诺 $\text{com}_f$ 和声称求值 $v$，另一个对应 $n$ 个商承诺中的每一个。

等价地，开销可总结如下：

PST 的局限性

• PST 需要一个包含隐藏值交叉乘积的承诺密钥。它可以通过为其公共参数执行单独的可信设置仪式来部署。然而，这样的仪式是一个操作负担，需要大量的协调、实现和审计。此外，现有的单变量 KZG 参数并不直接包含 PST 所需的独立隐藏值的交叉乘积。这促使我们使用已建立的单变量 $\tau$ 幂次设置结构和仪式基础设施来构造一个多线性 PCS。
• PST 的验证有 $n+1$ 个配对项。因此，其验证开销随变量数量线性增长。

结论

PST 将 KZG 商论证直接扩展到多线性多项式。对于求值断言 $f(\vec{u})=v$，证明者承诺每个变量对应的一个多线性商多项式，验证者使用双线性配对检查得到的恒等式。 这种直接方法在概念上很简单，但它需要专门的多元设置，并且配对项的数量随变量数量线性增长。这引出了另一个问题：

我们能否在使用单变量多项式承诺的同时，保留多线性商恒等式？ 在下一部分，我们将研究 Zeromorph，它使用一个加法同态的单变量 PCS（如单变量 KZG）和一个度数检查协议来构造一个多线性 PCS。

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