8. Availability & Validity

Polkadot serves as a replicated shared-state machine designed to resolve scalability issues and interoperability among blockchains. The validators of Polkadot execute transactions and participate in the consensus of Polkadots primary chain, the so-called relay chain. Parachains are independent networks that maintain their own state and are connected to the relay chain. Those parachains can take advantage of the relay chain consensus mechanism, including sending and receiving messages to and from other parachains. Parachain nodes that send parachain blocks, known as candidates, to the validators in order to be included in relay chain are referred to as collators.

The Polkadot relay chain validators are responsible for guaranteeing the validity of both relay chain and parachain blocks. Additionally, the validators are required to keep enough parachain blocks that should be included in the relay chain available in their local storage in order to make those retrievable by peers, who lack the information to reliably confirm the issued validity statements about parachain blocks. The Availability & Validity (AnV) protocol consists of multiple steps for successfully upholding those responsibilities.

Parachain blocks themselves are produced by collators (Section 8.1.), whereas the relay chain validators only verify their validity (and later, their availability). It is possible that the collators of a parachain produce multiple parachain block candidates for a child of a specific block. Subsequently, they send the block candidates to the relay chain validators who are assigned to the specific parachain. The assignment is determined by the Runtime (Section 8.2.). Those validators are then required to check the validity of submitted candidates (Section 8.3.), then issue and collect statements (Section 8.2.1.) about the validity of candidates to other validators. This process is known as candidate backing. Once a candidate meets specified criteria for inclusion, the selected relay chain block author then chooses any of the backed candidates for each parachain and includes those into the relay chain block (Section 8.2.2.).

Every relay chain validator must fetch the proposed candidates and issue votes on whether they have the candidate saved in their local storage, so-called availability votes (Section 8.4.1.), then also collect the votes sent by other validators and include them in the relay chain state (Section 8.2.2.). This process ensures that only relay chain blocks get finalized where each candidate is available on enough nodes of validators.

Parachain candidates contained in non-finalized relay chain blocks must then be retrieved by a secondary set of relay chain validators, unrelated from the candidate backing process, who are randomly assigned to determine the validity of specific parachains based on a VRF lottery and are then required to vote on the validity of those candidates. This process is known as approval voting (Section 8.5.). If a validator does not have the candidate data, it must recover the candidate data (Section 8.4.2.).

8.1. Collations

Collations are proposed candidates Definition 141 to the Polkadot relay chain validators. The Polkadot network protocol is agnostic on what candidate production mechanism each parachain uses and does not specify or mandate any of such production methods (e.g. BABE-GRANDPA, Aura, etc). Furthermore, the relay chain validator host implementation itself does not directly interpret or process the internal transactions of the candidate but rather rely on the parachain Runtime to validate the candidate (Section 8.3.). Collators, which are parachain nodes which produce candidate proposals and send them to the relay chain validator, must prepare pieces of data (Definition 111) in order to correctly comply with the requirements of the parachain protocol.

Definition 111. Collation

A collation is a data structure that contains the proposed parachain candidate, including an optional validation parachain Runtime update and upward messages. The collation data structure, C, is a data structure of the following format:

$${C}={\left({M},{H},{R},{h},{P},{p},{w}\right)}$$

$${M}={\left({u}_{{n}},…{u}_{{m}}\right)}$$

$${H}={\left({z}_{{n}},…{z}_{{m}}\right)}$$

where

• ${M}$ is an array of upward messages (Definition 147), ${u}$, interpreted by the relay chain itself.

• ${H}$ is an array of outbound horizontal messages (Definition 149), ${z}$, interpreted by other parachains.

• ${R}$ is an Option type (Definition 200) which can contain a parachain Runtime update. The new Runtime code is an array of bytes.

• ${h}$ is the head data (Definition 143) produced as a result of execution of the parachain specific logic.

• ${P}$ is the PoV block (Definition 142).

• ${p}$ is an unsigned 32-bit integer indicating the number of processed downward messages (Definition 148).

• ${w}$ is an unsigned 32-bit integer indicating the mark up to which all inbound HRMP messages have been processed by the parachain.

8.2. Candidate Backing

The Polkadot validator receives an arbitrary number of parachain candidates with associated proofs from untrusted collators. The assigned validators of each parachain (Definition 146) must verify and select a specific quantity of the proposed candidates and issue those as backable candidates to their peers. A candidate is considered backable when at least 2/3 of all assigned validators have issued a Valid statement about that candidate, as described in Section 8.2.1.. Validators can retrieve information about assignments via the Runtime APIs Section C.9.2. respectively Section C.9.3..

8.2.1. Statements

The assigned validator checks the validity of the proposed parachains blocks (Section 8.3.) and issues Valid statements (Definition 112) to its peers if the verification succeeded. Broadcasting failed verification as Valid statements is a slashable offense. The validator must only issue one Seconded statement based on an arbitrary metric, which implies an explicit vote for a candidate to be included in the relay chain.

This protocol attempts to produce as many backable candidates as possible but does not attempt to determine a final candidate for inclusion. Once a parachain candidate has been seconded by at least one other validator, and enough Valid statements have been issued about that candidate to meet the 2/3 quorum, the candidate is ready to be included in the relay chain (Section 8.2.2.).

The validator issues validity statements votes in form of a validator protocol message (Definition 124).

Definition 112. Statement

A statement, ${S}$, is a data structure of the following format:

$${S}={\left({d},{A}_{{i}},{A}_{{s}}\right)}$$

$${d}={\left\lbrace\begin{matrix}{1}&\rightarrow&{C}_{{r}}\\{2}&\rightarrow&{C}_{{h}}\end{matrix}\right.}$$

where

