前沿工作量证明算法：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的旧谈话《黑客策略》中得到了很好体现：即研究人员可发现漏洞的质量与花费时间强相关。一小时仅获极浅问题，一周显著更深，一月可发现可能无人 else 发现的漏洞。

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

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

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

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

当前项目状态

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

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