What does Merkle Trees for Manuscript Evidence conclude, in numbers, about “The Least Number of Hashes to Locate a Difference: the Information Bound, Tree Descent and the Break-Even Point”?
Answer: Chapter 3 finds the least number of comparisons needed to locate a difference and reports a result against the main thesis: once edits scatter over more than 0.1670 of the leaves, tree descent does worse than a flat list.
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.1670
| n = 1024 leaves, 60 trials per k | |||||
| k | bound | scattered | exact | bunched | flat |
| 1 | 10.0 | 21.0 | 21.0 | 21.0 | 1024 |
| 4 | 35.4 | 65.9 | 65.5 | 26.4 | 1024 |
| 16 | 115.6 | 196.1 | 197.6 | 50.7 | 1024 |
| 64 | 341.1 | 547.1 | 545.7 | 147.1 | 1024 |
| 128 | 551.9 | 859.0 | 859.9 | 274.2 | 1024 |
| 256 | 825.6 | 1280.4 | 1282.9 | 530.1 | 1024 |
| 512 | 1018.7 | 1760.1 | 1758.5 | 1040.8 | 1024 |
| 1024 | 0.0 | 2047.0 | 2047.0 | 2047.0 | 1024 |
| smallest scattered k whose expected cost exceeds n: 171 (0.1670 n) | |||||
| total nodes in the tree: 2047 |
Show the full program
# Chapter 3. p32: when many leaves change, the tree loses to a list.
# n = 1024 leaves; k leaves change at random positions (fixed seed, 60
# trials per k). Descent cost = node pairs compared from the root down
# (same rule as p31). Information bound = log2 C(n, k) one-bit answers
# needed to name the changed set. Flat list = n comparisons. We also
# print the cost when the k edits are bunched in one contiguous run,
# the usual shape of a rewritten chapter, and the exact expectation
# for scattered edits. Seed and sizes illustrative.
import hashlib
import math
import random
N = 1024
TRIALS = 60
def lh(data):
return hashlib.sha256(b"\x00" + data).digest()
def nh(left, right):
return hashlib.sha256(b"\x01" + left + right).digest()
def build(hs, lo, hi, table):
if hi - lo == 1:
h = hs[lo]
else:
mid = (lo + hi) // 2
h = nh(build(hs, lo, mid, table), build(hs, mid, hi, table))
table[(lo, hi)] = h
return h
def descent(ta, tb, lo, hi):
if ta[(lo, hi)] == tb[(lo, hi)] or hi - lo == 1:
return 1
mid = (lo + hi) // 2
return 1 + descent(ta, tb, lo, mid) + descent(ta, tb, mid, hi)
def exact(k):
# expected descent cost over random k-subsets, node by node
terms = [1.0]
for d in range(1, 11):
s = N >> (d - 1)
miss = math.comb(N - s, k) / math.comb(N, k)
terms.append((1 << d) * (1.0 - miss))
return math.fsum(terms)
def cost(changed, base, ta):
new = list(base)
for m in changed:
new[m] = lh(b"leaf %d v2" % m)
tb = {}
build(new, 0, N, tb)
return descent(ta, tb, 0, N)
rng = random.Random(20261113)
base = [lh(b"leaf %d v1" % i) for i in range(N)]
ta = {}
build(base, 0, N, ta)
print("n = %d leaves, %d trials per k" % (N, TRIALS))
print("%5s %8s %10s %9s %9s %6s" % ("k", "bound", "scattered", "exact",
"bunched", "flat"))
for k in (1, 4, 16, 64, 128, 256, 512, 1024):
scat = [cost(rng.sample(range(N), k), base, ta)
for _ in range(TRIALS)]
start = [rng.randrange(N - k + 1) for _ in range(TRIALS)]
bun = [cost(range(s, s + k), base, ta) for s in start]
bound = math.log2(math.comb(N, k)) if k < N else 0.0
print("%5d %8.1f %10.1f %9.1f %9.1f %6d" % (
k, bound, math.fsum(scat) / TRIALS, exact(k),
math.fsum(bun) / TRIALS, N))
kstar = 1
while exact(kstar) <= N:
kstar += 1
print("smallest scattered k whose expected cost exceeds n: %d (%.4f n)"
% (kstar, kstar / N))
print("total nodes in the tree: %d" % (2 * N - 1))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 3: The Least Number of Hashes to Locate a Difference: the Information Bound, Tree Descent and the Break-Even Point. 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 4 · Hash Chains and Linked Timestamps: from the Linking Scheme of Haber and Stornetta to Anchoring Intervals
- Chapter 5 · The Birthday Bound: Collision Probability, Truncated Fingerprints and the Claimant as Adversary
- 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