• ${d}$ is a varying datatype where 1 indicates that the validator “seconds” a candidate, meaning that the candidate should be included in the relay chain, followed by the committed candidate receipt (Definition 115), ${C}_{{r}}$. 2 indicates that the validator has deemed the candidate valid, followed by the candidate hash.

• ${C}_{{h}}$ is the candidate hash.

• ${A}_{{i}}$ is the validator index in the authority set that signed this statement.

• ${A}_{{s}}$ is the signature of the validator.

8.2.2. Inclusion

The Polkadot validator includes the backed candidates as parachain inherent data (Definition 113) into a block as described Section 2.3.3.. The relay chain block author decides on whatever metric which candidate should be selected for inclusion, as long as that candidate is valid and meets the validity quorum of 2/3+ as described in Section 8.2.1.. The candidate approval process (Section 8.5.) ensures that only relay chain blocks are finalized where each candidate for each availability core meets the requirement of 2/3+ availability votes.

Definition 113. Parachain Inherent Data

The parachain inherent data contains backed candidates and is included when authoring a relay chain block. The data structure, ${I}$, is of the following format:

$${I}={\left({A},{T},{D},{P}_{{h}}\right)}$$

$${T}={\left({C}_{{0}},…{C}_{{n}}\right)}$$

$${D}={\left({d}_{{n}},…{d}_{{m}}\right)}$$

$${C}={\left({R},{V},{i}\right)}$$

$${V}={\left({a}_{{n}},…{a}_{{m}}\right)}$$

$${a}={\left\lbrace\begin{matrix}{1}&\rightarrow&{s}\\{2}&\rightarrow&{s}\end{matrix}\right.}$$

$${A}={\left({L}_{{n}},…{L}_{{m}}\right)}$$

$${L}={\left({b},{v}_{{i}},{s}\right)}$$

where

• ${A}$ is an array of signed bitfields by validators claiming the candidate is available (or not). The array must be sorted by validator index corresponding to the authority set (Definition 33).

• ${T}$ is an array of backed candidates for including in the current block.

• ${D}$ is an array of disputes.

• ${P}_{{h}}$ is the parachain parent head data (Definition 143).

• ${d}$ is a dispute statement (Section 8.7.2.1.).

• ${R}$ is a committed candidate receipt (Definition 115).

• ${V}$ is an array of validity votes themselves, expressed as signatures.

• ${i}$ is a bitfield of indices of the validators within the validator group (Definition 146).

• ${a}$ is either an implicit or explicit attestation of the validity of a parachain candidate, where 1 implies an implicit vote (in correspondence of a Seconded statement) and 2 implies an explicit attestation (in correspondence of a Valid statement). Both variants are followed by the signature of the validator.

• ${s}$ is the signature of the validator.

• ${b}$ the availability bitfield (Section 8.4.1.).

• ${v}_{{i}}$ is the validator index of the authority set (Definition 33).

Definition 114. Candidate Receipt

A candidate receipt, ${R}$, contains information about the candidate and a proof of the results of its execution. It’s a data structure of the following format:

$${R}={\left({D},{C}_{{h}}\right)}$$

where ${D}$ is the candidate descriptor (Definition 116) and ${C}_{{h}}$ is the hash of candidate commitments (Definition 117).

Definition 115. Committed Candidate Receipt

The committed candidate receipt, ${R}$, contains information about the candidate and the result of its execution that is included in the relay chain. This type is similar to the candidate receipt (Definition 114), but actually contains the execution results rather than just a hash of it. It’s a data structure of the following format:

$${R}={\left({D},{C}\right)}$$

where ${D}$ is the candidate descriptor (Definition 116) and ${C}$ is the candidate commitments (Definition 117).

Definition 116. Candidate Descriptor

The candidate descriptor, ${D}$, is a unique descriptor of a candidate receipt. It’s a data structure of the following format:

$${D}={\left({p},{H},{C}_{{i}},{V},{B},{r},{s},{p}_{{h}},{R}_{{h}}\right)}$$

where

• ${p}$ is the parachain Id (Definition 144).

• ${H}$ is the hash of the relay chain block the candidate is executed in the context of.

• ${C}_{{i}}$ is the collators public key.

• ${V}$ is the hash of the persisted validation data (Definition 240).

• ${B}$ is the hash of the PoV block.

• ${r}$ is the root of the block’s erasure encoding Merkle tree.

• ${s}$ the collator signature of the concatenated components ${p}$, ${H}$, ${R}_{{h}}$ and ${B}$.

• ${p}_{{h}}$ is the hash of the parachain head data (Definition 143) of this candidate.

• ${R}_{{h}}$ is the hash of the parachain Runtime.

Definition 117. Candidate Commitments

The candidate commitments, ${C}$, is the result of the execution and validation of a parachain (or parathread) candidate whose produced values must be committed to the relay chain. Those values are retrieved from the validation result (Definition 119). A candidate commitment is a datastructure of the following format:

$${C}={\left({M}_{{u}},{M}_{{h}},{R},{h},{p},{w}\right)}$$

where

• ${M}_{{u}}$ is an array of upward messages sent by the parachain. Each individual message, m, is an array of bytes.

• ${M}_{{h}}$ is an array of individual outbound horizontal messages (Definition 149) sent by the parachain.

• ${R}$ is an Option value (Definition 200) that can contain a new parachain Runtime in case of an update.

• ${h}$ is the parachain head data (Definition 143).

• ${p}$ is an unsigned 32-bit integer indicating the number of downward messages that were processed by the parachain. It is expected that the parachain processes the messages from first to last.

• ${w}$ is an unsigned 32-bit integer indicating the watermark, which specifies the relay chain block number up to which all inbound horizontal messages have been processed.

8.3. Candidate Validation

