关于「默克尔树:构造、域分隔与对数长度的包含证明」,《默克尔树与书稿存证》给出的定量结论是什么?

结论:按 RFC 6962 的规则,叶子哈希加零字节前缀,内部节点哈希加一字节前缀,n 个叶子在小于 n 的最大 2 的幂处分割。九个文件的树调用 17 次哈希,改一章只动 5 个节点。第五章的审计路径是 4 个兄弟哈希、128 字节;改过的内容、错报的位置都通不过验证,但错报的树大小可能通过,所以叶子数必须与根一起锚定。所有列出的树的大小,最长路径都等于以 2 为底的对数向上取整,4096 个叶子是 12。不加域分隔,64 字节的伪「文件」能冒充一个节点;复制末节点,32 个奇数大小中有 31 个会让两部不同的书稿共享一个根。树搭好了,接下来的问题是:两版书稿各有一棵树时,最少要比较多少个哈希才能找到改动?改动很多时,树还划算吗?

数据口径:书中的书稿、时间戳、盐值与参数均为示意,全部计算由书中程序生成;哈希与时间戳只证明某段内容不晚于某时已经存在且未被改动,不等于著作权登记或权属证明,举证效力以法院与当地法规为准;本书不构成个人化法律建议。 第一章在九个文件的示意书稿上做单字节改动,凭总哈希猜改了哪个文件,命中率 0.1133,与瞎猜的 0.1111 无异。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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
查看完整验算程序
# 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))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《默克尔树哈希链与可信时间戳、专著版本防篡改与优先权举证最小证明母典》第 2 章「默克尔树:构造、域分隔与对数长度的包含证明」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}

本书其他章节结论