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 collision | 160 |
| observed share 0.4000 (95% CI 0.3520 to 0.4480) | |
| birthday prediction | 0.3934 |
| mean colliding pairs | 0.4975 |
| predicted pairs C(q,2)/2^b | 0.4999 |
| most pairs in one trial | 3 |
| q for P = 0.5 at 24 bits | 4822.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
- Chapter 1 · The Blind Spot of One Fingerprint: an Overall Hash Only Says Whether Something Changed
- Chapter 2 · The Merkle Tree: Construction, Domain Separation and Inclusion Proofs of Logarithmic Length
- Chapter 3 · The Least Number of Hashes to Locate a Difference: the Information Bound, Tree Descent and the Break-Even Point
- Chapter 4 · Hash Chains and Linked Timestamps: from the Linking Scheme of Haber and Stornetta to Anchoring Intervals
- Chapter 6 · A Minimal Bundle of Evidence for Priority: Append-Only Consistency, a Two-Level Design and Salted Leaves
- Chapter 7 · Classical Sources East and West: Matched Fish Tallies and Hooke's Anagram
- Chapter 8 · Closing the Loop: Writing the Hash Tree of Manuscripts and Programs into Receipts, the Small Tool and a Pre-Registered Test