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

第三章 确定性的五十四张牌:SHA-256 与费希尔-耶茨洗牌

为什么让神谕牌卡成为确定性的

线上抽牌总得有个来源。如果来自服务器的随机数发生器,事后谁也无法核对抽到的是什么,也无法知道有没有重抽。如果来自用户、日期与问题的哈希值,同样的输入永远得到同样的牌,任何持有输入的人都能重算,运营者也无法悄悄换一张「更好」的牌。这里的牌组有 54 张:四种花色各 13 张(代表一件事的四个维度),加上两张王牌。

构造分三步。种子是用户编号、日期与问题文本摘要拼接后的 SHA-256 摘要 (National Institute of Standards and Technology 2015)。把种子与计数器一起哈希,得到一串 32 位的字。然后用费希尔-耶茨算法的德斯坦菲尔德形式洗牌 (Durstenfeld 1964; Knuth 1997):从最后一个位置到第二个位置,每个位置与尚未固定的位置中均匀随机选出的一个交换。

推导

# Chapter 3. p05: A deterministic 54-card oracle shuffle from SHA-256.
# Deck: four suits F, W, A, E of 13 ranks, plus two jokers JK1, JK2.
# Seed = SHA-256(user | date | SHA-256(question)); a counter-mode stream
# SHA-256(seed || i) gives 32-bit words; an index below n is drawn by
# rejection (words at or above the largest multiple of n are discarded),
# and the deck is shuffled by Fisher-Yates (Durstenfeld). The top three
# cards are the past / present / way-out spread. Uniformity is checked
# over 54,000 user IDs with a chi-square test (Wilson-Hilferty p-value).
import hashlib
import math

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()

