Provisioner

NOTE: This module has suffered changes for the elastic scaling implementation. As a result, parts of this document may be out of date and will be updated at a later time. Issue tracking the update: https://github.com/paritytech/polkadot-sdk/issues/3699

Relay chain block authorship authority is governed by BABE and is beyond the scope of the Overseer and the rest of the subsystems. That said, ultimately the block author needs to select a set of backable parachain candidates and other consensus data, and assemble a block from them. This subsystem is responsible for providing the necessary data to all potential block authors.

Provisionable Data

There are several distinct types of provisionable data, but they share this property in common: all should eventually be included in a relay chain block.

Backed Candidates

The block author can choose 0 or 1 backed parachain candidates per parachain; the only constraint is that each backable candidate has the appropriate relay parent. However, the choice of a backed candidate must be the block author's. The provisioner subsystem is how those block authors make this choice in practice.

Signed Bitfields

Signed bitfields are attestations from a particular validator about which candidates it believes are available. Those will only be provided on fresh leaves.

Misbehavior Reports

Misbehavior reports are self-contained proofs of misbehavior by a validator or group of validators. For example, it is very easy to verify a double-voting misbehavior report: the report contains two votes signed by the same key, advocating different outcomes. Concretely, misbehavior reports become inherents which cause dots to be slashed.

Note that there is no mechanism in place which forces a block author to include a misbehavior report which it doesn't like, for example if it would be slashed by such a report. The chain's defense against this is to have a relatively long slash period, such that it's likely to encounter an honest author before the slash period expires.

Dispute Inherent

The dispute inherent is similar to a misbehavior report in that it is an attestation of misbehavior on the part of a validator or group of validators. Unlike a misbehavior report, it is not self-contained: resolution requires coordinated action by several validators. The canonical example of a dispute inherent involves an approval checker discovering that a set of validators has improperly approved an invalid parachain block: resolving this requires the entire validator set to re-validate the block, so that the minority can be slashed.

Dispute resolution is complex and is explained in substantially more detail here.

Protocol

The subsystem should maintain a set of handles to Block Authorship Provisioning iterations that are currently live.

On Overseer Signal

• ActiveLeavesUpdate:
  • For each activated head:
    • spawn a Block Authorship Provisioning iteration with the given relay parent, storing a bidirectional channel with that iteration.
  • For each deactivated head:
    • terminate the Block Authorship Provisioning iteration for the given relay parent, if any.
• Conclude: Forward Conclude to all iterations, waiting a small amount of time for them to join, and then hard-exiting.

On ProvisionerMessage

Forward the message to the appropriate Block Authorship Provisioning iteration, or discard if no appropriate iteration is currently active.

Per Provisioning Iteration

Input: ProvisionerMessage. Backed candidates come from the Candidate Backing subsystem, signed bitfields come from the Bitfield Distribution subsystem, and disputes come from the Disputes Subsystem. Misbehavior reports are currently sent from the Candidate Backing subsystem and contain the following misbehaviors:

1. Misbehavior::ValidityDoubleVote
2. Misbehavior::UnauthorizedStatement
3. Misbehavior::DoubleSign

But we choose not to punish these forms of misbehavior for the time being. Risks from misbehavior are sufficiently mitigated at the protocol level via reputation changes. Punitive actions here may become desirable enough to dedicate time to in the future.

At initialization, this subsystem has no outputs.

Block authors request the inherent data they should use for constructing the inherent in the block which contains parachain execution information.

Block Production

When a validator is selected by BABE to author a block, it becomes a block producer. The provisioner is the subsystem best suited to choosing which specific backed candidates and availability bitfields should be assembled into the block. To engage this functionality, a ProvisionerMessage::RequestInherentData is sent; the response is a ParaInherentData. Each relay chain block backs at most one backable parachain block candidate per parachain. Additionally no further block candidate can be backed until the previous one either gets declared available or expired. If bitfields indicate that candidate A, predecessor of B, should be declared available, then B can be backed in the same relay block. Appropriate bitfields, as outlined in the section on bitfield selection, and any dispute statements should be attached as well.

