從一起“盜幣”事件看以太坊存儲 hash 碰撞問題

Author : Kai Song(exp-sky)、hearmen、salt、sekaiwu of Tencent Security Xuanwu Lab
來源：騰訊安全玄武實驗室

“盜幣”

十一月六日，我們觀察到以太坊上出現了這樣一份合約，經調查發現是某區塊鏈安全廠商發布的一份讓大家來“盜幣”的合約。

pragma solidity ^0.4.21;
contract DVPgame {
    ERC20 public token;
    uint256[] map;
    using SafeERC20 for ERC20;
    using SafeMath for uint256;
    constructor(address addr) payable{
        token = ERC20(addr);
    }
    function (){
        if(map.length>=uint256(msg.sender)){
            require(map[uint256(msg.sender)]!=1);
        }
        if(token.balanceOf(this)==0){
            //airdrop is over
            selfdestruct(msg.sender);
        }else{
            token.safeTransfer(msg.sender,100);

            if (map.length <= uint256(msg.sender)) {
                map.length = uint256(msg.sender) + 1;
            }
            map[uint256(msg.sender)] = 1;  

        }
    }
    //Guess the value(param:x) of the keccak256 value modulo 10000 of the future block (param:blockNum)
    function guess(uint256 x,uint256 blockNum) public payable {
        require(msg.value == 0.001 ether || token.allowance(msg.sender,address(this))>=1*(10**18));
        require(blockNum>block.number);
        if(token.allowance(msg.sender,address(this))>0){
            token.safeTransferFrom(msg.sender,address(this),1*(10**18));
        }
        if (map.length <= uint256(msg.sender)+x) {
            map.length = uint256(msg.sender)+x + 1;
        }

        map[uint256(msg.sender)+x] = blockNum;
    }
    //Run a lottery
    function lottery(uint256 x) public {
        require(map[uint256(msg.sender)+x]!=0);
        require(block.number > map[uint256(msg.sender)+x]);
        require(block.blockhash(map[uint256(msg.sender)+x])!=0);
        uint256 answer = uint256(keccak256(block.blockhash(map[uint256(msg.sender)+x])))%10000;
        if (x == answer) {
            token.safeTransfer(msg.sender,token.balanceOf(address(this)));
            selfdestruct(msg.sender);
        }
    }
}

經過觀察之后，我們在這個合約中，發現了我們之前研究的一個 EVM 存儲的安全問題，即 EVM 存儲中的 hash 碰撞問題。

首先，針對上面的合約，如果構造出 x == uint256(keccak256(block.blockhash(map[uint256(msg.sender)+x])))%10000 即可在 lottery 方法中獲取到該合約中的以太幣，但是這個 x 的值，只能通過不斷的猜測去得到，并且概率微乎其微。

然后，我們發現在合約的 fallback 函數中，也存在一個 selfdestruct 函數可以幫助我們完成“盜幣”任務，但是要求本合約地址在 token 合約中的余額為 0。

根據我們之前對于 EVM 存儲的分析，我們發現在 guess 函數中存在對 map 類型數據任意偏移進行賦值 map[uint256(msg.sender)+x] = blockNum;，由于在 EVM 中，map 類型中數據存儲的地址計算方式為 address(map_data) = sha(key,slot)+offset，這就造成了一個任意地址寫的問題，如果我們能夠覆蓋到token 變量，就能向 token 寫入我們構造的合約，保證 DVPgame 合約在我們構造合約中的余額為 0，這樣就能執行 DVPgame 合約的 selfdestruct 函數完成“盜幣”。

token 變量的地址為0，溢出之后可以達到這個值，即我們需要構造 sha(msg.sender,slot)+x==2**256(溢出為0)即可。

深入分析

其實早在六月底的時候，經過對 ETH 以及其運行時環境 EVM 的初步研究，我們已經在合約層面和虛擬機層面分別發現了一些問題，其中變量覆蓋以及Hash 碰撞問題是非常典型的兩個例子。

變量覆蓋

