KZG变体：第一部分，单变量 —— ZK/SEC季刊

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

KZG 的变体：第一部分，单变量

KZG 的变体

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

多项式承诺方案 (PCS) 允许证明者承诺一个多项式，随后证明该多项式在验证者选择的点上的求值。验证者可以检查这些求值是否与承诺的多项式一致。大多数实用的 SNARK（简洁的非交互式知识论证）都是使用 PCS 构建的。它包含以下三个算法：

• setup(d)→pp：给定一个次数上限 d，输出用于承诺次数小于 d 的多项式的公共参数 pp。
• commit(pp,f)→comf：接收公共参数 pp 和一个次数 < d 的多项式 f，输出对该多项式的承诺 comf。
• open(P,V)→0/1：一个交互式协议，其中证明者 P 使验证者 V 确信 f(u)=v。验证者输出 1（接受）或 0（拒绝）。

通俗地说，PCS 的两个关键性质是：

• 绑定性：证明者 P 不能对其承诺的多项式的求值作假。
• 隐藏性：计算能力有界的敌手无法从承诺中获取关于多项式的任何信息。

使用最广泛的 PCS 之一是 KZG10，因为它的证明大小和验证时间都是常数。它被用于构建各种 SNARK，例如 Sonic 和 Plonk。在这篇文章中，我们探讨单变量多项式的 KZG 变体。但首先，让我们介绍一些记号和预备知识。

记号和预备知识

我们用 $\mathbb{F}_p^{(\lt d)}[X]$ 表示变量 $X$ 上次数小于 $d$ 的单变量多项式的集合，系数在素域 $\mathbb{F}_p$ 中。为简洁起见，我们有时省略变量，用 $f$ 代替 $f(X)$。我们使用 $[k]$ 表示整数集合 ${1,\dots,k}$。 我们假设存在适当安全参数 $\lambda$ 的群 $(G_1,G_2,G_T)$，以及它们的生成元 $(G_1,G_2,G_T)$。我们对 $G_1$ 和 $G_2$ 使用加法记号，对 $G_T$ 使用乘法记号。对于标量乘法，我们定义 $[x]_1 := x \cdot G_1$ 和 $[x]_2 := x \cdot G_2$。这些群支持双线性配对运算： $$ e: G_1 \times G_2 \to G_T $$ 配对的一个基本性质是双线性，也就是说，对于标量 $a,b$，有： $$ e(a \cdot G_1, b \cdot G_2) = e(G_1, G_2)^{ab} $$ 这一点很重要，因为它允许我们在指数上进行标量乘法。这个性质在许多构造中用于让验证者 $V$ 能够对证明者 $P$ 发送的消息进行一致性检查。

多项式恒等式

在本节中，我们介绍一些多项式的基本事实，这些事实将有助于理解后面介绍的各种构造。 对于一个多项式 $f \in \mathbb{F}_p^{(\lt d)}[X]$，$f$ 在点 $u$ 处求值为 $v$（即 $f(u)=v$）这一条件等价于多项式 $f(X)-v$ 在 $u$ 处有一个根（即 $f(u)-v=0$）。因此，根据因式定理，$(X-u)$ 是 $f(X)-v$ 的一个因式，即多项式 $f(X)-v$ 可被 $(X-u)$ 整除。换句话说，存在一个商多项式 $q(X)$ 使得： $$ (1)\quad q(X) = \frac{f(X)-v}{X-u} $$ 更一般地，在集合 $S$ 上求值 $f$（即对所有 $u \in S$ 计算 $f(u)$）等价于 $f(X)-r(X)$ 可被 $Z_S(X)$ 整除。即存在商多项式 $q(X)$ 使得： $$ (2)\quad q(X) = \frac{f(X)-r(X)}{Z_S(X)} $$ 其中 $r \in \mathbb{F}p^{(\lt |S|)}[X]$ 满足对所有 $u \in S$ 有 $r(u)=f(u)$，且 $Z_S(X) = \prod{u \in S}(X-u)$。 示例 让我们通过一个例子来理解上述内容。 假设 $f(X)=X^3+2X+1$ 且 $S={1,2}$。 那么 $f(1)=4$ 且 $f(2)=13$。 现在，$r(X)$ 是满足 $r(1)=f(1)=4$ 和 $r(2)=f(2)=13$ 的多项式。 我们可以使用这些点插值得到 $r(X)$，并发现： $$ r(X)=9X-5 $$ 此外，消失多项式为： $$ Z_S(X)=(X-1)(X-2)=X^2-3X+2 $$ 现在，$f(X)-r(X)$ 应能被 $Z_S(X)$ 整除。 使用多项式长除法，我们得到商多项式为： $$ q(X)=\frac{f(X)-r(X)}{Z_S(X)}=\frac{X^3-7X+6}{X^2-3X+2}=X+3 $$ 有了记号和预备知识，我们现在可以看第一个构造了。