Bitfield Selection

Our goal with respect to bitfields is simple: maximize availability. However, it's not quite as simple as always including all bitfields; there are constraints which still need to be met:

• not more than one bitfield per validator
• each 1 bit must correspond to an occupied core

Beyond that, a semi-arbitrary selection policy is fine. In order to meet the goal of maximizing availability, a heuristic of picking the bitfield with the greatest number of 1 bits set in the event of conflict is useful.

Dispute Statement Selection

This is the point at which the block author provides further votes to active disputes or initiates new disputes in the runtime state.

The block-authoring logic of the runtime has an extra step between handling the inherent-data and producing the actual inherent call, which we assume performs the work of filtering out disputes which are not relevant to the on-chain state. Backing votes are always kept in the dispute statement set. This ensures we punish the maximum number of misbehaving backers.

To select disputes:

• Issue a DisputeCoordinatorMessage::RecentDisputes message and wait for the response. This is a set of all disputes in recent sessions which we are aware of.

Determining Bitfield Availability

An occupied core has a CoreAvailability bitfield. We also have a list of SignedAvailabilityBitfields. We need to determine from these whether or not a core at a particular index has become available.

The key insight required is that CoreAvailability is transverse to the SignedAvailabilityBitfields: if we conceptualize the list of bitfields as many rows, each bit of which is its own column, then CoreAvailability for a given core index is the vertical slice of bits in the set at that index.

To compute bitfield availability, then:

• Start with a copy of OccupiedCore.availability
• For each bitfield in the list of SignedAvailabilityBitfields:
  • Get the bitfield's validator_index
  • Update the availability. Conceptually, assuming bit vectors: availability[validator_index] |= bitfield[core_idx]
• Availability has a 2/3 threshold. Therefore: 3 * availability.count_ones() >= 2 * availability.len()

Candidate Selection: Prospective Parachains Mode

The state of the provisioner PerRelayParent tracks an important setting, ProspectiveParachainsMode. This setting determines which backable candidate selection method the provisioner uses.

ProspectiveParachainsMode::Disabled - The provisioner uses its own internal legacy candidate selection. ProspectiveParachainsMode::Enabled - The provisioner requests that prospective parachains provide selected candidates.

Candidates selected with ProspectiveParachainsMode::Enabled are able to benefit from the increased block production time asynchronous backing allows. For this reason all Polkadot protocol networks will eventually use prospective parachains candidate selection. Then legacy candidate selection will be removed as obsolete.

Prospective Parachains Candidate Selection

The goal of candidate selection is to determine which cores are free, and then to the degree possible, pick a candidate appropriate to each free core. In prospective parachains candidate selection the provisioner handles the former process while prospective parachains handles the latter.

To select backable candidates:

• Get the list of core states from the runtime API
• For each core state:
  • On CoreState::Free
    • The core is unscheduled and doesn’t need to be provisioned with a candidate
  • On CoreState::Scheduled
    • The core is unoccupied and scheduled to accept a backed block for a particular para_id.
    • The provisioner requests a backable candidate from prospective parachains with the desired relay parent, the core’s scheduled para_id, and an empty required path.
  • On CoreState::Occupied
    • The availability core is occupied by a parachain block candidate pending availability. A further candidate need not be provided by the provisioner unless the core will be vacated this block. This is the case when either bitfields indicate the current core occupant has been made available or a timeout is reached.
    • If bitfields_indicate_availability
      • If Some(scheduled_core) = occupied_core.next_up_on_available, the core will be vacated and in need of a provisioned candidate. The provisioner requests a backable candidate from prospective parachains with the core’s scheduled para_id and a required path with one entry. This entry corresponds to the parablock candidate previously occupying this core, which was made available and can be built upon even though it hasn’t been seen as included in a relay chain block yet. See the Required Path section below for more detail.
      • If occupied_core.next_up_on_available is None, then the core being vacated is unscheduled and doesn’t need to be provisioned with a candidate.
    • Else-if occupied_core.time_out_at == block_number
      • If Some(scheduled_core) = occupied_core.next_up_on_timeout, the core will be vacated and in need of a provisioned candidate. A candidate is requested in exactly the same way as with CoreState::Scheduled.
      • Else the core being vacated is unscheduled and doesn’t need to be provisioned with a candidate The end result of this process is a vector of CandidateHashs, sorted in order of their core index.

