在影子里验证比较对象：随机指纹和哈希的数学原理

程序里经常会遇到一种看似朴素、实际很贵的问题：两个东西是不是一样？

它可能是两个字符串、两个文件、两个集合、一段文本里的子串，或者三个矩阵是否满足 $A \cdot B = C$。如果对象本身很大，尤其是在对象需要跨机器通信、被反复比较、以流式方式到达，或者比较结果只需要高概率可靠时，直接逐个字节比较往往不是最想要的方案。

随机指纹法处理的正是这类问题。它不试图完整保留对象，而是把对象映射成一个短得多的值，然后比较这些短值。这个短值可能丢失信息，所以它不是压缩意义上的可逆编码，而更像一个可快速比较的影子。

影子不能替代实体，但如果影子不同，实体一定不同；如果影子相同，实体也许相同，也许只是碰巧投在了同一个地方。随机性的作用，是让这种“碰巧”变得可控。

指纹与哈希

指纹和哈希函数有相似之处。设对象集合为 $\mathcal{O}$，我们从一组映射 $\mathcal{H}$ 中随机选择一个函数 $f$，然后用 $f(O)$ 作为对象 $O$ 的指纹。对于两个对象 $O_1$ 和 $O_2$：

• 如果 $O_1 = O_2$，那么必然有 $f(O_1) = f(O_2)$；
• 如果 $O_1 \ne O_2$，那么大多数 $f \in \mathcal{H}$ 都能让 $f(O_1) \ne f(O_2)$。

第二点是关键。对于输出空间远小于输入空间的固定哈希函数，理论上总会存在碰撞；在非密码学场景下，如果对手知道函数，也可能针对性地寻找碰撞。随机选择函数后，对手很难提前知道我们会拿哪一把尺子去量对象。随机化并不是为了神秘，而是为了把最坏情况变成概率问题。

在算法分析里，能区分 $O_1$ 和 $O_2$ 的函数常被称为 witness，也就是“见证者”。如果某个 $h \in \mathcal{H}$ 满足 $h(O_1) \ne h(O_2)$，那么 $h$ 就见证了 $O_1 \ne O_2$。指纹法的设计目标，就是让见证者足够多，同时让每个指纹足够短。

这两个目标天然冲突。指纹越短，比较越快，通信越省，但碰撞空间也更大；指纹越长，错误概率更低，却离“直接发送原对象”越来越近。许多随机化算法的味道，就藏在这个 trade-off 里。

用随机素数给二进制串取指纹

一切复杂对象都可以映射成二进制数，而一切二进制串又可以看成整数。给定 $x \in \{0,1\}^n$，令 $\mathrm{Number}(x)$ 表示它对应的二进制整数。例如 $1011_2$ 对应十进制的 $11$。

随机选择一个素数 $p$，定义：

$$\mathrm{Finger}_p(x) = \mathrm{Number}(x) \bmod p$$

这个定义非常朴素，但足够有力。如果有 $x$ 和 $y$ 不同，那么 $\mathrm{Number}(x)-\mathrm{Number}(y)$ 是一个非零整数。若它们在模 $p$ 下指纹相等，则有：

$$\mathrm{Number}(x) \equiv \mathrm{Number}(y) \pmod p$$

也就是：

$$p \mid \left(\mathrm{Number}(x)-\mathrm{Number}(y)\right)$$

所以，错误只会发生在随机选中的 $p$ 刚好是这个差值的某个素因子时。一个非零整数的素因子数量有限，而可选素数集合可以通过扩大范围来增加。

于是，只要 $p$ 的可选范围越大，坏素数所占比例就会越低。这就是模素数指纹法的基本逻辑：不是保证没有碰撞，而是让碰撞需要满足一个很具体、很稀疏的条件。

相等判断

考虑一个通信问题。机器 RI 有一个字符串 $x \in \{0,1\}^n$，机器 RII 有一个集合 $U=\{u_1,u_2,\ldots,u_k\}$，其中每个 $u_i$ 也是长度为 $n$ 的二进制串。RI 不知道 $U$，RII 不知道 $x$，它们要判断 $x \in U$。

最直接的方法是 RI 把整个 $x$ 发过去，通信量是 $n$ bit。随机指纹法可以把通信量降到 $O(\log n)$，代价是引入单边错误。

RI:
  choose random prime p from PRIME(n^2)
  s = Number(x) mod p
  send (p, s) to RII
 
