前沿工作量证明算法：RandomX的技术解析与安全审计

标准工作量证明

在经典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创建称为缓存的数据结构。Argon2d最初设计为内存硬密码哈希函数。计算机通常有大量快速内存可用，但内存对ASIC来说很昂贵。需要大量内存是对抗专用硬件的最常见防御之一。Argon2使用各种技术确保使用大量（可配置）内存，并且任何时间/内存权衡攻击都无效。您可以在argon2规范中阅读更多相关内容。

步骤2

数据集（只读内存结构）从缓存扩展。数据集设计为包含虚拟机将读取数据的大内存段。有两个值控制数据集的大小（RANDOMX_DATASET_BASE_SIZE和RANDOMX_DATASET_EXTRA_SIZE）。它们共同设定了算法所需总内存的上限。额外大小用于将内存略微推过2的幂边界，这使ASIC制造商的生活更加艰难。实际数据集生成通过从缓存加载数据、生成一组SuperscalarHash实例，然后调用这些实例以获得最终输出来执行。SuperscalarHash设计为在等待DRAM数据时消耗功率。这损害了试图从缓存动态计算数据集的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将本次参与的一半时间（一人周）用于评估算法实现的通用安全属性。虽然这项工作揭示了几项代码质量发现，但不足以验证VM实现中不存在语义错误。

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

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

可配置参数脆弱

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

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

评估深度

区块链行业有一种信念，即许多小审查比一次大审查更好地利用审查资本。这一信念基于每个审查团队将以不同方式处理代码库并应用不同专业知识的概念。假设的方法和专业知识多样性将提供更好的覆盖范围并发现更多错误，而不是让单个团队对给定项目进行深入挖掘。

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

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

软件保证的这一原则在Dave Aitel的旧演讲《黑客策略》中得到了很好的体现：即研究人员可以找到的漏洞质量与花费的时间密切相关。一小时让您获得极其肤浅的问题，一周显著更深入，一个月您可以找到可能没有人 else 发现的漏洞。

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

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

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

类似地，分析RandomX中每个函数的密码强度在参与范围内是可实现的，但探索是否存在方法在步骤之间传播潜在偏差需要更深入的审视。小参与禁止此类工作，倾向于更浅的结果。

当前项目状态

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

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