关于「差异定位的最少哈希数:信息下界、树形下降与分界点」,《默克尔树与书稿存证》给出的定量结论是什么?
结论:第三章求差异定位的最少比较次数,并发现与主轴相反的结果:改动分散地超过 0.1670 的叶子时,树的下降不如平铺清单。
数据口径:书中的书稿、时间戳、盐值与参数均为示意,全部计算由书中程序生成;哈希与时间戳只证明某段内容不晚于某时已经存在且未被改动,不等于著作权登记或权属证明,举证效力以法院与当地法规为准;本书不构成个人化法律建议。 第一章在九个文件的示意书稿上做单字节改动,凭总哈希猜改了哪个文件,命中率 0.1133,与瞎猜的 0.1111 无异。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.1670
| n = 1024 leaves, 60 trials per k | |||||
| k | bound | scattered | exact | bunched | flat |
| 1 | 10.0 | 21.0 | 21.0 | 21.0 | 1024 |
| 4 | 35.4 | 65.9 | 65.5 | 26.4 | 1024 |
| 16 | 115.6 | 196.1 | 197.6 | 50.7 | 1024 |
| 64 | 341.1 | 547.1 | 545.7 | 147.1 | 1024 |
| 128 | 551.9 | 859.0 | 859.9 | 274.2 | 1024 |
| 256 | 825.6 | 1280.4 | 1282.9 | 530.1 | 1024 |
| 512 | 1018.7 | 1760.1 | 1758.5 | 1040.8 | 1024 |
| 1024 | 0.0 | 2047.0 | 2047.0 | 2047.0 | 1024 |
| smallest scattered k whose expected cost exceeds n: 171 (0.1670 n) | |||||
| total nodes in the tree: 2047 |
查看完整验算程序
# 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))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《默克尔树哈希链与可信时间戳、专著版本防篡改与优先权举证最小证明母典》第 3 章「差异定位的最少哈希数:信息下界、树形下降与分界点」(版本 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}
}