Gas estimation via binary search

[TorstenStueber]

The user rightfully expects that eth_estimateGas returns a gas estimate that will lead to a successful execution if used as the gas limit for the transaction.

This is true for most Ethereum clients, but currently not for revive.

Details

Our gas estimation uses a very simple approach: dry run the transaction using some maximal gas limit max_gas, measure the consumed resources and extract a gas requirement from these consumed resources. Use that as the gas estimate.

This approach doesn't always work. For example consider a contract with the following function:

function bar() external {
   other.foo{gas: gasleft() / 2}();
}

and assume that the function other.foo does some heavy computation that requires gas $g$. Then the total gas usage of bar() is $\approx g$ but the proper gas limit for the transaction bar() is actually $\approx 2g$.

Most Ethereum clients use a different approach for gas estimation. They first dry run the transaction using the maximum limit max_gas like we do, extract the gas_used from that transaction and then do binary search in the range (gas_used, max_gas) to find the smallest amount of gas where the transaction does not fail (for Geth: see here for the definition of the lower limit and here for the definition of the binary search, which is not pure binary search but uses some heuristics). Using this gas estimation approach would indeed return the value $\approx 2g$.

Shortcomings

The binary search approach is not perfect and assumes that when the transaction is successful for any gas limit $g$, it is also successful for any gas limit $\geq g$ (in mathematical terms, the set of successful gas limits is an "upper set"). But that does not need to hold and there can be separate regions of gas limits that make the transaction successful. In this case the binary search can't guarantee to find the smallest successful gas limit as it can just completely skip over such regions. For example:

function foo2() external {
    if (gasleft() > 10_000_000) {
        // requires 510k gas
        sum = 0;
        for (uint i = 0; i < 1000; i++) {
            sum += i;
        }
        return;
    }
    
    if (gasleft() < 1_000_000) {
        // requires 610k gas
        sum = 0;
        for (uint i = 0; i < 1200; i++) {
            sum += i;
        }
        return;
    }

    // requires 4700k gas
    sum = 0;
    for (uint i = 0; i < 10000; i++) {
        sum += i;
    }
}

The initial lower bound of the binary search is about 510k because the execution given the maximum gas limit max_gas (which is more than 10_000_000) returns early and uses only 510k gas. However, using the gas limit 510k will lead to a revert as the second if is true but the body requires 610k gas.

The two successful regions for the gas limit are 610k - 1000k and 4700k – max_gas. Binary search between 510k and max_gas will completely miss the successful region 610k - 1000k and will eventually settle on the value 4700k but the minimal gas limit for success is actually 610k.

This is the actual behavior of Geth.

Bonus

As a bonus we don't need to track the difference between required and consumed resources anymore. We just need consumed resource and we just need it once to determine the lower limit for the binary search. In the binary search we don't neither need to determine consumed or required resources – we only need to check whether the transaction runs out of gas or not.

TODO

• Define how this works with the generalized resource model, i.e., how the actually tracked resources weight and storage deposit relate to the external resource limit "Ethereum gas"
• Implement a similar gas estimation approach as implemented in the de-facto standard client Geth.
  • This should not be implemented in the ETH RPC proxy but directly in pallet-revive.

[athei]

I thought the binary search was performed by the wallet. Are you saying geth is driving this loop?

[TorstenStueber]

I also thought it was the wallets, only learned recently that it is actually the Ethereum clients doing this. The wallet makes only one call and the loop is in Geth.

[athei]

But for us it still works with a one-shot run since we track and returm the highest amount of gas used. Not the actual consumed gas. It might break with the new gas model. But it used to work without the binary search.

[TorstenStueber]

The example I give in the description does not work with our approach. Neither before, nor after the new gas model.