最先进的抗ASIC工作量证明算法：RandomX

标准工作量证明

在经典的工作量证明算法（如比特币使用的hashcash）中，核心通常是一个密码学哈希函数，其中唯一的变量是函数的输入数据。为了实现目标"难度"，需要在哈希输出前缀中包含一定数量的零位。每增加一个零位，挖矿难度就会翻倍。然而，这类算法非常适合通过ASIC和GPU进行加速，因为所有输入都执行固定的操作集，且内存需求有限。这是不可取的。

为什么我们要关注抗ASIC性？

理想情况下，区块链挖矿应该是一个高度去中心化的任务，没有单一实体控制大量的哈希算力。区块链容易受到51%攻击，恶意多数可以覆盖全局状态，例如允许双花。如果能够构建比通用CPU显著提高挖矿效率的ASIC，那么经济因素将不利于基于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的旧演讲《黑客策略》中得到了很好的体现：即研究人员可以找到的漏洞质量与花费的时间密切相关。一小时让您发现极其肤浅的问题，一周显著增加深度，一个月您可以找到其他人不太可能发现的漏洞。

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

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

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

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

当前项目状态

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

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