What does Merkle Trees for Manuscript Evidence conclude, in numbers, about “The Birthday Bound: Collision Probability, Truncated Fingerprints and the Claimant as Adversary”?

Answer: Chapter 5 computes the birthday bound; an experiment with hashes cut to 24 bits observes a collision share of 0.4000 against a prediction of 0.3934, and a Yuval-style experiment shows that the claimant is the lowest-cost attacker, producing a collision with only 16384 hash calls.

Scope of the numbers: Its manuscripts, timestamps, salts and parameters are illustrative, and all calculations are generated by its programs. Chapter 1 makes single-byte edits to a nine-file illustrative manuscript and guesses the edited file from the overall hash, with a hit rate of 0.1133, no better than the 0.1111 of blind guessing.

中文版

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: 0.3934, 0.4000, 24

truncated SHA-256 to 24 bits, q = 4096 per trial, 400 trials
trials with a collision160
observed share 0.4000 (95% CI 0.3520 to 0.4480)
birthday prediction0.3934
mean colliding pairs0.4975
predicted pairs C(q,2)/2^b0.4999
most pairs in one trial3
q for P = 0.5 at 24 bits4822.7
Show the full program
# Chapter 5. p52: watch the birthday bound happen on a cut-down hash.
# SHA-256 is truncated to its first 24 bits. In each of 400 trials we
# hash q = 4096 distinct short messages and record whether any two
# truncated values coincide and how many colliding pairs appear. Theory:
# P(any) = 1 - exp(-q (q - 1) / 2^25) and E[pairs] = C(q, 2) / 2^24.
# The messages are fixed strings, so the run is fully reproducible; a
# 95 percent interval uses the normal approximation. Illustrative.
import hashlib
import math
from collections import Counter

B = 24
Q = 4096
TRIALS = 400


def trunc(msg):
    return int.from_bytes(hashlib.sha256(msg).digest()[:3], "big")


hit, pairs = 0, []
for t in range(TRIALS):
    c = Counter(trunc(b"trial %d message %d" % (t, i)) for i in range(Q))
    p = int(math.fsum(v * (v - 1) // 2 for v in c.values()))
    pairs.append(p)
    if p > 0:
        hit += 1
rate = hit / TRIALS
se = math.sqrt(rate * (1 - rate) / TRIALS)
theory = -math.expm1(-Q * (Q - 1) / 2.0 ** (B + 1))
epairs = math.comb(Q, 2) / 2.0 ** B
print("truncated SHA-256 to %d bits, q = %d per trial, %d trials"
      % (B, Q, TRIALS))
print("trials with a collision     %d" % hit)
print("observed share              %.4f  (95%% CI %.4f to %.4f)"
      % (rate, rate - 1.96 * se, rate + 1.96 * se))
print("birthday prediction         %.4f" % theory)
print("mean colliding pairs        %.4f" % (math.fsum(pairs) / TRIALS))
print("predicted pairs C(q,2)/2^b  %.4f" % epairs)
print("most pairs in one trial     %d" % max(pairs))
print("q for P = 0.5 at %d bits     %.1f"
      % (B, math.sqrt(2 * math.log(2) * 2.0 ** B)))

Single source and citation

Fan, Y. (2026). Merkle Hash Trees and Trusted Timestamps: Tamper-Evidence for Monograph Versions and Minimal Proofs of Priority (Version 1.0.0), Chapter 5: The Birthday Bound: Collision Probability, Truncated Fingerprints and the Claimant as Adversary. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-295 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026295,
  author    = {Fan, Yafu},
  title     = {Merkle Hash Trees and Trusted Timestamps: Tamper-Evidence for Monograph Versions and Minimal Proofs of Priority},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book