KZG变体（第二部分）：基于PST的多线性承诺 —— ZK/SEC季刊

修复后的 Markdown 文档： Variants of KZG · 第2部分，共2部分

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

Variants of KZG

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

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

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

多线性多项式恒等式

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

PST 承诺方案

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

• $\text{setup}(n) \rightarrow \text{pp}$
  • 采样 $\tau_0,\ldots,\tau_{n-1} \in \mathbb{F}p$ 并令 $\vec{\tau} = (\tau_0,\ldots,\tau{n-1})$。
  • 计算包含 $\vec{\tau}$ 所有 $2n$ 个单项式编码的承诺密钥 $ck$：$ck = \left( \left{ \left[ \prod_{i=0}^{n-1} \tau_i^{b_i} \right]_1 : \vec{b} \in {0,1}^n \right} \right).$
  • 计算包含每个 $\tau_i$ 编码的验证密钥 $vk$：$vk = \left( [1]_1, [1]_2, [\tau_0]2, \ldots, [\tau{n-1}]_2 \right).$
  • 输出 $pp = (ck, vk)$。
  • 丢弃 $\vec{\tau}$。
• $\text{commit}(pp, f) \rightarrow \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) \rightarrow 0/1$
  • $P$ 发送 $\text{com}_f$ 给 $V$。
  • $V$ 采样 $\vec{u} = (u_0,\ldots,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,\ldots,X_{k-1})$ 的商多项式 $q_0,\ldots,q_{n-1}$。$P$ 发送 $v$ 以及每个 $k=0,\ldots,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$ 接受。

打开协议的复杂度

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

• 证明大小： 证明者为每个变量发送一个商承诺 $\pi_k$。因此，打开证明包含 $G_1$ 中的 $n$ 个元素。假设 $G_1$ 元素由两个域元素编码，则证明大小为 $O(n)$ 个域元素。
• 证明者成本： 主要证明者成本包括以下操作：
  • 计算商多项式： 在第 $k$ 步，商多项式为：$q_k(X_0,\ldots,X_{k-1}) = \frac{f_{k+1}(X_0,\ldots,X_k) - f_k(X_0,\ldots,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,\ldots,X_k) = A_k(X_0,\ldots,X_{k-1}) + X_k B_k(X_0,\ldots,X_{k-1})$。设置 $X_k = u_k$ 得到 $f_k = A_k + u_k B_k$。现在将这些代入商得到 $q_k = \frac{f_{k+1} - f_k}{X_k - u_k} = \frac{A_k + X_k B_k - (A_k + u_k B_k)}{X_k - u_k} = B_k$。证明者将 $B_k$ 作为商 $q_k$，并计算 $f_k = A_k + u_k B_k$。$A_k$ 和 $B_k$ 最多有 $2k$ 个系数。计算 $A_k + u_k B_k$ 每个系数需要一次乘法和一次加法，共 $O(2k)$ 次域操作。对每个 $k$ 重复此过程，总成本为 $\sum_{k=0}^{n-1} O(2k) = O(2n)$ 次域操作。最终的偏求值是 $f_0 = f(\vec{u})$，因此同样的计算也产生了声称的值 $v$。
  • 承诺多线性多项式 $f$ 和商 $q_k$： 由于 $f$ 最多有 $2n$ 个系数，承诺 $f$ 需要大小为至多 $2n$ 的 MSM。承诺 $q_k$ 需要大小为至多 $2k$ 的 MSM。因此，承诺 $f$ 和所有商需要 $n+1$ 个 MSM，总大小为 $2^n + \sum_{k=0}^{n-1} 2^k = 2^{n+1} - 1$，即 $O(2^n)$ 次群标量乘法。
• 验证者成本： 对于每个 $k=0,\ldots,n-1$，验证者计算 $[\tau_k]_2 - u_k [1]_2$。这需要 $O(n)$ 次群标量乘法。最终的配对检查有 $n+1$ 个配对项：一个涉及承诺 $\text{com}_f$ 和声称的求值 $v$，以及 $n$ 个商承诺各一个。

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

PST 的局限性

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

结论

PST 直接将 KZG 商参数推广到多线性多项式。对于一个求值声明 $f(\vec{u}) = v$，证明者为每个变量承诺一个多线性商多项式，验证者使用双线性配对检查所得的恒等式。 这种直接方法概念上简单，但它需要专门的多元 setup 和随变量数量线性增长的配对项数。这引出了另一个问题：

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

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