id-glossary.md

title
Glossary

$P_n$

• A path graph or a path of $n$ nodes.

${\left({b}{{0}},{b}{{1}},\ldots,{b}_{{{n}-{1}}}\right)}$

• A sequence of bytes or byte array of length $n$

${𝔹}_n$

• A set of all byte arrays of length $n$

${I}={\left({B}{{n}}…{B}{{0}}\right)}_{{{256}}}$

• A non-negative integer in base 256

${B}={\left({b}{{0}},{b}{{1}},…,{b}_{{n}}\right)}$

• The little-endian representation of a non-negative interger ${I}={\left({B}{{n}}…{B}{{0}}\right)}{{{256}}}$ such that ${b}{{i}}≔{B}_{{i}}$

${\text{Enc}}_{LE}$

• The little-endian encoding function.

$C$

• A blockchain is defined as a directed path graph.

Block

• A node of the directed path graph (blockchain) C

Genesis Block

• The unique sink of blockchain C

Head

• The source of blockchain C

$P\left(B\right)$

• The parent of block $B$

UNIX time

• The number of milliseconds that have elapsed since the Unix epoch as a 64-bit integer

$BT$

• The block tree of a blockchain

$G$

• The genesis block, the root of the block tree BT

$\text{CHAIN}(B)$

• The path graph from $G$ to $B$ in $BT$.

$Head\left(C\right)$

• The head of chain C.

$\left|C\right|$

• The length of chain $C$ as a path graph

$\text{SubChain}(B^{\prime },B)$

• The subgraph of $Chain\left(B\right)$ path graph containing both $B$ and $B^{\prime }$.

${ℂ}_B\left(BT\right)$

• The set of all subchains of $BT$ rooted at block $B$.

$ℂ,ℂ\left(BT\right)$

• ${ℂ}_G\left(BT\right)$ i.e. the set of all chains of $BT$ rooted at genesis block

$\text{Longest-Chain}\left(BT\right)$

• The longest sub path graph of $BT$ i.e. ${C}:{\left|{C}\right|}=\max_{{{C}{{i}}∈ℂ}}{\left|{C}{{i}}\right|}$

$\text{Longest-Path}\left(BT\right)$

• The longest sub path graph of $\left(P\right)BT$ with earliest block arrival time

$\text{Deepest-Leaf}\left(BT\right)$

• $\text{Head}\text{Longest-Path}(BT)$ i.e. the head of $\text{Longest-Path}\left(BT\right)$

$B>B^{\prime }$

• $B$ is a descendant of $B^{\prime }$ in the block tree

$\text{StoredValue}\left(k\right)$

• The function to retrieve the value stored under a specific key in the state storage.

State trie, trie

• The Merkle radix-16 Tree, which stores hashes of storage entries.

$\text{KeyEncode}\left(k\right)$

• The function to encode keys for labeling branches of the trie.

$𝒩$

• The set of all nodes in the Polkadot state trie.

$N$

• An individual node in the trie.

${𝒩}_b$

• A branch node of the trie which has at least one and at most 16 children

${𝒩}_l$

• A childless leaf node of the trie

${pk}_N^{Agr}$

• The aggregated prefix key of node N

${pk}_N$

• The (suffix) partial key of node N

${\text{Index}}_N$

• A function returning an integer in range of {0, . . . ,15} representing the index of a child node of node $N$ among the children of $N$

$v_N$

• Node value containing the header of node $N$, its partial key and the digest of its childern values

${Head}_N$

• The node header of trie node $N$ storing information about the node’s type and kay

$H\left(N\right)$

• The Merkle value of node $N$.

$\text{ChildrenBitmap}$

• The binary function indicates which child of a given node is present in the trie.

${sv}_N$

• The subvalue of a trie node $N$.

Child storage

• A sub storage of the state storage which has the same structure, although being stored separately

Child trie

• State trie of a child storage

Transaction Queue

