Solidity RSA签名在空投和预售中的应用：在Gas效率上击败ECDSA和Merkle树

更新：2023年8月4日 由 Suthan Somadeva 和 Michael Burke

ECDSA 与 RSA 介绍

创建一个给予特定地址权限的合约有多种称呼：空投、预售、白名单、允许名单等。但这一思想的本质在于，有一组地址获得了以可取价格（有时甚至是免费的）购买高需求代币的特殊权限。有三种公认的解决方案：映射、Merkle 树和 ECDSA 签名。这些方法的相对优缺点已经在 其他地方讨论过，因此我们将总结结果：

• ECDSA 签名验证（Gas：29,293）
• 使用 Merkle 证明（Gas：30,517，128 个地址）

映射预售的工作原理是，卖方将客户的地址输入一个从地址到布尔值的映射，以标记该地址是否被授权。购买者完成交易后，映射会将该地址设置为 false。这确保了只有被标记为 true 的地址才能进行购买。这对买方非常节省 Gas，但卖方在允许千上万的地址时可能会 花费数百万 Gas（添加一个地址到允许名单至少会花费 22,100 Gas）。因此，Merkle 树和 ECDSA 签名（使用 以太坊预编译 的 ecRecover，或者更好地说，OpenZeppelin 出版的 更安全的封装）通常比映射更受青睐。执行 ECDSA 签名验证的 Gas 费用（针对买家）为 29,293 Gas。这包括启动交易的 21,000，因此 ECDSA 的费用为 8,293。值得注意的是，这包含从存储中读取签名地址的成本，但这个成本是必要的，否则我们将无法使签名失效。Merkle 树的成本取决于树的大小（更大的树需要更大的 Merkle 证明），但如果 Merkle 树中有超过 1,000 个地址，验证地址的费用将至少是 32,000 Gas（或更多）。这个成本显然低于 ECDSA。因此，目标是打败 ECDSA，费用为 8,293 Gas。为了保持解决方案的对比，我们的替代解决方案必须：

1. 能够使允许名单地址失效。Merkle 树可以更改其根，ECDSA 可以更改其签名地址，而映射可以将值设置为 false。
2. 不会像映射那样对卖方施加巨大的成本负担。
3. 买方的费用低于 8,200 Gas（包括存储加载）。
4. 在安全性上没有妥协。

先决条件

要理解提出的方法，读者应熟悉以下主题：

• 预编译智能合约（推荐阅读，stackexchange）
• 变形合约（介绍，推荐阅读）
• 访问列表（推荐阅读）
• 如何使用数字签名及其在区块链应用中的适用场景
• 如何计算 Gas 成本，特别是与 calldata、操作码、存储和内存使用相关的成本。

RSA 算法

如果我们想要大幅超过 ECDSA，我们需要找到一种不同的加密算法，允许集合成员资格的证明。ECDSA 实际上是原始数字签名算法 RSA 的更新且更酷的版本。ECDSA 依赖于在椭圆曲线上的离散对数是困难的（因此得名“椭圆曲线数字签名算法”）。RSA（以其作者 Rivest、Shamir 和 Adleman 命名）依赖于大整数难以因式分解。从年龄上讲，RSA 发布于1970年代，而 ECDSA 在 2000 年代初成为正式规范。 Admiral Piett 赞同 RSA 加密我们不会在这里详细解释 RSA，但一些先决条件还是必要的。签名者选择两个大的素数 p 和 q，并将它们相乘以产生 n。这个 n 是公钥的第一部分。其次，签名者选择一个小的素数 e（在我们的用例中可以设定为 3），并将对 (n、e) 对发布为公钥。在幕后，签名者计算：

t = (p - 1) * (q - 1)
d = t^(-1) % n

数字 d 就是私钥。如果对手能够将 n 分解为 p 和 q，那么计算 d 将是微不足道的。但众所周知 整数因式分解是困难的。要对消息进行签名，签名者将消息 m 哈希化以获得 h，然后将 h 乘以 d。即：

s = h(m) ^ d % n

签名者然后发布 (m、s) 作为消息和签名。验证者随后对 m 进行哈希处理，并将其提高到 e mod n 的幂。请记住，e 和 n 是公钥。仅当：

s == s ^ e % n

时，签名才对公钥 (n、e) 有效。请注意，如果 n 是极大的，那么 s == s ^ e % n 几率完全随机相等将微乎其微。如果等式成立，那么我们知道该签名对公钥有效。在以太坊中，我们可以简单地将一个地址签名为：

s = buyerAddress ^ d % n

而智能合约将验证：

msg.sender == s ^ e % n

使用仅 256 位是不安全的

我们说“因式分解整数是困难的”，但这显然意味着该数字必须足够大。例如，33 是由两个素数组成，分解它是微不足道的。幸好，我们有现实世界的基准，说明最新技术在 RSA 因式分解挑战 中所能取得的成就。为了解释，数字的“位数”是指公钥的大小。因此，当我们说“RSA 2048”时，这意味着数字 n，模数，有 2048 位。在比较密钥大小时，重要的是要记住每添加一位，数字的大小就会翻倍。因此，700 位比 350 位安全得多，而不是仅仅双倍安全。至今为止被破解（因式分解）的最大密钥有 829 位，且需要现代超级计算机来完成。这支团队利用了大约 2700 个 CPU 年，使用的是 2.1 GHz 的 Intel Xeon Gold 6130 CPU。AWS 上 最便宜的 16 核心 CPU 每小时费用为 $0.40 美元，因此破解这个密钥的费用在 940 万美元左右。即使假设云服务提供商的费用有很大折扣，成本也在数百万美元。

