PoW的最前沿技术:Random X

本文是门罗Random X审计机构Trail of Bits发布的Random X详解,由Tracey_头等仓翻译,筋斗云校对,欢迎阅读。
头等仓APP下载

本文是门罗Random X审计机构Trail of Bits发布的Random X详解,由Tracey_头等仓翻译,筋斗云校对,欢迎阅读。

RandomX是一种新型的抗ASIC和GPU的工作量证明算法,最初由门罗开发,任何偏爱CPU挖矿的PoW都可用Randomx。Trail of Bits受Arweave之托,采用为期“两人一周”的方式审核这种新型算法,并在可选参数选择上进行了指导。但RandomX有什么神秘的地方值得大家关注呢?

标准的Proof-of-Work

在传统的PoW算法(如比特币中使用的hashcash)中,核心部分通常是一个哈希加密函数,唯一的变量是函数的数据输入。要达到目标“难度”,需要在哈希输出前面添加一些0作为前缀。每多加一个0,挖矿难度递增两倍。但ASIC和GPU在内存有限的情况下,能以固定操作序列来处理所有输入,因此可以获得显著的挖矿加速。这不是我们想要看到的。

为什么要抗ASIC?

理想上区块链挖矿是一种高度去中心化的模式,无单一实体掌控大额算力。但区块链易受51%攻击,占据多数算力的作恶者控制整条链,允许双重支付。如果ASIC的挖矿效率显著高于普通的CPU挖矿效率,那么CPU的矿工经济效率会降低。可以从比特币的网络中看出,ASIC制造商建立了大型的矿场,少数几个实体控制着高的惊人的算力。

过去几年,ASIC制造商已经展现了快速设计和生产ASIC芯片的能力。要想抵抗ASIC(不转换为PoS模式的情况下,这种模式有利有弊),必须利用CPU具有而ASIC没有的特定优势。

大量围绕抵抗ASIC研究展开,其中RandomX便是加密领域中抗ASIC的最前沿的代表作。

RandomX如何工作?

RandomX核心是一个随机执行的概念。简而言之,利用CPU的灵活性和动态代码执行能力,执行一系列随机的命令。RandomX开发人员大量地记录下设计原理,并给出了一个更严格的规范解释,简化后的算法实现如下:

第一步

使用argon2d和输入K,创建一个名为Cache的数据结构。最初argon2d被设计为内存密集型的哈希加密函数。通常计算机上有大量快速存储器,但ASIC上的内存相对昂贵。提高内存需求也是阻止专用挖矿硬件的一个方法。Argon2采用各种技术确保需要使用到大量内存,任意权衡时间或内存的攻击都不凑效。你可以具体阅读argon2规范

第二步

Dataset(一种只读内存结构)从Cache扩展而来。Dataset中的数据占用大量内存,虚拟机可以读取这些数据。有两个值影响Dataset大小(RANDOMX_DATASET_BASE_SIZE和RANDOMX_DATASET_EXTRA_SIZE)。这两个值可以设置算法所需的内存上限,RANDOMX_DATASET_EXTRA_SIZE使内存超出功率边界,使ASIC制造商难以施展身手。实际的Dataset由Cache加载数据而来,生成一组超标量哈希实例,然后调用这些实例获得最终输出。超标量哈希的作用是在等待DRAM生成数据的过程中,消耗算力,这点损害了根据Cache动态计算Dataset的ASIC。

第三步

用blake2哈希输入数据,初始化Scratchpad,将哈希后的输出设为AesGenerator种子,AesGenerator通过AES-NI指令填Scratchpad。由 AES转换生成初始Scratchpad,RandomX算法已针对CPU实现了硬件加速,因此ASIC硬件在算法上丧失所有优势。Scratchpad身就是一个大型的读/写数据架构,专门适用于CPU缓存数据。

第四步

现在说说算法的核心部分——虚拟机上运行的随机程序。虚拟机的运作是用另一生成器生成的随机字节构建一个随机程序。RandomX虚拟机架构适用于任何8字节的有效指令。这些指令用于:
· 双倍精度浮点运算
· 128位向量数学运算
· 四大IEEE 754浮点循环模式
· 读写Scratchpad,如上述提到Scratchpad的设计非常适用于CPU,因此缓存速度极快。
· 利用小概率分支指令预测分支
· 使用超标量和乱序执行的CPU执行命令

上述所有项都是针对CPU的独特优势,如果在ASIC硬件上执行则需要另外的模块区域,因此它的优势大打折扣。

程序之行后的虚拟机结果状态会被加密,生成一个新程序。可以设定这种循环执行模式,但默认循环数为8。循环是为了避免ASIC矿工实现有针对性的操作。只有完全结束当前的程序,才能确定下一个程序,矿工无法确定整条链是否“简单”,因此矿工无法有针对性地执行特定的命令。

第五步

最后,用AesHash加密Scratchpad和Register File(虚拟机的寄存器),第5步并没有什么可以抵抗ASIC的地方,它的租用是生成64位的哈希值。

发现的问题

