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

By [Shurong Shen](https://paragraph.com/@shurong-shen) · 2022-09-21

---

生日碰撞
----

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

---

*Originally published on [Shurong Shen](https://paragraph.com/@shurong-shen/solidity-mapping)*