KZG变体：第一部分，单变量 - ZKSECURITY

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

• setup(d)→pp: 给定一个关于阶数的上限 d，它输出公共参数 pp，用于承诺阶数小于 d 的多项式。

• commit(pp,f)→comf: 接受公共参数 pp 和一个阶数 <d 的多项式 f，并输出对该多项式的承诺 comf。

• open(P,V)→0/1: 一个交互式协议，其中证明者 P 说服验证者 V，f(u)=v。验证者输出 1（接受）或 0（拒绝）。

非正式地说，PCS 的两个关键属性是：

• Binding（约束性）：证明者 P 不能谎报他们承诺的多项式的求值。

• Hiding（隐藏性）：在计算上受限的敌手不应从承诺中学到关于多项式的任何信息。

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

符号和预备知识

我们用 Fp(<d)[X] 表示变量 X 中阶数小于 d 的单变量多项式集合，其系数在素数域 Fp 中。为简洁起见，我们有时省略变量，写 f 而不是 f(X)。我们使用 [k] 表示整数集合 {1,…,k}。

我们假设存在具有适当安全参数 λ 的群 (G1,G2,GT) 及其生成元 (G1,G2,GT)。我们对 G1 和 G2 使用加法符号，对 GT 使用乘法符号。对于标量乘法，我们定义 [x]1:=x⋅G1 和 [x]2:=x⋅G2。这些群支持双线性配对操作：

𝟙𝟚𝕥e:G1×G2→Gt

配对的一个重要性质是双线性性，这意味着对于标量 a,b，我们有： e(a⋅G1,b⋅G2)=e(G1,G2)ab 这很重要，因为它允许我们在指数中乘以标量。在许多构造中，此属性用于使验证者 V 能够对证明者 P 发送的消息执行一致性检查。

多项式恒等式

在本节中，我们将介绍一些关于多项式的基本事实，这些事实将有助于理解稍后介绍的各种构造。

对于多项式 f∈Fp(<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)q(X)=f(X)−vX−u

更一般地，在一组 S 上求值 f（即，对所有 u∈S 求值 f(u)）等效于 f(X)−r(X) 可以被 ZS(X) 整除。也就是说，存在一个商多项式 q(X) 使得：

(2)q(X)=f(X)−r(X)ZS(X)

其中 r∈Fp(<|S|)[X] 使得对于所有 u∈S，r(u)=f(u)，并且 ZS(X)=∏u∈S(X−u)。

让我们通过一个例子来理解上面的内容。

假设 f(X)=X3+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

此外，消失多项式为：

ZS(X)=(X−1)(X−2)=X2−3X+2

现在，f(X)−r(X) 应该可以被 ZS(X) 整除。

使用多项式长除法，我们发现商多项式为：

q(X)=f(X)−r(X)ZS(X)=X3−7X+6X2−3X+2=X+3

有了符号和预备知识，我们现在可以看看第一个构造。

Plain KZG

这是最基本的构造，如 KZG10 的第 3.2 节所述。关键思想是，在接收到对多项式 f 的承诺 comf 后，V 需要检查是否 f(u)=?v。正如前面讨论的，检查 f(u)=?v 等效于检查方程 (1) 是否有效。

如果方程 (1) 在一个随机点处有效，那么以很高的概率，它在所有点处都有效（通过 Schwartz-Zippel 引理）。在这种情况下，随机点是秘密值 α。虽然 V 不知道 α，但它仍然可以使用 P 发送的承诺和配对操作来验证 α 处方程 (1) 的有效性。

构造的算法定义如下：

• setup(d)→pp
  • 示例一个随机 α∈Fp
  • pp=([1]1,[α]1,…,[αd−1]1,[1]2,[α]2)
  • 丢弃 α

• commit(pp,f)→comf

  • comf=[f(α)]1=f0⋅[1]1+f1⋅[α]1+f2⋅[α2]1+⋯+fd−1⋅[αd−1]1

  其中 f0,f1,f2,…,fd−1 是 f 的系数

• open(P,V)→0/1

  • P 计算 comf 并将其发送给 V
  • V 采样一个元素 u∈Fp 并请求在 u 处打开 f
  • P 使用方程 (1) 计算商多项式 q，并将 comq （对 q 的承诺）连同求值 v=f(u) 一起发送给 V

  请注意，检查方程 (1) 与检查以下方程的有效性相同：q(X)⋅(X−u)=f(X)−v 验证者 V 将使用配对在秘密值 α 处检查此方程。

  • 如果以下方程成立，则 V 验证打开证明 comq 并输出 1；否则，它输出 0。 e(comq,[α]2−u⋅[1]2)=?e(comf−v⋅[1]1,[1]2)

