更新时间：2023年8月4日
作者：Suthan Somadeva 和 Michael Burke
ECDSA 与 RSA 简介
创建一个赋予特定地址权限的合约有多种名称：airdrops（空投）、presale（预售）、whitelist（白名单）、allowlist（许可名单）等等。但其核心概念是，存在一组地址，它们拥有以理想价格（有时是免费）购买高需求代币的特殊权限。
目前有三种成熟的解决方案：mappings（映射）、Merkle trees（默克尔树）和 ECDSA 签名。
这些方法的相对优缺点已经在其他地方讨论过，因此我们将总结如下结果：
- ECDSA 签名验证（Gas：29,293）
- 使用 Merkle proofs（Gas：30,517，128 个地址）
基于 mapping 的 presale 机制是：卖家将客户地址输入到一个从 address 映射到 boolean 的 mapping 中，以标记该地址是否享有特权。买家完成交易后，该 mapping 的值会被设置为 false。这确保了只有被标记为 true 的地址才能进行购买。这使得买家的 gas 效率非常高，但是卖家可能会为了将数千个地址加入 allowlist 而花费数百万的 gas（将一个地址添加到 allowlist 至少需要消耗 22,100 gas）。
正因为如此，Merkle Trees 和 ECDSA 签名（使用 Ethereum 预编译 ecerecover，或者更好的选择是使用 OpenZeppelin 发布的更安全的包装器）通常比 mappings 更受青睐。执行 ECDSA 签名验证的 gas 成本（对买家而言）是 29,293 gas。这包含了发起交易的 21,000 gas，因此 ECDSA 本身的成本是 8,293 gas。请注意，这包含了从 storage 读取签名地址的成本，但这个成本是必须的，否则我们将无法使签名失效。
Merkle Trees 的成本因树的大小而异（更大的树需要更大的 Merkle proofs），但如果 Merkle tree 中包含超过 1,000 个地址，验证地址的成本至少需要 32,000 gas（或更多）。这个成本显然劣于 ECDSA。
因此，我们的目标是击败成本为 8,293 gas 的 ECDSA。为了保持解决方案的可比性（apples-to-apples），替代方案必须满足以下条件：
- 能够使 allowlisted 地址失效。Merkle trees 可以更改其 root，ECDSA 可以更改其签名地址，而 mappings 可以将值设置为 false。
- 不能像 mappings 那样给卖家带来巨大的成本负担。
- 买家成本低于 8,200 gas（包含 storage 负载成本）。
- 不在安全性上做出妥协。
先决条件
为了理解所提出的方法，读者应该熟悉以下主题：
- 预编译智能合约（推荐阅读，stackexchange）
- Metamorphic 合约（简介，推荐阅读）
- Access lists（推荐阅读）
- 如何使用数字签名及其在区块链应用中的适用场景
- gas 成本的计算方式，特别是与 calldata、opcodes、storage 和 memory 使用相关的部分。
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 成立的概率微乎其微。如果等式成立，那么我们就知道该签名对于该公钥是有效的。
要在 Ethereum 中实现这一点，我们只需将一个 address 签名为
s = buyerAddress ^ d % n
然后智能合约将验证
msg.sender == s ^ e % n
仅使用 256 位是不安全的
我们说“分解整数是困难的”，但这显然意味着该数字必须足够大。例如，33 由两个素数组成，分解它轻而易举。值得庆幸的是，在 RSA Factoring Challenge 中，我们有关于最先进技术能够达到何种程度的真实世界基准测试。
需要澄清的是，“bits（位）”的数量指的是公钥的长度。因此，当我们说“RSA 2048”时，这意味着数字 n（即模数）具有 2048 bits。在比较密钥长度时，必须记住，每增加一个 bit 都会使数字的大小翻倍。因此，700 bits 的安全性比 350 bits 呈指数级增长，而不是简单的两倍。
迄今为止被破解（分解）的最大密钥具有 829 bits，并且需要一台现代超级计算机来完成。该团队利用了约 2700 个 CPU 核心年，使用的是 2.1 GHz Intel Xeon Gold 6130 CPU。AWS 上最便宜的 16 核 CPU 成本为每小时 0.40 美元，因此破解此密钥的成本约为 940 万美元。即便考虑到云服务提供商慷慨的折扣，成本也在数百万美元的级别。
在 Solidity 中进行超过 256 位的模运算
Ethereum 仅支持 32 byte 的数据类型，因此默认情况下，我们无法执行
s ^ e % n
幸运的是，Ethereum blockchain 在 EIP 198 中专门增加了一个预编译合约来支持模运算。要使用它，必须将 base（底数）、exponent（指数）和 modulus（模数）以 abi encoded 格式加载到 memory 中。然后调用位于地址 0x05 的合约。
如果你使用安全的 bits 长度，存储公钥就会成为一个问题。如果密钥长度是 1024 bits，这需要 4 个 storage 插槽。从 storage 中读取公钥将需要执行四次 SLOAD 操作，总共消耗 8,400 gas。仅仅这一项操作就已经比上面基准测试的 ECDSA 解决方案效率低了。
如果我们使用 immutable 变量，这个成本在很大程度上被消除了，但如果我们无法追溯地将某人从 presale 中移除，这就会造成一个弱点。在传统的 ECDSA 或 Merkle Trees 中，我们只需替换签名地址或 Merkle Root。如果我们使用 immutable 变量，这是不可能的。
然而，将公钥存储在 bytecode 中而不是 storage 中是关键思路。读取外部合约的 bytecode（EXTCODECOPY）消耗 2,600 gas，这远低于分四次读取公钥各部分所需的 8,400 gas。
要使公钥失效，我们只需创建一个新合约，并更新一个 storage 变量以指向新地址。但这又增加额外的 2,100 gas。
事实证明，将外部合约的地址（其 bytecode 中存储着公钥）保存在 immutable 变量中是可行的，并且仍然可以通过改变外部智能合约的 bytecode 来使公钥失效。
使用 metamorphic 合约模式使公钥失效
创建智能合约的过程是将部署 bytecode 加载到 memory 中，然后返回包含 runtime code 的 bytecode 范围。
当使用 create2 命令创建智能合约时，合约的地址可以提前预测。该地址是结合 salt、部署者和 initialization bytecode 计算得出的。如果合约发生 selfdestruct，那么可以在同一地址部署一个新合约。
请注意，地址取决于 initialization code，而不是部署的代码。通过让 initialization code 加载不同的 runtime code，可以部署不同的 bytecode。通过 selfdestruct 并在相同的 initialization code 下使用不同的部署代码进行重新部署，合约的 bytecode 就可以发生改变。
因此，我们可以创建一个智能合约，其前 k 个 bytes 用于在特定条件下执行 selfdestruct，而剩余的 bytes 仅为 RSA 公钥。
因为地址是预先确定的，我们可以将这个 metamorphic 合约的地址存储在 immutable 变量中。当我们需要公钥时，我们可以从该地址执行 EXTCODECOPY。要替换公钥，我们只需指示该合约执行 selfdestruct，然后向该地址部署一个新合约。
使用 access lists 额外节省 100 gas
EIP 2930 增加了一种新的交易类型，允许用户提前指定将要访问哪些地址和 storage 插槽。这使得节点可以从 storage 中预取这些值，从而加快执行时间。在调用外部合约时使用 access list 交易可以节省 100 gas。请注意，当智能合约访问自身的 storage 变量时，这种节省并不适用。因为这个 RSA presale airdrop 设计依赖于外部合约来存储公钥，所以使用 access list 是非常合适的。
基准测试：Gas 成本与密钥长度
由于大型签名会导致非常大的 calldata，因此大部分 gas 成本来源于此。如果密钥长度设置为 1024 bits，那么 calldata 将达到 128 bytes。每个 byte 消耗 16 gas，因此仅拥有如此大的 calldata 总共就需要 2,048 gas。
与大多数其他用例相比，我们的方法使用了相当大量的 memory，而 Ethereum 会对此收费。
为什么这比 ECDSA 更节省 Gas
基准测试清楚地表明，密钥（及相应的签名）越大，gas 成本就越高。我们的设计利用了这样一个事实：预编译对于低次幂运算的定价很低。在这些条件下，执行 0x05 处的预编译合约的成本仅为几百 gas，而执行 ECDSA 的预编译则需要数千 gas。
选择密钥长度
虽然 829 bits 的密钥已被成功分解，但完成这项工作需要现代超级计算机。对于空投低价值代币或进行 NFT presale 等应用，攻击者没有动机花费六位数乃至百万美元去分解公钥，仅仅为了在 presale 中获取一个 NFT。在撰写本文时，最昂贵的 Ethereum 代币（Fidenza 和 Bored Ape Yacht Club）单价约为 100,000 美元，因此对于绝大多数应用而言，攻击者尝试分解公钥在经济上是不划算的。
请记住，每增加一个 bit，分解整数的难度就会翻倍，因此截至 2022 年，绝大多数低价值代币 presale 使用 896 bits 可能是安全的。在这种情况下，与 ECDSA 相比，为用户节省超过 2,500 gas 极具吸引力。
密钥长度基准测试
- RSA-896（Gas：26,850）
- RSA-960（Gas：26,925）
- RSA-1024（Gas：27,033）
- RSA-2048（Gas：29,271）
结论
我们提出了一种为 presale 或 airdrop 分配地址的新方法，该方法比当今已知解决方案更加高效。通过将模幂预编译与 metamorphic 合约模式和 access list 交易相结合，我们可以在链上以一种 gas 高效的方式验证安全的 RSA 签名。
目前，我们的工作仅仅是一个概念验证。建议开发者在生产环境中使用该代码时保持谨慎。
该项目由 Suthan Somadeva 和 Michael Burke 创建，作为 RareSkills Solidity Bootcamp 的一部分。代码实现和单元测试已发布在 github 上。
最初发表于 2022年12月7日