RandomX Design

Posted on Edited on

原文https://github.com/tevador/RandomX/blob/master/doc/design.md

为了最大限度地减少专用硬件的性能优势，工作量证明 (PoW) 算法必须通过针对现有通用硬件的特定功能来实现设备绑定。
这是一项复杂的任务，因为我们必须针对来自不同制造商的具有不同架构的一大类设备。

有两类不同的通用处理设备：中央处理单元 (CPU) 和图形处理单元 (GPU)。RandomX 针对 CPU 的原因如下：

  • CPU非专业挖矿设备，对于正常用户来说更普遍且更容易访问。受 CPU 限制的算法更加平等，并允许更多参与者加入网络。这是[原始CryptoNote白皮书][cn_paper]中所述的目标之一。
  • 在不同的 CPU 体系结构中存在大量通用的本地硬件指令子集。GPU 则不能这样说。例如，NVIDIA 和 AMD GPU 没有通用的整数乘法指​​令。
  • 所有主要的CPU 指令集都有详细的文档记录，有多个可用的开源编译器。相比之下，GPU 指令集通常是专有的，可能需要供应商特定的闭源驱动程序才能获得最大性能。

1. 设计考量

CPU 绑定工作量证明的最基本思想是“工作”必须是动态的。这利用了 CPU 接受两种输入的事实：数据（主要输入）和代码（指定对数据执行什么操作）。

相反，经典的加密散列hash函数 [ 3 ] 并不适合 CPU 的工作，因为它们的唯一输入是数据，而操作序列是固定的，可以通过专用集成电路ASIC更有效地执行。

1.1 动态工作量证明

一个动态PoW算法通常可以包括以下4个步骤：

  1. 生成随机程序。
  2. 将其翻译成CPU的本地机器代码（机器码）。
  3. 执行程序。
  4. 将程序的输出转换为加密安全值。

实际“有用”的 CPU 密集型工作在步骤 3 中执行，因此必须调整算法以最小化剩余步骤的开销。

1.1.1 生成随机程序

在动态PoW设计早期的尝试是基于在高级语言，如C或Javascript [4，5]。但是，由于两个主要原因，导致非常低效：

  • 高级语言具有复杂的语法，因此生成有效程序的速度相对较慢，因为它需要创建抽象语法树 (ASL)。
  • 一旦生成了程序的源代码，编译器一般会将文本表示解析回ASL，这使得生成源代码的整个过程变得多余。

生成随机程序的最快方法是使用无逻辑生成器：简单地用随机数据填充缓冲区。
这当然需要设计一种无语法的编程语言（或指令集），其中所有随机位串都代表有效程序。

1.1.2 将程序翻译成机器码

这一步是不可避免的，因为我们不想将算法限制在特定的 CPU 架构上。
为了尽可能快地生成机器代码，我们需要我们的指令集尽可能接近原生硬件，同时仍然足够通用以支持不同的架构。
在代码编译期间没有足够的时间进行昂贵的优化。

1.1.3 执行程序

实际的程序执行应该使用尽可能多的CPU组件。应该在程序中使用的一些功能是：

  • 多级缓存（L1、L2、L3）
  • μop 缓存 [ 6 ]
  • 算术逻辑单元 (ALU)
  • 浮点单元 (FPU)
  • 内存控制器
  • 指令级并行[ 7 ]
    • 超标量执行 [ 8 ]
    • 乱序执行 [ 9 ]
    • 投机性执行 [ 10 ]
    • 寄存器重命名 [ 11 ]

第2章描述了 RandomX VM 如何利用这些功能。

1.1.4 计算最终结果

Blake2b是一种加密安全的散列函数，专门设计用于在软件中快速运行，尤其是在现代 64 位处理器上，它比 SHA-3 快三倍左右，并且可以以每 3 个时钟周期的速度运行输入字节。此函数是用于 CPU 友好的工作证明的理想候选者。

为了以加密安全的方式处理大量数据，高级加密标准 (AES) 可以提供最快的处理速度，因为许多现代 CPU 支持这些操作的硬件加速。有关在 RandomX 中使用 AES 的更多详细信息，请参阅第 3 章。

1.2 “简易程序问题”

当一个随机程序产生时，人们可以选择只在它有利的时候执行它。这种策略之所以可行，主要有两个原因：

随机生成程序的运行时间通常遵循对数正态分布 [ 14 ]（另见附录 C）。

  1. 生成的程序可能会被快速分析，如果它的运行时间可能高于平均水平，则可能会跳过程序执行并生成一个新程序。这可以显着提高性能，尤其是在运行时分布有重尾（许多长期运行的异常值）并且程序生成成本低的情况下。
  2. 实现可以选择优化程序执行所需的功能子集。例如，可能会放弃对某些操作（例如除法）的支持，或者可能会更有效地实现某些指令序列。生成的程序只有在符合优化实施的特定要求时才会被分析和执行。

