What does A Screenshot Is Not a Payment conclude, in numbers, about “The Receipt Fingerprint Library: the Birthday Problem Among Hashes, and Pigeonhole Search”?

Answer: The hash library has its own birthday problem: chance neighbours of a single query grow in step with the library, and chance pairs within the library grow with its square. For an ideal 64-bit hash at threshold 10, a library of a million holds 4,991 chance pairs; at threshold 4, a library of 6,136,405 has better than even odds of one. A 390-bit field hash has almost no chance neighbours at the same size. The pigeonhole principle cuts a 64-bit hash into t+1 blocks; at threshold 4 a query checks about 10.56 candidates on average, and the answers agree with a full scan record by record. By now the three claims of the specification have been quantified, corrected and written into programs. The next chapter turns to the ancients. Ming officials guarded documents against misuse by matching half-seals against a register, and Galton argued the uniqueness of fingerprints with an estimate worth 36 bits. What did each of them get right, and where do they meet today's calculations?

Scope of the numbers: Orders, account tails, amounts, screenshots and hashes are synthesised from fixed seeds, parameters are illustrative, and every calculation is generated by the book's programs. Marked boxes separate published evidence, runnable Python calculations (20 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 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
Show the full program
# 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)

Single source and citation

Fan, Y. (2026). Fault-Tolerant Parsing of Payment Receipts and Spoken Orders: Last-Five-Digit Write-Off Automata and Blocking Duplicate-Screenshot Fraud (Version 1.0.0), Chapter 6: The Receipt Fingerprint Library: the Birthday Problem Among Hashes, and Pigeonhole Search. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 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}
}

Other chapter answers in this book