Source: https://rareskills.io/zh-cn/post/schwartz-zippel-lemma

几乎所有 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)$ 。

<aside> 💡 💡 一句话理解：两条不一样的曲线，最多只能在『有限的几个点』上碰头，碰头次数不会超过它们里头次数更高的那条。打个比方：一条直线 $y=x$ 和一条抛物线 $y=x^2$，你画出来它们最多交在 2 个点（这里抛物线是 2 次，所以上限就是 2）。反过来想——如果两条曲线在『很多很多』点上都重合，那它们其实就是同一条曲线。这个朴素的事实，正是后面所有把戏的地基。

</aside>

让我们来看几个例子。

示例多项式与 Schwartz-Zippel 引理

直线与抛物线相交

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

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

直线 y=x 与抛物线 y=x² 在 x=0 和 x=1 两点相交

<aside> 💡 💡 为什么交点数正好等于最高次数：『求两条曲线的交点』本质上就是解方程 $p(x)=q(x)$，也就是 $x^2-x=0$。一个 $n$ 次方程最多有 $n$ 个根，所以交点也最多 $n$ 个。这里 $x^2-x=0$ 是 2 次方程，解出来 $x=0$ 和 $x=1$，正好两个，一个不多一个不少。

</aside>

三次多项式与一次多项式

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

三次多项式 y=x³ 与直线 y=x 在 x=-1、0、1 三点相交

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

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

多项式相等性测试

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

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

<aside> 💡 💡 这里最划算的地方：要判断两个多项式是否相等，老办法是把两边的系数一个一个对——次数有一百万，就要对一百万次（这就是 $\mathcal{O}(d)$）。新办法是随便挑一个数 $u$ 代进去，各算出一个值，只比这一个值相不相等（这就是 $\mathcal{O}(1)$）。好比对比两本厚书是不是同一本：与其逐字逐句核对，不如双方都翻到同一个随机页码、念出那一行，听一句就够了。

</aside>