基本 KZG

这是最基本的构造，如 KZG10 第 3.2 节所述。关键思想是：在收到多项式 $f$ 的承诺 $\mathsf{com}_f$ 后，$V$ 需要检查 $f(u) \stackrel{?}{=} v$。如前所述，检查 $f(u) \stackrel{?}{=} v$ 等价于检查方程 (1) 是否成立。 如果方程 (1) 在一个随机点成立，那么它以高概率在所有点成立（根据 Schwartz-Zippel 引理）。在该设置中，随机点是秘密值 $\alpha$。尽管 $V$ 不知道 $\alpha$，但它仍然可以使用 $P$ 发送的承诺和配对运算来验证方程 (1) 在 $\alpha$ 处是否成立。 该构造的算法定义如下：

• $\mathsf{setup}(d) \to \mathsf{pp}$
  • 随机采样 $\alpha \in \mathbb{F}_p$
  • $\mathsf{pp} = ([1]_1, [\alpha]_1, \dots, [\alpha^{d-1}]_1, [1]_2, [\alpha]_2)$
  • 丢弃 $\alpha$
• $\mathsf{commit}(\mathsf{pp}, f) \to \mathsf{com}_f$
  • $\mathsf{com}_f = [f(\alpha)]_1 = f_0 \cdot [1]_1 + f_1 \cdot [\alpha]_1 + f_2 \cdot [\alpha^2]1 + \dots + f{d-1} \cdot [\alpha^{d-1}]1$
    其中 $f_0, f_1, f_2, \dots, f{d-1}$ 是 $f$ 的系数。
• $\mathsf{open}(P,V) \to 0/1$
  • $P$ 计算 $\mathsf{com}_f$ 并发送给 $V$
  • $V$ 采样一个元素 $u \in \mathbb{F}_p$ 并请求 $P$ 打开 $f$ 在 $u$ 处的值
  • $P$ 使用方程 (1) 计算商多项式 $q$，并将其承诺 $\mathsf{com}_q$ 以及求值 $v = f(u)$ 发送给 $V$ 注意 现在，检查方程 (1) 等同于检查以下方程的有效性：$q(X) \cdot (X-u) = f(X) - v$ 验证者 $V$ 将使用配对在秘密值 $\alpha$ 处检查该方程。
  • $V$ 验证打开证明 $\mathsf{com}_q$，如果以下方程成立则输出 $1$；否则输出 $0$： $$ e(\mathsf{com}_q, [\alpha]_2 - u \cdot [1]_2) \stackrel{?}{=} e(\mathsf{com}_f - v \cdot [1]_1, [1]_2) $$