这个方案是同态的，即给定对多项式 f(X) 和 g(X) 的承诺 comf 和 comg，我们可以计算对多项式 h(X)=f(X)+g(X) 的承诺 comh=comf+comg。我们将使用此属性来批量处理多个打开，并使用一些随机性使承诺无条件隐藏。

我们已经了解了如何在单个点打开单个多项式。现在，让我们将其扩展到在多个点打开多个多项式。

一种直接的方法是单独打开每个多项式并验证每个打开证明。但是，这将使证明者发送的打开证明的数量和验证者执行的配对检查的数量与多项式的数量成正比。

我们能否更有效地在多个点打开多个多项式？我们可以使用批处理。

Batched Variants（批处理变体）

在本节中，我们将研究能够有效打开多个多项式中多个求值点的方案。我们不是单独打开每个求值，而是将所有必需的打开一起批处理。这种方法利用了 KZG 承诺的同态属性。

KZG10 的第 3.4 节中描述了用于在多个求值点打开单个多项式的批处理协议。Plonk 的第 3 节中介绍了用于在两个求值点打开多个多项式的变体。在本节中，我们重点介绍更通用的变体，这些变体允许在多个点打开多个多项式，如 BDFG20 中所述。

在这种设置中，证明者 P 获得多项式 f1,…,fk∈Fp(<d)[X]，并且必须说服验证者 V 每个 fi 在对应集合 Si 上的正确求值，其中对于所有 i∈[k]，Si⊂T={u1,u2,…,ut}。

对于所有 i∈[k]，证明者 P 可以单独证明以下方程的有效性，这与方程 (2) 相同。 (3)qi(X)=fi(X)−ri(X)ZSi(X) 然而，正如前面提到的，这效率不高。关键思想是，如果上述方程对于所有 i∈[k] 都有效，那么这些 k 个方程的随机线性组合也将以很高的概率有效。证明者 P 从验证者 V 接收一个随机值 γ，并按如下方式计算随机线性组合： (4)q(X)=∑i∈[k]γi−1⋅qi(X)=∑i∈[k]γi−1fi(X)−ri(X)ZSi(X) 因此，验证者 V 只需要验证这个单一随机线性组合的有效性，而不是单独验证每个 i∈[k] 的方程 (3)。

我们专注于 open 协议，因为 setup 和 commit 算法保持相似。

open(P,V)→0/1

• P 将 com1,com2,…,comk 发送给 V，作为对多项式 f1,f2,…fk 的承诺
• V 采样集合 S1,S2,…,Sk 并要求 P 在 Si 处打开 fi，适用于所有 i∈[k]
• V 发送随机 γ（用于组合所有打开）

• P 执行以下操作：

  • 使用方程 (4) 计算 q(X)
  • 将对 q(X) 的承诺（即 comq）连同 fi 在 Si 上的声明的求值一起发送给 V，适用于所有 i∈[k]

请注意，验证方程 (4) 的有效性等效于验证以下方程： (5)q(X)⋅ZT(X)=∑i∈[k]γi−1⋅ZT∖Si(X)⋅(fi(X)−ri(X)) 其中 T∖Si 表示 T 和 Si 之间的集合差。这可以使用两种不同的方法来完成。

Method I（方法一）

验证者 V 可以使用配对直接在 α（秘密值）处检查方程 (5) 的有效性。如果以下方程成立，则 V 输出 1；否则，它输出 0。

e(comq,[ZT(α)]2)=?∏i∈[k]e(γi−1⋅(comi−[ri(α)]1),[ZT∖Si(α)]2)

请注意，在上述检查中，验证者 V 可以自行计算 [ZT(α)]2, [ZT∖Si(α)]2 和 [ri(α)]1，适用于每个 i∈[k]。由于 V 需要在群 G2 中计算承诺 [ZT(α)]2 和 [ZT∖Si(α)]2，因此公共参数 pp 必须包含 G2 中秘密 α 的其他幂次，即 ([1]2,[α]2,…,[αt]2)，其中 t 是 ZT(X) 的次数。

此方法中的打开证明包含单个群元素，即 comq。但是，它要求 V 计算多个配对并在目标群 GT 中执行乘积运算。在下一种方法中，我们减少验证者的工作量。

Method II（方法二）

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

• V 采样一个随机挑战 z 并将其发送给 P