Required Path

Required path is a parameter for ProspectiveParachainsMessage::GetBackableCandidates, which the provisioner sends in candidate selection.

An empty required path indicates that the requested candidate chain should start with the most recently included parablock for the given para_id as of the given relay parent.

In contrast, a required path with one or more entries prompts prospective parachains to step forward through its fragment tree for the given para_id and relay parent until the desired parablock is reached. We then select the chain starting with the direct child of that parablock to pass to the provisioner.

The parablocks making up a required path do not need to have been previously seen as included in relay chain blocks. Thus the ability to provision backable candidates based on a required path effectively decouples backing from inclusion.

Legacy Candidate Selection

Legacy candidate selection takes place in the provisioner. Thus the provisioner needs to keep an up to date record of all backed_candidates PerRelayParent to pick from.

The goal of candidate selection is to determine which cores are free, and then to the degree possible, pick a candidate appropriate to each free core.

To determine availability:

• Get the list of core states from the runtime API
• For each core state:
  • On CoreState::Scheduled, then we can make an OccupiedCoreAssumption::Free.
  • On CoreState::Occupied, then we may be able to make an assumption:
    • If the bitfields indicate availability and there is a scheduled next_up_on_available, then we can make an OccupiedCoreAssumption::Included.
    • If the bitfields do not indicate availability, and there is a scheduled next_up_on_time_out, and occupied_core.time_out_at == block_number_under_production, then we can make an OccupiedCoreAssumption::TimedOut.
  • If we did not make an OccupiedCoreAssumption, then continue on to the next core.
  • Now compute the core's validation_data_hash: get the PersistedValidationData from the runtime, given the known ParaId and OccupiedCoreAssumption;
  • Find an appropriate candidate for the core.
    • There are two constraints: backed_candidate.candidate.descriptor.para_id == scheduled_core.para_id && candidate.candidate.descriptor.validation_data_hash == computed_validation_data_hash.
    • In the event that more than one candidate meets the constraints, selection between the candidates is arbitrary. However, not more than one candidate can be selected per core.

The end result of this process is a vector of CandidateHashs, sorted in order of their core index.

Retrieving Full BackedCandidates for Selected Hashes

Legacy candidate selection and prospective parachains candidate selection both leave us with a vector of CandidateHashs. These are passed to the backing subsystem with CandidateBackingMessage::GetBackedCandidates.

The response is a vector of BackedCandidates, sorted in order of their core index and ready to be provisioned to block authoring. The candidate selection and retrieval process should select at maximum one candidate which upgrades the runtime validation code.

Glossary

• Relay-parent:
  • A particular relay-chain block which serves as an anchor and reference point for processes and data which depend on relay-chain state.
• Active Leaf:
  • A relay chain block which is the head of an active fork of the relay chain.
  • Block authorship provisioning jobs are spawned per active leaf and concluded for any leaves which become inactive.
• Candidate Selection:
  • The process by which the provisioner selects backable parachain block candidates to pass to block authoring.
  • Two versions, prospective parachains candidate selection and legacy candidate selection. See their respective protocol sections for details.
• Availability Core:
  • Often referred to simply as "cores", availability cores are an abstraction used for resource management. For the provisioner, availability cores are most relevant in that core states determine which para_ids to provision backable candidates for.
  • For more on availability cores see Scheduler Module: Availability Cores
• Availability Bitfield:
  • Often referred to simply as a "bitfield", an availability bitfield represents the view of parablock candidate availability from a particular validator's perspective. Each bit in the bitfield corresponds to a single availability core.
  • For more on availability bitfields see availability
• Backable vs. Backed:
  • Note that we sometimes use "backed" to refer to candidates that are "backable", but not yet backed on chain.
  • Backable means that a quorum of the candidate's assigned backing group have provided signed affirming statements.