Automated Detection of Dynamic State Access in Solidity

Sharded Execution
4

This is true, but this is missing some cases!

I know this is early work, but for the sake of completeness I thought it might be useful to enumerate all the other causes of DSA which I could think of.

Well, first, let me write out what I think the different kinds of state access are, let me know if I’m misunderstanding your terms:

  • SSA: The transaction specifies a short list of addresses and storage items it might touch (read or write).
    • for example: BALANCE > 1000 ? SSTORE[0] = 1 : SSTORE[1] = 1.
  • “large bound state accesses” (LBSA?): transactions for which the set of accounts/storage items it might touch is bounded, but too large to provide a witness for.
    • for example: I might call BLOCKHASH and depending on the result send a reward to any one of a thousand beneficiaries. It would be very expensive to provide a witness for all thousand of them!
  • DSA: The set of addresses the transaction might touch to is [0,2^{160}-1], or the set of storage items the transaction might touch is [0,2^{256}-1]. We have no idea what the transaction might try to access.
    • for example: SSTORE[SSLOAD[0]] = 1

There are some additional causes of full DSA:

  • The COINBASE opcode can’t be predicted at witness-creation time, and returns an address the transaction could try to interact with.

  • I might call BLOCKHASH (which can’t be predicted during witness creation) and treat the result as an address and try to send eth to that address. This will almost certainly fail, but proving that it fails requires a witness from the relevant part of the account trie.

  • I might call BLOCKHASH and use it to derive the salt for a call to CREATE2. This will result in the account being created at a completely unpredictable location.

  • Due to the Wild Magic shenanigans which CREATE2 enables, other contracts might entirely change between the time of witness creation and the time the txn makes it to the blockchain:

    • If the txn reads an address out of the result of EXTCODECOPY, that could cause full DSA.
    • If the txn calls any of the CALL opcodes (even STATICCALL) on a wild magic contract that contract could do anything, easily invalidating the transaction’s witness.

There are some potential sources of “LBSA”:

  • BALANCE returns your current balance, which might change between witness generation and transaction confirmation, someone might send your address ETH. So, SLOAD[BALANCE] could attempt to access any of a large variety of storage items.

  • Other opcodes have the same property: TIMESTAMP, NUMBER, DIFFICULTY, GASLIMIT. None of them can be predicted ahead of time (except possibly NUMBER) and and of them could be the target of an SLOAD.

  • GAS is also tricky. Even if you can know for sure wihch set of accounts / storage items that a call to CALL will touch, the values of those storage items can change how much gas the call consumes. This means the result of GAS cannot be known ahead of time.

There are also some additional complications:

  • The initcode passed to CREATE and CREATE2 has all of the same considerations, they also need to be analyzed.

  • In the general case it’s difficult to even construct a witness. Say that you have access to the entire state trie and you want to create a witness for a transaction, you would need to do something very fancy to determine which accounts might be accessed by the transaction, given that you don’t know the results of all the opcodes mentioned above.

  • It’s not just SLOAD which can read from different parts of the state trie. EXTCODESIZE, for instance, can also read from arbitrary parts of the account trie. EXTCODESIZE[BLOCKHASH] can read from almost anywhere, and proving that the result ought to be 0 requires proving that part of the state tree.

Anyway, I’m sure that most of this is already on your TODO list, posting it because there might be something here which hasn’t already surfaced.