Received candidates submitted by collators and must have their validity verified by the assigned Polkadot validators. For each candidate to be valid, the validator must successfully verify the following conditions in the following order:

1. The candidate does not exceed any parameters in the persisted validation data (Definition 240).

2. The signature of the collator is valid.

3. Validate the candidate by executing the parachain Runtime (Section 8.3.1.).

If all steps are valid, the Polkadot validator must create the necessary candidate commitments (Definition 117) and submit the appropriate statement for each candidate (Section 8.2.1.).

8.3.1. Parachain Runtime

Parachain Runtimes are stored in the relay chain state, and can either be fetched by the parachain Id or the Runtime hash via the relay chain Runtime API as described in Section C.9.8. and Section C.9.9. respectively. The retrieved parachain Runtime might need to be decompressed based on the magic identifier as described in Section 8.3.2..

In order to validate a parachain block, the Polkadot validator must prepare the validation parameters (Definition 118), then use its local Wasm execution environment (Section 2.6.3.) to execute the validate_block parachain Runtime API by passing on the validation parameters as an argument. The parachain Runtime function returns the validation result (Definition 119).

Definition 118. Validation Parameters

The validation parameters structure, ${P}$, is required to validate a candidate against a parachain Runtime. It’s a data structure of the following format:

$${P}={\left({h},{b},{B}_{{i}},{S}_{{r}}\right)}$$

where

• ${h}$ is the parachain head data (Definition 143).

• ${b}$ is the block body (Definition 142).

• ${B}_{{i}}$ is the latest relay chain block number.

• ${S}_{{r}}$ is the relay chain block storage root (Section 2.4.4.).

Definition 119. Validation Result

The validation result is returned by the validate_block parachain Runtime API after attempting to validate a parachain block. Those results are then used in candidate commitments (Definition 117), which then will be inserted into the relay chain via the parachain inherent data (Definition 113). The validation result, ${V}$, is a data structure of the following format:

$${V}={\left({h},{R},{M}_{{u}},{M}_{{h}},{p}_{,}{w}\right)}$$

$${M}_{{u}}={\left({m}_{{0}},…{m}_{{n}}\right)}$$

$${M}_{{h}}={\left({t}_{{0}},…{t}_{{n}}\right)}$$

where

• ${h}$ is the parachain head data (Definition 143).

• ${R}$ is an Option value (Definition 200) that can contain a new parachain Runtime in case of an update.

• ${M}_{{u}}$ is an array of upward messages sent by the parachain. Each individual message, m, is an array of bytes.

• ${M}_{{h}}$ is an array of individual outbound horizontal messages (Definition 149) sent by the parachain.

• ${p}$ is an unsigned 32-bit integer indicating the number of downward messages that were processed by the parachain. It is expected that the parachain processes the messages from first to last.

• ${w}$ is an unsigned 32-bit integer indicating the watermark, which specifies the relay chain block number up to which all inbound horizontal messages have been processed.

8.3.2. Runtime Compression

	Runtime compression is not documented yet.

8.4. Availability

8.4.1. Availability Votes

The Polkadot validator must issue a bitfield (Definition 151) which indicates votes for the availability of candidates. Issued bitfields can be used by the validator and other peers to determine which backed candidates meet the 2/3+ availability quorum.

Candidates are inserted into the relay chain in the form of parachain inherent data (Section 8.2.2.) by a block author. A validator can retrieve that data by calling the appropriate Runtime API entry (Section C.9.3.), then create a bitfield indicating for which candidate the validator has availability data stored and broadcast it to the network (Definition 128). When sending the bitfield distribution message, the validator must ensure ${B}_{{h}}$ is set appropriately, therefore clarifying to which state the bitfield is referring to, given that candidates can vary based on the chain fork.

Missing availability data of candidates must be recovered by the validator as described in Section 8.4.2.. If previously issued bitfields are no longer accurate, i.e., the availability data has been recovered or the candidate of an availability core has changed, the validator must create a new bitfield and broadcast it to the network. Candidates must be kept available by validators for a specific amount of time. If a candidate does not receive any backing, validators should keep it available for about one hour, in case the state of backing does change. Backed and even approved candidates (Section 8.5.) must be kept by validators for about 25 hours since disputes (Section 8.6.) can occur and the candidate needs to be checked again.

The validator issues availability votes in form of a validator protocol message (Definition 125).

8.4.2. Candidate Recovery

The availability distribution of the Polkadot validator must be able to recover parachain candidates that the validator is assigned to, in order to determine whether the candidate should be backed (Section 8.2.) respectively whether the candidate should be approved (Section 8.5.). Additionally, peers can send availability requests as defined in Definition 132 and Definition 134 to the validator, which the validator should be able to respond to.

Candidates are recovered by sending requests for specific indices of erasure encoded chunks (Section A.4.1.). A validator should request chunks by picking peers randomly and must recover at least ${f}+{1}$ chunks, where ${n}={3}{f}+{k}$ and ${k}\in{\left\lbrace{1},{2},{3}\right\rbrace}$. ${n}$ is the number of validators as specified in the session info, which can be fetched by the Runtime API as described in Section C.9.13..

8.5. Approval Voting

The approval voting process ensures that only valid parachain blocks are finalized on the relay chain. After backable parachain candidates were submitted to the relay chain (Section 8.2.2.), which can be retrieved via the Runtime API (Section C.9.3.), validators need to determine their assignments for each parachain and issue approvals for valid candidates, respectively disputes for invalid candidates. Since it cannot be expected that each validator verifies every single parachain candidate, this mechanism ensures that enough honest validators are selected to verify parachain candidates in order to prevent the finalization of invalid blocks. If an honest validator detects an invalid block that was approved by one or more validators, the honest validator must issue a dispute which will cause escalations, resulting in consequences for all malicious parties, i.e., slashing. This mechanism is described more in Section 8.5.1..

