[ReshardingV3] State Witness

[Longarithm]

Goals

• Algorithm to efficiently generate resharding proof and validate it in the state witness for every column type.
  • In particular, support shard layout change if it changes in state transition range covered by SW.
• Describe implications, e.g. size increase of the state witness.

[Longarithm]

[for old notes]

Proof

The key proof is new state roots generation.
It is two paths to keys: K1 - the greatest key which is less than boundary; K2 - the smallest key which is at least the boundary. (Needed because existence of boundary is never guaranteed). Generated by recording trie get operations.

(Do we ever need to check that K1 or K2 must exist?)

Verifying

First, verifier proves that K1 < boundary <= K2 and there are no other keys in between (one trie iteration).
Then,

• Left shard: new left state root is generated by setting all right children of K1 to None.
• Right shard: new right state root is generated by setting all left children of K2 to None.

Note that path has enough information, new root is generated by removing information from the path and recomputing the hash.

The result will be added as field resharding_proof: PartialState into ChunkStateWitness.
Note that if shard is not split, proof will be empty and no extra steps must be performed.

(Check annoying usecases related to node compression and going to some extra children)

[Longarithm]

Goal

Describe how to handle shard layout on stateless validation.

Overview

The chunk application logic contains many different steps. Some of them have to be adjusted in order to respect resharding. Though I prepare list of exact changes to be made, it may look messy.
The most complicated steps are:

• seamless generation and verifying of the new state root;
• remapping of outgoing receipts which cross epoch boundary.

Preparation

There is a specific step "new chunk extra generation" which will be mentioned couple times.
ChunkExtra is a result of processing a chunk, used to validate "starting" parameters of the next chunk - prev state root, prev outgoing receipts root, etc. It is stored for pair (block hash, shard uid).
We need to switch ChunkExtras to the new shard layout.
This will be handled in the following way:

• save chunk extra for all tracked shards for last block in old layout in usual way;
• generate frozen memtrie for child shards;
• manually create chunk extras for child shards (uses new state root from new memtries);
• validate chunks from the first block in new layout against these manual chunk extras.

After that we continue normal processing. This diagram may help:

[Layout/Epoch]

[Old/Old] --> [Old/Old]   | epoch change
                  |       |
                  v       |
              [New/Old] --|--> [New/New]
                          |
    H            H+1      |       H+2

The vertical arrow is "manual chunk extra creation". We may need to add special condition for GC to remove these extra "extras".
Note that this step doesn't care if chunk for any shard is missing or not - chunk extras are always created for all tracked shards.
If somehow there are two blocks with same height, they will have different hashes and will not collide. Anyway, this is block double signing, which should be extremely rare.

To implement that, we need to adjust code residing in process_resharding_results. This code belongs to ReshardingV2, but now it needs to be triggered only once, not for the whole epoch.

Proof

See #12074.

Stateless Logic

Starting from start_validating_chunk...

1. Locating last and last last new chunks.
   While going back, if shard layout changed, switch from shard_id to parent shard_id.

2. validate_source_receipt_proofs:

for block in receipt_source_blocks
    for chunk in block.chunks().iter()
        validate_receipt_proof 

There, in old shard layout, we need to pass parent of shard id.
And on receipt collection, we retain only receipts which target new shard_id, using EpochManager and receiver.

After prevalidation finishes, we start execution. We get

3. last_header = Chain::get_prev_chunk_header.

It must get header for parent shard id.
Then we will have two alternatives:

4.1: We have chunk extra for the prev block.

Then we track shard and we should have new chunk extra generation completed. Thus, chunk extra for new shard layout will exist, so it is enough to do validate_chunk_with_chunk_extra as we do currently.

4.2: We don't have chunk extra.

Then validate_chunk_state_witness is called.
There, after state transition (main or implicit) for the last block in old layout is applied,

• we verify the resharding proof on top of current state root;
• do new chunk extra generation using current state root, switch to resulting new state root;
• switch from shard id in main transition (old layout) to the new one.

Stateful Logic

There is a lot of ReshardingV2 logic to remove. For example,

• resharding_state_roots -> None,
• shard_context.need_to_reshard - to remove, etc.

We won't discuss it here.

Actual changes:

Before epoch switch:
If we process apply chunk result, and the next block is in new epoch with new shard layout, then we generate a proof and new chunk extra.

Somewhere on epoch switch, we rely on new memtrie being generated which allows processing of chunks in the new layout.

After epoch switch:

On missing chunks: just new chunk extra will be generated with state root copied from the previous one.

On the first chunk in new shard layout:
On new_receipts & old_receipts collection, they will target shards from old layout. We need to remap them to new shard layout.

On state witness generation, the previously generated proof must be included.

Note that the changes are the same for nodes which only track the shard, excluding state witness sending.

Next Steps

• Resolve leftover questions.
• Implement logic for new state root generation, perform unit testing.
• Rewrite process_resharding_results to implement "new chunk extra generation".
• Full prototype. Run on integration test, check different scenarios:
  • boundary key not present
  • trie node compression
  • resharding proof is invalid
  • first/last chunks around epoch boundary are missing
  • outgoing receipts are remapped correctly

Challenges

• Use naive memtrie creation until it is not implemented
• Use shard_id = shard index until we don't fix it everywhere
• For not split shards we need to add some trivial logic