P 必须证明方程 (5) 在 z 处有效，即 (6)q(z)⋅ZT(z)=?∑i∈[k]γi−1⋅ZT∖Si(z)⋅(fi(z)−ri(z))P 计算多项式 l(X) 使得 l(X)=∑i∈[k]γi−1⋅ZT∖Si(z)⋅(fi(X)−ri(z))−q(X)⋅ZT(z) 然后，P 表明 l(z)=0。请注意，值 ZT(z)、ZT∖Si(z) 和 ri(z) 都可以由验证者 V 计算。

• P 发送一个打开证明，证明 l(X) 在 z 处的求值为 0，即对多项式 l′(X) 的承诺 coml′，其中： l′(X)=l(X)X−z

现在，验证方程 (6) 的有效性简化为检查以下方程是否成立。

l′(X)⋅(X−z)=l(X) 我们应用与之前相同的想法——如果上述方程在随机选择的点处有效，那么以很高的概率，它对所有点都有效（通过 Schwartz-Zippel 引理）。因此，验证者 V 使用配对在秘密值 α 处检查此方程的有效性。

• V 使用 KZG 的同态属性计算 coml，即对 l(X) 的承诺： coml:=∑i∈[k]γi−1⋅ZT∖Si(z)⋅(comi−ri(z)⋅[1]1)−ZT(z)⋅comq

然后，如果以下方程成立，则 V 输出 1；否则，它输出 0： e(coml,[1]2)=?e(coml′,[α]2−z⋅[1]2)

在这种情况下，打开证明是两个群元素，即 comq 和 coml′。但是，验证者 V 只需要计算两个配对并且不在目标群 Gt 中执行任何操作。此外，由于 V 不需要计算群 G2 中的承诺 [ZT(α)]2 和 [ZT∖Si(α)]2，因此公共参数 pp 不需要群 G2 中秘密 α 的其他幂次（如方法 I 中的情况）。相反，它们只需要包括来自 G2 的元素 ([1]2,[α]2) 元素。

Unconditionally Hiding（无条件隐藏）

在我们目前看到的所有方案中，commit 算法 commit 都是确定性的，即它不采样随机值。这会泄露一些信息，例如，如果两个承诺相等，那么底层多项式必须相同。现在，我们将研究使用一些随机性来实现无条件隐藏 属性的方案。

非正式地说，无条件隐藏意味着即使是计算能力不受限制的敌手也无法从承诺中了解关于底层多项式的任何信息。这是通过向承诺添加随机性来实现的，从而使其在整个群上均匀分布。因此，在看到承诺后，敌手能做的最好的事情就是对多项式进行随机猜测。

在隐私很重要的环境中，无条件隐藏 PCS 至关重要，因为它能够构建 zkSNARK——即具有零知识属性的 SNARK。实现无条件隐藏 PCS 的方法如下。

Method I（方法一）：Using a random polynomial（使用随机多项式）

此方法在 KZG10 的第 3.3 节中描述。它利用同态属性，通过组合两个承诺来实现无条件隐藏：一个是对多项式 f 的承诺，另一个是对随机多项式 f~ 的承诺。关键思想是将随机承诺 comf~ 添加到原始承诺 comf，以便生成的承诺在整个群上均匀分布。算法描述如下：

• setup(d)→pp
  • 采样随机元素 α,β∈Fp。值 β 将用于组合对 f 和 f~ 的承诺。
  • pp=([1]1,[α]1,…,[αd−1]1,[β]1,[β⋅α]1,…,[β⋅αd−1]1,[1]2,[α]2)
  • 丢弃 α,β

• commit(pp,f)→comf^

  • 采样一个随机多项式 f~∈Fp(<d)[X]

  • comf^=[f(α)]1+[β⋅f~(α)]1=f0⋅[1]1+f1⋅[α]1+f2⋅[α2]1+⋯+fd−1⋅[αd−1]1+f~0⋅[β]1+f~1⋅[β⋅α]1+f~2⋅[β⋅α2]1+⋯+f~d−1⋅[β⋅αd−1]1

  其中 f0,f1,…,fd−1 是 f 的系数，f~0,f~1,…,f~d−1 是 f~ 的系数。

  承诺 comf^ 也可以看作是对多项式 f^(X) 的承诺，其中 f^(X)=f(X)+β⋅f~(X)。