8.5.1. Assignment Criteria

Validators determine their assignment based on a VRF mechanism, similar to the BABE consensus mechanism. First, validators generate an availability core VRF assignment (Definition 121), which indicates which availability core a validator is assigned to. Then a delayed availability core VRF assignment is generated, which indicates at what point a validator should start the approval process. The delays are based on “tranches” (Section 8.5.2.).

An assigned validator never broadcasts their assignment until relevant. Once the assigned validator is ready to check a candidate, the validator broadcasts their assignment by issuing an approval distribution message (Definition 129), where ${M}$ is of variant 0. Other assigned validators that receive that network message must keep track of if, expecting an approval vote following shortly after. Assigned validators can retrieve the candidate by using the availability recovery (Section 8.4.2.) and then validate the candidate (Section 8.3.).

The validator issues approval votes in form of a validator protocol message (Definition 124) respectively disputes (Section 8.6.).

8.5.2. Tranches

Validators use a subjective, tick-based system to determine when the approval process should start. A validator starts the tick-based system when a new availability core candidate have been proposed, which can be retrieved via the Runtime API (Section C.9.3.), and increments the tick every 500 milliseconds. Each tick/increment is referred to as a “tranche”, represented as an integer, starting at 0.

As described in Section 8.5.1., the validator first executes the VRF mechanism to determine which parachains (availability cores) the validator is assigned to, then an additional VRF mechanism for each assigned parachain to determine the delayed assignment. The delayed assignment indicates the tranche at which the validator should start the approval process. A tranche of value 0 implies that the assignment should be started immediately, while later assignees of later tranches wait until it’s their term to issue assignments, determined by their subjective, tick-based system.

Validators are required to track broadcasted assignments by other validators assigned to the same parachain, including verifying the VRF output. Once a valid assignment from a peer was received, the validator must wait for the following approval vote within a certain period as described in Section C.9.13. by orienting itself on its local, tick-based system. If the waiting time after a broadcasted assignment exceeds the specified period, the validator interprets this behavior as a “no-show”, indicating that more validators should commit on their tranche until enough approval votes have been collected.

If enough approval votes have been collected as described in Section C.9.13., then assignees of later tranches do not have to start the approval process. Therefore, this tranche system serves as a mechanism to ensure that enough candidate approvals from a random set of validators are created without requiring all assigned validators to check the candidate.

Definition 120. Relay VRF Story

The relay VRF story is an array of random bytes derived from the VRF submitted within the block by the block author. The relay VRF story, T, is used as input to determine approval voting criteria and generated in the following way:

$${T}=\text{Transcript}{\left({b}_{{r}},{b}_{{s}},{e}_{{i}},{A}\right)}$$

where

• $\text{Transcript}$ constructs a VRF transcript (Definition 185).

• ${b}_{{r}}$ is the BABE randomness of the current epoch (Definition 76).

• ${b}_{{s}}$ is the current BABE slot (Definition 59).

• ${e}_{{i}}$ is the current BABE epoch index (Definition 59).

• ${A}$ is the public key of the authority.

Definition 121. Availability Core VRF Assignment

An availability core VRF assignment is computed by a relay chain validator to determine which availability core (Definition 145) a validator is assigned to and should vote for approvals. Computing this assignment relies on the VRF mechanism, transcripts, and STROBE operations described further in Section A.1.3..

The Runtime dictates how many assignments should be conducted by a validator, as specified in the session index, which can be retrieved via the Runtime API (Section C.9.13.). The amount of assignments is referred to as “samples.” For each iteration of the number of samples, the validator calculates an individual assignment, ${T}$, where the little-endian encoded sample number, ${s}$, is incremented by one. At the beginning of the iteration, ${S}$ starts at value 0.

The validator executes the following steps to retrieve a (possibly valid) core index:

$${t}_{{1}}\leftarrow\text{Transcript}{\left(\text{'A\&V MOD'}\right)}$$

$${t}_{{2}}\leftarrow\text{append}{\left({t}_{{1}},\text{'RC-VRF'},{R}_{{s}}\right)}$$

$${t}_{{3}}\leftarrow\text{append}{\left({t}_{{2}},\text{'sample'},{s}\right)}$$

$${t}_{{4}}\leftarrow\text{append}{\left({t}_{{3}},\text{'vrf-nm-pk'},{p}_{{k}}\right)}$$

$${t}_{{5}}\leftarrow\text{meta-ad}{\left({t}_{{4}},\text{'VRFHash'},\text{False}\right)}$$

$${t}_{{6}}\leftarrow\text{meta-ad}{\left({t}_{{5}},{64}_{{\text{le}}},\text{True}\right)}$$

$${i}\leftarrow\text{prf}{\left({t}_{{6}},\text{False}\right)}$$

$${o}={s}_{{k}}\cdot{i}$$

where ${s}_{{k}}$ is the secret key, ${p}_{{k}}$ is the public key and ${64}_{{\text{le}}}$ is the integer 64 encoded as little endian. ${R}_{{s}}$ is the relay VRF story as defined in Definition 120. Following:

$${t}_{{1}}\leftarrow\text{Transcript}{\left(\text{'VRFResult'}\right)}$$

$${t}_{{2}}\leftarrow\text{append}{\left({t}_{{1}},\text{''},\text{'A\&V CORE'}\right)}$$

$${t}_{{3}}\leftarrow\text{append}{\left({t}_{{2}},\text{'vrf-in'},{i}\right)}$$

$${t}_{{4}}\leftarrow\text{append}{\left({t}_{{3}},\text{'vrf-out'},{o}\right)}$$