这些搜索特定属性程序的策略与此工作量证明的目标背道而驰，因此必须消除它们。这可以通过要求执行一系列N个随机程序来实现，这样每个程序都是从前一个程序的输出生成的。然后将最终程序的输出用作结果。

1
2
3
4
5
          +---------------+     +---------------+               +---------------+     +---------------+
          |               |     |               |               |               |     |               |
input --> |   program 1   | --> |   program 2   | -->  ...  --> | program (N-1) | --> |   program N   | --> result
          |               |     |               |               |               |     |               |
          +---------------+     +---------------+               +---------------+     +---------------+

其原理是，在第一个程序执行后，矿工要么承诺完成整个链（可能包括不利的程序），要么重新开始并浪费在未完成的链上花费的精力。附录 A 中给出了这如何影响不同挖掘策略的哈希率的示例。

此外，这种链式程序执行具有均衡整个链的运行时间的好处，因为相同分布的运行时间总和的相对偏差减少了。

1.3 验证时间
由于工作量证明的目的是在去信任的点对点网络中使用，网络参与者必须能够快速验证证明是否有效。这为工作量证明算法的复杂性设置了上限。特别是，我们为 RandomX 设定了一个目标，使其验证速度至少与 CryptoNight 哈希函数 [ 15 ]一样快，它旨在取代它。

1.4 记忆强度
除了纯计算资源，如 ALU 和 FPU，CPU 通常可以以 DRAM [ 16 ]的形式访问大量内存。内存子系统的性能通常会根据计算能力进行调整，例如 [ 17 ]：

  • 用于嵌入式和低功耗 CPU 的单通道内存
  • 用于台式机 CPU 的双通道内存
  • 用于工作站 CPU 的三通道或四通道内存
  • 用于高端服务器 CPU 的六或八通道内存

为了利用外部存储器以及片上存储器控制器，工作量证明算法应该访问一个大的存储器缓冲区（称为“数据集”）。数据集必须是：

  1. 大于可以存储在芯片上的内容（需要外部存储器）
  2. 动态（需要可写内存）

对于 16 nm 工艺而言，单个芯片上可放置的最大 SRAM 量超过 512 MiB，而对于 7 nm 工艺而言，则超过 2 GiB [ 18 ]。理想情况下，数据集的大小应至少为 4 GiB。但是，由于验证时间的限制（见下文），RandomX 使用的大小选择为 2080 MiB。虽然理论上可以使用当前技术（2019 年为 7 nm）使用如此数量的 SRAM 制造单个芯片，但这种解决方案的可行性值得怀疑，至少在不久的将来如此。

1.4.1 轻客户端验证
虽然对于解决工作量证明的专用挖矿系统要求 >2 GiB 是合理的，但必须为轻客户端提供一个选项，以使用更少的内存来验证证明。

必须谨慎选择“快速”和“轻”模式所需的内存比例，以免轻模式适合挖矿。特别是，光模式的面积时间（AT）乘积不应小于快速模式的AT乘积。减少 AT 乘积是衡量权衡攻击的常用方法 [ 19 ]。

考虑到前几章中描述的限制，根据经验确定快速和轻型验证模式之间的最大可能性能比为 8。这是因为：

  1. 进一步增加光验证时间将违反第 1.3 章中规定的限制。
  2. 进一步减少快速模式运行时间会违反第 1.1 章中规定的约束，特别是程序生成和结果计算的开销时间会变得太高。

此外，256 MiB 被选为轻客户端模式下可能需要的最大内存量。即使对于 Raspberry Pi 这样的小型单板计算机，这个数量也是可以接受的。

为了保持恒定的内存时间乘积，最大的快速模式内存要求是：

1
8 * 256 MiB = 2048 MiB

这可以进一步增加，因为光照模式需要额外的芯片面积用于 SuperscalarHash 函数（参见规范的第 3.4 章和第 6 章）。假设保守估计每个 SuperscalarHash 核心0.2 mm 2和 DRAM 密度为 0.149 Gb/mm 2 [ 20 ]，额外的内存为：

1
8 * 0.2 * 0.149 * 1024 / 8 = 30.5 MiB
  1. 虚拟机架构
    本节介绍 RandomX 虚拟机 (VM) 的设计。