在“两人一周”审核的过程中,找出了三个问题(两个轻微,一个值得注意)。

AesGenerator中使用一轮AES

RandomX规格中描述的AES加密是指进行一轮AES,一轮并不能完全混淆输入数据。但RandomX的安全性与AES加密无关,相反AES可以加快CPU交易速度,广播输出,但输出的位数广播速度取决于AES轮数。

这个问题被认定为“轻微”是因为缺乏足够的广播,导致算法的每一步都存在额外“偏差”,然后会创建一种可以在整条链中广播“偏差”的输入。

发现这一问题后,RandomX团队开发了一个新的执行4轮的AesGenerator4R函数。自提出更改请求#46后,便将AesGenerator4R函数合并到RandomX中了。4轮作为程序生成的一个环节,完美地解决了该问题。

虚拟机测试的正确性与验证不足

RandomX代码库的测试尚未覆盖虚拟机语义验证,Trail of Bits花费了一半的时间(一人一周)来评估RandomX 算法的安全性。虽然评估出了部分代码质量,但对虚拟机语义错误的验证不足。

此问题判定为“轻微”的原因是它并不影响RandomX的正确性,只要(1)RandomX的输出是确定性的;(2)输出是随机加密的;(3)它的参考实现仅用于某条链挖矿。但如果规范和参考实现间出现差异,则会导致共识问题和分叉。

鉴于此,具备RandomX规范的第三方净化室变得在使用RandomX的PoW链中受欢迎起来。过去如果矿工挖矿中出现细微语义差异,区块链就会分叉。

可配置参数非常脆弱

RandomX中有47个可配置参数,比如并行化标记、内存占用、初始KDF迭代、数据集的内存大小、虚拟CPU三层缓存空间的大小、虚拟机上执行程序大小和迭代计数、缓存访问和延迟。默认参数会最大化CPU优势,但51%攻击迫使替代链也使用RandomX,从而会更改默认参数,但更改必须是在具体哪个参数会损害算法优势不明朗的情况下做出的。脆弱性会阻碍第三方的采用。

发现此问题后,RandomX团队删除了一些不必要的参数,编写了关于更改哪些配置值是安全的指导,并添加了一组新的检查,禁止一些不安全的配置。

评估深度

在区块链行业中,深信小审核比大审核的资金利用率更高。它基于这样一种理念:每个评审团审核代码库的方式不同,审核专家也不同。相比通过一个单一团队,深入审核一个项目,小审核采用不同的方式和不同的专家可以覆盖不同的方面,能找出更多漏洞。

我们认为更大型、单一的评估团队可以为客户提供了一个更全面的审核。客户支付评估团队费用,获得专家意见,但就像新员工入职一样,他们需要时间了解你的代码库。一旦结束初始学习阶段,审核深度与质量的速度就会迅速加快。许多大规模、长期的代码审核直到审核后期才会得出重要和有价值的评估结果。

作为客户的你,应该雇佣一家大公司大范围参与,而不是多个小公司,一人审核一小块。与你重视留住员工的道理一样。换一家有专业知识的新公司很耗费时间和金钱。

“软件保障”这一原则在Dave Aitel很久前的一篇演讲中有所体现:《黑客思维》,即研究人员能发现的质量脆弱性与它花的时间成正比。一个小时你只能发现非常浅显的问题,一个星期则你可以更深一点挖掘,一个月你则能发现他人不易察觉的脆弱性。

这一原则在《零日,一千个夜晚》一书中得到进一步体现,这是一本基于对审核领域数十位专家的采访而撰写的关于脆弱性研究的权威参考文献:

“查找漏洞的方法对实际发现的漏洞有很大的影响。比方说,最近一个研究称模糊测试只是发现漏洞的冰山一角。但可以在不成熟或新产品中或单一代码库中进行模糊测试找到漏洞。对于那些使用时间长、更复杂和占据大量市场份额的产品或高回报生成器,很多人已经审核了它的代码库,要找出脆弱性则需要更深入的审计,逻辑检查和源代码分析,需要深入好几个层次。”

例如,手动验证RandomX虚拟机的正确性(这是我们发现的最严重的问题)将需要花费好几个人好几个星期的时间。很有可能,在4轮审计结束时,还无法确保虚拟机的实现是否有语义错误。

同样,以这样的时间消耗也可以分析RandomX中各个函数的加密强度,但是要探索广播是否存在偏差则需要进一步分析。小范围参与只能发现浅显的结论。

当前RandomX项目状态

“两人一周”审计是门罗设计的第一个多人审核计划。接下来几周,会对RandomX项目进行另外的3次小型审计,结果会在月末公布。一旦公布审计结果,并且RandomX作者解决了发现的问题后,Arweave和Monero都打算在计划的协议升级中各自采用这种算法。

本文由 区块链资讯平台头等仓 作者:筋斗云 发表,其版权均为 区块链资讯平台头等仓 所有,文章内容系作者个人观点,不代表 区块链资讯平台头等仓 对观点赞同或支持。如需转载,请注明文章来源。
头等仓APP下载

发表评论