$${t}_{{5}}\leftarrow\text{meta-ad}{\left({t}_{{4}},\text{''},\text{False}\right)}$$

$${t}_{{6}}\leftarrow\text{meta-ad}{\left({t}_{{5}},{4}_{\text{le}},\text{True}\right)}$$

$${r}\leftarrow\text{prf}{\left({t}_{{6}},\text{False}\right)}$$

$${c}_{{i}}={r}\text{mod}{a}_{{c}}$$

where ${4}_{{\text{le}}}$ is the integer 4 encoded as little endian, ${r}$ is the 4-byte challenge interpreted as a little endian encoded interger and ${a}_{{c}}$ is the number of availability cores used during the active session, as defined in the session info retrieved by the Runtime API (Section C.9.13.). The resulting integer, ${c}_{{i}}$, indicates the parachain Id (Definition 144). If the parachain Id doesn’t exist, as can be retrieved by the Runtime API (Section C.9.3.), the validator discards that value and continues with the next iteration. If the Id does exist, the validator continues with the following steps:

$${t}_{{1}}\leftarrow\text{Transcript}{\left(\text{'A\&V ASSIGNED'}\right)}$$

$${t}_{{2}}\leftarrow\text{append}{\left({t}_{{1}},\text{'core'},{c}_{{i}}\right)}$$

$${p}\leftarrow\text{dleq\_prove}{\left({t}_{{2}},{i}\right)}$$

where $\text{dleq\_prove}$ is described in Definition 182. The resulting values of ${o}$, ${p}$ and ${s}$ are used to construct an assignment certificate (Definition 123) of kind 0.

Definition 122. Delayed Availability Core VRF Assignment

The delayed availability core VRF assignments determined at what point a validator should start the approval process as described in Section 8.5.2.. Computing this assignment relies on the VRF mechanism, transcripts, and STROBE operations described further in Section A.1.3..

The validator executes the following steps:

$${t}_{{1}}\leftarrow\text{Transcript}{\left(\text{'A\&V DELAY'}\right)}$$

$${t}_{{2}}\leftarrow\text{append}{\left({t}_{{1}},\text{'RC-VRF'},{R}_{{s}}\right)}$$

$${t}_{{3}}\leftarrow\text{append}{\left({t}_{{2}},\text{'core'},{c}_{{i}}\right)}$$

$${t}_{{4}}\leftarrow\text{append}{\left({t}_{{3}},\text{'vrf-nm-pk'},{p}_{{k}}\right)}$$

$${t}_{{5}}\leftarrow\text{meta-ad}{\left({t}_{{4}},\text{'VRFHash'},\text{False}\right)}$$

$${t}_{{6}}\leftarrow\text{meta-ad}{\left({t}_{{5}},{64}_{{\text{le}}},\text{True}\right)}$$

$${i}\leftarrow\text{prf}{\left({t}_{{6}},\text{False}\right)}$$

$${o}={s}_{{k}}\cdot{i}$$

$${p}\leftarrow\text{dleq\_prove}{\left({t}_{{6}},{i}\right)}$$

The resulting value ${p}$ is the VRF proof (Definition 181). $\text{dleq\_prove}$ is described in Definition 182.

The tranche, ${d}$, is determined as:

$${t}_{{1}}\leftarrow\text{Transcript}{\left(\text{'VRFResult'}\right)}$$

$${t}_{{2}}\leftarrow\text{append}{\left({t}_{{1}},\text{''},\text{'A\&V TRANCHE'}\right)}$$

$${t}_{{3}}\leftarrow\text{append}{\left({t}_{{2}},\text{'vrf-in'},{i}\right)}$$

$${t}_{{4}}\leftarrow\text{append}{\left({t}_{{3}},\text{'vrf-out'},{o}\right)}$$

$${t}_{{5}}\leftarrow\text{meta-ad}{\left({t}_{{4}},\text{''},\text{False}\right)}$$

$${t}_{{6}}\leftarrow\text{meta-ad}{\left({t}_{{5}},{4}_{{\text{le}}},\text{True}\right)}$$

$${c}\leftarrow\text{prf}{\left({t}_{{6}},\text{False}\right)}$$

$${d}={d}\text{mod}{\left({d}_{{c}}+{d}_{{z}}\right)}-{d}_{{z}}$$

where

• ${d}_{{c}}$ is the number of delayed tranches by total as specified by the session info, retrieved via the Runtime API (Section C.9.13.).

• ${d}_{{z}}$ is the zeroth delay tranche width as specified by the session info, retrieved via the Runtime API (Section C.9.13.).

The resulting tranche, ${n}$, cannot be less than ${0}$. If the tranche is less than ${0}$, then ${d}={0}$. The resulting values ${o}$, ${p}$ and ${c}_{{i}}$ are used to construct an assignment certificate (\<Definition 123) of kind 1.

Definition 123. Assignment Certificate

The Assignment Certificate proves to the network that a Polkadot validator is assigned to an availability core and is, therefore, qualified for the approval of candidates, as clarified in Definition 121. This certificate contains the computed VRF output and is a data structure of the following format:

$${\left({k},{o},{p}\right)}$$

$${k}={\left\lbrace\begin{matrix}{0}&\rightarrow&{s}\\{1}&\rightarrow&{c}_{{i}}\end{matrix}\right.}$$

where ${k}$ indicates the kind of the certificate, respectively the value 0 proves the availability core assignment (Definition 121), followed by the sample number ${s}$, and the value 1 proves the delayed availability core assignment (Definition 122), followed by the core index ${c}_{{i}}$ (Section C.9.3.). ${o}$ is the VRF output and ${p}$ is the VRF proof.

8.6. Disputes

