Schwartz-Zippel 引理及其在零知识证明中的应用

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

Schwartz-Zippel 引理指出，如果我们有两个多项式 $p(x)$ 和 $q(x)$，它们的次数分别为 $d_p$ 和 $d_q$，并且 $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)$ 的时间内比较评估值，则会更快。

也就是说，在有限域 $\math...