How Predicting Access Lists Can Be a Potential Way to Speed Up Evm for Portal Clients

Last year, I became very interested in getting involved in the development of core Ethereum protocols. So I decided to participate in the Ethereum Core Developer Apprenticeship Program Cohort-one as a start.

I was specifically interested in EVM and Stateless Ethereum at the time and finally worked on implementing a prototype predict-al of predicting access list for Portal Network clients.

Applying a methodology like a taint checking, the prototype, when tested with about one million historical transactions on Ethereum Mainnet, achieves an average improvement of 2.448x on reducing the number of iterations to retrieve the state from the network.

Background

Piper initially proposed the idea of predicting the access list in the Ethereum Core Developer Apprenticeship Program Cohort-one.

It's crucial for blockchain decentralization that a regular user is able to run a node on resource-constrained devices. The Portal Network is an in-progress Ethereum research effort towards this goal.

In the Portal Network, Ethereum state data, including account balances, nonce values, contract codes, and storage values, should be evenly distributed across the nodes. A portal client that participates in the network typically exposes the standard JSON-RPC API, even though it only stores a small part of the whole state data of the network.

A portal client will encounter a new serious problem that does not exist in the current full nodes when it executes the API eth_call or eth_estimateGas because it typically does not have necessary state data and has to retrieve them on demand from the network.

If we keep the same implementation of EVM as the current popular execution layer clients in portal clients, the EVM engine will need to be paused to retrieve data from the network each time state data is accessed. This will dramatically slow down the EVM execution when the number of states to be accessed grows too large.

A potential solution for this problem is to build an engine that could predict a significant amount of the accounts and storage slots to be accessed before a transaction is performed. Then those predicted state data could be fetched concurrently instead of one by one.

If this contract calls for another contract's method or the location of a storage slot to be accessed depending on another storage slot's value, we can't predict all-state in one round. Once the predicted state data in the last round has been retrieved, the tool should be run again with those values to find more states to be accessed until there are no more new states.

We could run one process to perform the actual EVM execution and spawn another process at the same time to run this tool, predicting the transaction's access list and retrieving their values from the network in the background. Another potential benefit of this solution is that the current popular implementation of EVM could be re-used by portal clients without much modification.

Prototype Implementation

When the tool receives a transaction payload, the sender and receiver can be easily extracted directly from the payload. Once the two accounts' state data such as balances, nonces, and bytecodes have been fetched from remote nodes, the next step is to find out more state accesses if the receiver is a contract or zero.

We can perform some simple static analysis with the retrieved contract bytecode to find out some state accesses with constant locations. For example:

PUSH1 0x00
SLOAD

But for some more complicated data structures, such as dynamic arrays and maps, the storage locations are usually dynamically computed with the provided parameters. For example:

      // bytecode snippet of loading the value from a map by the provided key
      //
      //  mapping(address => uint256) public balances; 
      //  function balanceOf(address _owner) public view returns (uint balance){
      //    return balances[_owner];
      //  }
      //
     
      CALLDATALOAD
        ...           // A lot of codes many jumpings are omitted here
      JUMPDEST          
      PUSH 0            
      DUP1          
      PUSH 0            
      DUP4          
      PUSH FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF         
      AND           
      PUSH FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF         
      AND           
      DUP2          
      MSTORE            
      PUSH 20           
      ADD           
      SWAP1             
      DUP2          
      MSTORE            
      PUSH 20           
      ADD           
      PUSH 0            
      KECCAK256             
      SLOAD           

Even though we can find out these access patterns by static analysis, obviously we still need a virtual machine to execute those bytecodes to compute the exact storage locations.

Taint Checking

A customized EVM has been implemented in this prototype to resolve the above issue. We can run a transaction with this EVM and record potential state accesses. Taint checks were introduced into this EVM to dynamically identify which state accesses should be recorded. At the same time, it also removed the need to pause EVM execution when state access happens.

Considering the following example described in the YUL language, there are four possible different state accesses in this function.

function foo() -> result {
    let x := 0
    let y := 1
    let m := sload(x)
    let n := sload(y)
    let z := 2
    
    let k := gt(m, n)
    switch k
    case 0 {
        result := sload(n)
    }
    default {
        result := sload(z)
    }
} 

The graph below shows the flow of taint in the first round of running this tool. The return value of any state access will be marked as tainted unless the value has already been retrieved from the network and saved into local storage. Red nodes and arrows in this graph indicate taint, and dotted lines represent indirect influence.

Obviously, m is tainted by sload in this round. The customized EVM only marks it as tainted and then continues to handle the following opcodes. At the end of the execution of this function, there are four sloads to be found in total, but the location n of the third sload is a tainted value whose exact value is unknown at the moment. So only the other three untainted locations x, y and z will be recorded after this round.

Once these three states have been retrieved, we can run this tool again. A new flow of taint is shown as the following:

In this second round, the variables m and n are not marked as tainted anymore because their values have been retrieved and can be loaded from the local storage. Consequently, the switch condition k is also untainted.

If "case 0" is executed by the EVM, only n will be recorded in this round. It will be merged with the other three state accesses found in the previous round as the final access list.

