[ReshardingV3] Receipts Reassignment

[Longarithm]

First, we describe logic for which there are no alternatives for shard split.

(1) Outgoing receipts need one-time adjustment. For the last chunk created before resharding happened, for every shard, we need to iterate over them all to possibly reassign to new shard. This is required because CP producing that outcome didn’t know when resharding finished.
(2) There is no limit for PromiseYield receipts number stores in shard. Thus PromiseYield data must be treated as part of state and either near-instantly resharded or fully copied to both children shards.

Now, consider all other receipts. I see two approaches.

• IR - instant resharding, CB - continuous balancing

Lazy

The only feasible approach for CB.

Discard storing target shard for buffered receipts.
Move all receipts to some randomly selected shard. For CB, it will be source shard only.
Then, reassignment happens within some window after resharding happens.

I claim there are only two type of changes to make -

• Delayed receipt can become buffered.
• As noted in (2), PromiseYield must be copied. Then on processing PromiseYield can be discarded if account no longer belongs to the shard.

Note that for buffered receipts no change is required because the source account set only narrows.
Alternative: by default we can copy everything to both shards. I described the “random one shard" option because it is more lazy :)

Pros

• No tricky storage ops.
• Bounded proof size. CP need to prove only receipts which were reassigned in a chunk.

Con

Resharding kinda extends in time, logic becomes a bit more complex.

Instant

Reassign everything at once.
Feasible only for IR so I will describe it for IR.
We need to iterate over all receipts for the “big” shard for old layout.
I see two TODOs here.

TODO 1: proof

Chunk validators must be convinced that receipts are reassigned correctly.
If amount of receipts is >1K, we have only ~1 KB to prove each receipt, which looks challenging in current state structure. At least we need a way to avoid including all receipts in a proof.
Thus, some change to Trie structure is required.

Suggestion: change TrieKeys, from e.g. DelayedReceipt { index: u64 } to DelayedReceipt { index: u64, account_id: AccountId }
It still allows to query every DelayedReceipt by index, because for each index there is unique trie path to some value.
At the same time, it allows to prove which delayed receipts belong to which shard. This way everyone can send a proof what the new state root of delayed receipts will be without sending receipts themselves! The overhead will be in order of ~200 B, which may be near the boundary of what state witness allows.

TODO 2: limits

We need to figure out what is the upper bound for number of all receipt kinds.

• check in Congestion Control logic, what is such limit on Delayed and Buffered.
• check limit on PromiseYields. Due to yield_timeout_length_in_blocks = 200, currently it’s like 20K receipts, but may go to any direction.

If total limit is appr. < 100K then it can be handled in one iteration, SSDs seem good enough for that.

If both TODOs are resolved well, the approach is reasonable.
If some limits doesn’t allow to process everything within 1s, we need to split that work among several consecutive chunks which will complicate the logic.

Note: the receipt split work must be done independently with applying chunks - if chunk ends up missing, the work shouldn’t be repeated.

Conclusion

For now I slightly prefer Lazy approach, because it requires less logical changes and there is less pressure on the system limits.

[Longarithm]

Because we proceed with IR and there we plan just to copy receipts to children and discard unnecessary ones, we only need to maintain one-time outgoing receipts reassignment. Not sure we need this issue for tracking that, will keep it open for a while.