在某些合約中，我們發現在函數內部對 struct 類型的臨時變量進行修改，會在某些情況下覆蓋已有的全局變量。

pragma solidity ^0.4.23; 
contract Locked {
    bool public unlocked = false;    
    struct NameRecord { 
        bytes32 name;
        address mappedAddress;
    }
    mapping(address => NameRecord) public registeredNameRecord; 
    mapping(bytes32 => address) public resolve;
    function register(bytes32 _name, address _mappedAddress) public {
        NameRecord newRecord;
        newRecord.name = _name;
        newRecord.mappedAddress = _mappedAddress; 
        resolve[_name] = _mappedAddress;
        registeredNameRecord[msg.sender] = newRecord; 
        require(unlocked); 
    }
}

合約的源碼如上面所示，在正常情況下，由于合約并沒有提供修改 unlocked 的接口，因此不太可能達到修改它的目的。但是實際上我們在測試中發現，只要調用合約的 register 方法就可以修改 unlocked。

Hash 碰撞

經過對 EVM 的存儲結構分析，我們發現 EVM 的設計思路中，在其存儲某些復雜變量時可能發生潛在的 hash 碰撞，覆蓋已有變量，產生不可預知的問題。

pragma solidity ^0.4.23; 

contract Project
{
    mapping(address => uint) public balances; // records who registered names 
    mapping(bytes32 => address) public resolve; // resolves hashes to addresses

    uint[] stateVar;

    function Resolve() returns (bytes32){
        balances[msg.sender] = 10000000;   
        return sha3(bytes32(msg.sender),bytes32(0));
    }

    function Resize(uint i){
        stateVar.length = i;
    }

    function Rewrite(uint i){
        stateVar[i] = 0x10adbeef; 
    }

}

上面的代碼就存在類似的 hash 碰撞問題。查看合約源代碼可以看到 balances 字段只能通過 Reslove 接口進行訪問，正常情況下 balance 中存放的值是無法被修改的。但是在這個合約中，調用函數 Rewrite 對 stateVar 進行操作時有可能覆蓋掉 balances 中的數據

背景分析

在 EVM 中存儲有三種方式，分別是 memory、storage 以及 stack。

memory : 內存，生命周期僅為整個方法執行期間，函數調用后回收，因為僅保存臨時變量，故GAS開銷很小
storage : 永久儲存在區塊鏈中，由于會永久保存合約狀態變量，故GAS開銷也最大
stack : 存放部分局部值類型變量，幾乎免費使用的內存，但有數量限制

首先我們分析一下各種對象結構在 EVM 中的存儲和訪問情況

MAP

首先分析 map 的存儲，

    struct NameRecord { 
        bytes32 name; 
        address mappedAddress;
    }
    mapping(bytes32 => address) public resolve; 
    function register(bytes32 _name, address _mappedAddress) public {
        NameRecord newRecord;
        newRecord.name = _name;
        newRecord.mappedAddress = _mappedAddress; 
        resolve[_name] = _mappedAddress;
    }
}

我們在調試 storage 中 map 結構時發現，map 中數據的存儲地址其實是 map.key 以及 map 所在位置 map_slot 二者共同的 hash 值，這個值是一個 uint256。即

address(map_data) = sha(key,slot)

并且我們同時發現，如果 map 中存儲的數據是一個結構體，則會將結構體中的成員分別依次順序存入 storage 中，存儲的位置為 sha(key,slot) + offset，即是直接將成員在結構體中的偏移與之前計算的 hash 值相加作為存儲位置。

這種 hash + offset 的 struct 存儲方式會直接導致 sha3 算法的 hash 失去意義，在某些情況下產生 sha(key1,slot) + offset == sha(key2,slot) ，即 hash 碰撞。

ARRAY

接下來我們看一下 Array 的情況

調試中發現全局變量的一個定長 Array 是按照 index 順序排列在 storage 中的。

如果我們使用 new 關鍵字申請一個變長數組，查看其運行時存儲情況

    function GetSome() returns(uint){
        stateVar = new uint[](2);
        stateVar[1] = 0x10adbeef;
        //stateVar = [1,2,4,5,6]; // 這種方式和 new 是一樣的
        return stateVar[1];
    }

