How to derive the storage key of mapping to an account?

Question

I am trying to derive changes of account storage by mapping accounts (here, the accounts represent the key address in the ERC20 balances mapping mapping(address => uint256)) to their corresponding storage keys from a parity transaction trace.

An example trace (fetched through web3.py) of transaction https://etherscan.io/tx/0x210cfe3d3b62f415ed0327a3c6177086df4937b6280031255360b6d137308554 is:

{
    'output': '0x',
    'stateDiff': {
        '0x52bc44d5378309ee2abf1539bf71de1b7d7be3b5': {
            'balance': {
                '*': {
                    'from': '0x122291885d6222bc5ec',
                    'to': '0x12229193ca3f58565ec'
                }
            },
            'code': '=',
            'nonce': '=',
            'storage': {}
        },
        '0xaddba95f769b5d42c02e144102817eab9d00efd3': {
            'balance': '=',
            'code': '=',
            'nonce': '=',
            'storage': {
                '0x1ded6755a6d7d843883da8cd8948931cf9f8b1e8f8983ad77e1685ece0b92fc2': {
                    '*': {
                        'from': '0x0000000000000000000000000000000000000000000000000000000000000000',
                        'to': '0x000000000000000000000000000000000000000000000000000bfb8d0ebc5000'
                    }
                },
                '0x5020d77d5345022a5466af6f78731b10f92d31e17961c23ea6ce5c185dc75d49': {
                    '*': {
                        'from': '0x0000000000000000000000000000000000000000000000000000000000000000',
                        'to': '0x0000000000000000000000000000000000000000000000000000e1412a5f1c00'
                    }
                }
            }
        },
        '0xf2eeb980b60b9ed146636c65ecc5e8f27a8aed40': {
            'balance': {
                '*': {
                    'from': '0x2c4c7111f4801a8',
                    'to': '0x2c410434bee61a8'
                }
            },
            'code': '=',
            'nonce': {
                '*': {
                    'from': '0x143',
                    'to': '0x144'
                }
            },
            'storage': {}
        }
    },
    'trace': [{
        'action': {
            'callType': 'call',
            'from': '0xf2eeb980b60b9ed146636c65ecc5e8f27a8aed40',
            'gas': '0x9008',
            'input': '0xa9059cbb000000000000000000000000e034e561ce112c5f261f15d447e8f2436d9625040000000000000000000000000000000000000000000000000000e130de0be000',
            'to': '0xaddba95f769b5d42c02e144102817eab9d00efd3',
            'value': '0x0'
        },
        'result': {
            'gasUsed': '0x3924',
            'output': '0x'
        },
        'subtraces': 0,
        'traceAddress': [],
        'type': 'call'
    }],
    'vmTrace': None
}

According to https://solidity.readthedocs.io/en/v0.4.24/miscellaneous.html#layout-of-state-variables-in-storage, "value corresponding to a mapping key k is located at keccak256(k . p) where . is concatenation". I am aware of the necessary left pad, according to "keccack(LeftPad32(key, 0), LeftPad32(map position, 0))" https://github.com/ethereum/wiki/wiki/JSON-RPC#eth_getstorageat, although the hashing functions seem to handle this internaly already.

I tried the Web3.sha3() for this keccak256 storage key, and other issues on StackOverflow mention that Solidity employs a slightly different hashing algorithm. Nevertheless, also by using the proper Web3.soliditySha3() I do not arrive at a hash that would present me the key found in the the trace (here, 0x1ded6755a6d7d843883da8cd8948931cf9f8b1e8f8983ad77e1685ece0b92fc2 or 0x5020d77d5345022a5466af6f78731b10f92d31e17961c23ea6ce5c185dc75d49) to the account 0xf2eeb980b60b9ed146636c65ecc5e8f27a8aed40.

What is the right way (preferably with web3.py) to hash the account and position in order to arrive at the mapping storage key?

Answer 1

As mentioned by @jaime in the comments you need the position of the mapping variable to find the relation between address and storage key.

You can find a code I have written to detect the position for a basic erc20 contract below (using web3.py):

    import json
    from web3.auto.infura import w3
    from eth_utils import remove_0x_prefix, to_int, to_checksum_address, to_hex
# erc20 contract address
CONTRACT_ADDRESS = '0x89205A3A3b2A69De6Dbf7f01ED13B2108B2c43e7'
# address with non zero token balance
HOLDER_ADDRESS = '0xD1220A0cf47c7B9Be7A2E6BA89F429762e7b9aDb' 

def getStorageAtIndex(i):
    pos = str(i).rjust(64, '0')
    key = remove_0x_prefix(HOLDER_ADDRESS).rjust(64, '0').lower()
    storage_key = to_hex(w3.sha3(hexstr=key + pos))
    return to_int(w3.eth.getStorageAt(CONTRACT_ADDRESS, storage_key))

for i in range(0, 20):
    if getStorageAtIndex(i) != 0:
        print("position is {}".format(i))

Result:
>>> position is 5

Once you have the correct value of position you can fetch the values stored in contract easily.

    pos = str(5).rjust(64, '0')
    key = remove_0x_prefix(HOLDER_ADDRESS).rjust(64, '0').lower()
    storage_key = to_hex(w3.sha3(hexstr=key + pos))
    w3.eth.getStorageAt(CONTRACT_ADDRESS, storage_key)