cumulus: support submission for candidates with older relay parents (max_relay_parent_age_session alignment)

[iulianbarbu]

Problem Statement

When max_relay_parent_session_age > 0, the relay chain accepts candidates built against relay parents from older sessions. However, for V3 collations the collator-side parent search uses a narrow ancestry window (scheduling_lookahead - 1 blocks) that breaks at session boundaries unconditionally, and discards the blocks corresponding to candidates at the relay parents in the previous session. However, the parachain blocks at those relay parents can still be considered, by checking the relay parents at the scheduling parents via ancestor_relay_parent_info runtime API. Aditionally, it is important that the candidate's parachain parent block we build upon to have been submitted at a scheduling parent that is in the same session as the current scheduling parent session. Lastly, we don't want an unincluded segment to age out for many sessions (as many blocks as max_relay_parent_session_age allows), in case the candidates in the segment are not backed on-chain/included. Until the resubmission implementation arrives we should build the relay parents ancestry in a similar fashion to how we build for relay parents, for V2 collations, only that they'll be build for the scheduling_parent for V3.

Things to address for V3

1. We should find the parachain parent while checking their relay parents if they are valid with the relay client ancestor_relay_parent_info.
2. Cache relay best hashes session in the RelayChainDataCache.
3. Session-aware parachain block filtering — when evaluating a parachain block as a potential parent during DFS traversal, determine the session of its scheduling parent. For each candidate parachain parent: query the para client at that block to obtain its relay_parent_offset, extract the relay parent hash from the para block digest, add the offset to derive the scheduling parent number, and look up the scheduling parent's session from the cache (point 2 — the cache already holds session indices for cached relay blocks). Compare against the current session to decide whether the parachain block is a valid parent.
4. Check the parachain parents in DFS for their scheduling parents's sessions against a scheduling parent ancestry, computed like we compute for relay parents, for V2 collations.

Steps to reproduce

#10742 has V3 related zn-sdk tests related to a parachain with relay_parent_offset > 0, which has bad throughput because of issues in relation to the above subjects, and should have throughput similar with the test where relay_parent_offset is 0. Validating the fix should factor in prospective parachains fix PR on the relay chain side ideally (will be opened soon by @alindima ), and an appropriate zn-sdk test where we configure the parachain with relay parent offset big enough to be able to submit candidates built against relay parents in the previous session, but scheduled in the current session.

cargo test --features zombie-ci --test tests zombie_ci::elastic_scaling::upgrade_to_3_cores::elastic_scaling_upgrade_to_3_cores

[alindima]

When max_relay_parent_session_age > 0, the relay chain accepts candidates built against relay parents from older sessions. However, the collator-side parent search uses a narrow
ancestry window (scheduling_lookahead - 1 blocks) that breaks at session boundaries unconditionally. During a relay chain stall where candidates are not backed, the unincluded
segment ages out of this window, forcing the collator to unnecessarily fork and rebuild from the included block — even though those candidates are still valid for resubmission
on the relay chain.

This attempts to summarise all 3 problems into one, but they don't all have the same root cause and effects: #10742 (review). Also, we don't need a relay chain stall for these issues to be exhibited.

Configurable ancestry threshold via parachain-system — add a type config in parachain-system (e.g., type ResubmissionAncestryThreshold) with an associated runtime API,
defaulting to 20. This only applies to V3. V2 retains the existing scheduling_lookahead - 1 logic and session-break behavior in find_parent and its callees unchanged.

Why? I don't remember discussing this at all

Let's use the allowed_relay_parent_info as discussed, just looking at the session index is not enough

#10742 has V3 related zn-sdk tests related to a parachain with relay_parent_offset > 0, which has bad throughput because of issues in relation to the above subjects, and should have throughput similar with the test where relay_parent_offset is 0. Validating the fix should factor in prospective parachains fix PR on the relay chain side ideally (will be opened soon by @alindima ), and an appropriate zn-sdk test where we configure the parachain with relay parent offset big enough to be able to submit candidates built against relay parents in the previous session, but scheduled in the current session.

For quick testing, see the last two commits I authored that you can cherry-pick to fix the relay chain: https://github.com/paritytech/polkadot-sdk/commits/alindima/prospective-parachains-older-rps/

@serban300 please also look at my comment before starting to work on this: #10742 (review)

IMO this issue is focused more on how to fix the issues but doesn't explain as clearly the problems

[iulianbarbu]

After discussing with @alindima offline today he pointed out a few flaws in my previous understanding, and a missing aspect that was missed in the initial fixes mentioned on #10742. I tried to clarify the description of this issue once more after the discussion, and the things that should be done. cc @serban300

[serban300]

@iulianbarbu @alindima thank you for creating and investigating this issue and for the clear description. I just have 2 questions so far:

3. ... For each candidate parachain parent: query the para client at that block to obtain its relay_parent_offset, extract the relay parent hash from the para block digest, add the offset to derive the scheduling parent number, and look up the scheduling parent's session from the cache (point 2 — the cache already holds session indices for cached relay blocks).

I don't know if this strategy would work. The problem is that the scheduling parent number can map to multiple hashes if there are forks. Is there any way to find the actual hash of the scheduling parent ?

2. Not very important: I see DFS mentioned a couple of times here, but looking on find_deepest_valid_parent() it seems to traverse the tree level by level. Isn't that BFS ?

The other points are clear, but we need the scheduling parent for most of them

[iulianbarbu]

Not very important: I see DFS mentioned a couple of times here, but looking on find_deepest_valid_parent() it seems to traverse the tree level by level. Isn't that BFS ?

Should be DFS because we pop from the end, so we're going deeper with every descendant.

don't know if this strategy would work. The problem is that the scheduling parent number can map to multiple hashes if there are forks. Is there any way to find the actual hash of the scheduling parent ?

🤔 Given we need them for session index, even if there is a fork that could result in multiple hashes for same number, picking either of the resulting hashes to find out the session should be ok (blocks with same number on different forks should be in the same session). At 4 though, it gets trickier, without gossipping against which scheduling parent a certain para block was submitted. I think that before resubmissions a compromise here could be to still keep the relay parents ancestry based filtering (minus the part where we filter out relay parents if part of a previous session - we're interested mostly in the window, we could very well reduce this filtering to a certain window of block numbers being allowed for the para blocks relay parents), which to some extent it is equivalent to the filtering based on scheduling parents ancestry - freshness of relay parents is equivalent to freshness of scheduling parents before resubmissions are enabled. It could be the case that points 3 & 4 can be merged somehow, the cosntraints though are different (how I understand it is window & session aware filtering for scheduling parents, where session aware filtering influences the window filtering especially at session boundary).