• open(P,V)→0/1

  • P 计算 comf^ 并将其发送给 V
  • V 采样一个元素 u∈Fp 并要求 P 在 u 处打开 f
  • P 计算商多项式 q, q~ 并将承诺 comq^ 发送给 V，并附带求值 f(u) 和 f~(u)q(X)=f(X)−f(u)X−uq~(X)=f~(X)−f~(u)X−ucomq^=[q(α)]1+[β⋅q~(α)]1

  这将检查 f(u)=?v 减少为检查 q^=q+β⋅q~，即检查以下方程是否有效： q^(X)=f(X)−f(u)X−u+β⋅f~(X)−f~(u)X−uf(X)+β⋅f~(X)=q^(X)⋅(X−u)+(f(u)+β⋅f~(u))f^(X)=q^(X)⋅(X−u)+(f(u)+β⋅f~(u)) 使用与之前相同的想法，V 将使用 P 发送的求值 f(u),f~(u) 和承诺 comf^,comq^ 在 α 处检查上述方程

  • 如果以下成立，则 V 输出 1，否则输出 0：

  e(comf^,[1]2)=?e(comq^,[α]2−u⋅[1]2)⋅e(f(u)⋅[1]1+f~(u)⋅[β]1,[1]2)

在此方法中，我们使用随机多项式来混淆多项式，以实现无条件隐藏。但是，正如以下方法所示，仅使用单个随机群元素也可以实现相同的属性。

Method II（方法二）：Using a random group element（使用随机群元素）

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

• setup(d)→pp
  • 采样随机元素 α,β∈Fp
  • pp=([1]1,[α]1,…,[αd−1]1,[β]1,[1]2,[α]2,[β]2)
  • 丢弃 α,β

• commit(pp,f)→comf^

  • 选择一个随机元素 r∈Fp（用于随机化对多项式 f 的承诺）
  • comf^=[f(α)]1+r⋅[β]1=f0⋅[1]1+f1⋅[α]1+f2⋅[α2]1+⋯+fd−1⋅[αd−1]1+r⋅[β]1

  其中 f0,f1,…,fd−1 是 f 的系数。

  承诺 comf^ 可以看作是对多项式 f^(X)=f(X)+rβ 的承诺。

• open(P,V)→0/1

  • P 计算 comf^ 并将其发送给 V

  • V 采样一个元素 u∈Fp 并要求 P 在 u 处打开 f

  • P 采样一个随机 s∈Fp（用于随机化对商多项式 q 的承诺）并计算承诺 comq^，并将其与求值 f(u) 一起发送给 V。此外，P 还发送 δ，它是校正项，用于说明 comf^ 和 comq^ 中的随机性。

  q(X)=f(X)−f(u)X−u

  comq^=[q(α)]1+s⋅[β]1

  δ=r⋅[1]1−s⋅[α]1+(s⋅u)⋅[1]1=[r−s(α−u)]1

  承诺 comq^ 可以看作是对多项式 q^(X)=q(X)+sβ 的承诺。从我们之前的讨论中，我们知道检查求值 f(u) 等效于检查以下方程是否有效。 q(X)=f(X)−f(u)X−u 但是，验证者 V 无法直接在 α（秘密值）处检查上述方程，因为他们没有对 q(X) 和 f(X) 的承诺。相反，他们拥有随机承诺 comq^ 和 comf^。

  让我们结合相应的随机性并重新排列各项，以推导出一个 V 可以使用承诺 comq^、comf^ 和配对检查来验证的方程。这个过程还将提供对校正项 δ 的深入了解。我们首先将 comq^ 的随机性（即 sβ）添加到两边： q(X)+sβ=f(X)−f(u)X−u+sβ(q(X)+sβ)⋅(X−u)=f(X)−f(u)+sβ⋅(X−u) 将 comf^ 的随机性（即 rβ）添加到两边： (q(X)+sβ)⋅(X−u)+rβ=f(X)−f(u)+sβ⋅(X−u)+rβ(q(X)+sβ)⋅(X−u)+rβ−sβ⋅(X−u)=(f(X)+rβ)−f(u)(q(X)+sβ)⋅(X−u)+(r−s⋅(X−u))⋅β=(f(X)+rβ)−f(u) 请注意，在上面的方程中，项 (q(X)+sβ) 对应于 comq^，项 (f(X)+rβ) 对应于 comf^，项 (r−s⋅(X−u)) 对应于 δ。 因此，V 可以使用配对在秘密值 α 处验证上述方程。

  • 如果以下成立，则 V 输出 1；否则，它输出 0： e(comf^−v⋅[1]1,[1]2)=?e(comq^,[α]2−u⋅[1]2)⋅e(δ,[β]2)

在此方法中，我们使用单个随机群元素来实现无条件隐藏属性。但是，打开证明由两个群元素组成，即 comq^ 和 δ，而方法 I 中只有一个群元素。

Conclusion（结论）

在这篇文章中，我们探索了 KZG 多项式承诺方案的各种单变量变体，包括用于批量处理多个打开和实现无条件隐藏属性的技术。在本系列的下一部分中，我们将深入研究多变量设置。

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