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 sizes
Show 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