調試中發現如果是一個變長數組，數組成員的存儲位置就是根據 hash 值來選定的了, 數組的存儲位置為 sha3(address(array_object))+index。數組本身的 slot 中所存放的只是數組的長度而已，這樣也就很好理解為什么存放在 storage 中的變長數組可以通過調整 length 屬性來自增。

變長數組仍依照 hash + offset 的方式存儲。也有可能出現 hash 碰撞的問題。

ARRAY + STRUCT

如果數組和結構體組合起來，那么數據在 storage 中的索引將如何確定呢

    struct Person {
        address[] addr;
        uint funds;
    }    
    mapping(address => Person) public people;   
    function f() {
        Person p;
        p.addr = [0xca35b7d915458ef540ade6068dfe2f44e8fa733c,0x14723a09acff6d2a60dcdf7aa4aff308fddc160c];
        p.funds = 0x10af;

        people[msg.sender] = p;
    }

Person 類型的對象 p 第一個成員是一個動態數組 addr，存儲 p 對象時，首先在 map 中存儲動態數組：

storage[hash(msg_sender,people_slot)] = storage[p+slot]

接著依次存儲動態數組內容:

storage[hash(hash(msg_sender,people_slot))] = storage[hash(p_slot)]; storage[hash(hash(msg_sender,people_slot))+1] = storage[hash(p_slot)+1];

最后存儲 funds：

storage[hash(msg_sender,people_slot)+1]

同理，數組中的結構體存儲也是類似。

問題分析

變量覆蓋

pragma solidity ^0.4.23; 
contract Locked {
    bool public unlocked = false;    
    struct NameRecord { 
        bytes32 name;
        address mappedAddress;
    }
    mapping(address => NameRecord) public registeredNameRecord; 
    mapping(bytes32 => address) public resolve;
    function register(bytes32 _name, address _mappedAddress) public {
        NameRecord newRecord;
        newRecord.name = _name;
        newRecord.mappedAddress = _mappedAddress; 
        resolve[_name] = _mappedAddress;
        registeredNameRecord[msg.sender] = newRecord; 
        require(unlocked); 
    }
}

本合約中 unlocked 變量存儲在 storage 中偏移為1 的位置。而在調試中發現 newRecord 對象在 storage 部分的索引位置也是 0 ，和全局 unlocked 相重疊，因此訪問 newRecord 的時候也會順便修改到 unlocked。

調試中我們發現所有的臨時變量都是從 storage 的 0 位置開始存儲的，如果我們多設置幾個臨時變量，會發現在函數開始選定 slot 時，所有的臨時變量對應的 slot 值都是 0。

成因分析

我們下載 solidity 編譯器的源碼進行查看，分析這里出現問題的原因。源碼可在這里找到，直接使用 cmake 編譯源碼即可，編譯教程。 solidity 的源碼需要引用 boost 庫，如果之前沒有安裝的話需要先安裝 boost。編譯的過程不再贅述，最終會生成三個可執行文件（在 Windows 上的編譯會有點問題，依賴的頭文件沒辦法自動加入工程，需要手動添加，并且會還有一些字符表示的問題）

solc\solc
lllc\lllc
test\soltest

solc 可以將 sol 源碼編譯成 EVM 可以運行的 bytecode

調試 Solc ，查看其中對于 struct 作為臨時變量時的編譯情況

contract Project
{
    uint a= 12345678;
    struct Leak{
        uint s1;
    }
    function f(uint i) returns(uint) {
        Leak l;
        return l.s1;
    }

}

關鍵代碼調用棧如下