2.1 指令集
RandomX 使用固定长度的指令编码，每条指令有 8 个字节。这允许在指令字中包含 32 位立即数。选择指令字位的解释，以便任何 8 字节字都是有效指令。这允许非常有效的随机程序生成（参见第 1.1.1 章）。

2.1.1 指令复杂度
VM 是一个复杂的指令集机器，允许寄存器和内存寻址操作数。然而，每条 RandomX 指令只能转换为 1-7 条 x86 指令（平均 1.8 条）。保持指令复杂度相对较低以最小化具有定制指令集的专用硬件的效率优势非常重要。

2.2 程序
VM 执行的程序具有循环的形式，由 256 条随机指令组成。

  • 256条指令足够长，可以提供大量可能的程序和足够的分支空间。可以生成的不同程序的数量限制为 2 512 = 1.3e+154，这是随机生成器可能的种子值的数量。
  • 256 条指令足够短，因此高性能 CPU 可以在与从 DRAM 中获取数据所需的时间相似的时间内执行一次迭代。这是有利的，因为它允许同步数据集访问并完全可预取（参见第 2.9 章）。
  • 由于程序是一个循环，它可以利用一些 x86 CPU 中存在的 μop 缓存 [ 6 ]。从 μop 缓存运行循环允许 CPU 关闭 x86 指令解码器的电源，这应该有助于平衡 x86 和具有简单指令解码的体系结构之间的功率效率。

2.3 寄存器
VM 使用 8 个整数寄存器和 12 个浮点寄存器。这是 x86-64 中可以分配为物理寄存器的最大值，这是常见的 64 位 CPU 架构中架构寄存器最少的。使用更多寄存器会使 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、IMULR_RIXOR） 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组）：

Imgur

1e+14FSCAL 指令导致的 F 寄存器值较少，显着增加了寄存器值的范围。

E 组寄存器涵盖了非常大的值范围。大约 2% 的程序至少产生一个infinity值。

为了最大化熵并适应一个 64 字节的高速缓存线，浮点寄存器在每次迭代结束时使用 XOR 运算进行组合，然后存储到暂存器中。

（注意：bins 由区间的左侧值标记，例如标记为 1e-40 的 bin 包含从 1e-40 到 1e-20 的值。）

1e+14 处的 F 寄存器值较少是由 FSCAL 指令引起的，该指令显着增加了寄存器值的范围。

E 组寄存器涵盖了非常大的值范围。 大约 2% 的程序产生至少一个“无穷大”值。

为了最大化熵并适应一个 64 字节的高速缓存线，浮点寄存器在每次迭代结束时使用 XOR 操作进行组合，然后存储到暂存器中。

2.6 分支

现代 CPU 投入大量芯片面积和精力来处理分支。这包括：

  • 分支预测器单元 Branch predictor
  • 检查点/回滚状态，允许 CPU 在分支预测错误的情况下恢复。

为了利用推测设计，随机程序应该包含分支。但是，如果分支预测失败，则推测执行的指令将被丢弃，这导致每次错误预测都会浪费一定的能量。因此，我们的目标应该是尽量减少错误预测的数量。

此外，代码中的分支是必不可少的，因为它们显着减少了可以进行的静态优化的数量。例如，考虑以下 x86 指令序列：

1
2
3
4
5
6
7
8
    ...
branch_target_00:
    ...
    xor r8, r9
    test r10, 2088960
    je branch_target_00
    xor r8, r9
    ...

XOR 操作通常会取消，但由于分支而无法优化掉，因为如果采用分支，结果会有所不同。类似地，如果不是用于分支，ISWAP_R 指令可以始终被静态优化。

一般来说，随机分支必须以这样的方式设计：

  1. 无限循环是不可能的。
  2. 预测错误的分支数量少。
  3. 分支条件取决于运行时值以禁用静态分支优化。

2.6.1 分支预测

不幸的是，我们还没有找到如何在 RandomX 中利用分支预测的方法。因为 RandomX 是一个共识协议，所以所有的规则都必须提前制定，包括分支规则。完全可预测的分支不能依赖于任何 VM 寄存器的运行时值（因为寄存器值是伪随机且不可预测的），因此它们必须是静态的，因此可以通过专用硬件轻松优化。

2.6.2 CBRANCH 指令

因此，RandomX 使用跳跃概率为 1/256 的随机分支和依赖于整数寄存器值的分支条件。这些分支将被 CPU 预测为“未采用”。这些分支在大多数 CPU 设计中是“免费的”，除非它们被采用。虽然这没有利用分支预测器，但与非推测分支处理相比，推测设计将显着提高性能 - 有关更多信息，请参阅附录 B。