info

Disputes are not documented yet.

8.7. Network Messages

The availability and validity process requires certain network messages to be exchanged between validators and collators.

8.7.1. Notification Messges

The notification messages are exchanged between validators, including messages sent by collators to validators. The protocol messages are exchanged based on a streaming notification substream (Section 4.5.). The messages are SCALE encoded (Section A.2.2.).

Definition 124. Validator Protocol Message

The validator protocol message is a varying datatype used by validators to broadcast relevant information about certain steps in the A&V process. Specifically, this includes the backing process (Section 8.2.) and the approval process (Section 8.5.). The validator protocol message, ${M}$, is a varying datatype of the following format:

$${M}={\left\lbrace\begin{matrix}{1}&\rightarrow&{M}_{{f}}\\{3}&\rightarrow&{M}_{{s}}\\{4}&\rightarrow&{M}_{{a}}\end{matrix}\right.}$$

where

• ${M}_{{f}}$ is a bitfield distribution message (Definition 128).

• ${M}_{{s}}$ is a statement distribution message (Definition 127).

• ${M}_{{a}}$ is a approval distribution message (Definition 129).

Definition 125. Collation Protocol Message

The collation protocol message, M, is a varying datatype of the following format:

$${M}={\left\lbrace\begin{matrix}{0}&\rightarrow&{M}_{{c}}\end{matrix}\right.}$$

where ${M}_{{c}}$ is the collator message (Definition 126).

Definition 126. Collator Message

The collator message is sent as part of the collator protocol message (Definition 125). The collator message, ${M}$, is a varying datatype of the following format:

$${M}={\left\lbrace\begin{matrix}{0}&\rightarrow&{\left({C}_{{i}},{P}_{{i}},{C}_{{s}}\right)}\\{1}&\rightarrow&{H}\\{4}&\rightarrow&{\left({B}_{{h}},{S}\right)}\end{matrix}\right.}$$

where

• ${M}$ is a varying datatype where 0 indicates the intent to advertise a collation and 1 indicates the advertisement of a collation to a validator. 4 indicates that a collation sent to a validator was seconded.

• ${C}_{{i}}$ is the public key of the collator.

• ${P}_{{i}}$ is the parachain Id (Definition 144).

• ${C}_{{s}}$ is the signature of the collator using the PeerId of the collators node.

• ${H}$ is the hash of the parachain block (Definition 142).

• ${S}$ is a full statement (Definition 112).

Definition 127. Statement Distribution Message

The statement distribution message is sent as part of the validator protocol message (Definition 125) indicates the validity vote of a validator for a given candidate, described further in Section 8.2.1.. The statement distribution message, ${M}$, is of varying type of the following format:

$${M}={\left\lbrace\begin{matrix}{0}&\rightarrow&{\left({B}_{{h}},{S}\right)}\\{1}&\rightarrow&{S}_{{m}}\end{matrix}\right.}$$

$${S}_{{m}}={\left({B}_{{h}},{C}_{{h}},{A}_{{i}},{A}_{{s}}\right)}$$

where

• ${M}$ is a varying datatype where 0 indicates a signed statement and 1 contains metadata about a seconded statement with a larger payload, such as a runtime upgrade. The candidate itself can be fetched via the request/response message (Definition 138).

• ${B}_{{h}}$ is the hash of the relay chain parent, indicating the state this message is for.

• ${S}$ is a full statement (Definition 112).

• ${A}_{{i}}$ is the validator index in the authority set (Definition 33) that signed this message.

• ${A}_{{s}}$ is the signature of the validator.

Definition 128. Bitfield Distribution Message

The bitfield distribution message is sent as part of the validator protocol message (Definition 124) and indicates the availability vote of a validator for a given candidate, described further in Section 8.4.1.. This message is sent in the form of a validator protocol message (Definition 124). The bitfield distribution message, ${M}$, is a datastructure of the following format:

$${M}={\left\lbrace\begin{matrix}{0}&\rightarrow&{\left({B}_{{h}},{P}\right)}\end{matrix}\right.}$$

$${P}={\left({d},{A}_{{i}},{A}_{{s}}\right)}$$

where

• ${B}_{{h}}$ is the hash of the relay chain parent, indicating the state this message is for.

• ${d}$ is the bitfield array (Definition 151).

• ${A}_{{i}}$ is the validator index in the authority set (Definition 33) that signed this message.

• ${A}_{{s}}$ is the signature of the validator.

Definition 129. Approval Distribution Message

The approval distribution message is sent as part of the validator protocol message (Definition 124) and indicates the approval vote of a validator for a given candidate, described further in Section 8.5.1.. The approval distribution message, ${M}$, is a varying datatype of the following format:

$${M}={\left\lbrace\begin{matrix}{0}&\rightarrow&{\left({\left({C}_{,}{I}_{{}}\right)}_{{0}}…{\left({C},{I}\right)}_{{n}}\right)}\\{1}&\rightarrow&{\left({V}_{{0}},…{V}_{{n}}\right)}\end{matrix}\right.}$$

$${C}={\left({B}_{{h}},{A}_{{i}},{c}_{{a}}\right)}$$

$${c}_{{a}}={\left({c}_{{k}},{P}_{{o}},{P}_{{p}}\right)}$$

$${c}_{{k}}={\left\lbrace\begin{matrix}{0}→{s}\\{1}→{i}\end{matrix}\right.}$$

$${V}={\left({B}_{{h}},{I},{A}_{{i}},{A}_{{s}}\right)}$$

where

• ${M}$ is a varying datatype where 0 indicates assignments for candidates in recent, unfinalized blocks and 1 indicates approvals for candidates in some recent, unfinalized block.

