关于「凭证指纹库:哈希库里的生日问题与鸽巢检索」,《截图不是钱》给出的定量结论是什么?

结论:哈希库里同样有生日问题:单次查询的偶然近邻随库容线性增长,库内两两查重的偶然近邻对随库容平方增长。64 位理想哈希在门槛 10 下,一百万条记录里就有 4,991 对偶然近邻;门槛 4 下,库容到 6,136,405 时出现一对的机会过半。390 位字段哈希在同等库容下几乎没有偶然近邻。鸽巢原理把 64 位哈希切成 t+1 段,在门槛 4 时每次只需核对约 10.56 条候选,结果与全库扫描逐条一致。到这里,规格书的三个命题都已量化、修正并落到程序里。下一章回到古人:明代的勘合用半印与底簿比对防止文书被冒用,高尔顿用 36 位的估算论证指纹的独特性;他们各自说对了什么,又在哪里与今天的计算相遇?

数据口径:书中订单、账号末码、金额、截图与哈希均由固定种子合成,参数为示意,全部计算由书中程序生成;本书只讨论核销方如何检出重复或改动过的凭证,不提供任何制作凭证的方法;属非个人化经营方法,不构成法律、财务或理财建议,任何置付与发货都须由主事者人工放行。 第一章用生日问题量化撞单:从 10 单到 100 单,期望撞单配对数增长 110.0 倍,撞单概率只增长 41.3 倍;示意目录的有效金额只有 19.3 种,5.2 单即有对半机会撞单。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 10, 390, 4991, 6136405, 64

ideal 64-bit hash
t -log10 P(t) chance hits/query chance pairs in library
M100,000 M = 10^4 10^5 10^6
019.27 0.000000 0.000 0.000 0.000
215.95 0.000000 0.000 0.000 0.000
413.43 0.000000 0.000 0.000 0.018
611.35 0.000000 0.000 0.023 2.257
89.56 0.000028 0.014 1.391 139.067
108.00 0.000998 0.499 49.912 4991
126.64 0.022833 11.415 1142 114165
93-bit field hash, t6: -log10 P = 19.08, pairs at 10^6 0.000000
390-bit field hash, t10: -log10 P = 98.09, pairs at 10^6 0.000000
390-bit field hash, t20: -log10 P = 84.16, pairs at 10^6 0.000000
64-bit, t4: library size for even odds of a chance pair 6136405
查看完整验算程序
# Chapter 6. p61: the birthday problem again, inside the hash library
# Model: if hash bits were independent fair coins, two unrelated
# b-bit hashes would lie within distance t with probability
# P(t) = sum_{k<=t} C(b,k) / 2^b, computed here exactly with
# fractions. A library of M stored screenshots then holds
# C(M,2) * P(t) chance pairs in expectation, and a new query meets
# M * P(t) chance neighbours: the pair count grows with M squared,
# exactly as amounts did in p11. Printed as -log10 P(t) and as
# expected counts. Real hashes are far from fair coins (p52); this
# is the floor that an ideal hash would give, not a promise.
import math
from fractions import Fraction


def p_within(b, t):
    num = 0
    for k in range(t + 1):
        num += math.comb(b, k)
    return Fraction(num, 2 ** b)


print("ideal 64-bit hash")
print("   t  -log10 P(t)   chance hits/query   chance pairs in library")
print("                       M = 100,000     M = 10^4  10^5     10^6")
for t in (0, 2, 4, 6, 8, 10, 12):
    p = p_within(64, t)
    lg = -math.log10(p)
    row = "%4d  %11.2f  %18.6f " % (t, lg, float(p * 100000))
    for m in (10 ** 4, 10 ** 5, 10 ** 6):
        pairs = float(p * m * (m - 1) / 2)
        row += " %8.3f" % pairs if pairs < 1000 else " %8.0f" % pairs
    print(row)
for b, t in ((93, 6), (390, 10), (390, 20)):
    p = p_within(b, t)
    print("%3d-bit field hash, t = %2d: -log10 P = %.2f, pairs at 10^6"
          " %.6f" % (b, t, -math.log10(p),
                     float(p * 10 ** 6 * (10 ** 6 - 1) / 2)))
m_half = math.sqrt(2 * math.log(2) / float(p_within(64, 4)))
print("64-bit, t = 4: library size for even odds of a chance pair %.0f"
      % m_half)

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《多模态汇款凭证与口语订单容错解析、转账末五码核销自动机与重复截图欺诈阻断母典》第 6 章「凭证指纹库:哈希库里的生日问题与鸽巢检索」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-267 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026267,
  author    = {Fan, Yafu},
  title     = {Fault-Tolerant Parsing of Payment Receipts and Spoken Orders: Last-Five-Digit Write-Off Automata and Blocking Duplicate-Screenshot Fraud},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论