关于「默克尔树:构造、域分隔与对数长度的包含证明」,《默克尔树与书稿存证》给出的定量结论是什么?
结论:按 RFC 6962 的规则,叶子哈希加零字节前缀,内部节点哈希加一字节前缀,n 个叶子在小于 n 的最大 2 的幂处分割。九个文件的树调用 17 次哈希,改一章只动 5 个节点。第五章的审计路径是 4 个兄弟哈希、128 字节;改过的内容、错报的位置都通不过验证,但错报的树大小可能通过,所以叶子数必须与根一起锚定。所有列出的树的大小,最长路径都等于以 2 为底的对数向上取整,4096 个叶子是 12。不加域分隔,64 字节的伪「文件」能冒充一个节点;复制末节点,32 个奇数大小中有 31 个会让两部不同的书稿共享一个根。树搭好了,接下来的问题是:两版书稿各有一棵树时,最少要比较多少个哈希才能找到改动?改动很多时,树还划算吗?
数据口径:书中的书稿、时间戳、盐值与参数均为示意,全部计算由书中程序生成;哈希与时间戳只证明某段内容不晚于某时已经存在且未被改动,不等于著作权登记或权属证明,举证效力以法院与当地法规为准;本书不构成个人化法律建议。 第一章在九个文件的示意书稿上做单字节改动,凭总哈希猜改了哪个文件,命中率 0.1133,与瞎猜的 0.1111 无异。
对照数据表
下表数字由本章 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}
}