该方案是同态的，即给定多项式 $f(X)$ 和 $g(X)$ 的承诺 $\mathsf{com}_f$ 和 $\mathsf{com}_g$，我们可以计算多项式 $h(X)=f(X)+g(X)$ 的承诺为 $\mathsf{com}_h = \mathsf{com}_f + \mathsf{com}_g$。我们将利用这个性质来批量打开多个求值，并使用一些随机性使承诺具有无条件隐藏性。 我们已经看到如何在单个点打开单个多项式。现在，让我们将其扩展到在多个点打开多个多项式。 一种直接的方法是逐个打开每个多项式并验证每个打开证明。然而，这将导致证明者发送的打开证明数量和验证者执行的配对检查数量都与多项式数量成正比。 我们能否更高效地在多个点打开多个多项式？我们可以使用批处理。

批处理变体

在本节中，我们将研究能够高效地打开多个多项式在多个求值点上的方案。我们不是分别打开每个求值，而是将所有需要的打开一起批处理。这种方法利用了 KZG 承诺的同态性质。 KZG10 的第 3.4 节描述了一个针对单个多项式在多个求值点上的批量打开协议。Plonk 的第 3 节介绍了一个在两点打开多个多项式的变体。在本节中，我们关注更一般的变体，允许在多个点打开多个多项式，如 BDFG20 所述。 在该设置中，证明者 $P$ 被给予多项式 $f_1,\dots,f_k \in \mathbb{F}p^{(\lt d)}[X]$，并且必须使验证者 $V$ 相信每个 $f_i$ 在对应集合 $S_i$ 上的正确求值，其中对于所有 $i \in [k]$，$S_i \subset T = {u_1, u_2, \dots, u_t}$。 证明者 $P$ 可以单独证明以下方程对所有 $i \in [k]$ 成立，这等同于方程 (2)。 $$ (3)\quad q_i(X) = \frac{f_i(X)-r_i(X)}{Z{S_i}(X)} $$ 然而，如前所述，这样效率不高。关键思想是，如果上述方程对所有 $i \in [k]$ 成立，那么这些 $k$ 个方程的随机线性组合也以高概率成立。证明者 $P$ 从验证者 $V$ 处收到一个随机值 $\gamma$，并按如下方式计算随机线性组合： $$ (4)\quad q(X) = \sum_{i\in[k]} \gamma^{i-1} \cdot q_i(X) = \sum_{i\in[k]} \gamma^{i-1} \frac{f_i(X)-r_i(X)}{Z_{S_i}(X)} $$ 因此，验证者 $V$ 只需要验证这个单个随机线性组合的有效性，而不是分别验证每个 $i \in [k]$ 的方程 (3)。 我们关注打开协议，因为 setup 和 commit 算法保持类似。 $\mathsf{open}(P,V) \to 0/1$

• $P$ 向 $V$ 发送 $\mathsf{com}_1, \mathsf{com}_2, \dots, \mathsf{com}_k$，作为对多项式 $f_1, f_2, \dots f_k$ 的承诺
• $V$ 采样集合 $S_1, S_2, \dots, S_k$，并要求 $P$ 对所有 $i \in [k]$ 打开 $f_i$ 在 $S_i$ 上的值
• $V$ 发送随机 $\gamma$（用于组合所有打开）
• $P$ 执行以下操作：
  • 使用方程 (4) 计算 $q(X)$
  • 向 $V$ 发送对 $q(X)$ 的承诺 $\mathsf{com}_q$，以及所有 $i \in [k]$ 的 $f_i$ 在 $S_i$ 上的声称求值

注意，验证方程 (4) 的有效性等同于验证以下方程的有效性： $$ (5)\quad q(X) \cdot Z_T(X) = \sum_{i\in[k]} \gamma^{i-1} \cdot Z_{T \setminus S_i}(X) \cdot (f_i(X)-r_i(X)) $$ 其中 $T \setminus S_i$ 表示 $T$ 与 $S_i$ 的集合差。这可以通过两种不同的方法完成。

方法 I

