前沿工作量证明算法：RandomX

RandomX是一种新型抗ASIC和GPU的工作量证明（PoW）算法，最初为门罗币开发，但也可用于任何偏向通用CPU的区块链PoW系统。Trail of Bits受Arweave委托，以两人周的投入对这项创新算法进行评审，并就替代参数选择提供指导。其独特之处何在？为何值得关注？

标准工作量证明

在经典PoW算法（如比特币使用的hashcash）中，核心通常是密码学哈希函数，唯一变量是函数输入数据。为实现目标“难度”，要求哈希输出前缀为若干零位。每增加一个零位，挖矿难度翻倍。然而，此类算法极易通过ASIC和GPU加速，因为对所有输入执行固定操作集且内存需求有限，这是不理想的。

为何关注抗ASIC性？

理想情况下，区块链挖矿应是高度去中心化的任务，没有单一实体控制大量算力。区块链易受51%攻击，恶意多数可覆盖全局状态（如允许双花）。如果ASIC能显著提升挖矿效率超越通用CPU，经济因素将抑制基于CPU的挖矿。比特币网络即为例证，ASIC制造商建立大型矿场，少数实体控制惊人比例的算力。

过去几年，ASIC制造商展现出快速设计和制造ASIC的强大能力。因此，希望抗ASIC的项目（不转向权益证明模型，后者有其权衡）必须利用通用CPU相对于假设ASIC的特定优势。

这一需求催生了大量抗ASIC研究。RandomX代表了最新抗ASIC思想在加密货币中的具体实现。

RandomX工作原理

RandomX的核心是随机化执行概念。简言之，我们执行一系列随机指令，以利用通用CPU在动态代码执行上的灵活性。RandomX开发者详细记录了设计原理，并提供更严谨的规范说明，简化后算法步骤如下：

步骤1

使用输入密钥K通过argon2d创建称为Cache的数据结构。Argon2d最初设计为内存硬密码哈希函数。计算机通常拥有大容量快速内存，但ASIC上内存昂贵。要求大量内存是对抗专用硬件的最常见防御之一。Argon2使用多种技术确保使用大量（可配置）内存，且任何时间/内存权衡攻击无效。详情可参阅argon2规范。

步骤2

从Cache扩展数据集（只读内存结构）。数据集设计为大片内存，包含虚拟机将读取的数据。两个值控制数据集大小（RANDOMX_DATASET_BASE_SIZE和RANDOMX_DATASET_EXTRA_SIZE）。它们共同设定算法所需内存上限。额外大小用于将内存略微推过二次幂边界，增加ASIC制造商难度。实际数据集生成通过从Cache加载数据、生成一组SuperscalarHash实例，然后调用这些实例获取最终输出完成。SuperscalarHash设计在等待DRAM数据时消耗功率，这对试图从Cache动态计算数据集的ASIC不利。

步骤3

通过对输入数据执行blake2哈希并使用结果输出种子化AesGenerator来初始化暂存器（读写内存）。该生成器使用AES-NI指令填充暂存器。初始暂存器生成使用AES变换。该算法在现代CPU上已硬件加速，因此ASIC实现无优势。暂存器本身是（相对）大的读写数据结构，专门设计用于适配CPU可用缓存。

步骤4

现在进入算法核心：在虚拟机上运行的随机化程序。VM通过使用另一生成器创建的随机字节构建程序来执行。RandomX虚拟机架构精心设计，允许任何8字节字序列成为有效指令。这些指令设计用于：

• 需要双精度浮点操作
• 使用128位向量数学
• 使用所有四种IEEE 754浮点舍入模式
• 读写暂存器（如前所述，设计完全适配CPU缓存，因此非常快）
• 通过低概率分支指令利用分支预测
• 利用CPU的超标量和乱序执行能力执行指令

这些属性均是通用CPU的特定优势，在ASIC上实现需要额外晶片面积，减少其优势。

程序执行后VM的最终状态被哈希并用于生成新程序。此方式执行的循环次数可配置，默认设为八次。选择循环行为是为避免ASIC矿工可能仅实现部分操作子集并在虚拟机上仅运行“简单”程序的情况。由于后续程序无法在当前程序完全执行前确定，矿工无法预测整个链是否“简单”，因此实现部分指令集不切实际。

步骤5

最后，使用AesHash对暂存器和寄存器文件（虚拟机寄存器）进行哈希，后接最终blake2哈希。此步骤除使用AES指令外无显著抗ASIC性，但包含以显示最终哈希为64字节值。

我们的发现

在两人周评审中，我们发现三个问题（两个低严重性，一个信息性）。

