Tx rollup: update gas model of consume_add_message

Context

We add a snoop benchmark for Tx_rollup_inbox_repr.Merkle.add_message. We add a logarithmic cost model for this benchmark. The results of running the bench on the reference machine and inferring the parameters of the cost model are attached:

inbox-ref.sol

inbox-ref-solution.csv

inbox-ref-timings.csv

Usign this model, we update the earlier conservative upper-bound used in consume_add_message_cost.

Discussion

The cost model inferred from the benches is, in milligas:

cost(add_message(messages, message))  = 487 + log2(|messages| + 1)

(where 488 is conservatively rounded up from the inferred 487.32).

The previous, conservative over-approximation was:

cost(add_message(messages, message)) = cost(hashing(32 bytes)) +
    cost(hashing(32 bytes)) * log2(tree-depth(merkelized inbox of maximum length))

(i'm too lazy to render that in latex)

that gives the constant cost of cost(add_message(messages, message)) = 481_486 milligas.

In other words, the previous over-approximation would charge 481_486 milligas for each message whereas inferred cost model would charge between 487 and ~5000 milligas (for the inbox sizes that are relevant, that is from 0 to 1010, since tx_rollup_max_messages_per_inbox = 1010.)

In this MR we use the inferred model, but to make the price of adding a message constant, we charge each message addition the same cost as if the inbox was full, i.e.:

cost(add_message(messages, message))  = 487 + log2(|tx_rollup_max_messages_per_inbox| + 1)

Manually testing the MR

Checklist

• Document the interface of any function added or modified (see the coding guidelines)
• Document any change to the user interface, including configuration parameters (see node configuration)
• Provide automatic testing (see the testing guide).
• For new features and bug fixes, add an item in the appropriate changelog (docs/protocols/alpha.rst for the protocol and the environment, CHANGES.rst at the root of the repository for everything else).
• Select suitable reviewers using the Reviewers field below.
• Select as Assignee the next person who should take action on that MR