What does Merkle Trees for Manuscript Evidence conclude, in numbers, about “The Merkle Tree: Construction, Domain Separation and Inclusion Proofs of Logarithmic Length”?
Answer: Under the rules of RFC 6962, leaf hashes carry a zero prefix, interior hashes a one prefix, and n leaves split at the largest power of two below n. The nine-file tree takes 17 hash calls, and editing one chapter changes only 5 nodes. The audit path of Chapter 5 is 4 sibling hashes, 128 bytes; edited content and a misstated position both fail verification, but a misstated tree size may pass, so the leaf count must be anchored with the root. For every tree size listed, the longest path equals the base-two logarithm rounded up, 12 for 4096 leaves. Without domain separation a 64-byte fake "file" can impersonate a node; with last-node copying, 31 of 32 odd sizes let two different manuscripts share one root. With the tree built, the next questions are these: when two drafts each have a tree, what is the least number of hashes that must be compared to find the edit, and is the tree still worth it when many things change?
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: 31, 32, 64, 6962
(a) no prefixes, 4 real files vs 2 forged 64-byte 'files'
real root d70294670a61550b
forged root d70294670a61550b equal: True
RFC 6962 roots equal: False
forged leaf length 64 bytes, real file length 5160 bytes
(b) duplicate-last rule, 3 files vs the same 3 plus a copy
roots equal: True
RFC 6962 roots equal: False
sizes 1 to 64 where the copy collides: 31 of 32 odd sizesShow the full program
# Chapter 2. p23: two cheap ways to break a home-made Merkle tree.
# (a) No domain separation: if leaves and inner nodes are hashed the
# same way, the 64 bytes left || right of an inner node can be shown
# as a "leaf" of a shorter tree with the same root.
# (b) Duplicate-last rule: some designs pad an odd level by copying its
# last node; then the lists [a, b, c] and [a, b, c, c] share a root,
# so two different manuscripts carry one fingerprint.
# The RFC 6962 rules (0x00 / 0x01 prefixes, split at the largest power
# of two) reject both. Texts are illustrative.
import hashlib
def file_text(i, ver=1):
line = "B-295 demo manuscript, file %02d, version %d. " % (i, ver)
return (line * 120).encode("ascii")
def h(b):
return hashlib.sha256(b).digest()
def naive_root(level):
# no prefixes; odd levels duplicate their last node
level = [h(x) for x in level]
while len(level) > 1:
if len(level) % 2:
level = level + [level[-1]]
level = [h(level[i] + level[i + 1])
for i in range(0, len(level), 2)]
return level[0]
def rfc_root(data):
if len(data) == 1:
return h(b"\x00" + data[0])
k = 1
while k * 2 < len(data):
k *= 2
return h(b"\x01" + rfc_root(data[:k]) + rfc_root(data[k:]))
docs = [file_text(i) for i in range(4)]
real = naive_root(docs)
inner = [h(docs[0]) + h(docs[1]), h(docs[2]) + h(docs[3])]
fake = naive_root(inner)
print("(a) no prefixes, 4 real files vs 2 forged 64-byte 'files'")
print(" real root %s" % real.hex()[:16])
print(" forged root %s equal: %s" % (fake.hex()[:16], fake == real))
r1 = rfc_root(docs)
r2 = rfc_root(inner)
print(" RFC 6962 roots equal: %s" % (r1 == r2))
print(" forged leaf length %d bytes, real file length %d bytes"
% (len(inner[0]), len(docs[0])))
three = [file_text(i) for i in range(3)]
four = three + [three[2]]
print("(b) duplicate-last rule, 3 files vs the same 3 plus a copy")
print(" roots equal: %s" % (naive_root(three) == naive_root(four)))
print(" RFC 6962 roots equal: %s" % (rfc_root(three) == rfc_root(four)))
odd = 0
for n in range(1, 65):
data = [file_text(i) for i in range(n)]
if n % 2 and naive_root(data) == naive_root(data + [data[-1]]):
odd += 1
print(" sizes 1 to 64 where the copy collides: %d of %d odd sizes"
% (odd, 32))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 2: The Merkle Tree: Construction, Domain Separation and Inclusion Proofs of Logarithmic Length. 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 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 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