Starknet内置函数的好处及挑战

原文:Builtins and Dynamic Layouts

翻译及校对:「StarkNet 中文社区」

Starknet内置函数的好处及挑战

摘要

内置函数优化证明进程。然而,每条证明都是根据布局计算的。而对特定证明工作,如果布局效率低下,内置函数的优势就会大打折扣。目前,有个布局小型静态列表,每个证明都是根据该列表中最合适的布局计算的。这种布局静态列表的方式不足之处有二。首先,布局种类有限。这对于大多数证明工作来说效率低下,会造成复杂的收费机制,让用户承担不必要的成本。其次,手动维护列表困难。一旦内置函数数量过多,手动维护就会变得很困难,实际上会阻碍证明进程中支持大量细微之处高效的内置函数。为解决这些问题,StarkWare 团队正在开发一个动态布局系统,其中的布局都是为每个证明工作量身定制的。

Cairo 堆栈通过将 Cairo 代码编译成适用于 STARK 友好型 CPU 架构的指令来促进可证明的通用计算:Cairo VM(以下称为 CVM)。通用 CPU 的许多优势是以固有成本作为代价的,CVM 并未针对一些常用运算进行优化。Keccak、Pedersen、Poseidon 哈希函数是这类常见运算,还有椭圆曲线操作、范围检查(即检查特定数字是否位于特定值范围内)等其它运算。

为解决 CVM 相对低效的问题,Cairo 堆栈引入了关键运算的内置函数概念:即优化此类运算证明复杂性的插件。内置函数可以类比 ASIC:ASIC 是专用集成电路,而内置函数是应用程序专用代数约束(AIR)。如果不知道或者不记得什么是 AIR,文章稍后会简要介绍;更多详细信息请阅读这篇文章。

简而言之,证明复杂性与称为轨迹单元的资源相关(大致呈线性关系),内置函数通过使用比 Cairo VM 少得多的轨迹单元来简化特定运算的证明。

解释过内置函数的好处后,就知道为什么要为许多常用运算开发内置函数了。这说起来容易做起来难。目前把新内置函数引入 Starknet 的过程包含以下几个步骤:

1. 编写 AIR

2. 通过创建新布局(如下所述)与证明器集成

3. 集成到 Starknet,即修改其代码库和开发者工具以使用新的内置函数

除了编写 AIR 的挑战之外,在其余两个阶段还有很大的改进空间。这篇进阶级文章将更详细地介绍作为应用程序专用 AIR 的内置函数、上述问题以及未来计划。

内置函数:应用程序专用 AIR

AIR 是代数中间表达式(Algebraic Intermediate Representation)的缩写。在本文及 StarkWare 其它文章中,AIR 是表示虚拟机的多项式系统。例如,Cairo 的名称来源于 CPU AIR:表示特定 CPU 架构的多项式系统。此多项式系统的解代表有效的状态转移,称为有效代数执行轨迹(AET)。

STARK 通过证明给定的 AIR 对应的执行轨迹有效,来证明虚拟机的运算正确。大致上来说,执行轨迹是一组数字表,而 STARK 协议证明这些数字共同解决一个多项式系统。

同样的运算可以有多种计算方式,其中一些计算要更为高效。在本文中,证明复杂性基本上取决于轨迹大小,即表格中轨迹单元的数量。由于轨迹是针对 AIR 生成的,因此专为应用程序设计的 AIR 可以大幅减少特定计算的执行轨迹。内置函数是专为应用程序优化的专用 AIR。

下表展示了特定内置函数的效率改进(都已投入生产)。

Starknet内置函数的好处及挑战

轨迹布局:现在和未来

之前说到 AET 大致上是一个数字表,表示编码虚拟机的步骤排序(即程序的执行)。为计算证明,证明器在相关 AIR 的执行轨迹上运行 STARK 协议。

在上文中,我们介绍了内置函数作为应用程序专用的 AIR,旨在通过减少对计算进行编码所需的轨迹单元数量,来最大限度降低证明的复杂性。然而,如果在 Starknet 随意集成内置函数,可能会导致浪费许多轨迹单元,预期的好处也会减少。下面来详细说明。

简而言之,轨迹布局是将轨迹单元分配给不同的「组件」。在本文中,这些组件是 CVM 和内置函数。具体来说,布局指定每个组件获得的轨迹单元的相对数量。(布局构造始终是用来简化验证的。如需了解更多,请阅读这篇文章中的「简洁性」部分)。

关键点在于,证明复杂性取决于布局分配的轨迹单元总数,而轨迹单元分配有可能大于实际需要。例如,为证明 CVM 的步骤排序,仅将轨迹单元分配给 CVM 组件的布局,与把一半的轨迹单元分配给 Poseidon 内置函数的布局相比,效率大致翻倍。总之,合适的布局可以大大降低证明特定计算的复杂性。

目前有一份手动维护的布局列表,主要由于两个原因逐渐增长:

1. 内置函数只能用于为它们分配轨迹单元的布局。因此,添加内置函数至少需要一个新布局。

2. 为执行 Cairo 代码定制的布局可以优化单元分配。因此,单元里用例的优化通常需要新布局。

证明器和验证器(Solidity 和 Cairo 验证器)的代码是根据布局列表配置的。

随着添加 Keccak 和 Poseidon 内置函数,发现越来越难以保证布局列表小巧,同时容纳众多内置函数,保持大多数 Starknet 区块高效执行。此外,随着引入额外的内置函数,效率预计会大幅下降,因为布局必须考虑内置函数之间许多可能的组合与比例。

StarkWare 团队目前正在努力改进系统,放弃预先制定的布局列表,支持「动态布局」,即为每次执行 Cairo 代码即时定制。动态布局将始终针对手头的验证工作进行最佳比例的分配。从工程学的角度来看,支持动态输入需要对代码库进行相当大的更改。然而,StarkWare 团队希望利用动态布局,提高轨迹单元利用率,更好地利用证明器,来简化 Starknet 的证明层。

有了动态布局,手动维护许多内置函数的麻烦就不复存在,从而简化 Starknet 集成更多新内置函数的过程。

动态布局和费用

交易费用的一个目的是向用户收取交易产生的协议边际成本。由于交易费用的单位是货币,费用机制涉及从资源(例如虚拟机步骤、内置函数、calldata、以太坊 gas)到代币(例如 STRK、ETH)的转换。

目前,因为证明器根据总轨迹而非利用比率来收取费用,所以浪费的资源是由用户来承担的。动态布局将提高轨迹单元利用率,从而减少收取「不必要」的交易费用(包括并非由用户交易直接产生的资源消耗)。

Starknet 内置函数集成

至此,集成内置函数就差最后一步,即修改 Starknet 代码库来实现实际运用。代码修改幅度与布局应用相关,确保 Starknet 操作系统在可能的情况下调用内置函数就必须要修改代码。例如,Starknet 操作系统执行 Cairo 代码期间调用 Poseidon 哈希函数,同时要调用 Poseidon 内置函数。

与布局类似,现在可以手动支持 Starknet 内置函数。然而,与布局情况不同的是,这种手动支持即使有许多内置函数,也并不会对集成造成障碍。换句话说,Starknet 内置函数支持并不是集成的障碍,动态布局将真正为创建和集成额外内置函数铺平道路。

总结

在本文中解释了什么是内置函数、它们的好处、涉及的挑战以及 StarkWare 的计划。目前重点关注动态布局,它不仅会提高证明过程的效率,还会便于新内置函数集成。

本文由用户:麦妖榜 发布,不代表网站的立场,转转请注明出处:http://www.maiyaotop.com/hangye/125932.html

发表评论

登录后才能评论