| title |
|---|
-chap-num- Block Production |
import Pseudocode from '@site/src/components/Pseudocode'; import blockProductionLottery from '!!raw-loader!@site/src/algorithms/blockProductionLottery.tex'; import slotTime from '!!raw-loader!@site/src/algorithms/slotTime.tex'; import medianAlgorithm from '!!raw-loader!@site/src/algorithms/medianAlgorithm.tex'; import invokeBlockAuthoring from '!!raw-loader!@site/src/algorithms/invokeBlockAuthoring.tex'; import verifyAuthorshipRight from '!!raw-loader!@site/src/algorithms/verifyAuthorshipRight.tex'; import verifySlotWinner from '!!raw-loader!@site/src/algorithms/verifySlotWinner.tex'; import buildBlock from '!!raw-loader!@site/src/algorithms/buildBlock.tex';
The Polkadot Host uses BABE protocol for block production. It is designed based on Ouroboros praos . BABE execution happens in sequential non-overlapping phases known as an epoch. Each epoch on its turn is divided into a predefined number of slots. All slots in each epoch are sequentially indexed starting from 0. At the beginning of each epoch, the BABE node needs to run Block-Production-Lottery to find out in which slots it should produce a block and gossip to the other block producers. In turn, the block producer node should keep a copy of the block tree and grow it as it receives valid blocks from other block producers. A block producer prunes the tree in parallel by eliminating branches that do not include the most recent finalized blocks (Definition -def-num-ref-).
A block producer, noted by
Block authoring session key pair ${\left({s}{{k}{{j}}^{{s}}},{p}{{k}{{j}}^{{s}}}\right)}$ is an SR25519 key pair which the block producer
::::definition
A block production epoch, formally referred to as
:::info Substrate refers to an epoch as "session" in some places, however, epoch should be the preferred and official name for these periods. | :::
::::
:::definition
We refer to the number of slots in epoch ${\mathcal{{E}}}{{n}}$ by ${s}{c}{{n}}$. ${s}{c}{{n}}$ is set to the duration field in the returned data from the call of the Runtime entry BabeApi_configuration (Section -sec-num-ref-) at genesis. For a given block ${B}$, we use the notation **${s}{{B}}$** to refer to the slot during which
Definition -def-num-ref- provides an iterator over the blocks produced during a specific epoch.
:::
:::definition
By ${\text{SubChain}{\left({\mathcal{{E}}}{{n}}\right)}}$ for epoch ${\mathcal{{E}}}{{n}}$, we refer to the path graph of
:::
:::definition
A block producer equivocates if they produce more than one block at the same slot. The proof of equivocation are the given distinct headers that were signed by the validator and which include the slot number.
The Polkadot Host must detect equivocations committed by other validators and submit those to the Runtime as described in Section -sec-num-ref-.
:::
:::definition
$$ \text{CM}{{b}}={\left\lbrace\begin{matrix}{1}&{\left(\text{Auth}{{C}},{r}\right)}\{2}&{A}_{{i}}\{3}&{D}\end{matrix}\right.} $$
where
| 1 | implies next epoch data: The Runtime issues this message on every first block of an epoch. The supplied authority set Definition -def-num-ref-, |
| 2 | implies on disabled: A 32-bit integer, |
| 3 | implies next epoch descriptor: These messages are only issued on configuration change and in the first block of an epoch. The supplied configuration data are intended to be used from the next epoch onwards. |
-
$D$ is a varying datatype of the following format: $$ D = {1, (c,2_{\text{nd}})} $$ where${c}$ is the probability that a slot will not be empty Definition -def-num-ref-. It is encoded as a tuple of two unsigned 64-bit integers${c_{nominator},c_{denominator}}$ which are used to compute the rational${c = \frac{c_{nominator}}{c_{denominator}}}$ . -
${2_{\text{nd}}}$ describes what secondary slot Definition -def-num-ref-, if any, is to be used. It is encoded as one-byte varying datatype: $$ s_{\text{2nd}} = \begin{cases} 0 \rightarrow \text{no secondary slot} \ 1 \rightarrow \text{plain secondary slot} \ 2 \rightarrow \text{secondary slot with VRF output} \end{cases} $$
:::
The babe constant (Definition -def-num-ref-) is initialized at genesis to the value returned by calling BabeApi_configuration (Section -sec-num-ref-). For efficiency reasons, it is generally updated by the Runtime through the next config data consensus message in the digest (Definition -def-num-ref-) of the first block of an epoch for the next epoch.
A block producer aiming to produce a block during
In order to ensure consistent block production, BABE uses secondary slots in case no authority won the (primary) block production lottery. Unlike the lottery, secondary slot assignees are know upfront publically (Definition -def-num-ref-). The Runtime provides information on how or if secondary slots are executed (Section -sec-num-ref-), explained further in Definition -def-num-ref-.
:::definition
The BABE constant is the probability that a slot will not be empty and used in the winning threshold calculation (Definition -def-num-ref-). It’s expressed as a rational,
:::
:::definition
The Winning threshold denoted by ${T}{{{\mathcal{{E}}}{{n}}}}$ is the threshold that is used alongside the result of Block-Production-Lottery to decide if a block producer is the winner of a specific slot. ${T}{{{\mathcal{{E}}}{{n}}}}$ is calculated as follows:
$$ {A}{{w}}={\sum{{{n}={1}}}^{{{\left|\text{Auth}{{C}}{\left({B}\right)}\right|}}}}{\left({w}{{A}}\in\text{Auth}{{C}}{\left({B}\right)}{{n}}\right)} $$ $$ {T}{{{\mathcal{{E}}}{{n}}}}:={1}-{\left({1}-{c}\right)}^{{\frac{{w}{{a}}}{{A}{{w}}}}} $$
where ${A}{{w}}$ is the total sum of all authority weights in the authority set (Definition -def-num-ref-) for epoch ${\mathcal{{E}}}{{n}}$,
The numbers should be treated as 64-bit rational numbers.
:::
A block producer aiming to produce a block during
:::algorithm <Pseudocode content={blockProductionLottery} algID="blockProductionLottery" options={{ "lineNumber": true }} />
where
:::info The secondary slots (Definition -def-num-ref-) are running along side the primary block production lottery and mainly serve as a fallback to in case no authority was selected in the primary lottery. :::
:::definition
Secondary slots work along side primary slot to ensure consistent block production, as described in Section -sec-num-ref-. The secondary assignee of a block is determined by calculating a specific value, ${i}{{d}}$, which indicates the index in the authority set (Definition -def-num-ref-). The corresponding authority in that set has the right to author a secondary block. This calculation is done for every slot in the epoch, ${s}\in{s}{c}{{n}}$ (Definition -def-num-ref-).
$$ {p}\leftarrow{h}{\left(\text{Enc}{\text{SC}}{\left({r},{s}\right)}\right)} $$ $$ {i}{{d}}\leftarrow{p}\text{mod}{A}_{{l}} $$
where
-
${r}$ is the Epoch randomness (Definition -def-num-ref-). -
${s}$ is the slot number (Definition -def-num-ref-). -
$\text{Enc}_{\text{SC}}{\left(\ldots\right)}$ encodes its inner value to the corresponding SCALE value. -
${h}{\left(\ldots\right)}$ creates a 256-bit Blake2 hash from its inner value. -
${A}_{{l}}$ is the lengths of the authority list (Definition -def-num-ref-).
If
:::
:::definition
The BABE block production lottery requires a specific transcript structure (Definition -def-num-ref-). That structure is used by both primary slots (Block-Production-Lottery) and secondary slots (Definition -def-num-ref-).
$$ {t}{{1}}\leftarrow\text{Transcript}{\left(\text{'BABE'}\right)} $$ $$ {t}{{2}}\leftarrow\text{append}{\left({t}{{1}},\text{'slot number'},{s}\right)} $$ $$ {t}{{3}}\leftarrow\text{append}{\left({t}{{2}},\text{'current epoch'},{e}{{i}}\right)} $$ $$ {t}{{4}}\leftarrow\text{append}{\left({t}{{3}},\text{'chain randomness'},{r}\right)} $$ $$ {t}{{5}}\leftarrow\text{append}{\left({t}{{4}},\text{'vrf-nm-pk'},{p}{{k}}\right)} $$ $$ {t}{{6}}\leftarrow\text{meta-ad}{\left({t}{{5}},\text{'VRFHash'},\text{False}\right)} $$ $$ {t}{{7}}\leftarrow\text{meta-ad}{\left({t}{{6}},{64}{\text{le}},\text{True}\right)} $$ $$ {h}\leftarrow\text{prf}{\left({t}{{7}},\text{False}\right)} $$ $$ {o}={s}{{k}}\cdot{h} $$ $$ {p}\leftarrow\text{dleq_prove}{\left({t}_{{7}},{h}\right)} $$
The operators are defined in Definition -def-num-ref-,
:::
It is imperative for the security of the network that each block producer correctly determines the current slot numbers at a given time by regularly estimating the local clock offset in relation to the network (Definition -def-num-ref-).
:::danger
The calculation described in this section is still to be implemented and deployed: For now, each block producer is required to synchronize its local clock using NTP instead. The current slot
Polkadot does this synchronization without relying on any external clock source (e.g. through the or the ). To stay in synchronization, each producer is therefore required to periodically estimate its local clock offset in relation to the rest of the network.
This estimation depends on the two fixed parameters
All validators are then required to run Median-Algorithm at the beginning of each sync period (Definition -def-num-ref-) to update their synchronization using all block arrival times of the previous period. The algorithm should only be run once all the blocks in this period have been finalized, even if only probabilistically (Definition -def-num-ref-). The target slot to which to synchronize should be the first slot in the new sync period.
:::definition
Let ${s}{{i}}$ and ${s}{{j}}$ be two slots belonging to epochs ${\mathcal{{E}}}{{k}}$ and ${\mathcal{{E}}}{{l}}$. By Slot-Offset${\left({s}{{i}},{s}{{j}}\right)}$ we refer to the function whose value is equal to the number of slots between ${s}{{i}}$ and ${s}{{j}}$ (counting ${s}{{j}}$) on the time continuum. As such, we have Slot-Offset${\left({s}{{i}},{s}_{{i}}\right)}={0}$. :::
It is imperative for the security of the network that each block producer correctly determines the current slot numbers at a given time by regularly estimating the local clock offset in relation to the network (Definition -def-num-ref-).
:::definition
The relative time synchronization is a tuple of a slot number and a local clock timestamp ${\left({s}{\text{sync}},{t}{\text{sync}}\right)}$ describing the last point at which the slot numbers have been synchronized with the local clock.
:::
:::algorithm <Pseudocode content={slotTime} algID="slotTime" options={{ "lineNumber": true }} />
where
:::algorithm <Pseudocode content={medianAlgorithm} algID="medianAlgorithm" options={{ "lineNumber": true }} />
where
-
${\mathfrak{{{E}}}}$ is the sync period used for the estimate. -
${s}_{\text{sync}}$ is the slot time to estimate. -
$\text{Slot-Offset}$ is defined in Slot-Time. -
${\mathcal{{{T}}}}$ is the slot duration defined in Definition -def-num-ref-.
:::
:::definition
The pruned best chain
:::
:::definition
The chain quality ${s}{{{c}{q}}}$ represents the number of slots that are used to estimate the local clock offset. Currently, it is set to ${s}{{{c}{q}}}={3000}$.
The prerequisite for such a calculation is that each producer stores the arrival time of each block (Definition -def-num-ref-) measured by a clock that is otherwise not adjusted by any external protocol.
:::
:::definition
The block arrival time of block
:::
:::definition
A is an interval at which each validator (re-)evaluates its local clock offsets. The first sync period ${\mathfrak{{E}}}{{1}}$ starts just after the genesis block is released. Consequently, each sync period ${\mathfrak{{E}}}{{i}}$ starts after ${\mathfrak{{E}}}{{{i}-{1}}}$. The length of the sync period (Definition -def-num-ref-) is equal to ${s}{{{q}{c}}}$and expressed in the number of slots.
:::
Image -img-num- An exemplary result of Median Algorithm in first sync epoch with ${s}_{\text{cq}}={9}$ and ${k}={1}$ . {#img-median-algorithm}
Throughout each epoch, each block producer should run Invoke-Block-Authoring to produce blocks during the slots it has been awarded during that epoch. The produced block needs to carry the Pre-Digest (Definition -def-num-ref-) as well as the block signature (Definition -def-num-ref-) as Pre-Runtime and Seal digest items.
:::definition
The Pre-Digest, or BABE header,
$$ {P}={\left\lbrace\begin{matrix}{1}&\rightarrow&{\left({a}{\text{id}},{s},{o},{p}\right)}\{2}&\rightarrow&{\left({a}{\text{id}},{s}\right)}\{3}&\rightarrow&{\left({a}_{\text{id}},{s},{o},{p}\right)}\end{matrix}\right.} $$
where
-
1 indicates a primary slot with VRF outputs, 2 a secondary slot with plain outputs and 3 a secondary slot with VRF outputs (Section -sec-num-ref-). Plain outputs are no longer actively used and only exist for backwards compatibility reasons, respectively to sync old blocks.
-
${a}_{\text{id}}$ is the unsigned 32-bit integer indicating the index of the authority in the authority set (Section -sec-num-ref-) who authored the block. -
${s}$ is the slot number (Definition -def-num-ref-). -
${o}$ is VRF output (Block-Production-Lottery respectively Definition -def-num-ref-). -
${p}$ is VRF proof (Block-Production-Lottery respectively Definition -def-num-ref-).
The Pre-Digest must be included as a digest item of Pre-Runtime type in the header digest (Definition -def-num-ref-)
:::algorithm <Pseudocode content={invokeBlockAuthoring} algID="invokeBlockAuthoring" options={{ "lineNumber": true }} />
where
:::definition
The Block Signature
$$ \text{Sig}{{\text{SR25519},{\text{sk}{{j}}^{{s}}}}}{\left({H}_{{h}}{\left({B}\right)}\right)} $$
in which,
:::
At the beginning of each epoch, ${\mathcal{{E}}}{{n}}$ the host will receive the randomness seed ${\mathcal{{R}}}{{{\mathcal{{E}}}{{{n}+{1}}}}}$ (Definition -def-num-ref-) necessary to participate in the block production lottery in the next epoch ${\mathcal{{E}}}{{{n}+{1}}}$ from the Runtime, through the consensus message (Definition -def-num-ref-) in the digest of the first block.
:::definition
For epoch
:::
When a Polkadot node receives a produced block, it needs to verify if the block producer was entitled to produce the block in the given slot by running Verify-Authorship-Right. Verify-Slot-Winner runs as part of the verification process, when a node is importing a block.
:::algorithm <Pseudocode content={verifyAuthorshipRight} algID="verifyAuthorshipRight" options={{ "lineNumber": true }} />
where
-
$\text{Head}_{{s}}{\left({B}\right)}$ is the header of the block that’s being verified. -
${T}_{{B}}$ is${B}$ ’s arrival time (Definition -def-num-ref-). -
${H}_{{d}}{\left({B}\right)}$ is the digest sub-component (Definition -def-num-ref-) of$\text{Head}{\left({B}\right)}$ (Definition -def-num-ref-). -
The Seal ${D}{{s}}$ is the last element in the digest array ${H}{{d}}{\left({B}\right)}$ as described in Definition -def-num-ref-.
-
$\text{Seal-Id}$ is the type index showing that a digest item (Definition -def-num-ref-) of varying type (Definition -def-num-ref-) is of type Seal. -
$\text{AuthorityDirectory}^{{{\mathcal{{E}}}{{c}}}}$ is the set of Authority ID for block producers of epoch ${\mathcal{{E}}}{{c}}$.
-
$\text{AuthorId}$ is the public session key of the block producer.
-
-
$\text{BT}$ is the pruned block tree (Definition -def-num-ref-). -
$\text{Verify-Slot-Winner}$ is defined in Verify-Slot-Winner. :::
:::algorithm <Pseudocode content={verifySlotWinner} algID="verifySlotWinner" options={{ "lineNumber": true }} />
where
-
$\text{Epoch-Randomness}$ is defined in Definition -def-num-ref-. -
${H}_{\text{BABE}}{\left({B}\right)}$ is the BABE header defined in Definition -def-num-ref-. -
${\left({o},{p}\right)}$ is the block lottery result for block${B}$ (Block-Production-Lottery), respectively the VRF output (Definition -def-num-ref-). -
$\text{Verify-VRF}$ is described in Section -sec-num-ref-. -
${T}{{{\mathcal{{E}}}{{n}}}}$ is the winning threshold as defined in Definition -def-num-ref-. :::
The block building process is triggered by Invoke-Block-Authoring of the consensus engine which in turn runs Build-Block.
:::algorithm <Pseudocode content={buildBlock} algID="buildBlock" options={{ "lineNumber": true }} />
where
-
${C}_{\text{Best}}$ is the chain head at which the block should be constructed ("parent"). -
${s}$ is the slot number. -
$\text{Head}{\left({B}\right)}$ is defined in Definition -def-num-ref-. -
$\text{Call-Runtime-Entry}$ is defined in Definition -def-num-ref-. -
$\text{Inherent-Data}$ is defined in Definition -def-num-ref-. -
$\text{End-Of-Slot}$ indicates the end of the BABE slot as defined Median-Algorithm respectively Definition -def-num-ref-. -
$\text{Next-Ready-Extrinsic}$ indicates picking an extrinsic from the extrinsics queue (Definition -def-num-ref-). -
$\text{Block-Is-Full}$ indicates that the maximum block size is being used. -
$\text{Should-Drop}$ determines based on the result${R}$ whether the extrinsic should be dropped or remain in the extrinsics queue and scheduled for the next block. The ApplyExtrinsicResult (Definition -def-num-ref-) describes this behavior in more detail. -
$\text{Drop}$ indicates removing the extrinsic from the extrinsic queue (Definition -def-num-ref-). -
$\text{Add-Seal}$ adds the seal to the block (<<>>) before sending it to peers. The seal is removed again before submitting it to the Runtime. :::