>   solc.exe!dev::solidity::ContractCompiler::appendStackVariableInitialisation(const dev::solidity::VariableDeclaration & _variable) Line 951  C++
    solc.exe!dev::solidity::ContractCompiler::visit(const dev::solidity::FunctionDefinition & _function) Line 445   C++
    solc.exe!dev::solidity::FunctionDefinition::accept(dev::solidity::ASTConstVisitor & _visitor) Line 206  C++
    solc.exe!dev::solidity::ContractCompiler::appendMissingFunctions() Line 870 C++
    solc.exe!dev::solidity::ContractCompiler::compileContract(const dev::solidity::ContractDefinition & _contract, const std::map<dev::solidity::ContractDefinition const *,dev::eth::Assembly const *,std::less<dev::solidity::ContractDefinition const *>,std::allocator<std::pair<dev::solidity::ContractDefinition const * const,dev::eth::Assembly const *> > > & _contracts) Line 75  C++
    solc.exe!dev::solidity::Compiler::compileContract(const dev::solidity::ContractDefinition & _contract, const std::map<dev::solidity::ContractDefinition const *,dev::eth::Assembly const *,std::less<dev::solidity::ContractDefinition const *>,std::allocator<std::pair<dev::solidity::ContractDefinition const * const,dev::eth::Assembly const *> > > & _contracts, const std::vector<unsigned char,std::allocator<unsigned char> > & _metadata) Line 39 C++
    solc.exe!dev::solidity::CompilerStack::compileContract(const dev::solidity::ContractDefinition & _contract, std::map<dev::solidity::ContractDefinition const *,dev::eth::Assembly const *,std::less<dev::solidity::ContractDefinition const *>,std::allocator<std::pair<dev::solidity::ContractDefinition const * const,dev::eth::Assembly const *> > > & _compiledContracts) Line 730  C++
    solc.exe!dev::solidity::CompilerStack::compile() Line 309   C++
    solc.exe!dev::solidity::CommandLineInterface::processInput() Line 837   C++
    solc.exe!main(int argc, char * * argv) Line 59  C++

關鍵函數為 appendStackVariableInitialisation，可以看到這里調用 pushZeroValue 記錄臨時變量信息，如果函數發現 value 存在于 Storage 中，那么就直接 PUSH 0，直接壓入 0！！！所有的臨時變量都通過這條路徑，換而言之，所有的臨時變量 slot 都是 0 。

void ContractCompiler::appendStackVariableInitialisation(VariableDeclaration const& _variable)
{
    CompilerContext::LocationSetter location(m_context, _variable);
    m_context.addVariable(_variable);
    CompilerUtils(m_context).pushZeroValue(*_variable.annotation().type);
}

筆者目前還不能理解這樣設計的原因，猜測可能是因為 storage 本身稀疏數組的關系，不便于通過其他額外變量來控制 slot 位置，但是以目前這樣的實現，其問題應該更多。

與之相對的全局變量的編譯，函數調用棧如下

>   solc.exe!dev::solidity::ContractCompiler::initializeStateVariables(const dev::solidity::ContractDefinition & _contract) Line 403    C++
    solc.exe!dev::solidity::ContractCompiler::appendInitAndConstructorCode(const dev::solidity::ContractDefinition & _contract) Line 146    C++
    solc.exe!dev::solidity::ContractCompiler::packIntoContractCreator(const dev::solidity::ContractDefinition & _contract) Line 165 C++
    solc.exe!dev::solidity::ContractCompiler::compileConstructor(const dev::solidity::ContractDefinition & _contract, const std::map<dev::solidity::ContractDefinition const *,dev::eth::Assembly const *,std::less<dev::solidity::ContractDefinition const *>,std::allocator<std::pair<dev::solidity::ContractDefinition const * const,dev::eth::Assembly const *> > > & _contracts) Line 89   C++
    solc.exe!dev::solidity::Compiler::compileContract(const dev::solidity::ContractDefinition & _contract, const std::map<dev::solidity::ContractDefinition const *,dev::eth::Assembly const *,std::less<dev::solidity::ContractDefinition const *>,std::allocator<std::pair<dev::solidity::ContractDefinition const * const,dev::eth::Assembly const *> > > & _contracts, const std::vector<unsigned char,std::allocator<unsigned char> > & _metadata) Line 44 C++
    solc.exe!dev::solidity::CompilerStack::compileContract(const dev::solidity::ContractDefinition & _contract, std::map<dev::solidity::ContractDefinition const *,dev::eth::Assembly const *,std::less<dev::solidity::ContractDefinition const *>,std::allocator<std::pair<dev::solidity::ContractDefinition const * const,dev::eth::Assembly const *> > > & _compiledContracts) Line 730  C++
    solc.exe!dev::solidity::CompilerStack::compile() Line 309   C++
    solc.exe!dev::solidity::CommandLineInterface::processInput() Line 837   C++
    solc.exe!main(int argc, char * * argv) Line 59  C++

