走进零知识证明系统一Plonk之KZG承诺方案

PLONK是属于SNARK中最重要的零知识证明系统之一。与之前的Groth16相比，PLONK具有诸如通用和可更新的可信设置等优势。在Groth16中，通常需要电路特定的可信设置来完成，而在PLONK中，同样的可信设置可以用于任何电路。术语“可更新”指的是任何人都可以向设置中添加随机性，从而加强对其完整性的信任。

然而，PLONK的缺点是会导致更大的证明大小，这可能会影响以太坊网络上的gas fee，这可能是为什么Groth16仍被认为具有竞争力的潜在原因。

多项式是零知识证明系统的基础元素之一。我们中的许多人在学校里学过它们，但它们在这个背景下的应用可能并不明显。为什么要使用它们？

多项式提供了一种形式，使我们能够将特定过程的状态封装在一个函数内，因此，当我们想要证明某些事情时，比如程序执行的正确性或者某个陈述的验证，我们可以使用多项式来表示这些过程。这一特点使我们能够构建复杂的证明系统。

简而言之，Plonk利用了KZG（Kate, Zaverucha, Goldberg）多项式承诺方案来完成验证。让我们考虑一个简单的例子来理解承诺方案的工作原理。

(1). 设置阶段：

1. Alice有一些她想要承诺的事情，比如她在哪里吃晚餐的决定。假设她选择了“意大利菜”。

2. 她将其选择写在一张纸上。

(2). 承诺阶段：

1. Alice将纸放入盒子里。

2. 她用挂锁锁上盒子并保留钥匙。

3. 她把锁着的盒子交给Bob，并向他保证她的晚餐选择就在里面。

4. 此时，Bob手里有装有承诺内容的盒子，但他无法访问，因为它是锁着的。

(3). 打开阶段：

1. 到了揭示晚餐选择的时候，Alice把钥匙给了Bob。

2. Bob打开盒子，拿出纸条，读到了Alice的晚餐选择：“意大利菜”。

3. 现在Bob知道了Alice的承诺，并且他确信Alice在把锁着的盒子交给他后没有改变主意，因为整个过程中盒子都被安全地锁着。

在KZG承诺方案中，证明者承诺于一个多项式（例如，表示程序执行的正确性）。

假设一个证明者有一个n次的多项式P(x)需要进行承诺。为了做到这一点，他需要一个可信设置。

在这个背景下，可信设置是指需要生成一个随机秘密值τ（tau）的n次幂，然后这些幂会被“覆盖”或表示为椭圆曲线上的点。如果你对椭圆曲线上的点不熟悉，你可以把它们看作是秘密值τ与曲线上一个基点的乘积，这样可以隐藏τ的实际值。

这个过程防止任何人推断出原始的秘密值，这对于系统的安全性至关重要。

与此同时，对应的承诺长成如下形式：

证明者使用从可信设置中获得的公共参考字符串计算对多项式P(τ)的承诺，并将这个承诺（是椭圆曲线上的一个点）发送给验证者。

这是因为曲线的基点[G]的标量倍数（比如cτ）会得到曲线上的另一个点。验证者接收到对P(τ)的承诺，但为了保持零知识特性，实际的多项式P(x)不会被公开。

相反，验证者向证明者发送一个随机值r，然后证明者在那一点评估P(x)并继续执行协议。

证明者将评估的值P(r)发送回给验证者。现在验证者拥有承诺P(τ)、评估后的P(r)，以及对多项式余数定理的了解（在这个背景下常常与Bézout定理混淆），它的陈述如下：

如果你从P(x)中减去P(r)，然后除以x−r，除法应该没有余数，得到商多项式Q(x)。除了P(r)之外，证明者还将Q(τ)的承诺发送给验证者。现在验证者拥有P(τ)、Q(τ)、r和P(r)。由于椭圆曲线上没有定义这样的除法，承诺P和Q（它们是椭圆曲线上的点）经历一系列转换，以使验证者能够确认方程的有效性。

验证者不知道τ，但他从证明者那里得到了[Q(τ)]和[P(τ)]的承诺。当我们将方程的两边都乘以生成点[G]时，就变得很容易处理。

验证者知道[Q(τ)]和[P(τ)] — 对应于Q(τ)和P(τ)乘以[G]的承诺。验证者还可以计算P(r)[G]，因为P(r)是已知的。为了解决(τ−r)[G]，我们将使用椭圆曲线配对技术。

函数e表示一个双线性配对，它接受来自两个不同的椭圆曲线群中的一个点，并将它们“配对”以产生第三个目标群中的一个元素。这个配对函数的双线性性质是e(k⋅G1, G2) = e(G1, k⋅G2)，其中k是一个标量，G1和G2是来自两个不同群的点。这个性质意味着在应用配对函数之前将一个群中的点乘以k等同于首先应用配对函数，然后在最后的群中将其结果乘以k。

在双线性配对的背景下：

我们确认所有先前评估的元素都与曲线G1上的一个点相关联。

当我们在配对过程中提到“乘法”时，对于表达式(τ−r)Q(τ)与配对函数e交互，我们首先将(τ−r)映射到曲线G1上，方法是将其与G1的生成点相乘，类似地，将Q(τ)映射到曲线G2上。配对函数的交换性质使我们能够将标量(τ−r)与承诺Q(τ)互换位置，而不影响结果。

然后，我们应用分配性质来“展开括号”，这意味着在配对操作中在项之间分配乘法。

因此，现在我们可以说验证者知道承诺[Q(τ)]1，[P(τ)]1和[P(r)]1，并且还可以计算r[G2]，因为r是已知的。至于τ[G2] —— 这个值（点）应该来自可信设置，这是公共参考字符串（CRS）的一部分。

有了这些式子，验证方就可以很快地计算出证明方的承诺和陈述是否相一致。

在PLONK中，证明者需要承诺不止一个多项式，而是多个多项式。尽管理论上证明者和验证者可以使用上面提到的方案逐个处理所有的承诺，但PLONK的设计者给出了一种改进的方案，允许在单个步骤内承诺多个多项式，这是通过使用线性独立方法实现的。

假设我们有三个多项式P1(x)，P2(x)和P3(x)，我们的目标是证明每个多项式在某个值r处求值为零。为了在一个步骤内高效地证明这一点，我们可以构造一个新的多项式，其中包含了P1(x)，P2(x)和P3(x)。

新的多项式F(x)是P1(x)，P2(x)和P3(x)的组合。如果我们选择一个值r，使得在求值时，P1(r)，P2(r)和P3(r)分别得到2、3和-5的结果，我们会遇到一个问题。这些评估结果的总和为零，这可能错误地暗示每个单独的多项式在r处求值为零，而实际上它们都不是。

这可能会导致后续的过程出现很多问题，因为我们的目的是证明每个多项式在r处单独等于零，而不仅仅是它们的总和。

为了确保每个多项式P1(x)，P2(x)和P3(x)在特定点r处单独等于零，我们选择一个非零常数v（例如，v=2）并用它来通过增加的幂对多项式进行缩放。然后我们将一个新的多项式F(x)定义为F(x)=v⁰P1(x)+v¹P2(x)+v²P3(x)。当求F(r)的值并得到零时，这意味着P1(r)，P2(r)和P3(r)必须都是零，因为v是非零的，而且这些多项式是通过不同的幂次进行缩放的，使它们线性独立。这种巧妙的方法允许我们在单个组合方程中确认P1，P2和P3的各自的零点。

作者: Crypto Fairy

翻译： 杨赟博

来源：https://medium.com/@cryptofairy/under-the-hood-of-zksnarks-plonk-protocol-part-1-34bc406d8303