• ${C}$ is an assignment criterion that refers to the candidate under which the assignment is relevant by the block hash.

• ${I}$ is an unsigned 32-bit integer indicating the index of the candidate, corresponding to the order of the availability cores (Section C.9.3.).

• ${B}_{{h}}$ is the relay chain block hash where the candidate appears.

• ${A}_{{i}}$ is the authority set Id (Definition 78) of the validator that created this message.

• ${A}_{{s}}$ is the signature of the validator issuing this message.

• ${c}_{{a}}$ is the certification of the assignment.

• ${c}_{{k}}$ is a varying datatype where 0 indicates an assignment based on the VRF that authorized the relay chain block where the candidate was included, followed by a sample number, ${s}$. 1 indicates an assignment story based on the VRF that authorized the relay chain block where the candidate was included combined with the index of a particular core. This is described further in Section 8.5..

• ${P}_{{o}}$ is a VRF output and ${P}_{{p}}$ its corresponding proof.

8.7.2. Request & Response

The request & response network messages are sent and received between peers in the Polkadot network, including collators and non-validator nodes. Those messages are conducted on the request-response substreams (Section 4.5.). The network messages are SCALE encoded as described in Section ?.

Definition 130. PoV Fetching Request

The PoV fetching request is sent by clients who want to retrieve a PoV block from a node. The request is a data structure of the following format:

$${C}_{{h}}$$

where ${C}_{{h}}$ is the 256-bit hash of the PoV block. The response message is defined in Definition 131.

Definition 131. PoV Fetching Response

The PoV fetching response is sent by nodes to the clients who issued a PoV fetching request (Definition 130). The response, ${R}$, is a varying datatype of the following format:

$${R}={\left\lbrace\begin{matrix}{0}&\rightarrow&{B}\\{1}&\rightarrow&\phi\end{matrix}\right.}$$

where 0 is followed by the PoV block and 1 indicates that the PoV block was not found.

Definition 132. Chunk Fetching Request

The chunk fetching request is sent by clients who want to retrieve chunks of a parachain candidate. The request is a data structure of the following format:

$${\left({C}_{{h}},{i}\right)}$$

where ${C}_{{h}}$ is the 256-bit hash of the parachain candidate and ${i}$ is a 32-bit unsigned integer indicating the index of the chunk to fetch. The response message is defined in Definition 133.

Definition 133. Chunk Fetching Response

The chunk fetching response is sent by nodes to the clients who issued a chunk fetching request (Definition 132). The response, ${R}$, is a varying datatype of the following format:

$${R}={\left\lbrace\begin{matrix}{0}&\rightarrow&{C}_{{r}}\\{1}&\rightarrow&\phi\end{matrix}\right.}$$

$${C}_{{r}}={\left({c},{c}_{{p}}\right)}$$

where 0 is followed by the chunk response, ${C}_{{r}}$ and 1 indicates that the requested chunk was not found. ${C}_{{r}}$ contains the erasure-encoded chunk of data belonging to the candidate block, ${c}$, and ${c}_{{p}}$ is that chunks proof in the Merkle tree. Both ${c}$ and ${c}_{{p}}$ are byte arrays of type ${\left({b}_{{n}}…{b}_{{m}}\right)}$.

Definition 134. Available Data Request

The available data request is sent by clients who want to retrieve the PoV block of a parachain candidate. The request is a data structure of the following format:

$${C}_{{h}}$$

where ${C}_{{h}}$ is the 256-bit candidate hash to get the available data for. The response message is defined in Definition 135.

Definition 135. Available Data Response

The available data response is sent by nodes to the clients who issued an available data request (Definition 134). The response, ${R}$, is a varying datatype of the following format:

$${R}={\left\lbrace\begin{matrix}{0}&\rightarrow&{A}\\{1}&\rightarrow&\phi\end{matrix}\right.}$$

$${A}={\left({P}_{{{ov}}},{D}_{{{pv}}}\right)}$$

where 0 is followed by the available data, ${A}$, and 1 indicates the the requested candidate hash was not found. ${P}_{{{o}{v}}}$ is the PoV block (Definition 142) and ${D}_{{{p}{v}}}$ is the persisted validation data (Definition 240).

Definition 136. Collation Fetching Request

The collation fetching request is sent by clients who want to retrieve the advertised collation at the specified relay chain block. The request is a data structure of the following format:

$${\left({B}_{{h}},{P}_{{{id}}}\right)}$$

where ${B}_{{h}}$ is the hash of the relay chain block and ${P}_{{{i}{d}}}$ is the parachain Id (Definition 144). The response message is defined in Definition 137.

Definition 137. Collation Fetching Response

The collation fetching response is sent by nodes to the clients who issued a collation fetching request (Definition 136). The response, ${R}$, is a varying datatype of the following format:

$${R}={\left\lbrace\begin{matrix}{0}&\rightarrow&{\left({C}_{{r}},{B}\right)}\end{matrix}\right.}$$

where ${0}$ is followed by the candidate receipt (Definition 114), ${C}_{{r}}$, as and the PoV block (Definition 142), ${B}$. This type does not notify the client about a statement that was not found.

Definition 138. Statement Fetching Request

The statement fetching request is sent by clients who want to retrieve statements about a given candidate. The request is a data structure of the following format:

$${\left({B}_{{h}},{C}_{{h}}\right)}$$

where ${B}_{{h}}$ is the hash of the relay chain parent and ${C}_{{h}}$ is the candidate hash that was used to create a committed candidate receipt (Definition 115). The response message is defined in Definition 139.

Definition 139. Statement Fetching Response

The statement fetching response is sent by nodes to the clients who issued a collation fetching request (Definition 138). The response, ${R}$, is a varying datatype of the following format:

