KZG的变体们（一）：单变量批量打开和无条件隐藏

原文：https://blog.zksecurity.xyz/posts/kzg-1/

作者：Varun Thakore

译者：Kurt Pan

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

•  ：给定次数上限  ，输出用于承诺次数小于  的多项式的公共参数  。
•  输入公共参数  和次数  的多项式  ，输出对多项式的承诺 。
• : 交互式协议，证明者  说服验证者  相信  。验证者输出 1 （接受）或 0 （拒绝）。

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

• 绑定性：证明者  不能对其承诺的多项式的求值撒谎。
• 隐藏性：计算能力有限的敌手不应该从承诺中了解到有关多项式的任何信息。

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

符号和预备知识

 表示变量  的次数小于  的单变量多项式的集合，其系数在素域  中。为简洁起见，我们有时会省略变量，写成  而不是  。我们使用  来表示整数集合  。

假设存在具有适当安全参数  的群  ，及其生成元  。对  和 使用加法符号，对  使用乘法符号。对于标量乘法，定义  和  。这些群支持一个双线性配对运算：

配对的一个基本性质是双线性，这意味着对于标量  ，有：

这很重要，因为它允许我们在指数上乘以标量。此性质在许多构造中被使用，以使验证者  能够对证明者  发送的消息执行一致性检查。

多项式恒等式

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

对于多项式  在点求值为  （即  ）的条件等价于多项式  在点  有一个根（即 。因此，根据因子定理， 是  的因子，即多项式  能被  整除。换句话说，存在一个商多项式  使得：

更一般地，对集合  上求 （即，对所有  求  ）等价于  能被  整除。也就是说，存在一个商多项式  使得：

其中  使得对于所有  有  ，且  。

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

假设  和  。则  和  。 是满足  和  的多项式。我们可以使用这些点对  进行插值，得到：

此外，消失多项式为：

现在， 应该可以被  整除。 使用多项式长除法，我们发现商多项式为：

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

普通 KZG

这是最基本的构造，如 KZG10 的 3.2 节所述。其关键思想是，在收到对多项式  的承诺  后，  需要检查  是否成立。如前所述，检查  等价于检查等式（1）是否成立。

• https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf

如果等式（1）在某个随机点成立，则它在所有点都成立的概率很高（根据 Schwartz－Zippel 引理）。具体到这里，该随机点就是秘密值  。虽然  不知道  ，但它仍然可以使用  发送的承诺和配对运算，在  处验证等式 （1）的有效性。

构造算法定义如下：

• 随机抽取 
• 丢掉 
• 其中  是  的系数
•  计算  并将其发送给 
•  采样元素  并请求在  处打开 
•  使用等式（1）计算商多项式  ，并将其承诺  连同求值结果  一起发送给 

请注意，检查等式（1）与检查以下等式的有效性相同：

验证者  将用配对在秘密值  处检查此等式。

•  验证打打开证明  ，如果以下等式成立，则输出 1 ；否则，输出 0 。

该方案是同态的，即给定对多项式  和  的承诺  和  ，我们可以将对多项式  的承诺计算为  。我们将利用此性质批量处理多个打开操作，并使用一些随机性使承诺达到无条件隐藏。

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

一种直接的方法是分别打开每个多项式，并验证每个打打开证明。然而，这会导致证明者发送的打打开证明的数量和验证者执行的配对检查的数量与多项式的数量成正比。

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

批量变体

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

KZG10 的 3.4 节描述了在多个求值点处对单个多项式进行批量打开运算的协议。Plonk 的第 3 节介绍了在两个求值点处对多个多项式进行开运算的变体。本节将重点介绍更通用的变体，允许在多个求值点处对多个多项式进行打开运算，如 BDFG20 中所述。

• https://eprint.iacr.org/2019/953.pdf
• https://eprint.iacr.org/2020/081.pdf

在这种情况下，给定证明者  多项式  ，并且必须让验证者  相信对相应集合  中的每个  的求值都是正确的，其中对于所有  都有  。

证明者  可以单独证明下列等式对所有  的有效性，这与等式（2）相同。

但是，如前所述，这样做效率不高。关键思想是，如果上述等式对所有  都有效，那么这些  等式的随机线性组合也将以高概率有效。证明者  从验证者  接收随机值  ，并按如下方式计算随机线性组合：