關鍵函數為 StorageItem::StorageItem ，函數從 storageLocationOfVariable 中獲取全局變量在 storage 中的 slot

StorageItem::StorageItem(CompilerContext& _compilerContext, VariableDeclaration const& _declaration):
    StorageItem(_compilerContext, *_declaration.annotation().type)
{
    auto const& location = m_context.storageLocationOfVariable(_declaration);
    m_context << location.first << u256(location.second);
}

HASH 碰撞

如前文中提到的，使用 struct 和 array 的智能合約存在出現 hash 碰撞的可能。

一般來說 sha3 方法返回的 hash 是不會產生碰撞的，但是無法保證 hash(mem1)+n 不與其他 hash(mem2) 產生沖突。舉個例子來說有兩個 map

struct Account{
    string name；
    uint ID;
    uint amount;
    uint priceLimit;
    uint total;
}

map<address, uint> balances;     // slot 0  
map<string, Account> userTable;    // slot 1

在存儲 balances[key1] = value1 時計算 sha3(key1,0) = hash1; Storage[hash1] = value1 。

存儲 userTable[key2] = account 時計算 sha3(key2,1) = hash2; 。

hash1 和 hash2 是不相同的，但是 hash1 和 hash2 很有可能是臨近的，相差很小，我們假設其相差 4 。

此時實際存儲 account 時，會依次將 Account.name、Account.ID、Account.amount、Account.priceLimit、Account.total存放在 storage 中 hash2、hash2+1、hash2+2、hash2+3、hash2+4 的位置。而 hash2+4 恰恰等于 hash1 ，那么 Account.total 的值就會覆蓋之前存儲在 balances 中的內容 value1。

不過通過 struct 攻擊只是存在理論上可能，在實際中找到相差很小的 sha3 是很難的。但是如果將問題轉化到 array 中，就有可能實現真實的攻擊。

因為在 array 中，數組的長度由數組對象第一個字節中存儲的數據控制，只要這個值足夠大，攻擊者就可以覆蓋到任意差距的 hash 數據。

pragma solidity ^0.4.23; 
contract Project
{
    mapping(address => uint) public balances; // records who registered names 
    mapping(bytes32 => address) public resolve; // resolves hashes to addresses

    uint[] stateVar;

    function Resolve() returns (bytes32){
        balances[msg.sender] = 10000000;   // 0x14723a09acff6d2a60dcdf7aa4aff308fddc160c ->  0x51fb309f06bafadda6dd60adbce5b127369a3463545911e6444ab4017280494d 

        return sha3(bytes32(msg.sender),bytes32(0));
    }

    function Resize(uint i){
        stateVar.length = 0x92b6e4f83ec43f4bc9069880e92f6ea53e45d964038b04cc518a923857c1b79c; // 0x405787fa12a823e0f2b7631cc41b3ba8828b3321ca811111fa75cd3aa3bb5ace
    }

    function Rewrite(uint i){
        stateVar[i] = 0x10adbeef; // 0x11a3a8a4f412d6fcb425fd90f8ca757eb40f014189d800d449d4e6c6cec4ee7f = 0x51fb309f06bafadda6dd60adbce5b127369a3463545911e6444ab4017280494d - 0x405787fa12a823e0f2b7631cc41b3ba8828b3321ca811111fa75cd3aa3bb5ace
    }

}

