# 泡菜证明初步之PLONK
:::info
原文地址：https://eng-blog.o1labs.org/posts/plonk/
作者：Anaïs Querol
译者：Kurt Pan
:::

Kimchi 是我们新的无需信任的 zkSNARK，它基于[PLONK](https://eprint.iacr.org/2019/953.pdf)证明系统和[Bulletproofs](https://eprint.iacr.org/2017/1066.pdf)承诺方案。这篇文章的目的是缓解阅读上述论文后产生的症状。毕竟，PLONK精心挑选的缩写（_Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge_）绝不仅仅是一个有趣的巧合：让我们试着把一瓶 plonk（英式英语：廉价酒） 变成一杯美酒🍷，然后干杯🍻！

[TOC]
## Kimchi

通常，人们需要一些白菜、盐和香料来烹制自制泡菜。在 O(1) Labs，我们的Kimchi食谱略有不同：我们将使用以下三个论证系统来代替上述主要成分。

- **自定义门（Custom gates）**：这些是我们要品尝的香料。不同的配置（口味）将得到不同的Kimchi。更正式点说，根据我们想要证明的计算类型，我们将选择不同的自定义门来创建电路。
- **排列（Permutation）**：就像白菜一样，这是将泡菜的味道融合在一起的部分，它使泡菜成为一道菜，而不仅仅是一些不相交的简单成分。更正式点说，排列论证执行门之间的*连线*（即从输入和到输出的连接），表示执行迹（execution trace）中单元之间的复制约束（copy constraints）。
- **查找表（Lookup tables）**：再加点盐虽非必要，但会使结果脱颖而出。出于效率原因，我们可以使用查找表。一些公共信息（例如布尔函数）可以由双方（证明者和验证者）存储，而不是硬连线在电路中。

所有这些论证系统都被翻译成等式，这些等式必须对整个关系的正确证据（witness）成立。等价地，就是说这些表达式需要在一组特定数上求值为零。在烹饪泡菜之前，我们应该确保我们知道所涉及的流程。所以这里有两个问题需要解决：

1. **根检验 （Roots-check）**：确保各组分通过一些质量测试，正式说即查验方程在一组数上的求值为零。
2. **聚合（Aggregate）**：检验**所有**成分，即每个方程都必须满足上述条件。


下面，我们将使用符号$\mathbb{F}$指代一个*有限域*。你可以将其理解为其中元素像钟表🕙一样运行的数学结构，意思是域中的最大元素会回绕到最小元素（类比12点和0点指向一个位置）这些域的一个我们关心的良好属性是这些域中的数字不能无限增长，它们总是会保持在一个范围内（称为域的*阶*）。而且，代数仍然成立（我们称之为*模代数*）。有一个小点要注意一下，有限域的阶必须是素数或素数的幂。所以让我们带上你的 13 小时计时器，开始制作泡菜吧！

### 根检验
对第一个问题，给定一个阶为$d$的多项式，要求对一个集合$S$（一系列数）中的所有元素$x$检验$p(x)=0$ 。当然，你可以手动对集合中的所有元素求值，然后确保上述论断的正确。 但是那会花费太长时间（即不简洁）。反之，我们想要一次检验所有的方程。 一个很好的方法是通过使用**归零多项式**（vanishing polynomial）。这种多项式$v_{S}(X)$ 不过是在$S$上求值为0的最小多项式，意即刚好由下列单项式乘积构成的阶为$|S|$ 的多项式：
$$
v_{S}(X)=\prod_{s \in S}(X-s)
$$

为什么这个有用呢？ 首先我们需要做一个关键的观察。因为归零多项式在每一个$x \in S$上都等于0，且为满足该性质的最低阶多项式，如果我们的起始多项式$p(X)$ 在$S$上求值为0，那么$p(X)$ 一定是归零多项式$v_{S}(X)$的*倍数*。但这在实践中意味着什么？ 通过多项式除法，这意味着存在一个次数为 $d-|S|$ 的**商多项式**，使得：
$$
q(X):=\frac{p(X)}{v_{S}(X)}
$$

如果你能提供这样一个商多项式，你可以很容易地对一个随机数$a \in \mathbb{F} \backslash S$（不能在集合中，否则会得到$0/0$）检查 $q(a)=p(a) / v_{S}(a)$ 是否成立，如果是那么以很高概率意味着实际上 $p(X)=q( X) \cdot v_{S}(X)$，即$p(X)$ 在整个集合$S$ 上求值为0，注意这里我们只检查了一点！

让我们更深入地了解这里发生的“魔法”。 首先，我们所说的“以很高概率”是什么意思呢？ 这足够好吗？ 这个问题的答案是：与你想要的一样好。

1. 首先我们来分析这个检验的数学。如果$p(X)=q(X) \cdot v_{S}(X)$ 确实成立，那么对于任意可能的 $a \in \mathbb{F} \backslash S$ ，检验$p(a) \stackrel{?}{=} q(a) \cdot v_{S}(a)$ 一定成立。但是否有任何不幸的点实例使得$p(a)=q(a) \cdot v_{S}(a)$ ，但是$p(X) \neq q(X) \cdot v_{S}(X)$ 呢？答案是，有这样的点，但，没有很多。但到底有多少呢？有多不可能呢？你已经知道这个的答案了：**Schwartz-Zippel**。回顾该引理：
> 给定两个$d$阶不同的多项式$f(X)$ 和$g(X)$ ，他们至多相交于（*一致*于）$d$个点。或者等价地，另 $h(X):=f(X)-g(X)$，多项式$h(X)$可以至多在$d$个点求值为0（其根）。

因此，如果我们令 $p(X) \rightarrow f(X)$ ，$q(X) \cdot v_{S}(X) \rightarrow g(X)$ ，阶都为 $d$，则有至多 $\frac{d}{|F-S|}$ 个不幸的点 $a$ 可以诱使你认为 $p(X)$ 是归零多项式的倍数（因此在所有 $S$ 上的点都等于0）。那么，如何才能使这个错误概率可忽略呢？ 通过足够大的域大小（形式化定义是其大小的倒数应该比任何多项式表达式减小得更快）。 由于我们正在使用大小为 $2^{255}$ 的域，因此我们是安全的！

2. 其次，这真的比检查对所有 $x \in S$ 是否 $p(x)=0$ 更快吗？ 归根结底，我们似乎需要求值 $v_{S}(a)$，并且由于这是一个 $|S|$阶多项式，看起来我们仍在执行大约相同数量级的计算。 数学在这里又来救场了。 在实践中，我们希望将这个集合 $S$ 定义为具有良好的结构，使我们能够比使用任意数的集合更有效地执行一些计算。 实际上，这个集合通常是一个**乘法群**（通常表示为 $\mathbb{G}$ 或 $\mathbb{H}$ ），因为在这样的群中，归零多项式 $v_{\mathbb{G}}(X) :=\prod_{\omega \in \mathbb{G}}(X-\omega)$ 有一个有效的表示 $v_{\mathbb{G}}(X)=X^{|\mathbb{G}|} -1$，这相比于上述乘积求值速度要快得多。

3. 第三，我们可能想了解对 $p(a)$ 的求值会发生什么。由于这个阶 $d \geq|\mathbb{G}|$，看起来这也需要很多努力。但这就是密码学发挥作用的地方：验证者永远不会自己求值实际多项式有如下各种原因。第一，如果验证者可以访问完整的多项式 $p(X)$，那么证明者应该将该多项式与证明一起发送，这将需要 $d+1$个系数表示（对于一个SNARK来说这将不再简洁）。第二，这个多项式可能会携带一些秘密信息，如果验证者可以重新计算它的求值，他就可以通过在特定点求值来知道一些私有数据。因此，这些求值将只能成为“心理游戏”，这要归功于证明者发送的**多项式承诺**和**求值证明**（对他们来说，$d$ 数量级的计算不仅是可以接受的，而且是必要的）。实际证明长度将在很大程度上取决于我们使用的多项式承诺的类型。例如，在类Kate的承诺中，对多项式承诺会有常数数量的群元素（通常是一个），而在 Bulletproofs 中是对数个。但无论如何，这将比发送 $O(d)$ 个元素要短。
### 聚合
到目前为止，我们已经看到了如何只需一个点来检验在所有 $\mathbb{G}$ 上多项式是否等于 0。 这在某种程度上本身就是一种聚合。 但是对于多个多项式，我们要分析如何来证明这件事。 总而言之，如果它们成立，这将意味着多项式编码了一个正确的证据，且关系将得到满足。 这些检查可以一个一个地执行（检查每个商是否确实正确），或者使用有效的聚合机制并一次只检查*一个更长的方程*。

那么，执行这个一次性检查的最简单方法是什么？ 也许有人可以想到将所有方程 $p_{0}(X),\ldots, p_{n}(X)$ 加起来成为更长的方程 $\sum_{i=0}^{n } p_{i}(X)$。 但是这样做会使得有些项相互之间抵消，从而可能会得到一个不正确的陈述。

因此相反，我们可以将求和中的每个项乘以一个随机数。 这个技巧起作用的原因是随机数之间的独立性。 也就是说，如果两个不同的多项式 $f(X)$ 和 $g(X)$ 在给定的 $X=x$ 上都等于 0，那么同样的 $x$ 以很大概率会成为随机组合$\alpha \cdot f(x)+\beta \cdot g(x)=0$的一个根。 如果应用于整个语句，我们可以将 $n$ 个方程转换为单个方程，
$$
\bigwedge_{i_{n}} p_{i}(X) \stackrel{?}{=} 0 \Longleftrightarrow \text { w.h.p. } \sum_{i=0}^{n} \rho_{i} \cdot p_{i}(X)\stackrel{?}{=} 0
$$
到目前为止听起来都不错。 但是我们忘记了证明系统的一个重要部分，即证明长度。 为了使上述声明具有可靠性，用于聚合的随机值应该是验证者选择的，或者至少是独立于证明者的。 因此，如果验证者必须与证明者沟通以告知正在使用的随机值，我们将得到 $n$ 个域元素的开销。

相反，我们可以使用另一种称为「**阿尔法之幂**」的技术。 在这里，我们假设一个随机值的幂 $\alpha^{i}$ 与实际的另一个随机值 $\rho_{i}$ 无法区分。 然后，我们可以将上述声明调整为仅使用一个与证明者协调一致的随机元素 $\alpha$ ：
$$
\bigwedge_{i_{n}} p_{i}(X)\stackrel{?}{=} 0 \Longleftrightarrow \text { w.h.p. } \sum_{i=0}^{n} \alpha^{i} \cdot p_{i}(X)\stackrel{?}{=} 0
$$

## 门
在上一节中，我们看到了如何非常有效地证明特定的方程在给定的数字集合上成立。 剩下要了解的是这些技术背后的动机。 为什么我们可以执行这些操作如此重要，这些方程在现实世界中代表什么？

首先，让我们回顾一下这张总结了一些重要记号的表格：

我们必须掌握的第一个想法是**电路**的概念。 一个电路可以被认为是一组用电线连接它们的门。 能想到的最简单的电路类型是布尔电路。 布尔电路只有二进制值：1 和 0，真和假。 从非常高的层次来看，布尔电路就像一个复杂的管道网络，其值可以被视为有水或无水。 然后，门将像旋塞阀一样，使水在管道之间流动或不流动。 然后，每一个反应都将表示为一个门（即逻辑门）。 可以有可以执行更多操作的电路，例如算术电路。 这里，可用的门类型将是算术运算（加法和乘法），线可以具有数值，可以执行任意计算。

如果再动动脑筋，就可以构想出一个可以同时表示任何算术运算的“通用”门。 这种仔细构想的门就是在 Plonk 中使用其串联来描述任何关系的门。 除了线路之外，这些门还与一组有助于描述功能的**系数**相关联。但是这个门的问题在于它需要大量的该门来表示任何有意义的函数。 因此，最近出现了类 Plonk 的证明系统，它使用**自定义门**来更有效地表示重复使用的功能，而不是使用一系列相互连接的通用门。 Kimchi就是这些协议之一。 目前，我们支持如下操作的特定门：Poseidon 哈希函数、曲线点的 `CompleteAdd` 操作、变量基数乘法的 `VarBaseMul`、自同态变量基数标量乘法的 `EndoMulScalar` 以及 `ChaCha` 加密原语。

电路结构是提前知道的，因为这是与验证者共享的公共信息的一部分。秘密的是我们称之为一个关系的**证据**，它是满足所有检验的电路的输入和线路的正确实例化。这意味着验证者知道电路的每个部分出现什么类型的门，以及附在每个部分的系数。

门在矩阵中按行排列，列数根据需要加入（Plonk 需要 3列，而 Kimchi 目前使用 15列）。**执行迹**是指在证据实例化下整个电路中所有线路的状态。它将表示为一个表格，其中行对应于每个门，列指的是门的实际线路（也称为**输入和输出寄存器**）和计算所需的一些辅助值（也称为**建议寄存器**）。 Kimchi 的当前实现总共考虑了 15 列，前 7 列对应于 输入/输出寄存器。 排列论证作用于输入/输出寄存器（意思是，它将检查执行迹的前 7 列中的单元格是否正确复制到其目标单元格）。因此，这些检验也称为**复制约束**。

> 令 3 个 Plonk 列的证据为 $w_{L}、w_{R}$ 和 $w_{O}$，分别指左、右和输出。 与左、右、输出、乘法和标量的系数 $c_{L}、c_{R}、c_{O}、c_{M}、c_{S}$ 一起，可以将通用算术运算表示为
$$
0=c_{L} \cdot w_{L}+c_{R} \cdot w_{R}+c_{O} \cdot w_{O}+c_{M} \cdot w_{L} \cdot w_{R}+c_{S}
$$

系数充当二元选择器，但标量系数可以是任何常数。例如，加法可以通过关闭乘法选择器 $c_{M}$ 来表示。

回到该方案的主要动机，回想一下，我们想检验特定方程在给定的一组数字集合中是否成立。以下就是这种声明开始有意义的地方。执行迹中的总行数将为我们提供一个**求值域**。也就是说，我们定义了执行迹的每个行索引和乘法群 $\mathbb{G}$ 的元素之间的映射，该乘法群的元素与表中的行一样多。这里需要注意两点。首先，如果不存在这样的群，我们可以用零填充。其次，任何乘法群都有一个生成元$g$，它的幂生成整个群。然后我们可以为每一行分配 $g$ 的幂。我们为什么要这样做？因为这将成为我们要检查方程的那个集合：我们可以将关于群元素的声明转换为一个“这些属性对该表的每一行都适用”的声明。很有趣，对吧？