• See Definition -def-num-ref-.

$H_p$

• The 32-byte Blake2b hash of the header of the parent of the block.

${H}{{i}},{H}{{i}}{\left({B}\right)}$

• Block number, the incremental integer index of the current block in the chain.

$H_r$

• The hash of the root of the Merkle trie of the state storage at a given block

$H_e$

• An auxiliary field in the block header used by Runtime to validate the integrity of the extrinsics composing the block body.

${H}{{d}}$, ${H}{{d}}{\left({B}\right)}$

• A block header used to store any chain-specific auxiliary data.

$H_h\left(B\right)$

• The hash of the header of block $B$

$Body\left(B\right)$

• The body of block $B$ consisting of a set of extrinsics

$M_v^{r,stage}$

• Vote message broadcasted by the voter v as part of the finality protocol

$M_v^{r,Fin}\left(B\right)$

• The commit message broadcasted by voter $v$ indicating that they have finalized bock $B$ in round $r$

$v$

• GRANDPA voter node, which casts votes in the finality protocol

$k_v^{pr}$

• The private key of voter $v$

$v_{id}$

• The public key of voter $v$

${𝕍}_B,𝕍$

• The set of all GRANDPA voters for at block $B$

$GS$

• GRANDPA protocol state consisting of the set of voters, the number of times voters set has changed, and the current round number.

$r$

• The voting round counter in the finality protocol

$V_B$

• A GRANDPA vote casted in favor of block B

$V_v^{r,pv}$

• A GRANDPA vote casted by voter $v$ during the pre-vote stage of round $r$

$V_v^{r,pc}$

• A GRANDPA vote casted by voter $v$ during the pre-commit stage of round $r$

$J^{r,stage}\left(B\right)$

• The justification for pre-committing or committing to block $B$ in round $r$ of finality protocol

${Sign}^{{{r},{stage}}}{\left\lbrace{v}{{i}}\right\rbrace}{\left({B}\right)}$

• The signature of voter $v$ on their vote to block B, broadcasted during the specified stage of finality round $r$

${ℰ}^{r,stage}$

• The set of all equivocator voters in sub-round ‘‘stage'' of round $r$

${ℰ}_{\left\{obs\left(v\right)\right\}}^{r,stage}$

• The set of all equivocator voters in sub-round ‘‘stage'' of round $r$ observed by voter $v$

$V{D}_{\left\{obs\left(v\right)\right\}}^{r,stage}\left(B\right)$

• The set of observed direct votes for block B in round $r$

$V_{\left\{obs\left(v\right)\right\}}^{r,stage}$

• The set of total votes observed by voter v in sub-round ‘‘stage'' of round r

$V_{\left\{obs\left(v\right)\right\}}^{r,stage}\left(B\right)$

• The set of all observed votes by $v$ in the sub-round “stage” of round $r$ (directly or indirectly) for block $B$

$B_v^{r,pv}$

• The currently pre-voted block in round $r$. The GRANDPA GHOST of round $r$

Account key, $({sk}^a,{pk}^a)$

• A key pair of types accepted by the Polkadot protocol which can be used to sign transactions

${Enc}_{SC}\left(A\right)$

• SCALE encoding of value $A$

${T}≔{\left({A}{{1}},\ldots,{A}{{n}}\right)}$

• A tuple of values $A_i$'s each of different type

Varying Data Types $𝒯={\left\lbrace{T}{{1}},…,{T}{{n}}\right\rbrace}$

• A data type representing any of varying types ${T}{{1}},…,{T}{{n}}$.

${S}≔{A}{{1}},…,{A}{{n}}$

• Sequence of values $A_i$ of the same type

${Enc}_{\left\{SC\right\}}^{Len}\left(n\right)$

• SCALE length encoding, aka. compact encoding of non-negative interger $n$ of arbitrary size.

${Enc}_{HE}\left(PK\right)$

• Hex encoding