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 | |
| 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 |
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
- Chapter 1 · Matching on Amount Alone Must Collide: the Birthday Problem of Same-Day, Same-Amount Payments
- Chapter 2 · The Last Five Digits and a Time Window: How Far Collisions Fall, and What Will Not Fall
- Chapter 3 · A Finite Automaton for Spoken and Written Chinese Amounts, Simplified and Traditional
- Chapter 4 · The Write-Off Automaton: a Screenshot Is a Claim, a Credit Is a Fact
- Chapter 5 · Average Hash and Hamming Distance: Detecting Repeated Screenshots, and Where Detection Is Blind
- Chapter 7 · Classics East and West: Half-Seal Tallies in the Collected Statutes of the Ming and Galton's Finger Prints
- Chapter 8 · The Buying Agent's Reconciliation Loop and a Protocol for Refutation