class Stream:
    def __init__(self, seed):
        self.seed, self.i, self.buf = seed, 0, b""
    def word(self):
        if not self.buf:
            self.buf = hashlib.sha256(
                self.seed + self.i.to_bytes(4, "big")).digest()
            self.i += 1
        w, self.buf = int.from_bytes(self.buf[:4], "big"), self.buf[4:]
        return w
    def below(self, n):
        limit = (2 ** 32 // n) * n
        while True:
            w = self.word()
            if w < limit:
                return w % n

def shuffle(seed):
    deck, st = list(DECK), Stream(seed)
    for i in range(len(deck) - 1, 0, -1):
        j = st.below(i + 1)
        deck[i], deck[j] = deck[j], deck[i]
    return deck

def p_chi2(x, df):
    z = ((x / df) ** (1 / 3) - (1 - 2 / (9 * df))) / math.sqrt(2 / (9 * df))
    return 0.5 * math.erfc(z / math.sqrt(2))

if __name__ == "__main__":
    s = seed_of("u001", "2026-11-09", "Should I launch the course now?")
    d = shuffle(s)
    print("   seed {}...  spread: {}".format(s.hex()[:16], " ".join(d[:3])))
    print("   same inputs again give the same spread: {}".format(
        shuffle(seed_of("u001", "2026-11-09",
                        "Should I launch the course now?"))[:3] == d[:3]))
    print("   ordered three-card spreads: 54 x 53 x 52 = {:,}".format(
        54 * 53 * 52))
    n = 54000
    top = dict.fromkeys(DECK, 0)
    jpos = [0] * 54
    for u in range(n):
        d = shuffle(seed_of("u{:05d}".format(u), "2026-11-09",
                            "Should I launch the course now?"))
        top[d[0]] += 1
        jpos[d.index("JK1")] += 1
    e = n / 54
    print("   {:,} users, expected count per card {:,.0f}".format(n, e))
    for name, obs in (("top card", list(top.values())),
                      ("position of JK1", jpos)):
        x = sum((o - e) ** 2 / e for o in obs)
        print("   {:15s}: chi-square {:.1f} on 53 df, p = {:.3f}, "
              "counts {}-{}".format(name, x, p_chi2(x, 53), min(obs),
                                    max(obs)))
#    seed 6b33b8f955f4aaf1...  spread: F13 W02 E08
#    same inputs again give the same spread: True
#    ordered three-card spreads: 54 x 53 x 52 = 148,824
#    54,000 users, expected count per card 1,000
#    top card       : chi-square 66.8 on 53 df, p = 0.096, counts 907-1083
#    position of JK1: chi-square 57.5 on 53 df, p = 0.312, counts 924-1083

示范用户的「过去、现在、破局」三张牌是 F13、W02、E08,同一天问同一个问题,每次都得到这三张。有序的三张牌排列共有 54 x 53 x 52 = 148,824 种。在 54,000 个用户编号上,首张牌的计数在 907 到 1083 之间,期望值是 1,000,卡方值 66.8,自由度 53(p = 0.096);一张王牌所在位置的卡方值 57.5(p = 0.312)。两者都没有偏离均匀分布。

三种常见的错法

上面的均匀性依赖于两个容易出错的细节:哈希字怎样变成下标,以及每次交换能碰到哪些位置。

推导

# Chapter 3. p06: Three ways to get a "random" shuffle wrong.
# (a) taking one hash byte modulo 54 (5/256 or 4/256, odds 1.25);
# (b) a 32-bit word modulo 54; (c) the naive shuffle that swaps every
# position with ANY position (n**n equally likely paths spread over n!
# orders); (d) Sattolo's slip of drawing j below i instead of up to i,
# which only makes single cycles, so no card can stay where it was.
# All counts are exact.
from fractions import Fraction
from itertools import product
from math import factorial

def mod_bias(bits, n):
    m = 2 ** bits
    q, r = divmod(m, n)
    hi, lo = Fraction(q + 1, m), Fraction(q, m)
    tv = (r * abs(hi - Fraction(1, n)) +
          (n - r) * abs(lo - Fraction(1, n))) / 2 if r else Fraction(0)
    return (hi / lo if r else Fraction(1)), tv, r

def naive_counts(n):
    cnt = {}
    for js in product(range(n), repeat=n):
        a = list(range(n))
        for i, j in enumerate(js):
            a[i], a[j] = a[j], a[i]
        cnt[tuple(a)] = cnt.get(tuple(a), 0) + 1
    return cnt

def sattolo_orders(n):
    seen = set()
    def rec(a, i):
        if i == 0:
            seen.add(tuple(a))
            return
        for j in range(i):
            b = list(a)
            b[i], b[j] = b[j], b[i]
            rec(b, i - 1)
    rec(list(range(n)), n - 1)
    return seen

if __name__ == "__main__":
    for bits in (8, 32):
        ratio, tv, r = mod_bias(bits, 54)
        print("   {:2d}-bit word mod 54: {} favoured cards, odds {:.10f}, "
              "TV {:.3g}".format(bits, r, float(ratio), float(tv)))
    print("   naive swap-with-any shuffle:")
    for n in range(3, 8):
        c = naive_counts(n)
        lo, hi = min(c.values()), max(c.values())
        print("     n={}: {:,} paths over {:,} orders, count {}-{}, "
              "ratio {:.3f}".format(n, n ** n, factorial(n), lo, hi,
                                    hi / lo))
    for n in (4, 5, 6):
        s = sattolo_orders(n)
        fixed = sum(1 for p in s if any(p[i] == i for i in range(n)))
        print("   Sattolo slip, n={}: {} of {} orders, {} with a card "
              "left in place".format(n, len(s), factorial(n), fixed))
    print("   for 54 cards the slip reaches 1/54 of orders: {:.4f}".format(
        factorial(53) / factorial(54)))
#     8-bit word mod 54: 40 favoured cards, odds 1.2500000000, TV 0.0405
#    32-bit word mod 54: 22 favoured cards, odds 1.0000000126, TV 3.04e-09
#    naive swap-with-any shuffle:
#      n=3: 27 paths over 6 orders, count 4-5, ratio 1.250
#      n=4: 256 paths over 24 orders, count 8-15, ratio 1.875
#      n=5: 3,125 paths over 120 orders, count 16-47, ratio 2.938
#      n=6: 46,656 paths over 720 orders, count 32-159, ratio 4.969
#      n=7: 823,543 paths over 5,040 orders, count 64-543, ratio 8.484
#    Sattolo slip, n=4: 6 of 24 orders, 0 with a card left in place
#    Sattolo slip, n=5: 24 of 120 orders, 0 with a card left in place
#    Sattolo slip, n=6: 120 of 720 orders, 0 with a card left in place
#    for 54 cards the slip reaches 1/54 of orders: 0.0185

取一个哈希字节对 54 取模,会让 40 张牌各有 256 分之 5 的机会,其余 14 张只有 256 分之 4:比值 1.25,与公平分布的总变差距离为 0.0405。用 32 位的字,比值降到 1.0000000126,实际上可以忽略;把高于 54 的最大倍数的少数字丢弃重抽,偏差就完全消失,p05 正是这样做的。天真的洗牌法让每个位置与任意位置交换,把 nnn^n 条等可能路径分给 n!n! 种排列,不可能分得均匀:4 张牌时,有的排列在 256 条路径中出现 15 次,有的只有 8 次;7 张牌时,最常见的排列是最少见的 8.484 倍。萨托洛式的失误,即只从当前位置之下抽取交换对象,只会产生单一循环 (Sattolo 1986):6 张牌只有 720 种排列中的 120 种可达,而且没有任何一张牌能留在原位;54 张牌时只有 0.0185 的排列可能出现。

天真的「与任意位置交换」洗牌有多不均匀:最常见排列与最少见排列之比(p06)。

注

确定性不等于意义。 哈希使一次解读可以重现、可以核查,但并不让这次解读与问题有任何关系。牌面取决于问题文本的字节,而不是问题的含义,下一章会说明这一点。

小结

用用户、日期与问题哈希出的种子,加上计数器模式的 SHA-256 字流、拒绝采样与德斯坦菲尔德洗牌,可以得到一副可重现的牌,其首张牌在 54,000 个用户上通过卡方检验。对 54 取模单个字节、与任意位置交换、只从当前位置之下抽取,都会使牌组偏斜,后两种偏斜严重。

参考文献

Durstenfeld, Richard. 1964. “Algorithm 235: Random Permutation.” Communications of the ACM 7 (7): 420.
Knuth, Donald E. 1997. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3rd ed. Addison-Wesley.
National Institute of Standards and Technology. 2015. Secure Hash Standard (SHS). Federal Information Processing Standards Publication 180-4.
Sattolo, Sandra. 1986. “An Algorithm to Generate a Random Cyclic Permutation.” Information Processing Letters 22 (6): 315 to 317.

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).