當前的 sender 地址為 0x14723a09acff6d2a60dcdf7aa4aff308fddc160c , balance[msg.sender] 存儲的位置為 0x51fb309f06bafadda6dd60adbce5b127369a3463545911e6444ab4017280494d。調用 Resize 方法將數組 stateVar 的長度修改，數組的存儲位置在 0x405787fa12a823e0f2b7631cc41b3ba8828b3321ca811111fa75cd3aa3bb5ace。

最后調用合約方法 Rewrite 向數組賦值，該操作會覆蓋 balance 中的內容，將地址為 sender 的值覆蓋。

實際內存

最后我們來看一下實際內存的管理情況。無論以太坊區塊鏈的上層技術如何高深，內存終歸是需要落地的，最終這些數據還是需要存儲在實際的物理內存中的。因此我們通過源碼，實際分析 storage 部分的存儲情況。EVM 的源碼在 https://github.com/ethereum/cpp-ethereum

流程分析

1、 EVM 的返回值是通過 EVM 傳遞的，一般的在 Memory 偏移 0x40 的位置保存著返回值地址，這個地址上保存著真實的返回值

2、Storage 在最底層的實現上是一個 STL 實現稀疏數組，將 slot 值作為 key 來存儲值

3、在 Storage 中的 Map 和變長 Array 均是以 hash 值作為最底層稀疏數組的索引來進行的。其中變長數組的索引方式為 hash(array_slot) + index 而 Map 的索引方式為 hash(map_slot, key) ，當 Value 為 Struct 時 Struct 成員會分別存儲，每個成員的索引為 hash(map_slot, key) + offset

代碼分析

STORAGE

Storage 部分內存是與合約代碼共同存儲在區塊中的內存，因此 storage 內存消耗的 gas 回相對較多，我們通過 SLOAD 指令查看 Storage 在區塊上的存儲方式

SLOAD 指令在函數 interpretCases 中進行處理，當 EVM 解析到 SLOAD 指令后，首先從棧中獲取棧頂元素作為 storage 訪問的 key，然后調用函數 getStorage 進行實際訪問

    case SLOAD:
            evmc_uint256be key = toEvmC(m_SP[0]);
            evmc_uint256be value;
            m_context->fn_table->get_storage(&value, m_context, &m_message->destination, &key);
            m_SPP[0] = fromEvmC(value);

evmc_context_fn_table const fnTable = {
        accountExists,
        getStorage,
        setStorage,
        getBalance,
        getCodeSize,
        copyCode,
        selfdestruct,
        eth::call,
        getTxContext,
        getBlockHash,
        eth::log,
    };

getStorage 函數接收四個參數，第一個參數為返回地址，第二個參數是當前調用的上下文環境，第三個參數是此次交易信息的目的地址即合約地址，第四個參數是 storage 的索引 key

函數首先對 address 進行驗證，保證當前的上下文就是處于合約地址的空間內，接著再調用 env.store 實際獲取數據

void getStorage(
    evmc_uint256be* o_result,
    evmc_context* _context,
    evmc_address const* _addr,
    evmc_uint256be const* _key
) noexcept
{
    (void) _addr;
    auto& env = static_cast<ExtVMFace&>(*_context);
    assert(fromEvmC(*_addr) == env.myAddress);
    u256 key = fromEvmC(*_key);
    *o_result = toEvmC(env.store(key));
}

    virtual u256 store(u256 _n) override final { return m_s.storage(myAddress, _n); }

最終工作來到 State::storage 中

u256 State::storage(Address const& _id, u256 const& _key) const
{
    if (Account const* a = account(_id))
    {
        auto mit = a->storageOverlay().find(_key);
        if (mit != a->storageOverlay().end())
            return mit->second;

        // Not in the storage cache - go to the DB.
        SecureTrieDB<h256, OverlayDB> memdb(const_cast<OverlayDB*>(&m_db), a->baseRoot());          // promise we won't change the overlay! :)
        string payload = memdb.at(_key);
        u256 ret = payload.size() ? RLP(payload).toInt<u256>() : 0;
        a->setStorageCache(_key, ret);
        return ret;
    }
    else
        return 0;
}

