#SeededPRNG S2

中文标题：种子伪随机数生成器

#种子伪随机数

阶段：2

提案人：Tab Atkins-Bittner

规范草案：https://tc39.github.io/proposal-seeded-random/ （已过时，README 是当前信息源）

JS 的 PRNG 方法（Math.random()、crypto.getRandomValues() 等）都是“自动播种”的——每次调用都会产生一个全新的、不可预测的随机数，无法跨运行或跨 realm 重现。然而，有一些用例需要可重现的随机值序列，因此希望能够自行对随机生成器进行播种。

1. 像 CSS Custom Paint 这样的新 API，它们不能存储状态，但可以被任意频繁地调用，希望每次调用时都能产生同一组伪随机数。

   演示：https://lab.iamvdo.me/houdini/rough-boxes/ 这个演示使用 Math.random() 来不可预测地移动“粗糙边框”，但是 Houdini Custom Paint API 会在元素需要“重绘”时重新调用回调——当元素尺寸变化、或离开屏幕一会儿、或通常任何时候（UA 在这方面有相当大的自由度）。回调无法为自己存储状态（这是设计上的），所以它不能预先生成随机数列表并重复使用；相反，它目前只能产生一组全新的边框。（你可以通过放大或缩小页面观察到效果，因为每次变化都会重绘元素并重新调用回调。）

2. 测试框架，它们出于某种目的使用随机性，希望在本地和 CI 上能够使用相同的伪随机数序列，并且能够重现某个特定的有趣的测试运行。

3. 使用随机性的游戏，希望避免“存档/读档刷随机”，即玩家保存并反复重新加载游戏，直到事件以他们想要的方式出现。

目前，实现这些目标的唯一方法是在 JS 中手动实现自己的 PRNG。像 LCG 这样的简单 PRNG 不难编码，但它们产生的伪随机数质量不好；更好的 PRNG 更难正确实现。提供手动为生成器播种并获得可预测序列的能力会好得多。既然我们在这里，可以借助 JS 的特性来提供比典型随机库为这种用例提供的更好的可用性。

#预期用法

一个 Random.Seeded 对象，一旦构造完成，就有一个 .random() 方法。它的工作方式与 Math.random() 完全相同，因此字面上任何现有使用 Math.random() 的地方都可以通过初始化一个 Random.Seeded 然后调用 prng.random() 来替换。

它甚至可以安装到全局对象上，比如：

let globalPRNG = Random.Seeded.fromFixed(0);
Math.random = globalPRNG.random.bind(globalPRNG);

// 现在 `Math.random()` 在每次页面加载时产生相同的值序列。

目前“污染” Math.random() 以避免其可能用作通信渠道的安全库也可以执行上述操作，以允许它仍然大致按预期工作，但没有通信的可能性。

#API

以下是 API 提案的快速摘要：

const Random = { // 新的全局命名空间对象
  random(): Number {
    return TheInternalBrowserPRNG.random();
  },
  seed(): Uint8Array {
    return TheInternalBrowserPRNG.seed();
  },
};