验证者 $V$ 可以直接使用配对在 $\alpha$（秘密值）处检查方程 (5) 的有效性。如果以下方程成立，则 $V$ 输出 $1$；否则输出 $0$。 $$ e(\mathsf{com}_q, [Z_T(\alpha)]2) \stackrel{?}{=} \prod{i\in[k]} e\left(\gamma^{i-1} \cdot (\mathsf{com}_i - [r_i(\alpha)]1), [Z{T \setminus S_i}(\alpha)]_2\right) $$ 注意，在上述检查中，验证者 $V$ 可以自行计算 $[Z_T(\alpha)]2$、$[Z{T \setminus S_i}(\alpha)]_2$ 以及每个 $i \in [k]$ 的 $[r_i(\alpha)]_1$。由于 $V$ 需要在群 $G_2$ 中计算承诺 $[Z_T(\alpha)]2$ 和 $[Z{T \setminus S_i}(\alpha)]_2$，公共参数 $\mathsf{pp}$ 必须包含 $G_2$ 中秘密 $\alpha$ 的额外幂次，即 $([1]_2, [\alpha]_2, \dots, [\alpha^t]_2)$，其中 $t$ 是 $Z_T(X)$ 的次数。 这种方法中的打开证明由一个群元素组成，即 $\mathsf{com}_q$。然而，它要求 $V$ 计算多个配对并在目标群 $G_T$ 中执行乘积运算。在下一个方法中，我们减少验证者的工作量。

方法 II

在这种方法中，采样一个额外的随机点，并在该点检查方程 (5) 的有效性。根据 Schwartz-Zippel 引理，如果方程 (5) 在随机选择的点成立，那么它以高概率在所有点成立。

• $V$ 采样一个随机挑战 $z$ 并发送给 $P$ 注意 $P$ 必须证明方程 (5) 在 $z$ 处成立，即 $$ (6)\quad q(z) \cdot Z_T(z) \stackrel{?}{=} \sum_{i\in[k]} \gamma^{i-1} \cdot Z_{T \setminus S_i}(z) \cdot (f_i(z)-r_i(z)) $$ $P$ 计算多项式 $l(X)$ 使得 $$ l(X) = \sum_{i\in[k]} \gamma^{i-1} \cdot Z_{T \setminus S_i}(z) \cdot (f_i(X)-r_i(z)) - q(X) \cdot Z_T(z) $$ 然后，$P$ 证明 $l(z)=0$。注意，值 $Z_T(z)$、$Z_{T \setminus S_i}(z)$ 和 $r_i(z)$ 都可以由验证者 $V$ 计算。
• $P$ 发送一个打开证明，表明 $l(X)$ 在 $z$ 处求值为 $0$，即多项式 $l'(X)$ 的承诺 $\mathsf{com}_{l'}$，其中： $$ l'(X) = \frac{l(X)}{X-z} $$ 注意 现在，验证方程 (6) 的有效性简化为检查以下方程是否成立。
  $$ l'(X) \cdot (X-z) = l(X) $$ 我们应用与之前相同的想法：如果上述方程在一个随机选择的点成立，那么它以高概率在所有点成立（根据 Schwartz-Zippel 引理）。因此，验证者 $V$ 使用配对在秘密值 $\alpha$ 处检查该方程的有效性。
• $V$ 使用 KZG 的同态性质计算 $l(X)$ 的承诺 $\mathsf{com}l$： $$ \mathsf{com}l := \sum{i\in[k]} \gamma^{i-1} \cdot Z{T \setminus S_i}(z) \cdot (\mathsf{com}_i - r_i(z) \cdot [1]_1) - Z_T(z) \cdot \mathsf{com}_q $$