RII:
  for each u_i in U:
      q_i = Number(u_i) mod p
 
  if s is equal to some q_i:
      output "x may be in U"
  else:
      output "x is not in U"

这里 $\mathrm{PRIME}(n^2)$ 表示不超过 $n^2$ 的素数集合。因为 $p \le n^2$，发送 $p$ 需要约 $2\log n$ bit；又因为 $s < p$，发送 $s$ 也需要约 $2\log n$ bit。所以总通信复杂度大约是 $4\log n$，也就是 $O(\log n)$。

这个协议的正确性方向很清楚。如果 $x \in U$，设 $x=u_j$，那么对任何 $p$ 都有 $\mathrm{Finger}_p(x)=\mathrm{Finger}_p(u_j)$，协议一定会输出“在集合中”。

错误只可能发生在 $x \notin U$ 时。此时某个 $u_i$ 可能满足：

$$\mathrm{Number}(x) \equiv \mathrm{Number}(u_i) \pmod p$$

也就是一次碰撞。

在 $\mathrm{PRIME}(n^2)$ 的质数选取范围下，错误的概率具体有多大呢？设 $x\notin U$。对每个 $u_i$，令

$$\Delta_i = \left|\mathrm{Number}(x)-\mathrm{Number}(u_i)\right|$$

因为 $x\ne u_i$，所以 $\Delta_i\ne 0$；又因为二者都是 $n$ 位二进制串，所以 $\Delta_i < 2^n$。如果 $x$ 和 $u_i$ 在模 $p$ 下发生碰撞，那么 $p\mid \Delta_i$。

而数论知识还告诉我们，一个小于 $2^n$ 的非零整数最多有 $n$ 个不同的素因子。所以，对一个固定的 $u_i$，能造成碰撞的坏素数最多有 $n$ 个。对所有 $k$ 个元素，坏素数总数最多有 $kn$ 个。

另一方面，不超过 $n^2$ 的素数个数约为

$$\pi(n^2) \sim \frac{n^2}{\ln(n^2)} = \frac{n^2}{2\ln n}$$

所以随机选中坏素数的概率最多约为

$$\frac{kn}{\pi(n^2)} \approx \frac{kn}{n^2/(2\ln n)} = \frac{2k\ln n}{n}$$

这符合直觉：元素数量 $k$ 越多，越容易冲突；而当质数范围取 $n^2$ 时，规模越大越不容易冲突。当

$$k \le \frac{n}{4\ln n}$$

时，错误概率就至多约为 $\frac 12$。

为什么 $\frac 12$ 这个节点这么重要呢？它重要是因为，一旦单次错误概率被压到某个小于 $1$ 的常数，就可以通过独立重复把错误概率指数级压低。重复 $t$ 轮，每一轮都重新选择独立的随机素数，并且只有每一轮都发生碰撞才会误判，那么错误概率最多变成：

$$2^{-t}$$

随着次数增加，错误概率会迅速降低；而只要问题规模较大，$k$ 次实验发送的 $4k\log n$ bit 仍然远小于 $n$ 个全部比特。

这种协议叫 one-sided-error Monte Carlo protocol。它会很快给出答案，但答案只有一个方向是绝对可靠的：如果它说 $x \notin U$，那一定是真的；如果它说 $x \in U$，则可能是碰撞造成的假阳性。

集合不交：碰撞机会按成对数量累积

上面可以问题可以推广。RI 有 $V=\{v_1,v_2,\ldots,v_l\}$，RII 有 $U=\{u_1,u_2,\ldots,u_k\}$，目标是判断 $U \cap V$ 是否为空。

那么思路仍然没有变化，RI 选择一个随机素数 $p$，计算自己每个元素的指纹并发送，RII 也计算自己每个元素的指纹，并和 RI 发送的指纹比较。直接发送整个集合需要 $O(ln)$ bit。使用随机指纹时，RI 只需要发送一次 $p$，再发送 $l$ 个元素的模 $p$ 指纹，通信量变为 $O(l\log n)$ bit。

如果 $U \cap V \ne \emptyset$，真实公共元素一定会产生相同指纹，所以不会漏报。若 $U \cap V = \emptyset$，协议可能因为某一对 $(u_i,v_j)$ 的碰撞而误报“有交集”。

这里的错误风险不再只和 $k$ 有关，而是和 $k \cdot l$ 有关，因为每一对元素都可能成为碰撞源。若 $U\cap V=\emptyset$，那么每一对 $(u_i,v_j)$ 都是不相等的。对固定一对元素，碰撞要求：

