frazerpearce/TimeLord

来源: https://github.com/frazerpearce/TimeLord

TimeLord

选择你想要的随机未来，然后构造能产生它的种子。

TimeLord 是一个小型 Python 演示程序，展示了伪随机数生成器产生的惊人小概率序列，并不一定意味着惊人的运气。该程序构造一个普通的 Python 整数种子，使得如下常规代码：

import random
r = random.Random(seed)
for _ in range(100):
    print("H" if r.randrange(2) else "T")

产生：

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

即 100 次连续正面。

TimeLord 可以构造最多达 1,000 次连续正面 的种子。
此过程没有修改随机数生成器，没有使用 setstate()，没有进行猴子补丁操作，也没有在种子提供后进行任何隐藏干预。
该演示使用一个直接传递给以下代码的普通整数：

random.Random(seed)

关键在于，种子是在指定了期望未来之后才被选择的。

---

为何这很有趣？

如果一枚公平的硬币被抛掷 100 次，获得 100 次正面的概率是
2^{-100} \approx 7.9\times10^{-31}
对于 1000 次正面，概率是
2^{-1000} \approx 9.3\times10^{-302}

如果种子是事先独立选择的，那么这两种结果都将是非同寻常的。

但这不是 TimeLord 的做法。相反，我们首先决定：

我希望接下来的 100 次随机抛硬币结果都是正面。

然后 TimeLord 反向工作，构造一个初始种子，使得 Python 的伪随机数生成器恰好产生那个未来。

生成的序列是完全可复现的。任何获得该种子的人都可以运行普通的 Python 并得到相同的 100 次正面。

但可复现性并不能证明种子本身是独立或随机选择的。这就是这个演示的要点所在。

---

底层原理

伪随机数生成器是确定性的。一旦其内部状态被固定，其未来输出也就被固定了。

通常我们按照正向方向工作：

种子
↓
内部状态
↓
看似随机的输出

TimeLord 解决的是逆向问题：

期望的未来输出
↓
兼容的内部状态
↓
整数种子

因此，期望的结果并非被预测，而是被选择。

这与 事后选择、别处窥视效应 和选择偏差等统计概念密切相关。

如果我们在计算某个结果的概率时，假定产生该结果的条件是事先独立固定的，那么一个结果可能显得极其不可能。但事实并非如此。

---

TimeLord 如何实现？

CPython 中的 Python 标准库 random 模块使用 MT19937 梅森旋转算法 伪随机数生成器。

对于这里使用的抛硬币操作：

r.randrange(2)

CPython 最终调用：

getrandbits(2)

如果结果值不小于 2，则会重复。
getrandbits(2) 从经过调温处理的 32 位 MT19937 输出字中取高两位。

为了强制结果为 1（对应正面），可以简单地将这两位约束为：

01

因为 01 已经小于 2，所以不会发生拒绝采样。

因此，每个所需的正面仅给 TimeLord 带来对 MT19937 输出的 两个比特约束。
100 个正面有 200 个约束，1000 个正面有 2000 个约束。

MT19937 的状态包含大约 20,000 个比特，即使在施加这些约束后仍留有巨大的自由度。

---

求解状态

这里利用的重要性质是 MT19937 的 扭曲 和 调温 变换可以表示为二元域 (GF(2)) 上的线性运算。
换句话说，在比特级别，它们可以用基于异或的线性方程组来表达。

TimeLord：

1. 符号化地表示相关的 MT19937 状态比特；
2. 通过 MT 扭曲和调温操作传播它们；
3. 构造要求相应输出比特为 01 的方程；
4. 在 (GF(2)) 上求解这些方程；
5. 自由选择剩余未约束的状态比特。

这产生了一个 MT19937 状态，其未来输出以请求的正面序列开头。

程序跨多个 MT19937 输出块工作，因此也可以构造长于生成器 624 字状态数组的运行。

---

但 Python 接受的是种子，而不是 MT 状态

这是更有趣的部分。构造所需的 MT 状态然后使用：

random.setstate(...)

很容易。但这会削弱演示效果。TimeLord 不这样做。

相反，它逆转了 CPython 的 MT19937 整数播种过程。
CPython 将任意大小的 Python 整数转换为一系列 32 位字，并将它们通过 MT19937 的 init_by_array 初始化算法。

TimeLord 反向推导这些混合操作，找到生成它刚刚构造的状态所需的 624 个小端序 32 位种子字。

然后将这些字组合成一个普通但非常大的 Python 正整数。

最终结果很简单：

seed = ...
r = random.Random(seed)

从那时起，一切都完全符合标准 Python。

---

运行 TimeLord

不需要第三方包。
生成产生默认 100 个正面 的种子：

python3 find_heads_seed.py

生成 500 个正面的种子：

python3 find_heads_seed.py 500

生成 1000 个正面的种子：

python3 find_heads_seed.py 1000

当前支持的范围：

1–1000 个正面

生成的种子写入：

seed__heads.txt

例如：

seed_100_heads.txt
seed_1000_heads.txt

---

运行简单演示

一旦生成了种子：

python3 demo_heads.py 100

或：

python3 demo_heads.py 1000

