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.
- For each
Conclude
: ForwardConclude
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:
Misbehavior::ValidityDoubleVote
Misbehavior::MultipleCandidates
Misbehavior::UnauthorizedStatement
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 SignedAvailabilityBitfield
s. 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 SignedAvailabilityBitfield
s: 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
SignedAvailabilityBitfield
s:- Get the bitfield's
validator_index
- Update the availability. Conceptually, assuming bit vectors:
availability[validator_index] |= bitfield[core_idx]
- Get the bitfield's
- 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.
- The core is unoccupied and scheduled to accept a backed block for a particular
- 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 scheduledpara_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
isNone
, then the core being vacated is unscheduled and doesn’t need to be provisioned with a candidate.
- If
- 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 withCoreState::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
CandidateHash
s, sorted in order of their core index.
- If
- On
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 anOccupiedCoreAssumption::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 anOccupiedCoreAssumption::Included
. - If the bitfields do not indicate availability, and there is a scheduled
next_up_on_time_out
, andoccupied_core.time_out_at == block_number_under_production
, then we can make anOccupiedCoreAssumption::TimedOut
.
- If the bitfields indicate availability and there is a scheduled
- If we did not make an
OccupiedCoreAssumption
, then continue on to the next core. - Now compute the core's
validation_data_hash
: get thePersistedValidationData
from the runtime, given the knownParaId
andOccupiedCoreAssumption
; - 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.
- There are two constraints:
- On
The end result of this process is a vector of CandidateHash
s, sorted in order of their core index.
Retrieving Full BackedCandidate
s for Selected Hashes
Legacy candidate selection and prospective parachains candidate selection both leave us with a vector of
CandidateHash
s. These are passed to the backing subsystem with CandidateBackingMessage::GetBackedCandidates
.
The response is a vector of BackedCandidate
s, 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_id
s to provision backable candidates for. - For more on availability cores see Scheduler Module: Availability Cores
- 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
- 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.