关于「生日界:碰撞概率、截断长度与「主张者本人」这个对手」,《默克尔树与书稿存证》给出的定量结论是什么?

结论:第五章计算生日界,截断到 24 比特的实验观察到碰撞比例 0.4000,预测 0.3934,并用尤瓦尔式实验说明主张者本人是成本最低的攻击者,只花 16384 次哈希就造出碰撞。

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

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.3934, 0.4000, 24

truncated SHA-256 to 24 bits, q = 4096 per trial, 400 trials
trials with a collision160
observed share 0.4000 (95% CI 0.3520 to 0.4480)
birthday prediction0.3934
mean colliding pairs0.4975
predicted pairs C(q,2)/2^b0.4999
most pairs in one trial3
q for P = 0.5 at 24 bits4822.7
查看完整验算程序
# Chapter 5. p52: watch the birthday bound happen on a cut-down hash.
# SHA-256 is truncated to its first 24 bits. In each of 400 trials we
# hash q = 4096 distinct short messages and record whether any two
# truncated values coincide and how many colliding pairs appear. Theory:
# P(any) = 1 - exp(-q (q - 1) / 2^25) and E[pairs] = C(q, 2) / 2^24.
# The messages are fixed strings, so the run is fully reproducible; a
# 95 percent interval uses the normal approximation. Illustrative.
import hashlib
import math
from collections import Counter

B = 24
Q = 4096
TRIALS = 400


def trunc(msg):
    return int.from_bytes(hashlib.sha256(msg).digest()[:3], "big")


hit, pairs = 0, []
for t in range(TRIALS):
    c = Counter(trunc(b"trial %d message %d" % (t, i)) for i in range(Q))
    p = int(math.fsum(v * (v - 1) // 2 for v in c.values()))
    pairs.append(p)
    if p > 0:
        hit += 1
rate = hit / TRIALS
se = math.sqrt(rate * (1 - rate) / TRIALS)
theory = -math.expm1(-Q * (Q - 1) / 2.0 ** (B + 1))
epairs = math.comb(Q, 2) / 2.0 ** B
print("truncated SHA-256 to %d bits, q = %d per trial, %d trials"
      % (B, Q, TRIALS))
print("trials with a collision     %d" % hit)
print("observed share              %.4f  (95%% CI %.4f to %.4f)"
      % (rate, rate - 1.96 * se, rate + 1.96 * se))
print("birthday prediction         %.4f" % theory)
print("mean colliding pairs        %.4f" % (math.fsum(pairs) / TRIALS))
print("predicted pairs C(q,2)/2^b  %.4f" % epairs)
print("most pairs in one trial     %d" % max(pairs))
print("q for P = 0.5 at %d bits     %.1f"
      % (B, math.sqrt(2 * math.log(2) * 2.0 ** B)))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《默克尔树哈希链与可信时间戳、专著版本防篡改与优先权举证最小证明母典》第 5 章「生日界:碰撞概率、截断长度与「主张者本人」这个对手」(版本 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}
}

本书其他章节结论