If "case 0" isn't executed, there will be no more new state access. The state access list found in the previous round will then be the final access list.

Branch Traversal

The conditional branch is a very important case that needs to be handled carefully in this prototype. It's very common in a contract that there are many conditional branches based on the values of other storage slots. We need to traverse both branches and look up the possible state accesses either way if the slot value has not been retrieved from the network yet.

The YUL code in the above section also shows an example of this case. The switch condition k depends on the values of storage slots x and y. We need to follow both branches when k is tainted. Obviously, both branches would be traversed in the first round, but only one of them would be followed in the second round in this example.

In order to follow both branches, the EVM context needs to be backed up before the first branch is executed and restored before the second branch is executed. Branch paths will grow exponentially once there are nested branches with tainted conditions.

So the depth of nested branches must be limited to avoid path explosion. If a conditional branch with a tainted value were repeatedly hit in the execution, it's possible that there's an infinite loop here. We also need to set a threshold to break it up.

Testing with Real Transactions

To test the prototype with real transactions on Mainnet, this tool needs to fetch data from an archived Geth node via the JSON-RPC API to simulate retrieving state data from other nodes in the Portal Network.

First, I ran the prototype predict-al with some historical blocks on mainnet to get predicted access lists. Then the trace-helper tool was run with the same blocks to generate exact access lists for the validation of those predicted results. At last, another tool predict-analyze was executed to validate the outputs of predict-al and trace-helper and import them into a PostgreSQL database for further investigation.

The testing was performed with 5000 historical blocks on the Ethereum mainnet from block 13580500 to 13585500 (exclusive). The total number of transactions is 1043603. Among the 671567 contract calls and creation transactions among them is what we are interested in. The remaining other simple Ether transfer transactions will be ignored in the analysis because they don't interact with any contracts. Finally, we got the following findings with this data.

Effectiveness of State Retrieval

To measure the effectiveness of state retrieval of this prototype, we define a factor as follows:

factor = iterations-of-worst-case / (rounds-of-prediction + (total-pieces-of-state - number-of-correctly-predicted-accesses))

Suppose that there's a historical transaction that involves touching 20 different pieces of state. The worst case is that the tool has to fetch them one piece at a time sequentially. This means 20 iterations of network lookups for this transaction.

Suppose the tool has predicted 18 possible state accesses in 4 rounds, we found out that only 15 of them are accurately accessed in this historical transaction after comparing them with the exact access-list produced by the trace-helper tool. The remaining 5 pieces of state that haven't been predicted will still have to be fetched sequentially.

factor = 20 / (4 + (20 - 15))

According to the above expression, the factor of effectiveness should be 2.22. It means that this tool could fetch 2.22 pieces of state concurrently in each lookup on average, reducing the total iterations of lookups from 20 to 9.

The tool achieved an average effectiveness factor of 2.448x in this testing. To better understand the average factor, we further show the effectiveness distribution across all 671567 contract calls and create transactions in the above figures:

• Most of them are showing the effectiveness of between 1.0x and 4.0x
• Only 0.62% of them are less than 1.0x.
  • With further investigation of these transactions, we found that 80.4% of them are failed historical transactions. They reverted during the execution and only accessed small parts of the possible access lists that were predicted by the tool. This should explain why the tool got less effective for most of them.

Prediction Correctness

As mentioned in the above section, all the predicted access lists need to be validated with the exact access lists produced by tracing the same transactions. The tool predict-al predicts the access list based on the state of the previous block, while the trace-helper generates the data based on both the state of the previous block and the position of this transaction in this block.

This will usually cause some small differences between the datasets produced by these two tools. The ratio of correctness means how much percentage of the exact access list has been predicted correctly.

ratio = 15 / 20

For the example transaction mentioned in the above section, the ratio should be 75%, according to the above expression.

The tool achieves an average ratio of 91.45% correctness. It means that on average, 91.5% of the exact state accesses have been predicted correctly in this testing. The figure above shows the distribution of the ratio of correctness. It reports that about 76.37% of them have been predicted with 100% correctness.

Frequently Accessed State

In the testing, we observed that some contracts and their methods are called far more frequently than others. The table below shows the top 10 contract methods that have been called with high frequency.

There are a total of 89647 unique contract methods that have been called 2245330 times in all of the 671567 transactions. The top 10 contract methods have been called 607581 times in total, and occupy 27.06% of all method calls.

The potential to improve the efficiency of this tool is based on this kind of access pattern. For example, we could save bytecodes of some most frequently accessed contracts in local storage as a cache, then we could save one round to fetch those contracts' bytecodes sometimes.

Conclusion

With the approach of taint checking, the prototype of this solution can predict about 91.45% of the access lists correctly and achieves an average of 2.448x effectiveness of state retrieval. We also observed that some contract methods are called more frequently than others. This kind of access pattern can be utilized to improve this prototype.

It's very important to reduce the time spent on state data retrieval when a portal client executes the API eth_call or eth_estimateGas. Predicting the access list is a potential solution to resolve this problem, and as a result, speed up the EVM execution for portal clients.

Also published here.