Describe the feature

Whenever dealing with the tries and trie updates we have to carefully consider which block the DB tip was synced to when an operation started, and then later when persisting trie updates we have to consider if the trie updates are still valid given a potentially updated DB tip.

This complexity has recently bitten us and caused a major outage on mainnet.

In addition the current design is quite slow during reorg situations: we are forced to fallback to the slower ParallelStateRoot implementation (rather than the faster ParallelSparseTrie) during validation if the block being validated does not connect to the database tip. ParallelStateRoot is slower because we cannot use it to do partial state root computations as the block is being processed, it does all computation at the very end.

We can simplify the overall engine logic, make it faster during forks, and reduce surface area for edge-cases, by storing trie update change sets in the database. These changesets will function similarly to account/storage plain state changesets, allowing us to cheaply generate historical views of the trie tables, and quickly unwind them as needed.

Design

We store trie changesets for the most recent MAX_TRIE_HISTORY blocks, with MAX_TRIE_HISTORY being at least finality but also configurable by the user to be higher if they wish (e.g. if they want to provide eth_getProof RPC calls going back farther).

table AccountsTrieChangeSets {
    type Key = BlockNumber;
    type SubKey = StoredNibbles;
    type Value = Option<BranchNodeCompact>;
}

table StoragesTrieChangeSets {
    type Key = (BlockNumber, B256);
    type SubKey = StoredNibblesSubKey;
    type Value = Option<BranchNodeCompact>;
}

Using these tables we can modify HistoricalStateProvider (or create a companion trait which functions similarly) which provides historical trie state.

Additional context

This set of changes is a step forwards also for #18070. By providing cheap historical trie state the proof computation for historical blocks should be significantly improved.