Investigate on Async Backing

[axaysagathiya]

Issue summary

• [x] learn more about path of parachain block
• [x] watch video on async backing from polkadot blockchain academy
• [x] read the article on async backing from polkadot wiki
• [x] read about prospective parachain from implementor's guide
• [x] Look into async backing spec and tracking issue https://github.com/paritytech/polkadot/issues/3779

Other information and links

• Async backing Pokadot PR: https://github.com/paritytech/polkadot/pull/5022
• Async backing cumulus PR: https://github.com/paritytech/cumulus/pull/2300
• what will be removed? https://github.com/paritytech/polkadot-sdk/issues/4447

Acceptance criteria's (Outcomes)

@axaysagathiya please check how we put the AC in Elastic Scaling issue and add them here @kishansagathiya

• [x] How many subsystem we have to modify to support async backing?
• [x] How we need to modify them? (waht changes should we done)
• [x] Does newer versions backward compatible with older version?
• [x] Should we keep older versions of the code? Or should we remove them? Or should we maybe keep both (so we can keep version compatibility)?
• [x] Elastic scaling intoduces some changes that replces Async backing, so maybe we can skip this parts of Async Backing and start implementing Elastic Scaling.
• [ ] Prepare hackmd file with investigation outcomes

[axaysagathiya]

Notes from async backing video by polkadot blockchain academy

in legacy backing, (Collation generation + backing) and (availability and inclusion), they require one to finish before the other can start. They can't run in parallel.

a parachain produce a block whenever relaychain block has included a previous candidate from that parachain.

after a parachain candidate block gets enough supporting votes, relay chain block author selects one candidate of each parachain to be included in a relay chain. and they get included directly to the relay chain. but...

In Async backing, instead of back the candidate on chain, we cache these candidates in a storage structure in the relay chain client. and later these cached candidates are then used for the availability and inclusion steps.

The Async backing optimistic collator assumptions

1. The best existing parablock the collator aware of will eventually be included in the relay chain
2. There won't be a chain reversion impacting that best parablock.

The worst case here the parablock we assumed will be included, doesn't get included. may be we have remake a few blocks. But this assumptions gives us mmuch more than what they could take away.

Async backing advantages

Synchrounous backing diagram

Asynchrounous backing diagram

Unincluded Segment: it stores the parachain block which are not yet included into the relaychain block. unincluded segments live in the runtimes of parachain collators.

The core functionality that asynchronous backing brings is the ability to build on these unincluded segments of block ancestors rather than building only on ancestors included in the relay chain state.

[axaysagathiya]

Notes from Async backing Wiki

In Synchronous backing,

parablock generation is tightly coupled to the relay chain's progression:

• A new parablock can be produced after including the previous one (i.e., every 12 seconds).
  • 6 second for backing(in relay chain block 1), 6 second for inclusion(in relay chain block 2)
  • execution time can take maximum 0.5 seconds as parablock P is rushing to be backed in the next 5.5 seconds (2 seconds needed for backing and the rest for gossiping)
  • parachain block can be generated every alternative relaychain block.
• Context to build the next parablock is drawn from the latest included parablock ancestor
• The relay parent must be the latest relay chain block.

In Async Backing.

Two parameters of asynchronous backing can be controlled by Governance:

• max_candidate_depth: the number of parachain blocks a collator can produce that are not yet included in the relay chain.

• allowed_ancestry_len: the oldest relay chain parent a parachain block can be built on top of. Initial values will be set to 3 (4 unincluded parablocks at all times) and 2 (relay parent can be the third last).

parachain block Gets 2 second execution time, which was 0.5 seconds in synchronous backing.

The 2-second execution time is thus a limiter, not a system limitation. If parablock generation takes >2 seconds, the unincluded segment will shrink (less unincluded parablocks), while if it takes < 2 seconds, the segment will grow (more unincluded parablocks that will need to be backed and included). Such flexibility from the parachain side will be possible when, on the relay chain side, there will be elastic scaling (i.e., agile core usage and coretime allocation).

What is prospective Parachain in async backing?

Keep track of parablocks that have been submitted to backers but have yet to be included.

A parablock stops being a prospective parablock when it is included on chain. At that point prospective parachains does not have to care about it anymore. Alternatively, a parablock's relay parent can get too old before that parablock is included, in which case prospective parachains can throw away the candidate.

[axaysagathiya]

Prospective parachain

we can now build prospective parachains – that is, trees of potential (but likely) future parachain blocks. This is the subsystem responsible for doing so.

other subsystems such as Backing rely on Prospective Parachains, e.g. for determining if a candidate can be seconded.

Prospective Parachains is primarily an implementation of fragment trees.

Messages we send from backing to prospective parachain subsystem

ProspectiveParachainsMessage::IntroduceCandidate

• Informs the subsystem of a new candidate.
• Sent by the Backing Subsystem when it is importing a statement for a new candidate.

ProspectiveParachainsMessage::CandidateSeconded

• Informs the subsystem that a previously introduced candidate has been seconded.
• Sent by the Backing Subsystem when it is importing a statement for a new candidate after it sends IntroduceCandidate, if that wasn't rejected by Prospective Parachains.

ProspectiveParachainsMessage::CandidateBacked

• Informs the subsystem that a previously introduced candidate has been backed.
• Sent by the Backing Subsystem after it successfully imports a statement giving a candidate the necessary quorum of backing votes.

ProspectiveParachainsMessage::GetHypotheticalFrontier

• Gets the hypothetical frontier membership of candidates with the given properties under the specified active leaves' fragment trees.
• Sent by the Backing Subsystem when sanity-checking whether a candidate can be seconded based on its hypothetical frontiers.

ProspectiveParachainsMessage::GetTreeMembership

• Gets the membership of the candidate in all fragment trees.
• Sent by the Backing Subsystem when it needs to update the candidates seconded at various depths under new active leaves.

ProspectiveParachainsMessage::GetMinimumRelayParents

• Gets the minimum accepted relay-parent number for each para in the fragment tree for the given relay-chain block hash.
• That is, this returns the minimum relay-parent block number in the same branch of the relay-chain which is accepted in the fragment tree for each para-id.
• Sent by the Backing, Statement Distribution, and Collator Protocol subsystems when activating leaves in the implicit view.

[axaysagathiya]

Subsystems affected by Async backing support

Implemented v1 in Gossamer and need to update

• Candidate backing subsystem
• Collator Protocol

Not implemented in Gossamer:

• Statement distribution subsystem

  introduced cluster distribution protocol to share within backing group and grid distribution protocol to share with all the validators

• Provisioner subsystem:

  Modify code to request backable candidates from the candidate backing subsystem.

• Prospective parachain

  • New subsystem introduced in async backing.
  • Introduced fragment tree to store backable parachain block