在 Solidity 中使用超过 256 位的模运算

以太坊仅支持 32 字节数据类型，因此默认情况下，我们不能计算

s ^ e % n

幸运的是，以太坊的 区块链 在 EIP 198 中增加了一个专门支持模运算的预编译合约。为了使用它，基数、指数和模数必须以 abi 编码 形式加载到内存中。然后调用位于地址 0x05 的合约。如果使用安全位数存储公钥会有点麻烦。如果密钥大小为 1024 位，则需要 4 个存储槽。从存储中读取公钥将有四次 SLOAD 操作，总计 8,400 Gas。这本身的效率已经低于上面经过基准测试的 ECDSA 解决方案。如果我们使用不可变变量，这个费用大部分被消除，但如果我们不能追溯性地将某人从预售中移除，这样就会产生一个弱点。在传统的 ECDSA 或 Merkle 树中，我们只需替换签名地址或 Merkle 根。如果使用不可变变量，这种方式无法实现。然而，将公钥存储在字节码中而不是存储中是关键理念。从外部合约的字节码读取（EXTCODECOPY）费用为 2,600 Gas，远低于以四部分读取公钥的 8,400 Gas。为了使公钥失效，我们可以简单地创建一个新合约，并更新一个存储变量以指向新地址。但这将增加额外的 2,100 Gas。结果发现，可以将外部合约的地址（存储公钥的字节码）存储在不可变变量中，但仍通过改变外部智能合约的字节码来使公钥失效。

使用变形合约模式使公钥失效

一个智能合约是通过将 部署字节码 加载到内存中然后返回包含运行时代码的字节码范围而创建的。当使用 create2 命令创建智能合约时，可以预先预测合约的地址。该地址是通过盐、部署者和初始化字节码的组合计算得出的。如果合约自毁，则可以在相同地址部署新合约。请注意，地址是初始化代码的函数，而不是部署代码。通过让初始化代码加载不同的运行时代码，可以部署不同的字节码。通过自毁并使用相同的初始化代码和不同的部署代码重新部署，可以变更合约的字节码。因此，我们可以有一个智能合约，其前 k 字节在满足特定条件时自毁，而其余字节则仅仅是 RSA 公钥。因为地址事先确定，我们可以将这个变形合约的地址存储在一个不可变变量中。当我们需要公钥时，我们可以从该地址进行 EXTCODECOPY。为了替换公钥，我们指示合约自毁，然后在该地址上部署一个新合约。

通过访问列表节省额外的 100 Gas

EIP 2930 增加了一种新类型的交易，允许用户提前指定将访问哪些地址和存储插槽。这使得节点可以提前从存储中获取那些值，从而加快执行时间。在调用外部合约时使用访问列表交易可以节省 100 Gas。请注意，当智能合约访问其自己的存储变量时，这种节省是不适用的。因为这个 RSA 预售空投设计依赖于外部合约来存储公钥，因此使用访问列表是合适的。

基准测试：Gas 成本与密钥大小

大多数 Gas 成本来自于由于签名的大型 calldata。如果密钥大小设置为 1024 位，则调用数据将为 128 字节。每个字节花费 16 Gas，因此仅仅拥有如此大的 calldata 的总 Gas 成本为 2,048 Gas。与大多数其他用例相比，我们的用例占用了相当多的内存，而以太坊对此收费。

为什么这相对于 ECDSA 节省了 Gas

基准测试明确表明，密钥（因此签名）越大，Gas 成本越高。我们的设计利用了预编译给上次 G 于低功率的事实。在这种条件下，执行 0x05 地址下的预编译合约仅需几百 Gas，而执行 ECDSA 预编译合约则需数千 Gas。

选择密钥大小

尽管 829 位的密钥已被因式分解，但需要现代超级计算机来做到这一点。对于某些应用，如空投低价值代币或将 NFT 放在预售中，攻击者并没有动力去花费六位数到一百万美元来因式分解公钥并在预售中获取 NFT。在撰写本文时，最昂贵的以太坊代币（Fidenza 和 Bored Ape Yacht Club）每个约需 100,000 美元，因此对于绝大多数应用，攻击者尝试因式分解公钥并不经济。请记住，每位都增加了一位因式分解整数的难度，因此截至 2022 年，绝大多数低价值代币的预售采用 896 位密钥 probably 是安全的。在这种情况下，节省用户 2,500 多 Gas 相较于 ECDSA 是相当有吸引力的。

密钥大小基准

• RSA-896（Gas：26,850）
• RSA-960（Gas：26,925）
• RSA-1024（Gas：27,033）
• RSA-2048（Gas：29,271）

结论

我们提出了一种为预售或空投地址分配权限的新方法，其效率高于当前已知解决方案。通过结合模幂预编译、变形合约模式和访问列表交易，我们可以以高效的 Gas 成本在链上验证安全的 RSA 签名。我们的工作在这个阶段仅是一个概念验证。建议开发者在生产中谨慎使用代码。该项目由 Suthan Somadeva 和 Michael Burke 创建，作为 RareSkills Solidity Bootcamp 的一部分。代码实现和单元测试在 github 上发布。最初发布于2022年12月7日

• 原文链接： rareskills.io/post/solid...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～