epic: estimate_gas undershoots necessary gas

[greged93]

Bug Report

Current behavior:
The current flow for the gas estimation in Kakarot greatly divergences from the flow in Reth/Geth: both Reth and Geth use a binary search given a lower and upper bound for gas limit (link for Reth) whereas Kakarot sets the gas limit in the call to 5 millions and returns the gas_used + gas_refund as a gas estimation.

This can cause issue for example in the following scenario:

• Current available gas is 5M, used 10k: internal call in contract requires a gas limit of 95k but uses only 10k gas.
• Call proceeds and tx ends with 30k gas used.
• Kakarot returns 30k estimate gas, while transaction actually requires at least 95k gas in order to pass.

Tasks:

Tasks

Beta Give feedback

1. Increase the gas estimate returned by estimate_gas_helper by 20%. #1052
   good first issue +1
2. Implement a binary search method similar to the above Reth implementation. Use/modify the Database trait implementation in tracing/database.rs in order to cache the code of touched contracts, initial nonce, initial balance and initial storage of any touched slots.

[enitrat]

see kkrt-labs/kakarot#1133

[Eikix]

Is this still stuck?

[greged93]

this isn't stuck, we just decided not to implement the binary search method as long as the other method works.