AesGenerator中使用单轮AES

RandomX规范描述的AES加密指单轮AES，不足以完全混合输入数据。RandomX不依赖AES加密保障安全，而是将AES用作偏向CPU的快速变换，提供输出扩散。然而，位通过输出的扩散取决于AES轮数。

此发现严重性为“低”，因为缺乏必要扩散需在算法几乎每一步骤中找到额外偏差，然后构造输入使该偏差传播整个链。

披露此发现后，RandomX团队开发了执行四轮的新AesGenerator4R函数。该功能已通过拉取请求46合并入RandomX。程序生成部分的四轮解决了此问题记录的问题。

VM正确性测试和验证不足

RandomX代码库缺乏验证虚拟机（VM）语义的测试覆盖。Trail of Bits投入本 engagement 的一半时间（一人周）评估算法实现的通用安全属性。虽然此努力揭示若干代码质量发现，但不足以验证VM实现中无语义错误。

此发现严重性为“低”，因为RandomX的正确性无关紧要，只要：（1）其输出是确定性的，（2）其输出是密码学随机的，（3）其参考实现是区块链中挖矿的唯一实现。然而，规范与参考实现间的任何差异可能导致共识问题和区块链分叉。

考虑第三方净室实现RandomX规范在使用RandomX进行工作量证明的区块链上流行的情况。如果矿工实现间存在即使细微语义差异，区块链将分叉——可能发生在过去的某个遥远时点。

可配置参数脆弱

RandomX包含47个可配置参数，包括并行化标志、内存消耗、初始KDF迭代次数、数据集内存大小、虚拟CPU三级缓存大小、VM上执行程序的大小和迭代次数，以及缓存访问/延迟。默认参数选择为最大化算法的CPU优势。然而，51%攻击的威胁迫使有兴趣使用RandomX的替代区块链对这些参数做出不同选择。这些选择必须在无清晰洞察哪些参数可能损害算法优势的情况下做出。这种脆弱性可能阻碍第三方采用。

此发现后，RandomX团队移除了几个不必要参数，编写了关于哪些配置值可安全更改的额外指南，并添加了新检查集禁止一组不安全配置。

评估深度

区块链行业存在一种信念：多次小评审比一次大评审更好利用评审资本。此信念基于每个评审团队将以不同方式处理代码库并应用不同专业知识的概念。假定方法和专业知识的多样性将提供更好覆盖并摇出更多错误，而非让单一团队对给定项目进行深度挖掘。

我们相信，更大、单一的评估为客户提供更好整体价值。作为客户，您支付评估团队提供专家意见，但像任何新员工一样，他们需要时间熟悉您的代码库。一旦初始学习期完成，评估质量和深度迅速增加。许多大规模、长期代码评估直到 engagement 后期才揭示最关键或有意义的发现。

作为客户，您应雇佣单一公司进行更大 engagement 而非多家公司进行较小 engagement，原因与重视员工保留完全相同。替换拥有领域知识的公司将花费时间和金钱（如果您选择雇佣新公司）。

软件保证原则在Dave Aitel的旧演讲《黑客策略》中得到很好体现：即研究人员可发现漏洞的质量与花费时间强相关。一小时仅获极浅问题，一周显著更深，一月可发现无人可能发现的漏洞。

《零日，千夜》——基于与该领域数十位专家访谈的漏洞研究权威参考——进一步讨论此点：

发现漏洞的方法可影响实际找到的漏洞。例如，近期研究声称模糊测试器仅找到漏洞的冰山一角（Kirda等人，无日期）。可通过模糊测试在新产品或较不成熟产品，或代码库简单的产品中找到漏洞。对于生命周期较长、更复杂、市场份额大受欢迎或高收入生成的产品，更多人已评估代码库，发现漏洞通常需要更深入审计、逻辑评审和源代码分析，以深入多层。

例如，手动验证RandomX VM的正确性（这是我们发现的最严重问题）本身将花费数人周。很可能在所有四次审计结束时，无法保证VM实现无语义错误。

类似地，分析RandomX中每个函数的密码学强度在 engagement 内可实现，但探索是否存在方法在步骤间传播潜在偏差需要更深入查看。小 engagement 禁止此类工作，偏向较浅结果。

当前项目状态

我们的两人周审计是RandomX团队计划的多次评审中的第一次。接下来几周，项目将经历三次额外小审计，结果应于本月晚些时候发布。一旦这些审计发布且RandomX作者解决任何额外发现，Arweave和门罗币均计划在预定协议升级中在各自产品中采用此算法。

如果您喜欢本文，请分享：Twitter LinkedIn GitHub Mastodon Hacker News