Implement state parts in new format

[Longarithm]

Presentation about implemented state part format as of 23 May 2023: https://jamboard.google.com/d/1aSzP_ujR7u_m-fe7ZFxS6bpoFePhK6OKGMMvg2FO520/

---

This is the proposal for state parts format, to work well with #8899. Originated from Zulip. Goal - new format must be cleaner, contain only necessary data and support flat storage.

General idea

To split state, we take a list of DFS trie traversal order and compute prefix sums of node memory usages. If total size of memory usages is total_size and we split state in num_parts, we define boundary of X-th part as (total_size + num_parts - 1) / num_parts * X. All nodes between X and (X+1)-th boundaries define state items in range for part #X. See also https://pagodaplatform.atlassian.net/wiki/spaces/EAP/pages/302088267/State+sync+parts+DRAFT.

Current format

1. Two paths: from root to the first node and from root to the last node for part #X;
2. Full set of nodes between boundaries #X and #(X+1).

One can prove that this set of nodes is connected. Because it includes root, node can verify that these nodes do exist in state. Node can independently verify and apply each part. But reading nodes is very slow, and we want to reduce amount of data sent.

New format

1. Data part - all KV pairs (items) in range for part #X.
2. Proof part - two boundaries.
   2.1) path from root to the first key for part #X with all left siblings;
   2.2) path from root to the first key from part #(X+1).

On this example, all marked nodes are a proof for part 2.
2.1 is necessary and sufficient to prove first item for part; 2.2 does the same for the last item.
I’ve also considered to cut path in (2.2) on the first node which does not belong to part #X (on red node). But it looks a bit harder to verify.
To prove last part, it is enough to check that path to last item doesn’t have any right siblings. Or that “16” would be the next item in its DFS order, as the code does.

Generation

1. Search both boundaries in Trie with two different recording modes. Return also first key for both parts.
2. Make range query to flat storage.

Validation & applying

1. Size check (TBD). There should be some boundary on state part size.
2. (!) Validate state items: key.len() <= 2 KB, value.len() <= 4 MB. Otherwise I'm concerned about slowdowns/increased memory usages.
3. Restore first item from part #(X+1) from given path. Check that path doesn't have any extra nodes. Add it to the list of state items.
4. Create trie T1 induced by state boundary nodes.
5. Create trie T2 from scratch using received state items - by starting from empty root and calling Trie::insert.
6. Create T3 as a union of nodes from T1 of T2. We will work with T3 now.
7. Check that left boundary is the path to first key from #X and doesn't have extra nodes. Descend to it together with verifying memory usages, or fail if some node is missing.
8. Iterate over Trie until first key from #(X+1) is found or fail if some node is missing. Count visited state items and collect visited nodes.
9. Compare number of visited items with number of items in state part. If there is a match, validation is passed. Add all visited nodes to DB and add state items to flat storage.

Note that some nodes from T1 will not be visited and it is normal. For example, state root generated from state items will not match real state root from boundaries and will not be visited.

I claim that it is enough to verify data correctness.
https://jamboard.google.com/d/1aSzP_ujR7u_m-fe7ZFxS6bpoFePhK6OKGMMvg2FO520/ is a visual proof for slightly modified algo, if we include all left siblings into right boundary.
Note that we don't even have to check that state items are ordered!

Pros

• Number of nodes in state part is greatly reduced and allows us to do fast state sync.
• Format is cleaner than now. In theory we can switch to AVL or other tree and we will have to change only proof part, data part stays the same.
• It allows us to do optimistic state sync without proof part. Though please note that it requires building trie iteratively. When some part is applied, trie must be locked, as we build state root iteratively. Described process can be parallelised on parts.

Cons

• Validation is harder than before, because now we are in fact we have to "guess" nodes for which only hashes were sent to us. Previously, it was enough to send raw nodes and compare visited node counters. Now, range of items can be arbitrarily spoiled, which requires extra attention.

I'm especially interested in suggestions on simplifying validation process, because it already looks complicated. Though I don't think our current validation process is articulated very well, so thorough and accurate definition is also an improvement.

TBD

• Values deduplication

[Longarithm]

For history: it seems that our current state sync approach was tracked on #1237. Majority of code was added in #1592 which lacks documentation :P

[walnut-the-cat]

Can we also mention how this is different from what we have now?

Optimistic part

What does 'optimistic' here mean? is there a case where sames of the part can be missing?

[Longarithm]

Done. I need to add more pictures at some point.
Changed "optimistic" to "data part". It is optimistic in the sense that if node trusts its peers, they can only send data to it (optimistically) without sending proofs, which should speed the process up even more.

One more point: to release state sync sooner, we may stick with slight modification of current format. It is harder to generate on sender side and node has to send more data, but it is much much easier to validate.

[nikurt]

Huge +1, the proposal looks great.
Maximizing the amount of useful data in state parts will make the state sync process more efficient for both sender's and receivers.

Storing KV pairs introduces a cost of explicitly storing the keys, but that cost should be smaller than the Leaf nodes.

[Longarithm]

After looking at existing implementation, I think that "right boundary path" should include all left siblings as well, because:

1. We can reuse the same TrieRecordingStorage code
2. We can verify boundaries independently and get proven key boundaries sooner
3. To generate state part, you need to iterate over all left siblings anyway, and they shouldn't consume too much space. Removing them from state part is an extra effort.

[Longarithm]

To summarize:

• I refactored state parts so that they always begin and end on some state item;
• we considered compressing state parts further but don't go for it now as it is not crucial.

However, we still may want to implement the full plan at some pojnt because of two inefficiencies:

• State part proof size is too big #9098
• Speed up trie generation during state part construction #9099

I will close this exact issue in a week if there are no objections.