5D Library › 梦境意象二分图、确定性哈希牌卡与潜意识先验激活 · English

第四章 雪崩效应、碰撞与一次解读有多独特

改一个字符,换一副牌

好的哈希函数具有雪崩效应:输入改动一个比特,输出的每个比特都以二分之一的概率翻转 (National Institute of Standards and Technology 2015)。对哈希式神谕而言,后果很直白。先问「Should I launch the course now?」,再把问号换成句号问同样的话,得到的是两次毫不相干的解读;隔一天再问同样的问题,也是如此。

推导

# Chapter 4. p07: Avalanche - how much one changed character moves the
# reading. For 20,000 users the question "Should I launch the course
# now?" is compared with the same words ending in "." instead of "?",
# and with the same question asked one day later. Seed and shuffle as in
# p05. Reported: the share of the 256 seed bits that flip, and how often
# the top card or the whole three-card spread stays the same, against
# the 1/54 and 1/148,824 expected of independent readings.
import hashlib
import statistics

DECK = ["{}{:02d}".format(s, r) for s in "FWAE" for r in range(1, 14)]
DECK += ["JK1", "JK2"]

def seed_of(user, date, question):
    q = hashlib.sha256(question.encode("utf-8")).hexdigest()
    return hashlib.sha256("{}|{}|{}".format(user, date, q)
                          .encode("utf-8")).digest()

def spread(seed, k=3):
    deck, i, buf = list(DECK), 0, b""
    for n in range(len(deck) - 1, 0, -1):
        limit = (2 ** 32 // (n + 1)) * (n + 1)
        while True:
            if not buf:
                buf = hashlib.sha256(seed + i.to_bytes(4, "big")).digest()
                i += 1
            w, buf = int.from_bytes(buf[:4], "big"), buf[4:]
            if w < limit:
                break
        j = w % (n + 1)
        deck[n], deck[j] = deck[j], deck[n]
    return tuple(deck[:k])

def flipped(a, b):
    return bin(int.from_bytes(a, "big") ^ int.from_bytes(b, "big")) \
        .count("1") / 256

if __name__ == "__main__":
    n, q = 20000, "Should I launch the course now?"
    for label, alt in (("'?' -> '.'", lambda u: (u, "2026-11-09",
                                                  q[:-1] + ".")),
                       ("next day", lambda u: (u, "2026-11-10", q))):
        fl, top, three = [], 0, 0
        for k in range(n):
            u = "u{:05d}".format(k)
            a, b = seed_of(u, "2026-11-09", q), seed_of(*alt(u))
            fl.append(flipped(a, b))
            sa, sb = spread(a), spread(b)
            top += sa[0] == sb[0]
            three += sa == sb
        print("   {:10s}: bits flipped {:.3f} (sd {:.3f}); same top card "
              "{} of {:,}".format(label, statistics.mean(fl),
                                  statistics.pstdev(fl), top, n))
        print("               same spread {}; expected {:.1f} and {:.3f}"
              .format(three, n / 54, n / 148824))
#    '?' -> '.': bits flipped 0.500 (sd 0.031); same top card 349 of 20,000
#                same spread 0; expected 370.4 and 0.134
#    next day  : bits flipped 0.500 (sd 0.031); same top card 378 of 20,000
#                same spread 0; expected 370.4 and 0.134

把末尾的「?」改成「.」,256 个种子比特平均有 0.500 翻转(标准差 0.031)。在 20,000 名用户中,首张牌相同的有 349 次,三张牌完全相同的一次也没有;两次独立解读的期望值分别是 370.4 与 0.134。隔一天再问:首张牌相同 378 次,三张牌相同 0 次。解读跟随的是问题的字节,而不是问题的含义。这正是它公平、可核查的原因,也正是它不可能「理解」问题的原因:反复改写问题直到牌面顺眼,就等于重新抽牌。

「你的」解读有多独特

生日问题给出:多少名用户时,其中两人很可能得到同一次解读。若有 NN 种等可能的解读,nn 名用户各不相同的概率是 ∏i<n(1−i/N)\prod_{i<n}(1 – i/N),大约到 2Nln⁡2\sqrt{2N\ln 2} 名用户时,出现重复就比不出现更可能。

推导

# Chapter 4. p08: Birthday bounds - how unique is "your" reading?
# For N equally likely readings, the smallest number of users n with a
# 50% chance that two of them get the same one is found exactly from
# P(no repeat) = prod (1 - i/N); the approximation sqrt(2 N ln 2) is in
# brackets.
# Readings: one card (54), a three-card spread (148,824), a 7-day path
# of one card a day drawn with replacement (54**7), the full order (54!).
# Also: expected pairs sharing a spread among 10,000 users in one day.
import math

def n50(N, cap=5000000):
    p, n = 1.0, 1
    while n < cap:
        p *= 1 - n / N
        n += 1
        if p <= 0.5:
            return n
    return None

if __name__ == "__main__":
    cases = (("one card", 54), ("3-card spread", 54 * 53 * 52),
             ("7-day path", 54 ** 7), ("full order", math.factorial(54)))
    for name, N in cases:
        approx = math.sqrt(2 * N * math.log(2))
        exact = n50(N) if N < 10 ** 13 else None
        print("   {:13s} N = {:.4g}: 50% repeat at n = {} ({:.4g})"
              .format(name, N, "{:,}".format(exact) if exact else "-",
                      approx))
    users = 10000
    pairs = users * (users - 1) / 2 / 148824
    print("   10,000 users in a day: expected pairs with the same spread "
          "{:.1f}".format(pairs))
    share = 1 - (1 - 1 / 148824) ** (users - 1)
    print("   chance a given user shares the spread with someone: {:.3f}"
          .format(share))
#    one card      N = 54: 50% repeat at n = 9 (8.652)
#    3-card spread N = 1.488e+05: 50% repeat at n = 455 (454.2)
#    7-day path    N = 1.339e+12: 50% repeat at n = 1,362,405 (1.362e+06)
#    full order    N = 2.308e+71: 50% repeat at n = - (5.657e+35)
#    10,000 users in a day: expected pairs with the same spread 335.9
#    chance a given user shares the spread with someone: 0.065

单张牌只要 9 名用户,出现重复的机会就过半。有序的三张牌(148,824 种)需要 455 名用户。七天、每天一张、有放回地抽,需要 1,362,405 名用户。只有整副牌的完整排列,是任何用户规模都碰不到的。一天里有 10,000 名用户时,大约有 335.9 对用户得到完全相同的三张牌,任何一名用户与别人撞牌的概率是 0.065。一次解读可以在「由用户自己的输入算出」的意义上是个人的,同时又与几百个陌生人相同。

注

碰撞不是缺陷。 碰撞并不说明哈希不够强,它只是关于不同解读一共有多少种的算术。一个告诉用户「这次解读独一无二」的服务,要么让可能的解读数远多于用户数,要么就不要这样说。

小结

改动一个字符或相隔一天,种子会有一半比特翻转,得到毫不相干的解读。三张牌共有 148,824 种排列,455 名用户就有一半机会出现重复;每天 10,000 名用户,约有 335.9 对得到相同的三张牌。

参考文献

National Institute of Standards and Technology. 2015. Secure Hash Standard (SHS). Federal Information Processing Standards Publication 180-4.

Fan, Y. (2026). Dream Motif Bipartite Graphs, Deterministic Oracle Decks and Subconscious Prior Activation: REM Semantic Spreading, SHA-256 Fisher-Yates Permutations and Retroactive Coincidence Rates [梦境意象二分图、确定性哈希牌卡与潜意识先验激活] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090233 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).