SCORU: Linear traversals are critically bad
Problem
The commitment tree will contain branches of at most max_lookahead_in_blocks / commitment_period
blocks.
Unfortunately, we have linear traversals of these branches: with the latest values of the constants, these traversals exhaust the gas limit per operation.
This is witnessed by two failing tests in !6933 (closed).
More precisely, there are three linear traversals:
-
Sc_rollup_refutation_storage.get_conflict_point
: this function is used when a refutation game is started to determine what are the oldest conflicting commitments of the two stakers. -
Sc_rollup_stake_storage.remove_staker
: this function is used to remove all the implicit stakes of a slashed staker. -
Sc_rollup_stake_storage.refine_staker
: this function is used to move the stake during a publish commitment
Solution
get_conflict_point
can be removed as it suffices to ask for two conflicting commitments to be provided when the refutation game is started. We just need to check that these two commitments are indeed the oldest conflicting commitments for the two stakers.
remove_staker
can be removed in favor of a lazy removal of commitments at cementation time.
No fix for refine_staker
yet. <- We have one, will describe it as soon as possible.