$$p\mid \left(\mathrm{Number}(u_i)-\mathrm{Number}(v_j)\right)$$

这个非零差值仍然小于 $2^n$，所以最多有 $n$ 个不同素因子可能造成碰撞。

现在这样的元素对一共有 $kl$ 个，因此所有可能导致误报的坏素数总数最多是 $kln$。随机从 $\mathrm{PRIME}(n^2)$ 中选 $p$，错误概率最多约为：

$$\frac{kln}{\pi(n^2)} \approx \frac{2kl\ln n}{n}$$

因此，只要

$$|U| \cdot |V| = o\left(\frac{n}{\ln n}\right)$$

错误概率就会随着 $n$ 增大而趋近于 $0$。如果希望把单次错误概率压到大约不超过 $1/2$，可以要求：

$$|U| \cdot |V| \le \frac{n}{4\ln n}$$

在对象对数太多时，碰撞机会会累积。想继续压低错误概率，要么增加指纹长度，要么重复多轮独立随机试验。这里体现的是一个非常常见的原则：单个比较的碰撞概率再低，也会被大量比较通过 union bound 放大。

从 Monte Carlo 到 Las Vegas

上面的协议是 Monte Carlo 型的：它运行很快，但在某个方向上允许小概率错误。另一种常见改造是 Las Vegas 型：先用随机指纹做便宜的初筛，如果指纹已经不同，就直接给出确定的否定答案；如果指纹相同，则回到原对象上做一次完整验证。

这样一来，算法不再出错。因为所有可能出错的“指纹相同”情形，都会被后续的完整验证拦住。

可以把期望成本写成一个简单公式。设随机指纹阶段的成本为 $T_f$，完整验证的成本为 $T_v$，假阳性概率为 $\varepsilon$。在真实答案是否定的情况下，只有发生碰撞时才会进入完整验证，所以期望成本为：

$$T_f+\varepsilon T_v$$

例如成员判断中，如果 $x\notin U$，初筛大多数时候会直接发现“不在集合中”。只有当 $x$ 和某个 $u_i$ 的指纹碰撞时，才需要让 RI 发送完整的 $x$，或者用其他确定性方式检查。因此期望通信量可以写成：

$$O(\log n)+\varepsilon O(n)$$

如果通过扩大素数范围或重复独立试验把 $\varepsilon$ 压得足够低，那么第二项就会变小。

但 Las Vegas 改造并不是免费午餐。在真实答案是肯定的情况占多数下，例如 $x\in U$，真实相等的元素必然产生相同指纹，于是不管如果选取质数，完整验证通常一定会发生。这样也就退化成了全部比较。

Monte Carlo 用小概率错误换取始终很快；Las Vegas 消除了错误，但把部分情形的完整成本放进了期望复杂度里。适合哪一种，取决于应用更不能接受错误，还是更不能接受偶尔变慢。

Freivalds 算法：不乘矩阵也能验证矩阵乘法

再看一个例子。给定三个 $n\times n$ 矩阵 $A,B,C$，要判断 $A\cdot B=C$。如果直接计算 $A\cdot B$ 需要 $O(n^3)$ 时间。而 Freivalds 算法把验证降到了 $O(n^2)$。

随机选择一个向量 $\alpha \in \{0,1\}^n$，然后计算：

$$\beta = A\cdot(B\cdot \alpha), \qquad \gamma = C\cdot \alpha$$

如果 $\beta \ne \gamma$，输出 $A\cdot B \ne C$；如果 $\beta=\gamma$，接受 $A\cdot B=C$，或者说认为它们“可能相等”。

这里就利用了“不计算，只验证”的思想。直接计算 $A\cdot B$ 是复杂的。但是，矩阵乘向量只需要 $O(n^2)$，所以 $B\cdot \alpha$、$A\cdot(B\cdot\alpha)$ 和 $C\cdot\alpha$ 都只需要 $O(n^2)$。整个过程不需要显式算出完整的 $A\cdot B$。

• 如果 $A\cdot B=C$。那么对任何 $\alpha$ 都有 $A\cdot B\cdot\alpha=C\cdot\alpha$，算法不会误判为不相等。

• 若 $A\cdot B \ne C$。令 $D=A\cdot B-C$，则 $D\ne 0$。我们希望随机选出的 $\alpha$ 让 $D\alpha \ne 0$。