重要的是，demo_heads.py 不包含任何逆向工程机制。它只是加载整数种子并使用普通的 Python 随机数生成。

这种分离是有意的：演示旨在清楚地表明，在表面上的“抛硬币”过程中没有发生任何不寻常的事情。不寻常的步骤发生在之前选择种子的时候。

---

让随机程序写一条消息

python3 find_text_seed.py "THE FUTURE IS ALREADY WRITTEN."
python3 demo_text.py

演示仅使用普通的 random.Random(seed) 和连续的 chr(r.randrange(128)) 调用来打印 THE FUTURE IS ALREADY WRITTEN.

只将 demo_text.py 和 seed_text.txt 交给某人：该文件只包含一个十六进制整数（0x...），就像正面种子文件一样。

演示中没有存储或知道消息长度。构造函数在末尾附加 ASCII 30 和 31（记录分隔符和单元分隔符）；演示程序在遇到这对字符时停止，不打印它们，然后打印一个最终换行符。一个字符的缓冲区将终止符排除在输出之外。

单个控制字符仍然受支持，但连续的配对 \x1e\x1f 在输入中被保留并拒绝。

抛硬币将未来约束为两个符号之一。文本生成使用更大的字母表。

对于 128 字符 ASCII，CPython 的 randrange(128) 请求 八 位（128.bit_length() 是 8），拒绝至少 128 的值。
getrandbits(8) 从调温后的 MT19937 字中取第 31 到 24 位，最高有效位优先。

将这些位约束为所需的 ASCII 值可使每次抽取立即被接受：每个字符需要八个方程。

此行为在测试中已针对安装的 CPython 进行了检查。

选择一个消息
↓
构造其所需的未来 MT 输出
↓
反向求解状态
↓
构造一个普通的 Python 整数种子
↓
将该种子提供给一个原本简单的 Python 程序
↓
“随机”程序写下选定的消息

两个构造函数都共享 timelord_mt.py 中的原始 GF(2) 求解器和逆向整数播种机制。

自由状态比特保留随机值；使用 --free-seed 42 以进行可重现的构造。

种子以十六进制保存；--show-seed 可选打印大整数。

诊断报告约束计数、达到的秩、剩余自由比特、种子大小、计时和验证。

仅接受 ASCII 值 0..127。对于控制字符，使用 python3 find_text_seed.py --file message.bin；文件作为原始字节读取，无编码或换行符转换。

也支持空输入。容量由约束一致性决定，而不是硬编码的消息长度。

两个终止符字符增加 16 个约束。在 CPython 3.9.6 上，一个重复的 2490 个消息字符的 The future is already written. 前缀加终止符，在秩 19,936 时验证通过，没有自由状态比特。

2491 个消息字符加终止符的前缀则不一致。这是该消息的测量边界，而非保证的最大值：相关但一致的约束被接受，失败则报告矛盾前达到的秩。

MT19937 是一个成熟的生成器；此演示将现有的种子构造扩展到了文本。它不适用于密码学用途。

---

可重现的构造

默认情况下，TimeLord 使用操作系统熵填充 MT19937 状态中未约束的部分。这意味着重复运行通常会产生不同的种子，但都满足要求的未来。

为了使构造本身可重现，提供 --free-seed：

python3 find_heads_seed.py 1000 --free-seed 42

这固定了原本未约束的比特，从而重现相同的生成种子。

---

为什么种子文件是十六进制的？

构造的种子是非常大的整数。Python 3.11 及更高版本对十进制整数/字符串转换施加了默认 4,300 位数字的限制。十六进制表示可以方便地避免此限制，并且对于底层 32 位种子字来说也是一种自然的表示方式。

---

测试

测试套件仅使用 Python 标准库：

python3 -m unittest discover -s tests -v

---

此演示展示了什么——以及没有展示什么

TimeLord 不表明公平的随机过程会自然地以可观的概率产生 1,000 个正面。它们不会。

它也不表明 Python 的 random 模块在其预期的模拟用途中存在统计缺陷。

它证明的是不同的东西：

一个看似不可能的伪随机结果，除非我们也知道初始条件是如何选择的，否则它几乎说明不了什么。

一个结果可能是：

• 确定性的；
• 可复现的；
• 在预先指定的种子下具有统计显著性；

然而，一旦我们了解到种子是根据获得该结果的条件选择的，它就完全不足为奇了。

这个区别远远超出了玩具抛硬币的范畴。这是研究人员在探索多种可能性后报告产生有趣结果的那一个时遇到的同一个普遍问题。

---

为什么叫 “TimeLord”？

一位时间领主不需要被动地等待发现哪个未来会发生。他们选择他们想要的未来。

TimeLord 对 MT19937 做了类似的事情：

选择未来
↓
反向求解
↓
构造初始条件
↓
观察选定的未来展开

无需时间旅行。

---

实现说明

TimeLord 与 CPython 使用的 MT19937 实现和整数播种行为紧密相关。它依赖于对应于 CPython 的：

Modules/_randommodule.c

的细节。因此，生成的种子不应被假定在无关的 Python 实现或具有不同播种算法的生成器中产生相同的行为。

该仓库包含用于 100 和 1000 次连续正面的已验证种子 fixtures。