# Prospective Parachains

## Overview

**Purpose:** Tracks and handles prospective parachain fragments and informs
other backing-stage subsystems of work to be done.

"prospective":
- [*prə'spɛktɪv*] adj.
- future, likely, potential

Asynchronous backing changes the runtime to accept parachain candidates from a
certain allowed range of historic relay-parents. This means 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. This subsystem is the main
coordinator of work within the node for the collation and backing phases of
parachain consensus.

Prospective Parachains is primarily an implementation of fragment trees. It also
handles concerns such as:

- the relay-chain being forkful
- session changes

See the following sections for more details.

### Fragment Trees

This subsystem builds up fragment trees, which are trees of prospective para
candidates. Each path through the tree represents a possible state transition
path for the para. Each potential candidate is a fragment, or a node, in the
tree. Candidates are validated against constraints as they are added.

This subsystem builds up trees for each relay-chain block in the view, for each
para. These fragment trees are used for:

- providing backable candidates to other subsystems
- sanity-checking that candidates can be seconded
- getting seconded candidates under active leaves
- etc.

For example, here is a tree with several possible paths:

```
Para Head registered by the relay chain:     included_head
                                                  ↲  ↳
depth 0:                                  head_0_a    head_0_b
                                             ↲            ↳
depth 1:                             head_1_a              head_1_b
                                  ↲      |     ↳
depth 2:                 head_2_a1   head_2_a2  head_2_a3
```

### The Relay-Chain Being Forkful

We account for the same candidate possibly appearing in different forks. While
we still build fragment trees for each head in each fork, we are efficient with
how we reference candidates to save space.

### Session Changes

Allowed ancestry doesn't cross session boundary. That is, you can only build on
top of the freshest relay parent when the session starts. This is a current
limitation that may be lifted in the future.

Also, runtime configuration values needed for constraints (such as
`max_pov_size`) are constant within a session. This is important when building
prospective validation data. This is unlikely to change.

## Messages

### Incoming

- `ActiveLeaves`
  - Notification of a change in the set of active leaves.
  - Constructs fragment trees for each para for each new leaf.
- `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::GetBackableCandidates`
  - Get the requested number of backable candidate hashes along with their relay parent for a given
    parachain,under a given relay-parent (leaf) hash, which are descendants of given candidate
    hashes.
  - Sent by the Provisioner when requesting backable candidates, when
    selecting candidates for a given relay-parent.
- `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.
- `ProspectiveParachainsMessage::GetProspectiveValidationData`
  - Gets the validation data of some prospective candidate. The
    candidate doesn't need to be part of any fragment tree.
  - Sent by the Collator Protocol subsystem (validator side) when
    handling a fetched collation result.

### Outgoing

- `RuntimeApiRequest::ParaBackingState`
  - Gets the backing state of the given para (the constraints of the para and
    candidates pending availability).
- `RuntimeApiRequest::AvailabilityCores`
  - Gets information on all availability cores.
- `ChainApiMessage::Ancestors`
  - Requests the `k` ancestor block hashes of a block with the given
    hash.
- `ChainApiMessage::BlockHeader`
  - Requests the block header by hash.

## Glossary

- **Candidate storage:** Stores candidates and information about them
  such as their relay-parents and their backing states. Is indexed in
  various ways.
- **Constraints:**
  - Constraints on the actions that can be taken by a new parachain
    block.
  - Exhaustively define the set of valid inputs and outputs to parachain
    execution.
- **Fragment:** A prospective para block (that is, a block not yet referenced by
  the relay-chain). Fragments are anchored to the relay-chain at a particular
  relay-parent.
- **Fragment tree:**
  - A tree of fragments. Together, these fragments define one or more
    prospective paths a parachain's state may transition through.
  - See the "Fragment Tree" section.
- **Inclusion emulation:** Emulation of the logic that the runtime uses
  for checking parachain blocks.
- **Relay-parent:** A particular relay-chain block that a fragment is
  anchored to.
- **Scope:** The scope of a fragment tree, defining limits on nodes
  within the tree.
