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
kboundscatteredexactbunchedflat
110.021.021.021.01024
435.465.965.526.41024
16115.6196.1197.650.71024
64341.1547.1545.7147.11024
128551.9859.0859.9274.21024
256825.61280.41282.9530.11024
5121018.71760.11758.51040.81024
10240.02047.02047.02047.01024
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