为什么至少一半的 $\alpha$ 能发现错误？因为 $D$ 至少有一行非零，记为 $d=(d_1,\ldots,d_n)$。存在某个 $d_j\ne 0$。固定 $\alpha$ 中除 $\alpha_j$ 外的其他坐标后，表达式 $d\cdot\alpha$ 可以看作关于 $\alpha_j$ 的一次式：

$$d_j\alpha_j + c$$

其中 $c$ 由其他坐标决定。由于 $d_j \ne 0$，在 $\alpha_j \in {0,1}$ 的两个选择中，不可能两个都让它等于 $0$。如果 $c=0$，那么 $\alpha_j=1$ 时值为 $d_j\ne 0$；如果 $c\ne 0$，也至多只有一个选择会把它抵消为 $0$。

于是，在所有 $2^n$ 个 0-1 向量中，至少 $2^{n-1}$ 个能让这一行的内积非零，从而让 $D\alpha\ne 0$。

所以，一次运行的错误概率最多是 $1/2$。独立重复 $t$ 次，并且只有每次都通过才接受 $A\cdot B=C$，错误概率最多降为 $2^{-t}$，复杂度变为 $O(tn^2)$。当 $t$ 是几十这样的常数时，这在工程上已经非常强。

这个算法的美感在于，它并没有计算要验证的对象本身，而是随机观察它在某个方向上的投影。若两个矩阵真的不同，它们在至少一半的 0-1 方向上会表现出差异。

更多例子

很多看似不同的算法，都在使用同一个原则：不直接比较对象本身，而是比较它们在某个随机选择下的影子。

Rabin-Karp 字符串匹配

要在长文本 $T$ 中寻找模式串 $P$，朴素方法会把 $P$ 和 $T$ 的每个等长窗口逐字符比较。Rabin-Karp 则先比较窗口的指纹。

如果指纹不同，窗口一定不匹配；如果指纹相同，再逐字符确认。由于相邻窗口只差一个字符，指纹还可以滚动更新，不必每次从头计算。这就是随机指纹在字符串算法中的典型用法：它不直接证明两个字符串相等，而是快速排除大量“不可能相等”的候选。

参考：字符串问题的歪门奇宝：进制哈希

多项式恒等测试

给定两个多项式 $P(x)$ 和 $Q(x)$，要判断它们是否完全相同。直接展开可能很贵，但可以随机选一个点 $r$，比较：

$$P(r) \quad \text{和} \quad Q(r)$$

如果 $P=Q$，那么对所有 $r$ 都相等。若 $P\ne Q$，则 $P-Q$ 是一个非零多项式。一个次数为 $d$ 的非零多项式最多只有 $d$ 个根。因此，只要随机点来自足够大的集合，误判概率就不高。

集合测试

集合也可以被编码成多项式。给定集合 $S={s_1,\ldots,s_m}$，定义：

$$P_S(z)=\prod_{i=1}^m(z-s_i)$$

如果两个集合 $S$ 和 $T$ 相等，那么 $P_S=P_T$。如果集合不同，则两个多项式不同。随机选择一个点 $r$，比较 $P_S(r)$ 和 $P_T(r)$，就能用一个短值随机验证两个集合是否相等。

这些例子的共同点是：对象不同的时候，能让它们“看起来相同”的随机选择只占少数。随机性不是为了制造不确定，而是为了把潜在碰撞压缩到一个可计算、可放大的概率界里。

总结

随机指纹适合“否定容易、肯定昂贵”的场景。两个指纹不同，通常可以立刻否定；两个指纹相同，则要看算法类型决定是否接受。成员判断和矩阵验证中的协议选择接受小概率错误，因此是 Monte Carlo；如果指纹相同后回查原文，就变成 Las Vegas。

它不适合无条件要求零错误、且又不能回查原对象的场景。比如安全认证里不能把普通随机哈希当作密码学承诺；面对主动攻击者时，也不能只靠短指纹断言两个对象完全相同。这里讨论的是算法意义上的随机化验证，不是密码学安全。

实现层面还有几个现实细节。随机源要足够独立，否则重复试验未必能按 $2^{-t}$ 衰减；模运算要注意溢出和负数；当对象数量很大时，单个碰撞概率再小也会被 union bound 放大。很多“理论上概率很低”的事件，在海量系统里会变成迟早发生的事件。