文章由 ds-r1 翻译自 https://github.com/tevador/RandomX/blob/master/doc/design.md
RandomX 设计
为了最小化专用硬件的性能优势，工作量证明 (PoW) 算法必须通过针对现有通用硬件的特定功能来实现设备绑定。这是一项复杂的任务，因为我们必须针对来自不同制造商、具有不同架构的一大类设备。
通用处理设备分为两大类：中央处理器 (CPU) 和图形处理器 (GPU)。RandomX 针对 CPU，原因如下：
- CPU 作为专用性较低的设备，更为普及且易于访问。受 CPU 限制的算法更具平等性，允许更多参与者加入网络。这是原始 CryptoNote 白皮书 [1] 中阐述的目标之一。
- 不同 CPU 架构之间存在一个庞大的通用原生硬件指令子集。而 GPU 则无法做到这一点。例如，NVIDIA 和 AMD GPU 之间没有通用的整数乘法指令 [2]。
- 所有主要的 CPU 指令集都有完善的文档记录，并有多个开源编译器可用。相比之下，GPU 指令集通常是专有的，并且可能需要特定供应商的闭源驱动程序才能获得最大性能。
1. 设计考量
受 CPU 限制的工作量证明最基本的思想是，“工作”必须是动态的。这利用了 CPU 接受两种输入的事实：数据（主要输入）和代码（指定对数据执行什么操作）。
相反，典型的加密哈希函数 [3] 并不代表适合 CPU 的工作，因为它们唯一的输入是数据，而操作序列是固定的，可以通过专用的集成电路更高效地执行。
1.1 动态工作量证明
一个动态工作量证明算法通常可以由以下 4 个步骤组成：
1) 生成一个随机程序。
2) 将其翻译成 CPU 的原生机器码。
3) 执行该程序。
4) 将程序的输出转换为加密安全的值。
实际的“有用”的受 CPU 限制的工作在第 3 步中执行，因此必须调整算法以最小化其余步骤的开销。
1.1.1 生成随机程序
早期动态工作量证明设计的尝试基于用高级语言（如 C 或 Javascript [4, 5]）生成程序。然而，这效率非常低，主要有两个原因：
- 高级语言语法复杂，因此生成有效程序相对较慢，因为它需要创建抽象语法树 (AST)。
- 一旦生成程序源代码，编译器通常会将文本表示解析回 AST，这使得生成源代码的整个过程变得多余。
生成随机程序最快的方法是使用无逻辑生成器——简单地用随机数据填充缓冲区。这当然需要设计一种无语法的编程语言（或指令集），其中所有随机比特串都代表有效的程序。
1.1.2 将程序翻译成机器码
这一步是不可避免的，因为我们不希望将算法限制在特定的 CPU 架构上。为了尽可能快地生成机器码，我们需要我们的指令集尽可能接近原生硬件，同时仍然足够通用以支持不同的架构。在代码编译期间没有足够的时间进行昂贵的优化。
1.1.3 执行程序
实际的程序执行应尽可能利用 CPU 的多个组件。程序中应利用的一些功能包括：
- 多级缓存 (L1, L2, L3)
- μop 缓存（微操作缓存）[6_cache)]
- 算术逻辑单元 (ALU)
- 浮点单元 (FPU)
- 内存控制器
指令级并行 (ILP) [7]
第 2 章描述了 RandomX 虚拟机 (VM) 如何利用这些特性。
1.1.4 计算最终结果
Blake2b [12] 是一种加密安全的哈希函数，专门设计为在软件中快速运行，尤其是在现代 64 位处理器上，其速度大约是 SHA-3 的三倍，并且可以以每字节输入约 3 个时钟周期的速度运行。该函数是用于对 CPU 友好的工作量证明的理想候选者。
对于以加密安全的方式处理更大量的数据，高级加密标准 (AES) [13] 可以提供最快的处理速度，因为许多现代 CPU 支持这些操作的硬件加速。有关 AES 在 RandomX 中使用的更多详细信息，请参见第 3 章。
1.2 “简单程序问题”
当生成一个随机程序时，人们可能会选择仅在有利时才执行它。这种策略是可行的，主要有两个原因：
- 随机生成的程序的运行时间通常遵循对数正态分布 [14]（另见附录 C）。可以对生成的程序进行快速分析，如果它可能具有高于平均水平的运行时间，则可以跳过程序执行并生成一个新程序。这可以显著提高性能，特别是在运行时间分布具有重尾（许多运行时间长的异常值）且程序生成成本低廉的情况下。
- 实现可以选择针对程序执行所需功能的子集进行优化。例如，可以放弃对一些操作（如除法）的支持，或者可以更高效地实现某些指令序列。然后会对生成的程序进行分析，并且仅当它们符合优化实现的特定要求时才执行。
这些寻找具有特定属性程序的策略偏离了此工作量证明的目标，因此必须消除。这可以通过要求执行一系列 N 个随机程序链来实现，其中每个程序都是由前一个程序的输出生成的。然后使用最终程序的输出作为结果。
+---------------+ +---------------+ +---------------+ +---------------+
| | | | | | | |
输入 --> | 程序 1 | --> | 程序 2 | --> ... --> | 程序 (N-1) | --> | 程序 N | --> 结果
| | | | | | | |
+---------------+ +---------------+ +---------------+ +---------------+
其原理是，在执行完第一个程序后，矿工必须要么承诺完成整个链（其中可能包含不利的程序），要么重新开始并浪费在未完成链上所付出的努力。附录 A 给出了这如何影响不同挖矿策略的哈希率示例。
此外，这种链式程序执行具有均衡整个链运行时间的好处，因为相同分布运行时间之和的相对偏差减小了。
1.3 验证时间
由于工作量证明的用途是在无需信任的点对点网络中使用，网络参与者必须能够快速验证证明是否有效。这对工作量证明算法的复杂性设定了上限。特别是，我们为 RandomX 设定了一个目标：其验证速度至少要与它旨在取代的 CryptoNight 哈希函数 [15] 一样快。
1.4 内存硬度
除了纯粹的计算资源（如 ALU 和 FPU）之外，CPU 通常还可以访问大量 DRAM（动态随机存取存储器）[16] 形式的内存。内存子系统的性能通常被调整以匹配计算能力，例如 [17]：
- 嵌入式低功耗 CPU：单通道内存
- 桌面 CPU：双通道内存
- 工作站 CPU：三通道或四通道内存
- 高端服务器 CPU：六通道或八通道内存
为了利用外部内存以及片内内存控制器，工作量证明算法应访问一个大的内存缓冲区（称为“数据集”）。数据集必须满足：
- 大于可以存储在片上的容量（以需要外部内存）。
- 动态的（以需要可写内存）。
使用 16 纳米工艺，单个芯片上可放置的最大 SRAM 超过 512 MiB；使用 7 纳米工艺，则超过 2 GiB [18]。理想情况下，数据集的大小至少应为 4 GiB。然而，由于验证时间的限制（见下文），RandomX 选择使用的数据集大小为 2080 MiB。虽然使用当前技术（2019 年的 7 纳米）理论上可以制造出具有此 SRAM 容量的单芯片，但至少在不久的将来，这种解决方案的可行性是值得怀疑的。
1.4.1 轻客户端验证
虽然要求专用挖矿系统拥有 >2 GiB 的内存来解决工作量证明是合理的，但必须为轻客户端提供使用更少内存量来验证证明的选项。
“快速”模式和“轻量”模式所需内存的比率必须谨慎选择，以免轻量模式适合挖矿。特别是，轻量模式的空间-时间（AT）乘积不应小于快速模式的 AT 乘积。AT 乘积的减少是衡量折中攻击 [19] 的常用方法。
鉴于前面章节描述的约束，快速验证模式和轻量验证模式之间最大可能的性能比经验证确定为 8。这是因为：
- 进一步增加轻量验证时间将违反第 1.3 章规定的约束。
- 进一步减少快速模式的运行时间将违反第 1.1 章规定的约束，特别是程序生成和结果计算的开销时间会变得过高。
此外，选择 256 MiB 作为轻客户端模式所需的最大内存量。这个量对于 Raspberry Pi 等小型单板计算机来说也是可以接受的。
为了保持恒定的内存-时间乘积，快速模式的最大内存需求为：
8 * 256 MiB = 2048 MiB
这可以进一步增加，因为轻量模式需要额外的芯片面积用于 SuperscalarHash 函数（参见规范第 3.4 章和第 6 章）。假设每个 SuperscalarHash 核心的保守估计面积为 0.2 mm²，DRAM 密度为 0.149 Gb/mm² [20]，则额外内存为：
8 * 0.2 * 0.149 * 1024 / 8 = 30.5 MiB
或四舍五入到最接近的 2 次幂为 32 MiB。快速模式的总内存需求可以是 2080 MiB，同时保持大致恒定的 AT 乘积。
2. 虚拟机架构
本节描述 RandomX 虚拟机 (VM) 的设计。
2.1 指令集
RandomX 使用固定长度的指令编码，每条指令 8 字节。这允许在指令字中包含一个 32 位的立即数值。指令字位的解释经过选择，使得任何 8 字节字都是有效指令。这允许非常高效的随机程序生成（参见第 1.1.1 章）。
2.1.1 指令复杂度
该 VM 是一个复杂指令集 (CISC) 机器，允许寄存器和内存寻址操作数。然而，每条 RandomX 指令仅转换为 1-7 条 x86 指令（平均 1.8 条）。保持指令复杂度相对较低以最小化具有定制指令集的专用硬件的效率优势非常重要。
2.2 程序
VM 执行的程序采用由 256 条随机指令组成的循环形式。
- 256 条指令足够长，可以提供大量可能的程序，并为分支提供足够的空间。可以生成的不同程序数量限制为 2512 = 1.3e+154，这是随机生成器可能种子值的数量。
- 256 条指令足够短，使得高性能 CPU 执行一次迭代所需的时间与从 DRAM 获取数据所需的时间相似。这是有利的，因为它允许数据集访问同步并可完全预取（参见第 2.9 章）。
- 由于程序是一个循环，它可以利用某些 x86 CPU 中存在的 μop 缓存 [6_cache)]。从 μop 缓存运行循环允许 CPU 关闭 x86 指令解码器，这应有助于平衡 x86 架构与具有简单指令解码的架构之间的能效。
2.3 寄存器
VM 使用 8 个整数寄存器和 12 个浮点寄存器。这是在常见 64 位 CPU 架构中（x86-64 的架构寄存器数量最少）可以分配为物理寄存器的最大值。使用更多的寄存器会使 x86 CPU 处于劣势，因为它们将不得不使用内存来存储 VM 寄存器内容。
2.4 整数运算
RandomX 使用所有具有高输出熵的基本整数运算：加法 (IADD_RS, IADD_M)、减法 (ISUB_R, ISUB_M, INEG_R)、乘法 (IMUL_R, IMUL_M, IMULH_R, IMULH_M, ISMULH_R, ISMULH_M, IMUL_RCP)、异或 (IXOR_R, IXOR_M) 和循环移位 (IROR_R, IROL_R)。
2.4.1 IADD_RS
IADD_RS 指令利用了 CPU 的地址计算逻辑，并且可以被大多数 CPU（x86 lea，arm add）在单个硬件指令中执行。
2.4.2 IMUL_RCP
由于整数除法在 CPU 中没有完全流水线化，并且可以在 ASIC 中做得更快，因此 IMUL_RCP 指令要求每个程序只进行一次除法来计算倒数。这迫使 ASIC 包含一个硬件除法器，同时不会在程序执行期间给它们带来性能优势。
2.4.3 IROR_R/IROL_R
循环移位指令在右移和左移之间分配，比例为 4:1。右移频率更高，因为某些架构（如 ARM）本身不支持左移（必须使用右移来模拟）。
2.4.4 ISWAP_R
该指令可以被支持寄存器重命名/移动消除的 CPU 高效执行。
2.5 浮点运算
RandomX 使用双精度浮点运算，大多数 CPU 都支持双精度，并且比单精度需要更复杂的硬件。所有操作都作为 128 位向量运算执行，这也得到所有主要 CPU 架构的支持。
RandomX 使用 IEEE 754 标准保证给出正确舍入结果的五种运算：加法、减法、乘法、除法和平方根。使用了标准定义的所有 4 种舍入模式。
2.5.1 浮点寄存器组
浮点运算的域被分成“加法”运算（使用寄存器组 F）和“乘法”运算（使用寄存器组 E）。这样做是为了防止在将小数加到大数时加法/减法变成空操作。由于 F 组寄存器的范围限制在 ±3.0e+14 左右，因此加或减绝对值大于 1 的浮点数总是会改变至少 5 个小数位。
因为 F 组寄存器的有限范围允许使用更高效的定点表示（使用 80 位数字），所以 FSCAL 指令操作浮点格式的二进制表示以使这种优化更加困难。
E 组寄存器被限制为正值，这避免了 NaN 结果（例如负数的平方根或 0 * ∞）。除法仅使用内存源操作数，以避免被优化为乘以常数倒数。E 组内存操作数的指数设置为 -255 到 0 之间的值，以避免除以 0 和乘以 0，并增加可获得的数字范围。E 组寄存器值的近似范围是 1.7E-77 到 无穷大 (infinity)。
每个程序循环结束时浮点寄存器值的近似分布如下图所示（左图 - F 组，右图 - E 组）：
(注：区间由左侧值标记，例如标记为 1e-40 的区间包含从 1e-40 到 1e-20 的值。)
F 组寄存器值在 1e+14 处的小数目是由 FSCAL 指令引起的，该指令显著增加了寄存器值的范围。
E 组寄存器覆盖了非常大的数值范围。大约 2% 的程序至少产生一个 无穷大 (infinity) 值。
为了最大化熵，同时也为了适应一个 64 字节的缓存行，浮点寄存器在每个迭代结束时使用异或 (XOR) 操作组合后存储到暂存器 (Scratchpad) 中。
2.6 分支
现代 CPU 投入了大量的芯片面积和能量来处理分支。这包括：
- 分支预测单元 [21]
- 检查点/回滚状态，允许 CPU 在分支预测错误时恢复。
为了利用推测设计，随机程序应包含分支。然而，如果分支预测失败，推测执行的指令将被丢弃，这会导致每次预测错误都会浪费一定量的能量。因此，我们应致力于最小化预测错误的分支数量。
此外，代码中的分支至关重要，因为它们显著减少了可以进行的静态优化的数量。例如，考虑以下 x86 指令序列：
...
branch_target_00:
...
xor r8, r9
test r10, 2088960
je branch_target_00
xor r8, r9
...
XOR 操作通常会相互抵消，但由于分支的存在，不能进行优化，因为如果分支被采用，结果将会不同。同样，如果不是因为分支，ISWAP_R 指令总是可以被静态优化掉。
通常，随机分支的设计必须满足：
- 不可能出现无限循环。
- 预测错误的分支数量很少。
- 分支条件依赖于运行时值，以禁用静态分支优化。
2.6.1 分支预测
不幸的是，我们尚未找到在 RandomX 中利用分支预测的方法。因为 RandomX 是一个共识协议，所有规则必须预先设定，这包括分支规则。完全可预测的分支不能依赖于任何 VM 寄存器的运行时值（因为寄存器值是伪随机且不可预测的），因此它们必须是静态的，从而容易被专用硬件优化。
2.6.2 CBRANCH 指令
因此，RandomX 使用随机分支，其跳转概率为 1/256，并且分支条件依赖于一个整数寄存器值。这些分支将被 CPU 预测为“不跳转 (not taken)”。在大多数 CPU 设计中，除非发生跳转，否则这类分支是“免费的”。虽然这没有利用分支预测器，但与非推测性分支处理相比，推测性设计将看到显著的性能提升——更多信息参见附录 B。
分支条件和跳转目标的选择方式确保了在 RandomX 代码中不可能出现无限循环，因为控制分支的寄存器在重复的代码块中永远不会被修改。每条 CBRANCH 指令最多可以连续跳转两次。使用谓词执行 [22)] 来处理 CBRANCH 是不切实际的，因为大多数情况下分支不被采用。
2.7 指令级并行
CPU 利用多种利用代码指令级并行性的技术来提高性能。这些技术包括：
- 拥有多个可以并行执行操作的执行单元（超标量执行）。
- 不按程序顺序执行指令，而是按操作数可用的顺序执行（乱序执行）。
- 预测分支的走向，以增强超标量和乱序执行的益处。
RandomX 受益于所有这些优化。详细分析见附录 B。
2.8 暂存器 (Scratchpad)
暂存器用作读写内存。其大小被选择为完全适合 CPU 缓存。
2.8.1 暂存器层级
暂存器分为 3 级，以模拟典型的 CPU 缓存层次结构 [23]。大多数 VM 指令访问“L1”和“L2”暂存器，因为 L1 和 L2 CPU 缓存靠近 CPU 执行单元，并提供最佳随机访问延迟。从 L1 和 L2 读取的比例为 3:1，这与典型延迟的反比相匹配（见下表）。
| CPU μ架构 | L1 延迟 | L2 延迟 | L3 延迟 | 来源 |
|---|
| ARM Cortex A55 | 2 | 6 | - | [24] |
| AMD Zen+ | 4 | 12 | 40 | [25] |
| Intel Skylake | 4 | 12 | 42 | [26#Memory_Hierarchy)] |
L3 缓存要大得多，并且距离 CPU 核心更远。因此，其访问延迟要高得多，并可能导致程序执行停滞。
因此，RandomX 每次程序迭代仅执行 2 次对“L3”暂存器的随机访问（规范第 4.6.2 章中的步骤 2 和 3）。来自给定迭代的寄存器值被写入它们加载的相同位置，这保证了所需的缓存行已被移动到更快的 L1 或 L2 缓存中。
此外，从固定地址读取的整数指令也使用整个“L3”暂存器（规范表 5.1.4），因为重复访问将确保缓存行被放置在 CPU 的 L1 缓存中。这表明暂存器级别并不总是直接对应于相同的 CPU 缓存级别。
2.8.2 暂存器写入
在 VM 执行期间，暂存器以两种方式被修改：
- 在每次程序迭代结束时，所有寄存器值被写入“L3”暂存器（参见规范第 4.6.2 章，步骤 9 和 11）。这每次迭代总共写入 128 字节，分为两个 64 字节块。
- ISTORE 指令执行显式存储。平均每个程序有 16 次存储，其中 2 次存储进入“L3”级别。每条 ISTORE 指令写入 8 字节。
下图显示了在哈希计算期间对暂存器写入分布的示例。图像中的每个像素代表暂存器的 8 字节。红色像素代表在哈希计算期间至少被覆盖一次的暂存器部分。“L1”和“L2”级别在左侧（几乎完全被覆盖）。暂存器的右侧代表底部的 1792 KiB。其中只有大约 66% 被覆盖，但写入是均匀且随机分布的。
暂存器熵分析见附录 D。
2.8.3 读写比率
程序每次迭代平均进行 39 次读取（指令 IADD_M, ISUB_M, IMUL_M, IMULH_M, ISMULH_M, IXOR_M, FADD_M, FSUB_M, FDIV_M）和 16 次写入（指令 ISTORE）到暂存器。每次迭代额外隐式读写 128 字节以初始化并存储寄存器值。每次迭代从数据集 (Dataset) 读取 64 字节数据。总计：
- 每次程序迭代从内存读取的平均数据量为：39 * 8 + 128 + 64 = 504 字节。
- 每次程序迭代写入内存的平均数据量为：16 * 8 + 128 = 256 字节。
这接近 2:1 的读/写比率，这是 CPU 优化的目标。
2.9 数据集 (Dataset)
由于暂存器通常存储在 CPU 缓存中，因此只有数据集访问会利用内存控制器。
RandomX 每次程序迭代从数据集随机读取一次（每个哈希结果 16384 次）。由于数据集必须存储在 DRAM 中，它提供了一个自然的并行化限制，因为 DRAM 每个存储体组 (bank group) 每秒最多只能进行约 2500 万次随机访问。每个独立寻址的存储体组允许约 1500 H/s 的吞吐量。
所有数据集访问读取一个 CPU 缓存行（64 字节）并且是完全预取的。执行规范第 4.6.2 章中描述的一次程序迭代所需的时间大约等于典型的 DRAM 访问延迟（50-100 ns）。
2.9.1 缓存 (Cache)
用于轻量验证和数据集构建的缓存 (Cache) 比数据集小约 8 倍。为了保持恒定的空间-时间乘积 (AT)，每个数据集项由 8 次随机缓存访问构造而成。
因为 256 MiB 足够小，可以包含在片内，所以 RandomX 使用自定义的高延迟、高功耗混合函数（“SuperscalarHash”），它抵消了使用低延迟内存的优势，并且计算 SuperscalarHash 所需的能量使得轻量模式用于挖矿效率非常低下（参见第 3.4 章）。
使用少于 256 MiB 内存是不可能的，因为使用了具有 3 次迭代的抗折衷攻击 (tradeoff-resistant) 的 Argon2d。当使用 3 次迭代（遍数）时，将内存使用减半会使最佳折衷攻击 [27] 的计算成本增加 3423 倍。
3. 自定义函数
3.1 AesGenerator1R
AesGenerator1R 设计用于尽可能快地生成伪随机数据以填充暂存器。它利用了现代 CPU 中硬件加速的 AES。每输出 16 字节仅执行一轮 AES，这导致在大多数现代 CPU 中吞吐量超过 20 GB/s。
AesGenerator1R 在初始化状态足够“随机”时能提供良好的输出分布（参见附录 F）。
3.2 AesGenerator4R
AesGenerator4R 使用 4 轮 AES 为程序缓冲区初始化生成伪随机数据。由于 2 轮 AES 足以实现所有输入位的完全雪崩效应 [28]，AesGenerator4R 具有优异的统计特性（参见附录 F），同时保持非常好的性能。
该生成器的可逆特性不是问题，因为生成器状态总是使用不可逆哈希函数 (Blake2b) 的输出进行初始化。
3.3 AesHash1R
AesHash 设计用于尽可能快地计算暂存器指纹。它将暂存器解释为一组 AES 轮密钥，因此相当于进行了 32768 轮的 AES 加密。最后执行额外的两轮以确保每个通道 (lane) 中的所有暂存器位都发生雪崩效应。
AesHash1R 的可逆特性不是问题，主要有两个原因：
- 无法直接控制 AesHash1R 的输入。
- AesHash1R 的输出被传递到不可逆的 Blake2b 哈希函数中。
3.4 SuperscalarHash
SuperscalarHash 设计用于在 CPU 等待从 DRAM 加载数据时消耗尽可能多的功耗。170 个周期的目标延迟对应于通常 40-80 ns 的 DRAM 延迟和 2-4 GHz 的时钟频率。为具有低延迟内存的轻量模式挖矿设计的 ASIC 设备在计算数据集项时将被 SuperscalarHash 所瓶颈，并且其效率将被 SuperscalarHash 的高功耗所破坏。
平均 SuperscalarHash 函数总共包含 450 条指令，其中 155 条是 64 位乘法。平均而言，最长的依赖链是 95 条指令长。一个用于轻量模式挖矿的 ASIC 设计，具有 256 MiB 片内内存和所有操作 1 周期延迟，在假设无限并行化的情况下，平均需要 95 8 = 760 个周期来构建一个数据集项。它必须为每个项执行 155 8 = 1240 次 64 位乘法，这将消耗与从 DRAM 加载 64 字节相当的能量。
附录
A. 链接 VM 执行的效果
第 1.2 章描述了为什么链接 N 个随机程序以防止寻找“简单”程序的挖矿策略。RandomX 使用 N = 8。
让我们将 Q 定义为使用过滤策略时可接受程序的比率。例如 Q = 0.75 表示 25% 的程序被拒绝。
对于 N = 1，没有浪费的程序执行，唯一的成本是程序生成和过滤本身。下面的计算假设这些成本为零，唯一的实际成本是程序执行。然而，这是一种简化，因为在 RandomX 中程序生成并非免费（第一个程序生成需要完整的暂存器初始化），但它描述了攻击者的最佳情况。
对于 N > 1，第一个程序可以像往常一样被过滤，但在程序执行后，有 1-Q 的几率下一个程序应该被拒绝，这样我们就浪费了一次程序执行。
对于 N 次链接执行，只有 QN 的几率链中的所有程序都是可接受的。然而，在每次尝试找到这样一条链的过程中，我们将浪费执行一些程序。对于 N = 8，每次尝试浪费的程序数量等于 (1-Q)*(1+2*Q+3*Q2+4*Q3+5*Q4+6*Q5+7*Q6)（当 Q = 0.75 时约为 2.5）。
让我们考虑 3 种挖矿策略：
策略 I
诚实的矿工，不拒绝任何程序 (Q = 1)。
策略 II
使用优化的定制硬件的矿工，无法执行 25% 的程序 (Q = 0.75)，但受支持的程序可以快 50% 执行。
策略 III
可以执行所有程序的矿工，但拒绝链中第一个程序运行时间最慢的 25%。这为链中第一个程序提供了 5% 的性能提升（这与附录 C 中的运行时间分布相匹配）。
结果
下表列出了上述 3 种策略针对不同 N 值的结果。列 N(I), N(II) 和 N(III) 列出了每种策略平均需要执行的程序数量以获得一个有效的哈希结果（这包括在拒绝链中浪费的程序）。列 Speed(I), Speed(II) 和 Speed(III) 列出了相对于策略 I 的平均挖矿性能。
| N | N(I) | N(II) | N(III) | Speed(I) | Speed(II) | Speed(III) |
|---|
| 1 | 1 | 1 | 1 | 1.00 | 1.50 | 1.05 |
| 2 | 2 | 2.3 | 2 | 1.00 | 1.28 | 1.02 |
| 4 | 4 | 6.5 | 4 | 1.00 | 0.92 | 1.01 |
| 8 | 8 | 27.0 | 8 | 1.00 | 0.44 | 1.00 |
对于 N = 8，策略 II 的执行速度不到诚实矿工的一半，尽管对选定程序具有 50% 的性能优势。策略 III 的微小统计优势在 N = 8 的情况下可以忽略不计。
B. 性能模拟
如第 2.7 章所讨论的，RandomX 旨在利用现代高性能 CPU 的复杂设计。为了评估超标量、乱序和推测执行的影响，我们进行了简化的 CPU 模拟。源代码可在 perf-simulation.cpp 中找到。
CPU 模型
模型 CPU 使用 3 级流水线来实现每周期 1 条指令的理想吞吐量：
(1) (2) (3)
+------------------+ +----------------+ +----------------+
| 指令取指 | | | | |
| + 解码 | ---> | 内存访问 | ---> | 执行 |
| | | | | |
+------------------+ +----------------+ +----------------+
3 个阶段是：
- 指令取指和解码。此阶段从程序缓冲区加载指令并解码指令操作和操作数。
- 内存访问。如果该指令使用内存操作数，则在此阶段从暂存器加载。这包括内存地址的计算。存储也在此阶段执行。地址寄存器的值必须在此阶段可用。
- 执行。此阶段使用前几个阶段检索到的操作数执行指令，并将结果写入寄存器文件。
请注意，这是一个乐观的短流水线，不允许非常高的时钟速度。使用更长流水线的设计将显著增加推测执行的好处。
超标量执行
我们的模型 CPU 包含两种组件：
- 执行单元 (EXU) - 用于执行实际的整数或浮点操作。除 ISTORE 外的所有 RandomX 指令都必须在第 3 流水线阶段使用执行单元。所有操作都被认为仅需 1 个时钟周期。
- 内存单元 (MEM) - 用于加载和存储到暂存器。所有内存指令（包括 ISTORE）在第 2 流水线阶段使用内存单元。
超标量设计将包含多个执行或内存单元以提高性能。
乱序执行
模拟模型支持两种设计：
- 按序 - 所有指令按照它们在程序缓冲区中出现的顺序执行。如果遇到依赖关系或所需的 EXU/MEM 单元不可用，此设计将暂停。
- 乱序 - 不按程序顺序执行指令，而是当指令的操作数就绪且所需的 EXU/MEM 单元可用时执行该指令。
分支处理
模拟模型支持两种分支处理类型：
- 非推测性 - 遇到分支时，流水线暂停。这通常为每个分支增加 3 个周期的惩罚。
- 推测性 - 所有分支被预测为“不跳转”，如果发生预测错误，则刷新流水线（概率为 1/256）。
结果
模拟了以下 10 种设计，并测量了执行一个 RandomX 程序（256 条指令）的平均时钟周期数。
| 设计 | 超标量配置 | 重排序 | 分支处理 | 执行时间 [周期] | IPC |
|---|
| #1 | 1 EXU + 1 MEM | 按序 | 非推测性 | 293 | 0.87 |
| #2 | 1 EXU + 1 MEM | 按序 | 推测性 | 262 | 0.98 |
| #3 | 2 EXU + 1 MEM | 按序 | 非推测性 | 197 | 1.3 |
| #4 | 2 EXU + 1 MEM | 按序 | 推测性 | 161 | 1.6 |
| #5 | 2 EXU + 1 MEM | 乱序 | 非推测性 | 144 | 1.8 |
| #6 | 2 EXU + 1 MEM | 乱序 | 推测性 | 122 | 2.1 |
| #7 | 4 EXU + 2 MEM | 按序 | 非推测性 | 135 | 1.9 |
| #8 | 4 EXU + 2 MEM | 按序 | 推测性 | 99 | 2.6 |
| #9 | 4 EXU + 2 MEM | 乱序 | 非推测性 | 89 | 2.9 |
| #10 | 4 EXU + 2 MEM | 乱序 | 推测性 | 64 | 4.0 |
超标量、乱序和推测设计的好处显而易见。
C. RandomX 运行时间分布
运行时间数据在运行于 3.0 GHz 的 AMD Ryzen 7 1700（使用 1 个核心）上测量。测量程序执行和验证时间的源代码可在 runtime-distr.cpp 中找到。测量 x86 JIT 编译器性能的源代码可在 jit-performance.cpp 中找到。
快速模式 - 程序执行
下图显示了单个 VM 程序（在快速模式下）运行时间的分布。这包括：程序生成、JIT 编译、VM 执行和寄存器文件的 Blake2b 哈希。测得程序生成和 JIT 编译每个程序耗时 3.6 μs。
AMD Ryzen 7 1700 在快速模式下（使用 1 个线程）每秒可计算 625 个哈希，这意味着单个哈希结果耗时 1600 μs (1.6 ms)。这包括（大约）：
- 1480 μs 用于 VM 执行（8 个程序）
- 45 μs 用于初始暂存器填充 (AesGenerator1R)。
- 45 μs 用于最终暂存器哈希 (AesHash1R)。
- 30 μs 用于程序生成和 JIT 编译（8 个程序）
这给出了 7.5% 的总开销（每个哈希花费在未执行 VM 上的时间）。
轻量模式 - 验证时间
下图显示了使用轻量模式计算 1 个哈希结果所需时间的分布。大部分时间用于执行 SuperscalarHash 来计算数据集项（14.8 ms 中的 13.2 ms）。平均验证时间与 CryptoNight 算法的性能完全匹配。
D. 暂存器熵分析
执行 8 次程序后暂存器的平均熵是使用 LZMA 压缩算法近似的：
- 计算哈希结果，并将最终的暂存器写入扩展名为 '.spad' 的文件（源代码：scratchpad-entropy.cpp）
- 使用 7-Zip [29] 在 Ultra 压缩模式下压缩文件：
7z.exe a -t7z -m0=lzma2 -mx=9 scratchpads.7z *.spad
生成的存档大小大约是暂存器文件未压缩大小的 99.98%。这表明在 VM 执行期间，暂存器保持了高熵。
E. SuperscalarHash 分析
SuperscalarHash 是 RandomX 用于生成数据集项的自定义函数。它对 8 个整数寄存器进行操作，并使用随机指令序列。大约 1/3 的指令是乘法。
下图显示了 SuperscalarHash 对改变输入寄存器单个比特的敏感性：
这表明 SuperscalarHash 对高位比特的敏感性相当低，对最低位比特的敏感性略有降低。对第 3-53 位（含）的敏感性最高。
在计算数据集项时，第一个 SuperscalarHash 的输入仅依赖于项编号。为了确保结果的良好分布，规范第 7.3 节中描述的常量经过选择，为范围 0-34078718（数据集包含 34078719 项）内的所有项编号提供唯一的第 3-53 位值。所有数据集项编号的所有初始寄存器值都经过检查，以确保每个寄存器的第 3-53 位是唯一的且没有冲突（源代码：superscalar-init.cpp）。虽然这对于从 SuperscalarHash 获得唯一输出并非严格必要，但这是一种安全预防措施，可以减轻随机生成的 SuperscalarHash 实例的非完美雪崩特性的影响。
F. RNG 的统计测试
AesGenerator1R 和 AesGenerator4R 都使用 TestU01 库 [30] 进行了测试，该库用于随机数生成器的经验测试。源代码可在 rng-tests.cpp 中找到。
测试对每个生成器采样约 200 MB（“SmallCrush”测试）、500 GB（“Crush”测试）或 4 TB（“BigCrush”测试）的输出。这远远超过 RandomX 中生成的量（AesGenerator4R 为 2176 字节，AesGenerator1R 为 2 MiB），因此测试失败并不一定意味着生成器不适合其用例。
AesGenerator4R
当使用 Blake2b 哈希函数初始化时，该生成器通过了“BigCrush”套件中的所有测试：
$ bin/rng-tests 1
state0 = 67e8bbe567a1c18c91a316faf19fab73
state1 = 39f7c0e0a8d96512c525852124fdc9fe
state2 = 7abb07b2c90e04f098261e323eee8159
state3 = 3df534c34cdfbb4e70f8c0e1826f4cf7
...
========= BigCrush 的摘要结果 =========
版本: TestU01 1.2.3
生成器: AesGenerator4R
统计量数量: 160
总 CPU 时间: 02:50:18.34
所有测试均已通过
即使初始状态设置为全零，该生成器也通过了“Crush”套件中的所有测试。
$ bin/rng-tests 0
state0 = 00000000000000000000000000000000
state1 = 00000000000000000000000000000000
state2 = 00000000000000000000000000000000
state3 = 00000000000000000000000000000000
...
========= Crush 的摘要结果 =========
版本: TestU01 1.2.3
生成器: AesGenerator4R
统计量数量: 144
总 CPU 时间: 00:25:17.95
所有测试均已通过
AesGenerator1R
当使用 Blake2b 哈希函数初始化时，该生成器通过了“Crush”套件中的所有测试。
$ bin/rng-tests 1
state0 = 67e8bbe567a1c18c91a316faf19fab73
state1 = 39f7c0e0a8d96512c525852124fdc9fe
state2 = 7abb07b2c90e04f098261e323eee8159
state3 = 3df534c34cdfbb4e70f8c0e1826f4cf7
...
========= Crush 的摘要结果 =========
版本: TestU01 1.2.3
生成器: AesGenerator1R
统计量数量: 144
总 CPU 时间: 00:25:06.07
所有测试均已通过
当初始状态初始化为全零时，该生成器在“Crush”套件的 144 项测试中有 1 项失败：
$ bin/rng-tests 0
state0 = 00000000000000000000000000000000
state1 = 00000000000000000000000000000000
state2 = 00000000000000000000000000000000
state3 = 00000000000000000000000000000000
...
========= Crush 的摘要结果 =========
版本: TestU01 1.2.3
生成器: AesGenerator1R
统计量数量: 144
总 CPU 时间: 00:26:12.75
以下测试给出的 p 值超出了 [0.001, 0.9990]：
(eps 表示值 < 1.0e-300):
(eps1 表示值 < 1.0e-15):
测试 p 值
----------------------------------------------
12 BirthdaySpacings, t = 3 1 - 4.4e-5
----------------------------------------------
所有其他测试均已通过
参考文献
[1] CryptoNote 白皮书 - https://cryptonote.org/whitepaper.pdf
[2] ProgPoW: 低效的整数乘法 - https://github.com/ifdefelse/ProgPOW/issues/16
[3] 加密哈希函数 - https://en.wikipedia.org/wiki/Cryptographic_hash_function
[4] randprog - https://github.com/hyc/randprog
[5] RandomJS - https://github.com/tevador/RandomJS
[6] μop 缓存 - https://en.wikipedia.org/wiki/CPU_cache#Micro-operation_(%CE%BCop_or_uop)_cache
[7] 指令级并行 - https://en.wikipedia.org/wiki/Instruction-level_parallelism
[8] 超标量处理器 - https://en.wikipedia.org/wiki/Superscalar_processor
[9] 乱序执行 - https://en.wikipedia.org/wiki/Out-of-order_execution
[10] 推测执行 - https://en.wikipedia.org/wiki/Speculative_execution
[11] 寄存器重命名 - https://en.wikipedia.org/wiki/Register_renaming
[12] Blake2 哈希函数 - https://blake2.net/
[13] 高级加密标准 - https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
[14] 对数正态分布 - https://en.wikipedia.org/wiki/Log-normal_distribution
[15] CryptoNight 哈希函数 - https://cryptonote.org/cns/cns008.txt
[16] 动态随机存取存储器 - https://en.wikipedia.org/wiki/Dynamic_random-access_memory
[17] 多通道内存架构 - https://en.wikipedia.org/wiki/Multi-channel_memory_architecture
[18] Obelisk GRN1 芯片细节 - https://www.grin-forum.org/t/obelisk-grn1-chip-details/4571
[19] Biryukov 等人：内存困难函数的折衷密码分析 - https://eprint.iacr.org/2015/227.pdf
[20] SK 海力士 20nm DRAM 密度 - http://en.thelec.kr/news/articleView.html?idxno=20
[21] 分支预测器 - https://en.wikipedia.org/wiki/Branch_predictor
[22] 谓词执行 - https://en.wikipedia.org/wiki/Predication_(computer_architecture)
[23] CPU 缓存 - https://en.wikipedia.org/wiki/CPU_cache
[24] Cortex-A55 微架构 - https://www.anandtech.com/show/11441/dynamiq-and-arms-new-cpus-cortex-a75-a55/4
[25] AMD Zen+ 微架构 - https://en.wikichip.org/wiki/amd/microarchitectures/zen%2B#Memory_Hierarchy
[26] Intel Skylake 微架构 - https://en.wikichip.org/wiki/intel/microarchitectures/skylake_(client)#Memory_Hierarchy
[27] Biryukov 等人：用于加密货币和密码哈希的快速且抗折衷的内存困难函数 - https://eprint.iacr.org/2015/430.pdf 表 2，第 8 页
[28] J. Daemen, V. Rijmen: AES 提案: Rijndael - https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guidelines/documents/aes-development/rijndael-ammended.pdf 第 28 页
[29] 7-Zip 文件归档器 - https://www.7-zip.org/
[30] TestU01 库 - http://simul.iro.umontreal.ca/testu01/tu01.html