函數首先根據 address 獲取對應的 Account 對象

Account* State::account(Address const& _addr)
{
    auto it = m_cache.find(_addr);   // m_cache 使用 unordered_map 作為存儲結構， find 返回 pair<key, value> 迭代器，迭代器 it->frist 表示 key ; it->second 表示 value
    if (it != m_cache.end())
        return &it->second;

    if (m_nonExistingAccountsCache.count(_addr))  // m_nonExistingAccountsCache 用于記錄那些在當前環境下不存在的 addr
        return nullptr;

    // Populate basic info.
    string stateBack = m_state.at(_addr);  //  m_state 即為 StateDB ，以 addr 作為 key 獲取這個 account 相關的信息，StateDB 中的數據已經格式化成了 string
    if (stateBack.empty())
    {
        m_nonExistingAccountsCache.insert(_addr);
        return nullptr;
    }

    clearCacheIfTooLarge();

    RLP state(stateBack);  // 創建 RLP 對象。交易必須是正確格式化的RLP。”RLP”代表Recursive Length Prefix，它是一種數據格式，用來編碼二進制數據嵌套數組。以太坊就是使用RLP格式序列化對象。
    auto i = m_cache.emplace(
        std::piecewise_construct,
        std::forward_as_tuple(_addr),
        std::forward_as_tuple(state[0].toInt<u256>(), state[1].toInt<u256>(), state[2].toHash<h256>(), state[3].toHash<h256>(), Account::Unchanged)
    );  // 把這個 addr 以及其對應的數據加入到 cache 中，使用逐片構造函數
    m_unchangedCacheEntries.push_back(_addr);
    return &i.first->second;  // 返回這個 account
}

下面的注釋是部分 Account 對象的說明 ,Account 對象用于表示一個以太賬戶的狀態，Account 對象和 addr 通過 Map 存儲在 State 對象中。每一個 Account 賬戶包含了一個 storage trie 用于索引其在整個 StateDB 中的節點，Account 對于 storage 的操作會首先在 storageOverlay 這個 map 上進行，待之后有需要時才會將數據更新到 trie 上

