生日攻击是一种密码攻击，它利用概率论中生日问题背后的数学原理，极大地降低发生碰撞的计算复杂度。利用生日攻击进行 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));