$${R}={\left\lbrace\begin{matrix}{0}&\rightarrow&{C}_{{r}}\end{matrix}\right.}$$

where ${C}_{{r}}$ is the committed candidate receipt (Definition 115). No response is returned if no statement is found.

8.7.2.1. Dispute Request

The dispute request is sent by clients who want to issue a dispute about a candidate. The request, ${D}_{{r}}$, is a data structure of the following format:

$${D}_{{r}}={\left({C}_{{r}},{S}_{{i}},{I}_{{v}},{V}_{{v}}\right)}$$

$${I}_{{v}}={\left({A}_{{i}},{A}_{{s}},{k}_{{i}}\right)}$$

$${V}_{{v}}={\left({A}_{{i}},{A}_{{s}},{k}_{{v}}\right)}$$

$${k}_{{i}}={\left\lbrace\begin{matrix}{0}&\rightarrow&\phi\end{matrix}\right.}$$

$${k}_{{v}}={\left\lbrace\begin{matrix}{0}&\rightarrow&\phi\\{1}&\rightarrow&{C}_{{h}}\\{2}&\rightarrow&{C}_{{h}}\\{3}&\rightarrow&\phi\end{matrix}\right.}$$

where

• ${C}_{{r}}$ is the candidate that is being disputed. The structure is a candidate receipt (Definition 114).

• ${S}_{{i}}$ is an unsigned 32-bit integer indicating the session index the candidate appears in.

• ${I}_{{v}}$ is the invalid vote that makes up the request.

• ${V}_{{v}}$ is the valid vote that makes this dispute request valid.

• ${A}_{{i}}$ is an unsigned 32-bit integer indicating the validator index in the authority set (Definition 33).

• ${A}_{{s}}$ is the signature of the validator.

• ${k}_{{i}}$ is a varying datatype and implies the dispute statement. 0 indicates an explicit statement.

• ${k}_{{v}}$ is a varying datatype and implies the dispute statement.

  • ${0}$ indicates an explicit statement.

  • ${1}$ indicates a seconded statement on a candidate, ${C}_{{h}}$, from the backing phase. ${C}_{{h}}$ is the hash of the candidate.

  • ${2}$ indicates a valid statement on a candidate, ${C}_{{h}}$, from the backing phase. ${C}_{{h}}$ is the hash of the candidate.

  • ${3}$ indicates an approval vote from the approval checking phase.

The response message is defined in Section 8.7.2.2..

8.7.2.2. Dispute Response

The dispute response is sent by nodes to the clients who issued a dispute request (Section 8.7.2.1.). The response, ${R}$, is a varying type of the following format:

$${R}={\left\lbrace\begin{matrix}{0}&\rightarrow&\phi\end{matrix}\right.}$$

where ${0}$ indicates that the dispute was successfully processed.

8.8. Definitions

Definition 140. Collator

A collator is a parachain node that sends parachain blocks, known as candidates (Definition 141), to the relay chain validators. The relay chain validators are not concerned with how the collator works or how it creates candidates.

Definition 141. Candidate

A candidate is a submitted parachain block (Definition 142) to the relay chain validators. A parachain block stops being referred to as a candidate as soon it has been finalized.

Definition 142. Parachain Block

A parachain block or a Proof-of-Validity block (PoV block) contains the necessary data for the parachain-specific state transition logic. Relay chain validators are not concerned with the inner structure of the block and treat it as a byte array.

Definition 143. Head Data

The head data contains information about a parachain block (Definition 142). The head data is returned by executing the parachain Runtime, and relay chain validators are not concerned with its inner structure and treat it as a byte array.

Definition 144. Parachain Id

The Parachain Id is a unique, unsigned 32-bit integer which serves as an identifier of a parachain, assigned by the Runtime.

Definition 145. Availability Core

Availability cores are slots used to process parachains. The Runtime assigns each parachain to an availability core, and validators can fetch information about the cores, such as parachain block candidates, by calling the appropriate Runtime API (Section C.9.3.). Validators are not concerned with the internal workings from the Runtimes perspective.

Definition 146. Validator Groups

Validator groups indicate which validators are responsible for creating backable candidates for parachains (Section 8.2.), and are assigned by the Runtime (Section C.9.2.). Validators are not concerned with the internal workings from the Runtimes perspective. Collators can use this information for submitting blocks.

Definition 147. Upward Message

An upward message is an opaque byte array sent from a parachain to a relay chain.

Definition 148. Downward Message

A downward message is an opaque byte array received by the parachain from the relay chain.

Definition 149. Outbound HRMP Message

An outbound HRMP message (Horizontal Relay-routed Message Passing) is sent from the perspective of a sender of a parachain to another parachain by passing it through the relay chain. It’s a data structure of the following format:

$${\left({I},{M}\right)}$$

where ${I}$ is the recipient Id (Definition 144) and ${M}$ is an upward message (Definition 147).

Definition 150. Inbound HRMP Message

An inbound HRMP message (Horizontal Relay-routed Message Passing) is seen from the perspective of a recipient parachain sent from another parachain by passing it through the relay chain. It’s a data structure of the following format:

$${\left({N},{M}\right)}$$

where ${N}$ is the unsigned 32-bit integer indicating the relay chain block number at which the message was passed down to the recipient parachain and ${M}$ is a downward message (Definition 148).

Definition 151. Bitfield Array

A bitfield array contains single-bit values, which indicates whether a candidate is available. The number of items is equal to the number of availability cores (Definition 145), and each bit represents a vote on the corresponding core in the given order. Respectively, if the single bit equals 1, then the Polkadot validator claims that the availability core is occupied, there exists a committed candidate receipt (Definition 115) and that the validator has a stored chunk of the parachain block (Definition 142).