因此，验证者  只需要验证这个单个随机线性组合的有效性，而不是对每个  单独验证等式（3）。

我们重点关注open 协议，因为 setup 和 commit 算法是类似的。

•  将  发送给  ，分别作为对多项式  的承诺
•  采样集合  并要求  在  为所有  打开 
•  发送随机 （用于组合所有打开）
•  执行以下操作：
• 使用等式（4）计算 
• 向 发送承诺 （即 ），同时发送  对  对所有  的声称求值

注意到验证等式（4）的有效性等同于验证以下等式：

，其中  表示  和  之间的集合差。这可以使用两种不同的方法来完成。

方法一

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

在上述检查中，验证者  可以自行为每个  计算  和  。由于  需要计算群  中的承诺  和  ，因此公共参数  必须包含秘密  在  中的额外幂，即  ，其中  是  的次数。

该方法中的打开证明仅包含一个群元素，即  。然而，它需要  计算多个配对，并在目标群  中进行乘积运算。在下一个方法中，我们减少了验证者的工作量。

方法二

在这种方法中，会额外采样一个随机点，并在该点处检验等式（5）的有效性。根据 Schwartz－Zippel 引理，如果等式（5）在随机选取的点处成立，则它对所有点都成立的概率很高。

•  采样随机质询  并将其发送至 

 必须证明等式（5）在  处有效，即

 计算多项式  使得

然后，  证明  。注意，值  和  都可以由验证者  计算出来。

•  发送一个打开证明，其中  在  处求值为 0 ，即对多项式  的承诺  ，其中：

现在，验证等式（6）的有效性就归约到检查下列等式是否成立。

我们运用与之前相同的思路——如果上述等式在随机选择的点上成立，那么它在所有点上也极有可能成立 （根据 Schwartz－Zippel 引理）。因此，验证者  使用配对来验证该等式在秘密值  处的有效性。

•  使用 KZG 的同态性质计算  ，即对  的承诺：

然后，如果以下等式成立，则  输出 1 ；否则，输出 0 ：

在这种情况下，打开证明是两个群元素，即  和  。然而，验证者  只需计算两个配对，而无需在目标群  中执行任何操作。此外，由于  不需要计算群  中的承诺  和  ，因此公共参数  不需要群  中秘密  的额外幂次（方法一中的情况）。相反，它们只需要包含  中的元素  即可。

无条件隐藏

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

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

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

方法一：使用随机多项式

该方法在 KZG10的 3.3 节中进行了描述。它利用同态性质，通过组合两个承诺来实现无条件隐藏：一个承诺是对多项式  的承诺，另一个承诺是对随机多项式  的承诺。其关键思想是将随机承诺  加到原始承诺 中，从而使最终的承诺在整个群中均匀分布。算法描述如下：

• 采样随机元素  。值  将用于合并对  和  的承诺。
• 丢弃 

• 采样随机多项式 

其中  是  的系数， 是  的系数。

承诺  也可以看作对多项式  的承诺，其中  。

•  计算  并将其发送给 
•  对元素  进行采样，并要求  在  处打开 
•  计算商多项式  ，并将承诺  连同求值值  和 

一起发送给 

这会将检查  归约到检查  ，即检查以下等式是否有效：

使用与之前相同的想法，  将在  使用由  发送的求值  和承诺  检查上述等式

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

在这个方法中，我们使用随机多项式遮蔽多项式，从而实现无条件隐藏。然而，仅使用单个随机群元素也可以实现同样的特性，如下面方法所示。

方法二：使用随机群元素

该方法使用单个随机群元素实现无条件隐藏。Zeromorph 的 3.5.3 节对此进行了描述。其主要思想是在原始承诺中添加一个随机群元素，以确保最终的承诺在整个群中均匀分布。算法如下：

• https://eprint.iacr.org/2023/917.pdf

• 采样随机元素 
• 丢弃 

• 选择一个随机元素 （用于随机化对多项式  的承诺）
• 其中  是  的系数。

承诺  可以看作对多项式  的承诺。

•  计算  并将其发送给 
•  对元素  进行采样，并要求  在  处打开 
•  随机采样一个 （用于将承诺随机化为商多项式  ），并计算承诺  ，然后将其与求值值  一起发送到  。此外，  还会发送  ，它是用于针对  和  中随机性的校正项。