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

程序里经常会遇到一种看似朴素、实际很贵的问题两个东西是不是一样它可能是两个字符串、两个文件、两个集合、一段文本里的子串或者三个矩阵是否满足 A⋅BCA⋅BC。如果对象本身很大尤其是在对象需要跨机器通信、被反复比较、以流式方式到达或者比较结果只需要高概率可靠时直接逐个字节比较往往不是最想要的方案。随机指纹法处理的正是这类问题。它不试图完整保留对象而是把对象映射成一个短得多的值然后比较这些短值。这个短值可能丢失信息所以它不是压缩意义上的可逆编码而更像一个可快速比较的影子。影子不能替代实体但如果影子不同实体一定不同如果影子相同实体也许相同也许只是碰巧投在了同一个地方。随机性的作用是让这种“碰巧”变得可控。指纹与哈希指纹和哈希函数有相似之处。设对象集合为 OO我们从一组映射 HH 中随机选择一个函数 ff然后用 f(O)f(O) 作为对象 OO 的指纹。对于两个对象 O1O1​ 和 O2O2​如果 O1O2O1​O2​那么必然有 f(O1)f(O2)f(O1​)f(O2​)如果 O1≠O2O1​O2​那么大多数 f∈Hf∈H 都能让 f(O1)≠f(O2)f(O1​)f(O2​)。第二点是关键。对于输出空间远小于输入空间的固定哈希函数理论上总会存在碰撞在非密码学场景下如果对手知道函数也可能针对性地寻找碰撞。随机选择函数后对手很难提前知道我们会拿哪一把尺子去量对象。随机化并不是为了神秘而是为了把最坏情况变成概率问题。在算法分析里能区分 O1O1​ 和 O2O2​ 的函数常被称为 witness也就是“见证者”。如果某个 h∈Hh∈H 满足 h(O1)≠h(O2)h(O1​)h(O2​)那么 hh 就见证了 O1≠O2O1​O2​。指纹法的设计目标就是让见证者足够多同时让每个指纹足够短。这两个目标天然冲突。指纹越短比较越快通信越省但碰撞空间也更大指纹越长错误概率更低却离“直接发送原对象”越来越近。许多随机化算法的味道就藏在这个 trade-off 里。用随机素数给二进制串取指纹一切复杂对象都可以映射成二进制数而一切二进制串又可以看成整数。给定 x∈{0,1}nx∈{0,1}n令 Number(x)Number(x) 表示它对应的二进制整数。例如 1011210112​ 对应十进制的 1111。随机选择一个素数 pp定义Fingerp(x)Number(x)modpFingerp​(x)Number(x)modp这个定义非常朴素但足够有力。如果有 xx 和 yy 不同那么 Number(x)−Number(y)Number(x)−Number(y) 是一个非零整数。若它们在模 pp 下指纹相等则有Number(x)≡Number(y)(modp)Number(x)≡Number(y)(modp)也就是p∣(Number(x)−Number(y))p∣(Number(x)−Number(y))所以错误只会发生在随机选中的 pp 刚好是这个差值的某个素因子时。一个非零整数的素因子数量有限而可选素数集合可以通过扩大范围来增加。于是只要 pp 的可选范围越大坏素数所占比例就会越低。这就是模素数指纹法的基本逻辑不是保证没有碰撞而是让碰撞需要满足一个很具体、很稀疏的条件。相等判断考虑一个通信问题。机器 RI 有一个字符串 x∈{0,1}nx∈{0,1}n机器 RII 有一个集合 U{u1,u2,…,uk}U{u1​,u2​,…,uk​}其中每个 uiui​ 也是长度为 nn 的二进制串。RI 不知道 UURII 不知道 xx它们要判断 x∈Ux∈U。最直接的方法是 RI 把整个 xx 发过去通信量是 nn bit。随机指纹法可以把通信量降到 O(log⁡n)O(logn)代价是引入单边错误。RI:choose random prime p from PRIME(n^2)s Number(x) mod psend (p, s) to RIIRII:for each u_i in U:q_i Number(u_i) mod pif s is equal to some q_i:output x may be in Uelse:output x is not in U这里 PRIME(n2)PRIME(n2) 表示不超过 n2n2 的素数集合。因为 p≤n2p≤n2发送 pp 需要约 2log⁡n2logn bit又因为 spsp发送 ss 也需要约 2log⁡n2logn bit。所以总通信复杂度大约是 4log⁡n4logn也就是 O(log⁡n)O(logn)。这个协议的正确性方向很清楚。如果 x∈Ux∈U设 xujxuj​那么对任何 pp 都有 Fingerp(x)Fingerp(uj)Fingerp​(x)Fingerp​(uj​)协议一定会输出“在集合中”。错误只可能发生在 x∉Ux∈/U 时。此时某个 uiui​ 可能满足Number(x)≡Number(ui)(modp)Number(x)≡Number(ui​)(modp)也就是一次碰撞。在 PRIME(n2)PRIME(n2) 的质数选取范围下错误的概率具体有多大呢设 x∉Ux∈/U。对每个 uiui​令Δi∣Number(x)−Number(ui)∣Δi​∣Number(x)−Number(ui​)∣因为 x≠uixui​所以 Δi≠0Δi​0又因为二者都是 nn 位二进制串所以 Δi2nΔi​2n。如果 xx 和 uiui​ 在模 pp 下发生碰撞那么 p∣Δip∣Δi​。而数论知识还告诉我们一个小于 2n2n 的非零整数最多有 nn 个不同的素因子。所以对一个固定的 uiui​能造成碰撞的坏素数最多有 nn 个。对所有 kk 个元素坏素数总数最多有 knkn 个。另一方面不超过 n2n2 的素数个数约为π(n2)∼n2ln⁡(n2)n22ln⁡nπ(n2)∼ln(n2)n2​2lnnn2​所以随机选中坏素数的概率最多约为knπ(n2)≈knn2/(2ln⁡n)2kln⁡nnπ(n2)kn​≈n2/(2lnn)kn​n2klnn​这符合直觉元素数量 kk 越多越容易冲突而当质数范围取 n2n2 时规模越大越不容易冲突。当k≤n4ln⁡nk≤4lnnn​时错误概率就至多约为 1221​。为什么 1221​ 这个节点这么重要呢它重要是因为一旦单次错误概率被压到某个小于 11 的常数就可以通过独立重复把错误概率指数级压低。重复 tt 轮每一轮都重新选择独立的随机素数并且只有每一轮都发生碰撞才会误判那么错误概率最多变成2−t2−t随着次数增加错误概率会迅速降低而只要问题规模较大kk 次实验发送的 4klog⁡n4klogn bit 仍然远小于 nn 个全部比特。这种协议叫 one-sided-error Monte Carlo protocol。它会很快给出答案但答案只有一个方向是绝对可靠的如果它说 x∉Ux∈/U那一定是真的如果它说 x∈Ux∈U则可能是碰撞造成的假阳性。集合不交碰撞机会按成对数量累积上面可以问题可以推广。RI 有 V{v1,v2,…,vl}V{v1​,v2​,…,vl​}RII 有 U{u1,u2,…,uk}U{u1​,u2​,…,uk​}目标是判断 U∩VU∩V 是否为空。那么思路仍然没有变化RI 选择一个随机素数 pp计算自己每个元素的指纹并发送RII 也计算自己每个元素的指纹并和 RI 发送的指纹比较。直接发送整个集合需要 O(ln)O(ln) bit。使用随机指纹时RI 只需要发送一次 pp再发送 ll 个元素的模 pp 指纹通信量变为 O(llog⁡n)O(llogn) bit。如果 U∩V≠∅U∩V∅真实公共元素一定会产生相同指纹所以不会漏报。若 U∩V∅U∩V∅协议可能因为某一对 (ui,vj)(ui​,vj​) 的碰撞而误报“有交集”。这里的错误风险不再只和 kk 有关而是和 k⋅lk⋅l 有关因为每一对元素都可能成为碰撞源。若 U∩V∅U∩V∅那么每一对 (ui,vj)(ui​,vj​) 都是不相等的。对固定一对元素碰撞要求p∣(Number(ui)−Number(vj))p∣(Number(ui​)−Number(vj​))这个非零差值仍然小于 2n2n所以最多有 nn 个不同素因子可能造成碰撞。现在这样的元素对一共有 klkl 个因此所有可能导致误报的坏素数总数最多是 klnkln。随机从 PRIME(n2)PRIME(n2) 中选 pp错误概率最多约为