然后，$V$ 如果以下方程成立则输出 $1$；否则输出 $0$： $$ e(\mathsf{com}_l, [1]2) \stackrel{?}{=} e(\mathsf{com}{l'}, [\alpha]_2 - z \cdot [1]_2) $$ 在这种情况下，打开证明是两个群元素，即 $\mathsf{com}q$ 和 $\mathsf{com}{l'}$。然而，验证者 $V$ 只需要计算两个配对，并且不需要在目标群 $G_T$ 中执行任何运算。此外，由于 $V$ 不需要在群 $G_2$ 中计算承诺 $[Z_T(\alpha)]2$ 和 $[Z{T \setminus S_i}(\alpha)]_2$，公共参数 $\mathsf{pp}$ 不需要包含群 $G_2$ 中秘密 $\alpha$ 的额外幂次（如方法 I 中那样）。相反，它们只需要包含来自 $G_2$ 的元素 $([1]_2, [\alpha]_2)$。

无条件隐藏性

在我们迄今为止看到的所有方案中，commit 算法 $\mathsf{commit}$ 是确定性的，即它不采样随机值。这会泄露一些信息，例如，如果两个承诺相等，那么底层的多项式一定相同。我们现在将研究使用一些随机性来实现无条件隐藏性质的方案。 非正式地说，无条件隐藏意味着即使是计算能力无界的敌手也无法从承诺中获取关于底层多项式的任何信息。这是通过向承诺添加随机性实现的，使得承诺在整个群上均匀分布。结果，在看到承诺之后，敌手最多只能对多项式进行随机猜测。 无条件隐藏的 PCS 在隐私重要的场景中至关重要，因为它能够构建 zkSNARK，即具有零知识性质的 SNARK。实现无条件隐藏 PCS 的方法如下。

方法 I：使用随机多项式

该方法在 KZG10 的第 3.3 节中描述。它利用同态性质，通过组合两个承诺来实现无条件隐藏：一个是对多项式 $f$ 的承诺，另一个是对随机多项式 $\tilde{f}$ 的承诺。关键思想是将随机承诺 $\mathsf{com}_{\tilde{f}}$ 添加到原始承诺 $\mathsf{com}_f$ 中，使得结果承诺在群上均匀分布。算法描述如下：

• $\mathsf{setup}(d) \to \mathsf{pp}$
  • 采样随机元素 $\alpha, \beta \in \mathbb{F}_p$。值 $\beta$ 将用于组合对 $f$ 和 $\tilde{f}$ 的承诺。
  • $\mathsf{pp} = ([1]_1, [\alpha]_1, \dots, [\alpha^{d-1}]_1, [\beta]_1, [\beta \cdot \alpha]_1, \dots, [\beta \cdot \alpha^{d-1}]_1, [1]_2, [\alpha]_2)$
  • 丢弃 $\alpha, \beta$
• $\mathsf{commit}(\mathsf{pp}, f) \to \mathsf{com}_{\hat{f}}$
  • 采样一个随机多项式 $\tilde{f} \in \mathbb{F}_p^{(\lt d)}[X]$
  • $\mathsf{com}_{\hat{f}} = [f(\alpha)]_1 + [\beta \cdot \tilde{f}(\alpha)]_1 = f_0 \cdot [1]_1 + f_1 \cdot [\alpha]_1 + f_2 \cdot [\alpha^2]1 + \dots + f{d-1} \cdot [\alpha^{d-1}]_1 + \tilde{f}_0 \cdot [\beta]_1 + \tilde{f}_1 \cdot [\beta \cdot \alpha]_1 + \tilde{f}_2 \cdot [\beta \cdot \alpha^2]1 + \dots + \tilde{f}{d-1} \cdot [\beta \cdot \alpha^{d-1}]1$ 其中 $f_0, f_1, \dots, f{d-1}$ 是 $f$ 的系数，$\tilde{f}0, \tilde{f}1, \dots, \tilde{f}{d-1}$ 是 $\tilde{f}$ 的系数。 注意 承诺 $\mathsf{com}{\hat{f}}$ 也可以看作是对多项式 $\hat{f}(X)$ 的承诺，其中 $\hat{f}(X) = f(X) + \beta \cdot \tilde{f}(X)$。
• $\mathsf{open}(P,V) \to 0/1$
  • $P$ 计算 $\mathsf{com}_{\hat{f}}$ 并发送给 $V$
  • $V$ 采样一个元素 $u \in \mathbb{F}_p$ 并请求 $P$ 打开 $f$ 在 $u$ 处的值
  • $P$ 计算商多项式 $q$, $\tilde{q}$，并将承诺 $\mathsf{com}{\hat{q}}$ 以及求值 $f(u)$ 和 $\tilde{f}(u)$ 发送给 $V$ $$ q(X) = \frac{f(X)-f(u)}{X-u}, \quad \tilde{q}(X) = \frac{\tilde{f}(X)-\tilde{f}(u)}{X-u}, \quad \mathsf{com}{\hat{q}} = [q(\alpha)]1 + [\beta \cdot \tilde{q}(\alpha)]1 $$ 注意 这将检查 $f(u) \stackrel{?}{=} v$ 简化为检查 $\hat{q} = q + \beta \cdot \tilde{q}$，即检查以下方程的有效性： $$ \hat{q}(X) = \frac{f(X)-f(u)}{X-u} + \beta \cdot \frac{\tilde{f}(X)-\tilde{f}(u)}{X-u} $$ $$ f(X) + \beta \cdot \tilde{f}(X) = \hat{q}(X) \cdot (X-u) + (f(u) + \beta \cdot \tilde{f}(u)) $$ $$ \hat{f}(X) = \hat{q}(X) \cdot (X-u) + (f(u) + \beta \cdot \tilde{f}(u)) $$ 使用与之前相同的想法，$V$ 将使用 $P$ 发送的求值 $f(u), \tilde{f}(u)$ 和承诺 $\mathsf{com}{\hat{f}}, \mathsf{com}{\hat{q}}$，在 $\alpha$ 处检查上述方程。
  • $V$ 如果以下方程成立则输出 $1$，否则输出 $0$： $$ e(\mathsf{com}_{\hat{f}}, [1]2) \stackrel{?}{=} e(\mathsf{com}{\hat{q}}, [\alpha]_2 - u \cdot [1]_2) \cdot e(f(u) \cdot [1]_1 + \tilde{f}(u) \cdot [\beta]_1, [1]_2) $$

在这种方法中，我们使用一个随机多项式来盲化多项式，以实现无条件隐藏。然而，同样的性质也可以仅使用一个随机群元素实现，如下一种方法所示。

方法 II：使用随机群元素

这种方法使用一个随机群元素实现无条件隐藏。它在 Zeromorph 的第 3.5.3 节中描述。主要思想是向原始承诺添加一个随机群元素，确保结果承诺在群上均匀分布。算法如下：

• $\mathsf{setup}(d) \to \mathsf{pp}$
  • 采样随机元素 $\alpha, \beta \in \mathbb{F}_p$
  • $\mathsf{pp} = ([1]_1, [\alpha]_1, \dots, [\alpha^{d-1}]_1, [\beta]_1, [1]_2, [\alpha]_2, [\beta]_2)$
  • 丢弃 $\alpha, \beta$
• $\mathsf{commit}(\mathsf{pp}, f) \to \mathsf{com}_{\hat{f}}$
  • 选择一个随机元素 $r \in \mathbb{F}_p$（用于随机化对多项式 $f$ 的承诺）
  • $\mathsf{com}_{\hat{f}} = [f(\alpha)]_1 + r \cdot [\beta]_1 = f_0 \cdot [1]_1 + f_1 \cdot [\alpha]_1 + f_2 \cdot [\alpha^2]1 + \dots + f{d-1} \cdot [\alpha^{d-1}]1 + r \cdot [\beta]1$
    其中 $f_0, f_1, \dots, f{d-1}$ 是 $f$ 的系数。 注意 承诺 $\mathsf{com}{\hat{f}}$ 可以看作是对多项式 $\hat{f}(X) = f(X) + r \beta$ 的承诺。
• $\mathsf{open}(P,V) \to 0/1$
  • $P$ 计算 $\mathsf{com}_{\hat{f}}$ 并发送给 $V$
  • $V$ 采样一个元素 $u \in \mathbb{F}_p$ 并请求 $P$ 打开 $f$ 在 $u$ 处的值
  • $P$ 采样一个随机 $s \in \mathbb{F}p$（用于随机化对商多项式 $q$ 的承诺），计算承诺 $\mathsf{com}{\hat{q}}$，并将其与求值 $f(u)$ 一起发送给 $V$。此外，$P$ 还发送 $\delta$，这是补偿 $\mathsf{com}{\hat{f}}$ 和 $\mathsf{com}{\hat{q}}$ 中随机性的校正项。 $$ q(X) = \frac{f(X)-f(u)}{X-u}, \quad \mathsf{com}{\hat{q}} = [q(\alpha)]1 + s \cdot [\beta]1, \quad \delta = r \cdot [1]1 - s \cdot [\alpha]1 + (s \cdot u) \cdot [1]1 = [r - s(\alpha-u)]1 $$ 注意 承诺 $\mathsf{com}{\hat{q}}$ 可以看作是对多项式 $\hat{q}(X) = q(X) + s \beta$ 的承诺。从我们之前的讨论中，我们知道检查求值 $f(u)$ 等价于检查以下方程是否成立。 $$ q(X) = \frac{f(X)-f(u)}{X-u} $$ 然而，验证者 $V$ 不能直接在 $\alpha$（秘密值）处检查上述方程，因为他们没有 $q(X)$ 和 $f(X)$ 的承诺。相反，他们拥有随机化后的承诺 $\mathsf{com}{\hat{q}}$ 和 $\mathsf{com}{\hat{f}}$。 让我们加入相应的随机性并重新排列项，以推导出一个 $V$ 可以使用承诺 $\mathsf{com}{\hat{q}}$、$\mathsf{com}{\hat{f}}$ 和配对检查来验证的方程。这个过程也将帮助理解校正项 $\delta$。我们首先将 $\mathsf{com}{\hat{q}}$ 的随机性 $s\beta$ 加到等式两边： $$ q(X) + s\beta = \frac{f(X)-f(u)}{X-u} + s\beta $$ $$ (q(X) + s\beta) \cdot (X-u) = f(X) - f(u) + s\beta \cdot (X-u) $$ 将 $\mathsf{com}{\hat{f}}$ 的随机性 $r\beta$ 加到等式两边： $$ (q(X) + s\beta) \cdot (X-u) + r\beta = f(X) - f(u) + s\beta \cdot (X-u) + r\beta $$ $$ (q(X) + s\beta) \cdot (X-u) + r\beta - s\beta \cdot (X-u) = (f(X) + r\beta) - f(u) $$ $$ (q(X) + s\beta) \cdot (X-u) + (r - s \cdot (X-u)) \cdot \beta = (f(X) + r\beta) - f(u) $$ 注意，在上述方程中，项 $(q(X) + s\beta)$ 对应于 $\mathsf{com}{\hat{q}}$，项 $(f(X) + r\beta)$ 对应于 $\mathsf{com}{\hat{f}}$，项 $(r - s \cdot (X-u))$ 对应于 $\delta$。因此，$V$ 可以使用配对在秘密值 $\alpha$ 处验证上述方程。
  • $V$ 如果以下方程成立则输出 $1$；否则输出 $0$： $$ e(\mathsf{com}_{\hat{f}} - v \cdot [1]_1, [1]2) \stackrel{?}{=} e(\mathsf{com}{\hat{q}}, [\alpha]_2 - u \cdot [1]_2) \cdot e(\delta, [\beta]_2) $$

在这种方法中，我们使用一个随机群元素实现了无条件隐藏性质。然而，打开证明由两个群元素组成，即 $\mathsf{com}_{\hat{q}}$ 和 $\delta$，而方法 I 中只有一个群元素。

结论

在这篇文章中，我们探讨了 KZG 多项式承诺方案的各种单变量变体，包括批量打开多个求值的技术以及实现无条件隐藏性质的方法。在本系列的下一部分中，我们将深入探讨多变量设置。

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