/**
 * Models the state of a single Ethereum account.
 * Used to cache a portion of the full Ethereum state. State keeps a mapping of Address's to Accounts.
 *
 * Aside from storing the nonce and balance, the account may also be "dead" (where isAlive() returns false).
 * This allows State to explicitly store the notion of a deleted account in it's cache. kill() can be used
 * for this.
 *
 * For the account's storage, the class operates a cache. baseRoot() specifies the base state of the storage
 * given as the Trie root to be looked up in the state database. Alterations beyond this base are specified
 * in the overlay, stored in this class and retrieved with storageOverlay(). setStorage allows the overlay
 * to be altered.
 *

回到 State::storage 函數，在獲取了 Account 之后查看 Account 的 storageOverlay 中是否有指定 key 的 value ，如果沒有就去 DB 中查找，以 Account->m_storageRoot 為根，從 State->m_db 中獲取一個 db 的拷貝。在這個 tire 的拷貝中查找并將其 RLP 格式化之后存在 m_storageOverlay 中

可以看到在實際數據同步到區塊上之前，EVM 為 storage 和 account 均提供了二級緩存機制用以提高訪存的效率：

storage：一級緩存->account->m_storageOverlay; 二級緩存->state->m_db
account: 一級緩存->state->m_cache; 二級緩存->state->m_state

同樣我們從存儲 Storage 的入口點 SSTORE 開始進行分析, 主體函數為 VM::interpretCases , SSTORE opcode 最終會訪問一個 unordered_map 類型的 hash 表

void VM::interpretCases(){
        // .....
        CASE(SSTORE)
        {
            ON_OP();
            if (m_message->flags & EVMC_STATIC)
                throwDisallowedStateChange();

            updateSSGas();
            updateIOGas();

            evmc_uint256be key = toEvmC(m_SP[0]);
            evmc_uint256be value = toEvmC(m_SP[1]);
            m_context->fn_table->set_storage(m_context, &m_message->destination, &key, &value);
        }
        NEXT
        // .....
}

|-
    evmc_context_fn_table const fnTable = {
        accountExists,
        getStorage,
        setStorage,
        getBalance,
        getCodeSize,
        copyCode,
        selfdestruct,
        eth::call,
        getTxContext,
        getBlockHash,
        eth::log,
    };


    void setStorage(
        evmc_context* _context,
        evmc_address const* _addr,
        evmc_uint256be const* _key,
        evmc_uint256be const* _value
    ) noexcept
    {
        (void) _addr;
        auto& env = static_cast<ExtVMFace&>(*_context);
        assert(fromEvmC(*_addr) == env.myAddress);
        u256 index = fromEvmC(*_key);
        u256 value = fromEvmC(*_value);
        if (value == 0 && env.store(index) != 0)                   // If delete
            env.sub.refunds += env.evmSchedule().sstoreRefundGas;  // Increase refund counter

        env.setStore(index, value);    // Interface uses native endianness
    }

    |-
        void ExtVM::setStore(u256 _n, u256 _v)
        {
            m_s.setStorage(myAddress, _n, _v);
        }

        |-

            void State::setStorage(Address const& _contract, u256 const& _key, u256 const& _value)
            {
                m_changeLog.emplace_back(_contract, _key, storage(_contract, _key));
                m_cache[_contract].setStorage(_key, _value);
            }

            |-

                class Account{
                    // ...
                    std::unordered_map<u256, u256> m_storageOverlay;
                    // ...
                    void setStorage(u256 _p, u256 _v) { m_storageOverlay[_p] = _v; changed(); }
                    // ...
                }

MEMORY

依舊從 MSTORE 入手，查看 EVM 中對 memory 的處理

        CASE(MSTORE)
        {
            ON_OP();
            updateMem(toInt63(m_SP[0]) + 32);
            updateIOGas();

            *(h256*)&m_mem[(unsigned)m_SP[0]] = (h256)m_SP[1];
        }
        NEXT

可以看到 memory 只在當前運行環境中有效，并不存儲在與 state 相關的任何位置，因此 memory 只在當前這次運行環境內生效，即 Memory 只在一次交易內生效

CODE

code 與 storage 類似，也是與 Account 相關的，因此 code 也會存儲在 Account 對應的結構中，一級緩存為 account->m_codeCache；二級緩存存放位置 state->m_db[codehash]，

void State::setCode(Address const& _address, bytes&& _code)
{
    m_changeLog.emplace_back(_address, code(_address));
    m_cache[_address].setCode(std::move(_code));
}

總結

雖然 hash 碰撞的問題出現在了一起類似 CTF 的“盜幣”比賽中，但是我們也應該重視由于 EVM 存儲設計問題而帶來的變量覆蓋以及 hash 碰撞之類的問題，希望各位智能合約的開發者們在開發中關注代碼中的數據存儲，避免由于此類問題帶來的損失。

Timeline

6月28日——發現存在變量覆蓋以及 hash 碰撞問題
11月6日——發現存在 hash 碰撞問題的合約

Reference

[1] https://github.com/ethereum/solidity/issues/1550 [2] https://lilymoana.github.io/ethereum_theory.html [3] https://github.com/FISCO-BCOS/Wiki/tree/master/%E6%B5%85%E8%B0%88Ethereum%E7%9A%84%E5%AD%98%E5%82%A8#StateDB%E6%A8%A1%E5%9D%97 [4] https://github.com/ethereum/cpp-ethereum

Paper 本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/739/

Paper - 安全技術精粹

從一起“盜幣”事件看以太坊存儲 hash 碰撞問題

目錄

“盜幣”

深入分析

變量覆蓋

Hash 碰撞

背景分析

MAP

ARRAY

ARRAY + STRUCT

問題分析

變量覆蓋

成因分析

HASH 碰撞

實際內存

流程分析

代碼分析

STORAGE

MEMORY

CODE

總結

Timeline

Reference