Summary.
4.5 PLONK 风格的 ZK-SNARK 证明系统的工作原理
在 ZK-SNARK 证明系统中，我们采用了改进的交互式预言证明方法来证明见证人的知识，该方法使用多项式承诺为证明者的消息提供预言访问，并通过 Fiat-Shamir 启发式使其无需交互。在这一部分，我们将详细描述给定的构造器。
请记住，将 ZK-SNARK 证明系统应用于算法需要构建相应的约束系统。为了能够构建它，我们定义了算法执行跟踪表的结构以及其中的常数值。我们使用“电路”这个术语来指代仅填充常数的执行跟踪表的复杂结构以及相应的约束系统。为了生成算法执行实例的 ZK-SNARK 证明，我们需要为其合成一个电路实例，这是算法电路和执行跟踪表（即，指定常数、证人和公开声明值的表）的相应实例的组合。
让我们考虑一下 PLONK 风格的 ZK-SNARK 证明系统所使用的跟踪表的结构。这样的表中的所有列都属于三种类型之一，我们按照 Halo2 中使用的术语来命名和描述：
固定列 - 它们的单元格包含来自执行跟踪表的常量；
实例列 - 用于存储公共声明值；
建议栏 - 存储所有证人数据的地方（包括独立的证人值和计算出的秘密结果）。
总的来说，我们注意到以下几点：
执行跟踪表（PLONKish 类型）= 固定列 + 实例列 + 提案列；电路 = 执行跟踪表 + 仅包含常量的约束系统；电路实例 = 电路 + 其表中的证人 + 其表中的公开声明；合成：（电路，公开声明，独立证人值）→ 电路实例；将 ZK-SNARK 证明系统应用于某一算法 = 描述电路 + 定义合成过程。
为什么在这种情境下广泛使用“电路”这个术语呢？最初，当只有基于 R1CS 的 ZK-SNARK 证明系统可用时，将约束系统以算术电路的形式表示是方便的，其输出必须为零。我们认为，在 PLONKish SNARKs 的情境下，“电路”这个词出于历史原因而被使用。不管怎样，让我们简要考虑一下用于早期版本的 ZK-SNARK 的算术电路。
基于 R1CS 的 SNARKs 的算术电路定义了一个有限域上的 n 变量多项式，并具有一个评估方案。最初，它被表示为一个有向无环图（DAG）：
it includes:
公共输入 x，用于指定公共声明值；
用于指定独立见证值的秘密输入 w；
用于指定有限域上的加法和乘法的算术门。
让我们来看一个关于有理数领域的算术电路的例子。
我们从底部开始，处理图表中最低的门，即（2 x 4 = 8）和（4 + 11 = 15），将这些值保存为中间值；
然后我们向上移动一行（到第二行），计算两个中间值的总和（这是我们在上一阶段得到的），即（8 + 15 = 23）；
由于我们只有三个门，而我们已经通过了它们所有，所以 23 是我们的最终输出。
在 PLONK 式的 ZK-SNARK 证明系统合成电路实例后，每个实例执行追踪表的列会以以下方式被编码为有限域上的多项式。假设 C_j(x) 是描述第 j 列的多项式，ω是 2^k 次的原始根，其中 k 被选定为使 2^k 略大于表实例的初始高度。表实例被填充了随机行（只在建议的列中有非零单元格）以包含 2^k 行，且 C_j(ω^i) 被设定为给定表实例的第 j 列的第 i 行的值。零知识属性的填充作用将在后面解释。
该声明“ω是原始根 2^k 次方”意味着ω^(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_m(x) 中建议的列多项式和商多项式 T(x) 满足这个多项式方程。验证者可以让验证者在验证者从 Z(x) 的非根点ζ中随机选择的点处评估给定的多项式，并在该点ζ处评估等式的两边。我相信证明者可能知道这些多项式。这种方法可以通过 Schwartz-Zippel 引理来证明。
为了使证明生成非交互式，交互版本中由验证者生成的所有随机值都应使用 Fiat-Shamir 启发式来获取。
为了将证明者与其提案多项式和商多项式 T(x) 绑定，我们使用了一个多项式承诺方案。证明者对这些多项式做出承诺，在ζ（或在ζ ω^q 上，如果某些约束影响到行 i 和 i + q）处打开这些承诺，并创建一个包含（I）这些承诺，（II）多项式在ζ（或在ζ ω^q 上，如果需要）的值，以及（III）相应的开放证明的证明。实际上，为了使证明更短，使用多次开放，即为所有多项式点的值生成一个小的证明。因此，证明是直接的。
为满足零知识性质，证明者随机选择的行被添加到执行跟踪表的一个实例中，使其高度达到 2^k 行。这些行只在建议的列中有非零的单元格，因为只有建议的列包含我们想要隐藏的数据。在构建提案列多项式之前做这个，以便在承诺开放期间揭示的“参数值”对的数量小于每个多项式随机添加的对的数量。因此，对于每个提案列多项式，承诺开放后恢复它所需的信息量大于见证信息的量。这种情况导致了零知识。
在预处理阶段，执行电路的所有实例都会进行一些相同的计算，包括设定和计算多项式承诺方案的固定列多项式及其承诺。这些计算产生的数据部分被验证者使用，通常被称为验证密钥。同样，可以定义出一个证明密钥的概念。基础的多项式承诺方案决定了在预处理阶段是否进行信任设置。
评论