分支条件和跳转目标的选择方式使得 RandomX 代码中的无限循环是不可能的，因为控制分支的寄存器永远不会在重复代码块中被修改。每条 CBRANCH 指令最多可以连续跳转两次。使用谓词执行 [22] 处理 CBRANCH 是不切实际的，因为大部分时间都不采用分支。

2.7 指令级并行

CPU 使用几种利用执行代码的指令级并行性的技术来提高其性能。这些技术包括：

  • 拥有多个可以并行执行操作的执行单元（超标量执行）。
  • 执行指令不是按照程序顺序，而是按照操作数可用性的顺序（乱序执行）。
  • 预测分支将采用哪种方式来增强超标量和无序执行的好处。

RandomX 受益于所有这些优化。详细分析见附录 B。

2.8 Scratchpad

Scratchpad 用作读写存储器。它的大小被选择为完全适合 CPU 缓存。

2.8.1 Scratchpad 级别

Scratchpad 分为 3 个级别以模仿典型的 CPU 缓存层次结构 CPU_cache。大多数 VM 指令访问“L1”和“L2”暂存器，因为 L1 和 L2 CPU 缓存位于靠近 CPU 执行单元的位置，并提供最佳的随机访问延迟。从 L1 和 L2 读取的比率为 3:1，这与典型延迟的反比相匹配（见下表）。

CPU μ 架构 L1 延迟 L2 延迟 L3 延迟 来源
ARM Cortex A55 2 6 - [src]
AMD Zen+ 4 12 40 [src]
Intel Skylake 4 12 42 [src]

L3 缓存要大得多，并且离 CPU 内核更远。因此，它的访问延迟要高得多，并可能导致程序执行停顿。

因此，RandomX 每次程序迭代仅对“L3”Scratchpad 执行 2 次随机访问（规范第 4.6.2 章中的第 2 步和第 3 步）。来自给定迭代的寄存器值被写入它们从中加载的相同位置，这保证了所需的缓存线已移动到更快的 L1 或 L2 缓存中。

此外，从固定地址读取的整数指令也使用整个“L3”暂存器（规范的表 5.1.4），因为重复访问将确保缓存线将放置在 CPU 的 L1 缓存中。这表明 Scratchpad 级别并不总是直接对应于相同的 CPU 缓存级别。

2.9 数据集

由于 Scratchpad 通常存储在 CPU 缓存中，因此只有数据集访问使用内存控制器。

RandomX 每次程序迭代从数据集随机读取一次（每个哈希结果 16384 次）。由于数据集必须存储在 DRAM 中，因此它提供了一个自然的并行化限制，因为 DRAM 每个存储体组每秒不能进行超过约 2500 万次随机访问。每个可单独寻址的银行组允许大约 1500 H/s 的吞吐量。

所有数据集访问读取一个 CPU 缓存行（64 字节）并完全预取。执行规范第 4.6.2 章中描述的一个程序迭代的时间与典型的 DRAM 访问延迟（50-100 ns）大致相同。

2.9.1 缓存

用于光照验证和Dataset构建的Cache，比Dataset小8倍左右。为了保持恒定的区域时间乘积，每个数据集项都由 8 次随机缓存访问构成。

由于 256 MiB 足够小，可以包含在芯片上，RandomX 使用自定义的高延迟、高功率混合函数（“SuperscalarHash”），这抵消了使用低延迟内存的好处，并且计算 SuperscalarHash 所需的能量变得轻巧模式非常低效的挖矿（见第 3.4 章）。

由于使用了具有 3 次迭代的抗折衷 Argon2d，因此不可能使用少于 256 MiB 的内存。当使用 3 次迭代（passes）时，将内存使用量减半会使最佳权衡攻击的计算成本增加 3423 倍 Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing

2.8.2 Scratchpad 写入

在 VM 执行期间，有两种方式修改 Scratchpad：

  1. 在每次程序迭代结束时，所有寄存器值都写入“L3”暂存器（参见规范章节 4.6.2，步骤 9 和 11）。这在两个 64 字节的块中每次迭代总共写入 128 字节。
  2. ISTORE 指令执行显式存储。每个程序平均有 16 个商店，其中 2 个商店进入“L3”级别。每个 ISTORE 指令写入 8 个字节。

下图显示了写入暂存器的分布示例。图像中的每个像素代表 Scratchpad 的 8 个字节。红色像素代表在散列计算期间至少被覆盖一次的便签本部分。 “L1”和“L2”级别位于左侧（几乎完全覆盖）。暂存器的右侧代表底部 1792 KiB。其中只有大约 66% 被覆盖，但写入是均匀随机分布的。

Imgur

有关 Scratchpad 熵的分析，请参见附录 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 优化的。

References