Random.Seeded = class SeededRandom {
  #state: Uint8Array;

  constructor(seed: Uint8Array) {
    if(!seed instanceof Uint8Array) throw new TypeError();
    if(seed.length > 32) throw new RangeError();
    
    // 如果需要，用 0 字节作为前缀。
    const paddedSeed = new Uint8Array(32);
    paddedSeed.set(32 - seed.length, seed);

    this.#state = stateFromSeed(paddedSeed);
    return this;
  }

  static fromSeed(seed: Uint8Array): Random.Seeded {
    if(!seed instanceof Uint8Array) throw new TypeError();
    if(seed.length != 32) throw new RangeError();
    const prng = InternalMakeFreshSeededRandom();
    prng.setState(stateFromSeed(seed));
    return prng;
  }

  static fromState(state: Uint8Array): Random.Seeded {
    if(!state instanceof Uint8Array) throw new TypeError();
    if(state.length != 112) throw new RangeError();
    const prng = InternalMakeFreshSeededRandom();
    prng.setState(state);
    return prng;
  }

  static fromFixed(byte: Number): Random.Seeded {
    if(typeof byte != "number") throw new TypeError();
    if(!Number.isInteger(byte) || byte < 0 || byte > 255) throw new RangeError();
    const prng = InternalMakeFreshSeededRandom();
    const seed = new Uint8Array(32);
    seed[31] = byte;
    prng.setState(stateFromSeed(seed));
    return prng;
  }

  random(): Number {
    let [val, this.#state] = randomVal(this.#state); // Number in [0,1)
    return val;
  }

  seed(): Uint8Array {
    let [seed, this.#state] = randomSeed(this.#state); // Uint8Array that's a valid seed.
    return seed;
  }

  getState(): Uint8Array {
    return copy(this.#state);
  }

  setState(state: Uint8Array): Seeded.Random {
    if(!state instanceof Uint8Array) throw new TypeError();
    if(state.length != 112) throw new RangeError();
    this.#state = copy(state);
    return this;
  }
}

#Random 命名空间对象

结合更多随机方法提案， 本提案添加了一个新的 Random 命名空间对象， 用于容纳各种新的与随机性相关的操作。

Random 命名空间对象，除了持有 Random.Seeded 类（如下所述）之外， 还持有与 Random.Seeded 类匹配的方法， 这些方法只是调用用户代理内部 SeededPRNG 实例上的匹配方法。 该内部实例由用户代理从随机种子初始化。

#Random.random() 和 Random.seed() 函数

本提案在 Random 命名空间对象上定义了两个方法， .random() 和 .seed()， 与 Random.Seeded 定义的同名两个方法匹配。 “更多随机方法”将定义更多。

每个方法简单返回调用 UA 内部 Random.Seeded 对象的 .random() 或 .seed() 的结果。

因此，Random.random() 与 Math.random() 相同，只是它使用了更高质量的 PRNG 算法。

Random.seed() 旨在用于将 Random.Seeded 初始化为不可预测的起始值， 例如 new Random.Seeded(Random.seed())。

#创建 PRNG：new Random.Seeded(Uint8Array) 构造函数

本提案添加了一个新类 Random.Seeded，它作为 Random.Seeded 存在于 Random 命名空间对象上。

构造函数接受一个 seed 参数，它是一个长度不超过 32 的 Uint8Array。

如果 seed 小于 32 字节，则在其前面添加足够多的 0 字节，使其长度为 32 字节。如果超过 32 字节，则抛出 RangeError。

然后使用 seed 创建状态向量，并返回一个带有该状态向量的新的 Random.Seeded 对象。

#工厂方法：.fromSeed()、.fromState()、.fromFixed()

除了构造函数之外，Random.Seeded 类上还有三个静态工厂方法。

• Random.Seeded.fromSeed(seed) 与构造函数行为相同，但要求正确的长度（32 字节）的种子值。（如果您想确保种子源不会意外退化并开始传递过少的熵，这很有用。）
• Random.Seeded.fromState(state) 接受一个状态向量（一个长度为 112 的 Uint8Array），并返回一个直接初始化为该状态的 Random.Seeded 对象。（这比从垃圾值创建 Seeded.Random 并立即调用 .setState() 更方便/高效。）
• Random.Seeded.fromFixed(num) 接受一个 Number 字节（0-255 的整数），并将其视为全零种子值的最低字节。（换句话说，等同于 new Random.Seeded(Uint8Array.of(num))。）

#获取随机数：.random() 方法

要从 PRNG 对象获取随机数，该对象有一个 .random() 方法。每次调用时，它会根据其状态输出一个在 [0,1) 范围内的适当伪随机数，然后更新其状态以供下次调用。

生成此值的步骤：

1. 从 PRNG 获取 64 个随机位。
2. 右移 11 位，得到一个 53 位整数。
3. 将该整数转换为等效的 float64。
4. 将此 float64 乘以 1/(2**53)。
5. 返回结果。

因此，使用 prng 对象基本上与使用 Math.random() 相同：

const prng = new Random.Seeded(0);
for(let i = 0; i < limit; i++) {
  const r = prng.random();
  // 对每个值执行某些操作
}

#获取随机种子：.seed() 方法

在页面上生成多个、不同的 PRNG 有合理的用例； 例如，游戏可能想用一个生成地形，一个生成云，一个用于 AI 等等。 使用单个 Random.Seeded 对象可以通过技巧实现这一点 （例如，规定每三个值中的第一个用于地形，第二个用于云等）， 但这很笨拙且浪费。

相反，您可以使用来自现有 Random.Seeded 对象的随机种子来初始化多个 Random.Seeded 对象， 如下所示：

const parent = Random.Seeded.fromFixed(0);
const child1 = new Random.Seeded(parent.seed());
const child2 = new Random.Seeded(parent.seed());
// child1.random() != child2.random()

这确保了如果您从同一个“父”PRNG 开始，您的“子”PRNG 将始终产生相同的值序列， 同时利用完整的可能种子熵。

生成此值的步骤：

1. 从 PRNG 获取 256 个随机位。
2. 返回一个包含这些位的（长度为 32）Uint8Array。

#序列化/恢复/克隆 PRNG：.getState() 和 .setState() 方法

.getState() 方法返回一个包含 PRNG 当前状态的新 Uint8Array。 （注意：状态与种子不同且更大；112 字节对 32 字节。）

.setState() 方法接受一个包含 PRNG 状态的 Uint8Array， 验证它是否是 PRNG 的有效状态 （正确大小，以及任何其他约束） 并用该数据替换自身的状态 （从参数复制，而不直接使用对象）。

然后您可以克隆一个 PRNG，如下所示：

const prng = Random.Seeded.fromFixed(0);
for(let i = 0; i < 10; i++) prng.random(); // 将状态前进一点
const clone = Random.Seeded.fromState(prng.getState());
// prng.random() === clone.random()

例如，游戏可以将 prng 的当前状态存储在存档文件中， 确保加载后将会产生与玩家继续游戏时相同的随机数序列。

#算法选择

本提案指定使用 ChaCha12 算法作为 PRNG 算法。 这确保了两件事：

1. 可能的种子范围是可知且稳定的，因此如果您生成随机种子，您可以充分利用可能的熵。
2. 产生的数字在（a）用户代理之间和（b）同一用户代理的版本之间是相同的。这对于例如使用种子序列模拟试验并在不同计算机上获得相同结果很重要。

#FAQ

#为什么不用 Math.random() 的参数？

另一种可能的方法是为 Math.random() 添加一个选项对象，并定义一个可以提供的 state 键。当您这样做时，它使用该种子生成值，而不是其内部种子值。这种方法在 C/Java 等中应该很熟悉。

这种方法的缺点是，如果您试图生成多个值，您必须在下次调用时手动将随机值传回生成器作为下一个 state。当您只想要一个可预测的值序列时，这相当笨拙，并且意味着如果随机生成跨函数或回调发生，您必须携带额外的状态。

它还要求产生的值适合作为状态，这并不总是如此（对于许多算法，状态包含远多于 64 位的信息），或者要求 Math.random() 在带有状态调用时，产生一个 {val, nextState} 对，而不是像正常那样直接产生值。

#我们还应该添加 randInt() 等

本提案专注于制作一个种子 PRNG，并有意与当前未种子的 Math.random() 的签名/行为匹配。我不打算在这里探索额外的随机方法，因为它们应该以种子和未种子两种形式存在。

相反，https://github.com/tc39-transfer/proposal-random-functions 是一个单独的提案，用于向现有的未种子功能添加更多随机函数。意图是本提案中的 Random.Seeded 对象将增加所有相同的方法，因此如果我们添加 Math.randomInt()，我们也会获得 Random.Seeded.randomInt() 等。

无论哪个提案先推进，都将只关注自己，而第二个推进的将承担定义重叠部分的负担。（也就是说，如果本提案先走，那么 proposal-random-functions 将定义其所有方法也存在于 Random.Seeded 上；如果它先走，那么本提案将定义所有新的随机函数也作为 Random.Seeded 方法存在。）