几乎所有 ZK-Proof 算法都依赖 Schwartz-Zippel 引理来实现简洁性。

Schwartz-Zippel 引理指出，如果我们有两个次数分别为 $d_p$ 和 $d_q$ 的多项式 $p(x)$ 和 $q(x)$，并且如果 $p(x) \neq q(x)$，那么 $p(x)$ 和 $q(x)$ 相交的点的数量小于或等于 $\mathsf{max}(d_p, d_q)$。

让我们来看几个例子。

示例多项式与 Schwartz-Zippel 引理

直线与抛物线相交

考虑多项式 $p(x) = x$ 和 $q(x) = x^2$。它们在 $x = 0$ 和 $x = 1$ 处相交。

它们相交于两点，这是多项式 $y = x$ 和 $y = x^2$ 之间的最大次数。

三次多项式与一次多项式

考虑多项式 $p(x) = x^3$ 和 $q(x) = x$。这些多项式在 $x = -1$、$x = 0$ 和 $x = 1$ 处相交，而在其他任何地方均不相交。交点的数量受多项式最大次数的限制，在本文例子中为 3。

有限域中的多项式与 Schwartz-Zippel 引理

Schwartz-Zippel 引理同样适用于有限域中的多项式（即所有计算都是在模素数 $p$ 的情况下进行的）。

多项式相等性测试

我们可以通过检查两个多项式的所有系数是否相等来测试它们是否相等，但这需要 $\mathcal{O}(d)$ 的时间，其中 $d$ 是多项式的次数。

相反，如果我们在一个随机点 $u$ 处对多项式进行求值，则可以在 $\mathcal{O}(1)$ 的时间内比较求值结果。

也就是说，在有限域 $\mathbb{F}_{p}$ 中，我们从 $[0,p)$ 中选择一个随机值 $u$。然后我们计算 $y_f=f(u)$ 和 $y_g=g(u)$。如果 $y_f = y_g$，那么以下两种情况必有其一为真：

1. $f(x) = g(x)$
2. $f(x) \neq g(x)$ 且我们刚好选中了它们相交的 $d$ 个点之一，其中 $d = \mathsf{max}(\deg(f), \deg(g))$

如果 $d \ll p$，那么情况 2 发生的可能性极小，几乎可以忽略不计。

例如，如果域 $\mathbb{F}_{p}$ 的 $p \approx 2^{254}$（比 uint256 略小一点），并且多项式的次数不超过一百万次，那么选中一个交点的概率为

为了让大家对这个数量级有直观的感受：宇宙中的原子数量大约在 $10^{78}$ 到 $10^{82}$ 之间。因此，如果多项式不相等，我们恰好选中一个交点的可能性微乎其微。

使用 Schwartz-Zippel 引理测试两个向量是否相等

我们可以将拉格朗日插值法与 Schwartz-Zippel 引理结合起来，以此来测试两个向量是否相等。

通常情况下，我们会通过比较两个向量中 $n$ 个分量是否各自相等来测试向量的相等性。

但是，如果我们使用一组公共的 $x$ 值（比如 $[1,2,..,n]$）来对向量进行插值：

1. 我们可以为每个向量插值出一个多项式 $f(x)$ 和 $g(x)$
2. 选取一个随机点 $u$
3. 在 $u$ 处对多项式求值
4. 检查是否 $f(u) = g(u)$

尽管计算多项式的工作量更大，但最终检查的计算成本要低得多。

下面是一个使用 Python 执行此计算的示例：

Copy
import galois
import numpy as np

p = 103
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

# arbitrary vectors
v1 =  GF(np.array([4,8,19]))
v2 =  GF(np.array([4,8,19]))


def L(v):
    return galois.lagrange_poly(xs, v)

p1 = L(v1)
p2 = L(v2)

import random
u = random.randint(0, p)

lhs = p1(u)
rhs = p2(u)

# only one check required
assert lhs == rhs

在 ZK Proofs 中使用 Schwartz-Zippel 引理

我们的最终目标是让证明者（prover）向验证者（verifier）发送一小段数据，以便验证者能够快速进行检查。

大多数情况下，ZK proof 的本质就是一个在一个随机点上求值的多项式。

我们需要解决的难点在于，我们不知道多项式是否被诚实地求值——我们必须以某种方式确信证明者在计算 $f(u)$ 时没有说谎。

但在讨论这个问题之前，我们需要学习如何将整个算术电路表示为在一组随机点处求值的少量多项式，这正是引入二次算术程序（Quadratic Arithmetic Programs）的动机所在。