# Solidity mapping 变量的生日碰撞风险

**Published by:** [Shurong Shen](https://paragraph.com/@shurong-shen/)
**Published on:** 2022-09-21
**URL:** https://paragraph.com/@shurong-shen/solidity-mapping

## Content

生日碰撞生日攻击是一种密码攻击，它利用概率论中生日问题背后的数学原理，极大地降低发生碰撞的计算复杂度。利用生日攻击进行 hash 碰撞便称为生日碰撞。 一个好的设计应该尽量避免生日碰撞的风险，不幸的是 Solidity 的 mapping 变量便存在该风险，截至到本文发表时，所有 Solidity 版本（最新版本为 0.8.17）都存在该问题。这将给数以万亿美元计的链上资产带来潜在的安全隐患。Solidity 的 mapping 实现在 Solidity 中，mapping 变量会根据变量的索引位置（该变量在源文件中定义的顺序位置）和 key 值计算出存储 slot 位置，然后将 value 存储在该位置（注：当 value 类型是 string 等变长数组时，该位置是起始位置）。 设变量索引位置为 i，则一级 mapping(k) 的 slot 位置算法（伪代码，下同）如下：storage_slot = keccak(memory_concat(k,i)); 二级 mapping(k1, k2) 的 slot 位置算法如下：ii = keccak(memory_concat(k1,i)); storage_slot = keccak(memory_concat(k2, ii)); 多级 mapping 可以以此类推。 显而易见，如果有两个变量，其存储 slot 位置相同，则会发生存储位置碰撞。一旦发生存储位置碰撞，便可以通过修改一个变量的值来改变另一个变量的值。ERC20 中的生日碰撞风险在 ERC20 中通常有如下两个变量，前者表示一个地址的余额，后者表示地址A授予地址B操作其账户的额度。mapping(address => uint) public balanceOf; mapping(address => mapping(address => uint)) public allowance; 特别注意，allowance 变量具有如下两个特性：授予的地址可以任意授予的额度可以任意我们只需找到一组地址 a1、a2、a3，使得 balanceOf(a1) 的存储 slot 地址等于 allowance(a2, a3)，便可以随意改写 a1 的账户余额！！！ 具体细节，这里不进一步展开，稍作思考便可领会。 这明显是一个生日碰撞问题，以 Ethereum 256 位强度为例，碰撞的复杂度为 O(2**128)。 此外，这里虽然只分析了 ERC20，但其他合约显然也很容易存在类似问题。改进建议通过前面的分析，我们可以看出，该问题的根源在于 Solidity mapping 变量的底层实现没有从技术上规避生日碰撞风险。 这里提一个简单的改进思路：从 slot 位置划出若干位来存放变量索引值，具体划多少位可以固定一个数，也可以根据合约的 storage 变量总数动态决定。改进后的 slot 位置算法如下：p = keccak(memory_concat(k,i); m1 = bits(i)[x:256-x]; m2 = bits(p)[0:x]; storage_slot = bits_concat(m1, m2));

## Publication Information

- [Shurong Shen](https://paragraph.com/@shurong-shen/): Publication homepage
- [All Posts](https://paragraph.com/@shurong-shen/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@shurong-shen): Subscribe to updates