关于「凭证指纹库:哈希库里的生日问题与鸽巢检索」,《截图不是钱》给出的定量结论是什么?
结论:哈希库里同样有生日问题:单次查询的偶然近邻随库容线性增长,库内两两查重的偶然近邻对随库容平方增长。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 单即有对半机会撞单。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 10, 390, 4991, 6136405, 64
| ideal 64-bit hash | |
| t -log10 P(t) chance hits/query chance pairs in library | |
| M | 100,000 M = 10^4 10^5 10^6 |
| 0 | 19.27 0.000000 0.000 0.000 0.000 |
| 2 | 15.95 0.000000 0.000 0.000 0.000 |
| 4 | 13.43 0.000000 0.000 0.000 0.018 |
| 6 | 11.35 0.000000 0.000 0.023 2.257 |
| 8 | 9.56 0.000028 0.014 1.391 139.067 |
| 10 | 8.00 0.000998 0.499 49.912 4991 |
| 12 | 6.64 0.022833 11.415 1142 114165 |
| 93-bit field hash, t | 6: -log10 P = 19.08, pairs at 10^6 0.000000 |
| 390-bit field hash, t | 10: -log10 P = 98.09, pairs at 10^6 0.000000 |
| 390-bit field hash, t | 20: -log10 P = 84.16, pairs at 10^6 0.000000 |
| 64-bit, t | 4: 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}
}