1.介绍
ZK-SNARK是一种加密证明系统，它允许某个实体证明某个事物为真，而无需透露其他信息。
ZK-SNARK在多个应用和领域中都非常有用，例如区块链和可验证计算。一个显著的区块链应用是在ZK-Rollups中使用。
ZK-Rollups是建立在其他区块链（如以太坊）之上的第二层区块链，利用ZK-SNARK（或其他加密证明系统）来证明状态转换的有效性。也就是说，每次进行新的网络更新（添加新的交易批次）时，都会计算新的网络状态，并生成此状态有效性的证明。关键是，只需要一个实体生成此证明，之后任何人都可以相信其有效性。
ZK-Rollups提供的期望属性通常是（i）可扩展性和/或（ii）隐私保护。当仅需要可扩展性时，ZK-Rollups有时被称为有效性Rollups。
为了计算设计用于扩展以太坊EVM的ZK-Rollups中的证明，可以使用ZK-EVM。严格定义上，ZK-EVM是一组加密程序（电路），负责生成零知识证明（ZKP），尽管有时口语上也指EVM-capable通用ZK-Rollup的整体。
2.ZK-SNARK定义
SNARK是一个简洁的证明，证明某个陈述为真。形式上，它证明了算法执行跟踪的知识，该跟踪生成了某个问题的正确解。更确切地说，它证明了执行跟踪的非公共和非恒定值的知识。这些值作为一个整体通常被称为证人。证人的元素，也就是算法输入的部分，构成独立的证人，因为它们在算法执行之前存在，并且不由执行跟踪的其他元素确定。执行跟踪的公共非恒定值，指定了算法解决的问题实例，我们称之为公共陈述。
ZK-SNARK代表零知识简洁非交互式知识论证。
S - 简洁
简洁 - 证明是“短的”，并且验证时间是“快的”：
“短”证明意味着证明的大小是子线性的，相对于证人的大小。
“快”验证时间意味着验证者的运行时间应该（i）是证人大小的子线性，且（ii）是公共声明的线性。
但事实上，我们希望它不仅“简洁”，而且是“对数多项式级别”。
这意味着证明大小和验证时间几乎与证人的大小无关。
证明π的大小应该不会比证人w的大小的对数的平方的某个常数倍增长得更快（对于足够大的w）：
证明的大小取决于特定的ZK-SNARK协议。对于Plonky2，它是O(log^2(|w|))，但这是“最坏”的情况。例如，对于经典的PLONK和Groth16，证明的大小为O(1)，即一个常数。
验证时间t_v应不超过某个常数乘以witness w的对数的平方，并且与公共声明x的大小呈线性关系（当只有它们中的一个改变其大小时，x和w足够大）。
N - 非交互式 - 证明生成是在不从验证者那里接收任何数据的情况下进行的。
ARK - 知识证明 - 类似于常规证明，但声音只针对多项式有界的证明者保持，而在证明中，声音针对计算上无限制的证明者保持。我们将在下一部分讨论声音的概念。
ZK - 零知识 - 不披露见证人。
3.ZK-SNARKs的属性
ZK-SNARKs有三个主要的属性，如下所述：
完备性：如果证明者知道算法的正确执行轨迹，那么验证者必须相信证明者拥有这种知识。
知识声音性：除非证明者确实知道正确的执行轨迹，否则证明者无法说服验证者知道它，但存在一些非常小的概率。
零知识性：验证者不知道执行轨迹的任何知识，除了它是正确的。
4.PLONKish ZK-SNARK证明系统
4.1简介 PLONKish ZK-SNARKs 及其作用
为了应用于某个算法，ZK-SNARK证明系统需要了解有限域上的方程系统，这些方程描述了该算法的执行轨迹表中数值之间的关系（存储执行轨迹的数据结构），以确保计算的完整性。用于表达这个方程系统（也称为约束系统）的语言称为算术化。
与旧的证明系统相比，PLONKish ZK-SNARK证明系统使用具有更高表达能力的算术化。第一个允许我们使用约束变量上任意多项式形式的约束系统方程，而对于旧的证明系统（即基于R1CS的系统）这些方程的形式为线性和二次多项式。这个特性使得PLONKish ZK-SNARK证明系统对证明者的计算效率产生了积极影响，并使其更容易应用于各种算法。因此，近年来出现了许多PLONKish ZK-SNARK证明系统，如经典PLONK、Halo2、Kimchi、Plonky2、HyperPlonk等。
在Taiko中，我们使用基于KZG多项式承诺方案的Halo2证明系统的变种。
PLONKish ZK-SNARK证明系统由三个组件组成：
4.2 承诺方案
承诺方案允许提交者发布一个值，称为承诺，将提交者与一条消息绑定而不透露消息本身。之后，提交者可以打开承诺并向验证者公开承诺的消息或其某部分，验证者可以检查所公开的信息是否与承诺一致。
不同的作者描述了组成承诺方案的不同算法数量。然而，我们应该至少提到其中的四个算法：
设置：以一些初始参数为输入并生成设置参数。设置指定了（i）我们承诺的对象（例如，对于一元多项式承诺方案，我们指定系数域和我们承诺的多项式的最大次数），以及（ii）以比特为单位的安全级别。 我们可以简单地定义安全级别如下：如果破解一个加密系统需要 O(2^n) 时间，则该加密系统具有 n 比特的安全级别。
承诺：根据设置参数生成消息的承诺。
部分打开：生成特定于消息中所选部分的部分打开证明（例如，针对某个参数的已承诺一元多项式的值），以及设置参数。
验证：使用部分打开证明和设置参数来检查由证明人公开的信息是否是与指定的承诺相对应的消息的指定部分。
*对于一些承诺方案，“设置（setup）”和“打开（open）”算法可能不存在（例如，在使用哈希函数承诺大数值时）。
承诺方案应具备以下特性：
绑定（Binding）：一旦证明者承诺特定的消息，它将与它承诺的消息绑定在一起；
隐藏（Hiding）：承诺不透露有关消息的任何信息。隐藏可以是完美的，即部分打开证明不透露有关消息的未查询部分的任何信息（例如KZG承诺），也可以是非完美的，即部分打开证明揭示了前述信息的某些部分（例如基于FRI的多项式承诺）。
承诺方案可以根据目标对象分为几种类型：单个元素承诺； 集合承诺； 向量承诺； 多项式承诺。
多项式承诺方案是直接用于 PLONKish ZK-SNARK 证明系统的唯一类型。对于上述证明系统（如 classic PLONK、Halo2、Kimchi、Plonky2 等），单变量多项式承诺方案非常重要。然而，现在出现了一些基于多线性多项式承诺方案的新型 PLONKish ZK-SNARK 方法（例如 HyperPlonk）。
4.3 交互式Oracle证明
交互式Oracle证明是一种交互证明，其中验证者可以“访问Oracle”以获得证明者的消息，可以以概率方式对它们进行查询，并不需要读取整个证明者的消息。
4.4 Fiat-Shamir启发式
Fiat-Shamir启发式提供了一种将（公共硬币）交互式论证转化为非交互式论证的方法。直观地说，这个想法是用先前消息的哈希值替换验证者的随机挑战，但具体细节通常未指定。
*公共硬币协议是一种协议，其中验证者只发送随机元素。
4.5 PLONK式ZK-SNARK证明系统的工作原理
在ZK-SNARK证明系统中，使用改进的交互式Oracle证明方法来证明见证人的知识，该方法使用多项式承诺提供对证明者消息的Oracle访问，并通过Fiat-Shamir启发式使其无需交互。在本节中，我们将详细介绍给定的构造方法。
回想一下，将ZK-SNARK证明系统应用于某个算法需要构建相应的约束系统。为了能够构建它，我们定义该算法的执行跟踪表的结构和其中的常量值。我们使用术语“电路”来表示仅填充常量的执行跟踪表的复杂结构以及相应的约束系统。为了为某个算法的执行实例生成ZK-SNARK证明，我们需要为它合成电路实例，该实例是算法的电路和执行跟踪表的相应实例（即指定了常量、见证和公共声明值的表）的组合。
让我们考虑PLONK式ZK-SNARK证明系统使用的跟踪表的结构。这样一个表格中的所有列都属于三种类型之一，我们根据Halo2中使用的术语命名并描述如下：
固定列 - 它们的单元格包含执行跟踪表的常量；
实例列 - 用于存储公共声明值；
建议列 - 所有见证数据都存储在其中（包括独立的见证值和计算的秘密结果）。
总结一下，我们注意到以下几点：
执行跟踪表（PLONKish类型）= 固定列 + 实例列 + 建议列； 电路=仅包含常量的执行跟踪表+约束系统； 电路实例=电路+其表中的见证+其表中的公共声明； 合成：（电路、公共声明、独立见证值）→电路实例； 将ZK-SNARK证明系统应用于某个算法=描述电路+定义合成过程。
为什么在这种情况下广泛使用“电路”这个术语？最初，当只有基于R1CS的ZK-SNARK证明系统可用时，用算术电路的形式表示约束系统是方便的，其输出必须为零。我们认为，在PLONKish SNARKs的上下文中，“电路”这个术语出于历史原因而被使用。无论如何，让我们简要地考虑一下用于旧版ZK-SNARK的算术电路。
用于基于R1CS的SNARKs的算术电路定义了一个有限域上的n变量多项式，并具有一个评估方案。最初，它表示为有向无环图（DAG）：
它包括：
公共输入x，用于指定公共声明值；
秘密输入w，用于指定独立见证值；
算术门，用于在有限域上指定加法和乘法。
让我们看一个有理数域上的算术电路的例子。
我们从底部开始处理图中最低的门，即（2 x 4 = 8）和（4 + 11 = 15），将这些值保存为中间值；
然后我们向上移动一行（到第二行），计算两个中间值的总和（我们在上一个阶段获得的），即（8 + 15 = 23）；
由于我们只有三个门，而且我们经过了所有的门，所以23是我们的最终输出。
在 PLONKish ZK-SNARK 证明系统合成电路实例后，每个实例执行跟踪表的列都按以下方式编码为有限域上的多项式。假设 C_j(x) 是描述第 j 列的多项式，ω 是原根 2^k-th，其中 k 被选择为使 2^k 稍微大于该表实例的初始高度。表实例用随机行填充（仅在建议列中具有非零单元格），以包含 2^k 行，并将 C_j(ω^i) 设置为给定表实例的第 j 列的第 i 行的值。填充对于零知识属性的作用将在后面解释。
语句“ω 是原根 2^k-th”意味着 ω^(2^k) = 1，并且对于任何小于 2^k 的正整数 t，我们都有 ω^t ≠ 1。
约束系统通过将其中的变量替换为从列多项式获得的相应多项式，通过将“x 乘以 ω 的某个幂次方”代替 x 而被转化为多项式方程形式。
例如，让我们考虑约束系统方程 s(i) * (a(i) * b(i) - c(i+1)) = 0。它意味着如果 s(i) 非零，那么 a(i) * b(i) 必须等于 c(i+1)。在这里，a、b 和 c 是建议列，s 是固定列，i 是当前行号。
这个约束可以应用于所有 2^k 行，方式如下。让 S(x)、A(x)、B(x) 和 C(x) 分别为列 a、b、c 和 s 的多项式。因此，我们希望：
这意味着这个集合中的所有元素必须是 S(x) * (A(x) * B(x) - C(x * ω)) 的根。因此，这个多项式必须被下式整除：
因为ω是一个2^k阶原根。
Z(x) = x^(2^k) - 1被称为“消失多项式”，因为它对于所有作为ω生成的循环乘法群元素的x都为0。因此，S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0意味着上述约束对于所有2^k行都成立。
假设P_0(x), P_1(x), ... , P_m(x)是应用于所有2^k行的约束，并且与上面考虑的多项式S(x) * (A(x) * B(x) - C(x * ω))形式相似。如果α是由验证者从有限域随机选择的，则
这意味着以极高的概率所有这些约束条件都对所有2^k行都得到满足。这个等式意味着我们可以找到一个商多项式T(x)，使得
因此，为了让验证者相信证明者以极高的概率知道满足所有m个约束条件的执行跟踪表的内容，只需证明对于随机选择的α，证明者拥有出现在P_0(x)、P_1(x)、...、P_m(x)中的建议列多项式和商多项式T(x)，满足此多项式方程。验证者可以通过要求证明者在验证者从Z(x)的非根点ζ中选择的随机点上求出给定多项式的值，并在该方程的两侧在该点ζ上进行评估来使自己相信证明者很可能知道这些多项式。此方法可以通过Schwartz-Zippel引理进行证明。
为了使证明生成非交互式，所有在交互式版本中由验证者生成的随机值都应使用Fiat-Shamir启发式获得。
为了将证明者绑定到其建议多项式和商多项式T(x)，使用多项式承诺方案。证明者对这些多项式进行承诺，在ζ（如果某个约束条件影响行i和i + q，则在ζ * ω^q上）处打开这些承诺，并创建证明，其中包括（I）这些承诺，（II）多项式在ζ（如果需要则在ζ * ω^q上）处的值以及（III）相应的开放证明。实际上，为了使证明更短，使用多重打开，即为所有多项式点的值生成一个小证明。因此，该证明是简明的。
为了满足零知识属性，证明者随机选择的行被附加到执行跟踪表的实例中，使其高度为2^k行。这些行仅在建议列中具有非零单元格，因为只有建议列包含我们要隐藏的数据。在构造建议列多项式之前进行此操作，以使在承诺开放期间揭示的“参数值”对的数量小于每个多项式的随机添加对的数量。因此，对于每个建议列多项式，在承诺开放后恢复它所需的信息量大于证人信息量。这种情况导致零知识。
在预处理阶段，执行电路的所有实例都要进行一些相同的计算，包括为多项式承诺方案设置和计算固定列多项式及其承诺。这些计算所产生的数据部分，被用于验证者，通常被称为验证密钥。类似地，可以定义证明密钥的概念。底层的多项式承诺方案决定了在预处理阶段是否进行可信设置。
