Implement binary search based fee estimation algorithm

[kkovaacs]

Starknet 0.13.4 introduces runtime L2 gas accounting. A dedicated withdraw_gas libfunc call is added by the compiler into loops. For non-tail-recursive calls withdraw_gas always requires the worst-case gas amount to be available, so the compiler inserts redeposit_gas libfunc calls onto paths that cost less than the worst-case. (For a detailed analysis please check this document.)

This means that simply taking the L2 gas costs of a transaction execution and using that as a fee cap when submitting a transaction might lead to the transaction reverting due to insufficient gas. Whether or not this happens depends on whether there are paths during the execution where worst-case gas requirements are significantly larger than the actual costs.

To get a fee estimate that guarantees that the transaction will succeed we have to resort to trial-and-error:

• Run transaction with a large fee cap (maybe balance induced but can be max as well), get consumed gas g.
• Unfortunately the VM doesn't currently do accounting on gas refunds (g'), so let's just assume that in most cases the transaction does not have a pathological case and try executing it with (1 + epsilon) * g gas.
  • If that succeeds, just use that as a fee estimate.
  • If the transaction reverts, check that the cause of the revert is insufficient gas and do a binary search for a sufficient gas cap within [ (1 + epsilon) * g, max ].

[kkovaacs]

Some transactions on integration to help with testing. The contract is called twice:

• First with an L2 gas allowance of 1M: it succeeds. L2 gas consumption in the receipt is 861350:

    {
      "execution_status": "SUCCEEDED",
      "transaction_index": 0,
      "transaction_hash": "0xf9e2327f6edb64a41f54088ca88bcf7f2331efeb0343b668a69b469986d8b8",
      "l2_to_l1_messages": [],
      "events": [
        {
          "from_address": "0x4718f5a0fc34cc1af16a1cdee98ffb20c31f5cd61d6ab07201858f4287c938d",
          "keys": [
            "0x99cd8bde557814842a3121e8ddfd433a539b8c9f14bf31ebf108d12e6196e9",
            "0x3ad02acd6e492fcccf20d22f66a7f759623ffd243f9b5c71d6e72978d7cfa5c",
            "0x1176a1bd84444c89232ec27754698e5d2e7e1a7f1539f12027f28b23ec9f3d8"
          ],
          "data": [
            "0x97a6f09ef4a2",
            "0x0"
          ]
        }
      ],
      "execution_resources": {
        "n_steps": 4467,
        "builtin_instance_counter": {
          "range_check_builtin": 137,
          "pedersen_builtin": 19,
          "poseidon_builtin": 3
        },
        "n_memory_holes": 0,
        "data_availability": {
          "l1_gas": 0,
          "l1_data_gas": 128,
          "l2_gas": 0
        },
        "total_gas_consumed": {
          "l1_gas": 0,
          "l1_data_gas": 128,
          "l2_gas": 861350
        }
      },
      "actual_fee": "0x97a6f09ef4a2"
    }

• The second invocation was done with an L2 gas limit of 900k and it still failed with "out of gas":

{
      "revert_error": "Transaction execution has failed:\n0: Error in the called contract (contract address: 0x03ad02acd6e492fcccf20d22f66a7f759623ffd243f9b5c71d6e72978d7cfa5c, class hash: 0x05b04ab0c4ddc9e87184afd1710abe9750d88e0612858a132a3d0af2c943ef5d, selector: 0x015d40a3d6ca2ac30f4031e42be28da9b056fef9bb7357ac5e85627ee876e5ad):\nExecution failed. Failure reason:\nError in contract (contract address: 0x03ad02acd6e492fcccf20d22f66a7f759623ffd243f9b5c71d6e72978d7cfa5c, class hash: 0x05b04ab0c4ddc9e87184afd1710abe9750d88e0612858a132a3d0af2c943ef5d, selector: 0x015d40a3d6ca2ac30f4031e42be28da9b056fef9bb7357ac5e85627ee876e5ad):\nError in contract (contract address: 0x057db596276973cab6285927b2c743bca4f420d6ea4748ebe5038dc83ffa8c08, class hash: 0x01d81fac99dc637b14bcc7a9203441b8f1092461f4c40888d8b3833f3a2ee208, selector: 0x014a9a610b6c242b01e01b59a4474f46f0213139737c69cab5d3e95f1cbc00f0):\n0x4f7574206f6620676173 ('Out of gas').\n",
      "execution_status": "REVERTED",
      "transaction_index": 3,
      "transaction_hash": "0x4e5d474350e71811418d4dc643b913d57fbedc85bf64d98017bfddf0b8f7369",
      "l2_to_l1_messages": [],
      "events": [
        {
          "from_address": "0x4718f5a0fc34cc1af16a1cdee98ffb20c31f5cd61d6ab07201858f4287c938d",
          "keys": [
            "0x99cd8bde557814842a3121e8ddfd433a539b8c9f14bf31ebf108d12e6196e9",
            "0x3ad02acd6e492fcccf20d22f66a7f759623ffd243f9b5c71d6e72978d7cfa5c",
            "0x1176a1bd84444c89232ec27754698e5d2e7e1a7f1539f12027f28b23ec9f3d8"
          ],
          "data": [
            "0x8e4256892440",
            "0x0"
          ]
        }
      ],
      "execution_resources": {
        "n_steps": 4467,
        "builtin_instance_counter": {
          "pedersen_builtin": 19,
          "range_check_builtin": 137,
          "poseidon_builtin": 3
        },
        "n_memory_holes": 0,
        "data_availability": {
          "l1_gas": 0,
          "l1_data_gas": 128,
          "l2_gas": 0
        },
        "total_gas_consumed": {
          "l1_gas": 0,
          "l1_data_gas": 128,
          "l2_gas": 808000
        }
      },
      "actual_fee": "0x8e4256892440"
    }