6. Finality

6.1. Introduction

The Polkadot Host uses GRANDPA Finality protocol to finalize blocks. Finality is obtained by consecutive rounds of voting by the validator nodes. Validators execute GRANDPA finality process in parallel to Block Production as an independent service. In this section, we describe the different functions that GRANDPA service performs to successfully participate in the block-finalization process.

Definition 72. GRANDPA Voter

A GRANDPA Voter, ${v}$, represented by a key pair ${\left({{K}_{{v}}^{{\text{pr}}}},{v}_{{\text{id}}}\right)}$ where ${{k}_{{v}}^{{\text{pr}}}}$ represents an ed25519 private key, is a node running a GRANDPA protocol and broadcasting votes to finalize blocks in a Polkadot Host-based chain. The set of all GRANDPA voters for a given block B is indicated by ${\mathbb{{V}}}_{{B}}$. In that regard, we have [To do: change function name, only call at genesis, adjust V_B over the sections]

$${\mathbb{{V}}}={\tt{grandpa\_authorities}}{\left({B}\right)}$$

where ${\tt{grandpa\_authorities}}$ is a function entrypoint of the Runtime described in Section C.10.1.. We refer to ${\mathbb{{V}}}_{{B}}$ as ${\mathbb{{V}}}$ when there is no chance of ambiguity.

Analogously we say that a Polkadot node is a non-voter node for block ${B}$, if it does not own any of the key pairs in ${\mathbb{{V}}}_{{B}}$.

Definition 73. Authority Set Id

The authority set Id ($\text{id}_{{{\mathbb{{V}}}}}$) is an incremental counter which tracks the amount of authority list changes that occurred (Definition 86). Starting with the value of zero at genesis, the Polkadot Host increments this value by one every time a Scheduled Change or a Forced Change occurs. The authority set Id is an unsigned 64-bit integer.

Definition 74. GRANDPA State

The GRANDPA state, $\text{GS}$, is defined as:

$$\text{GS}\:={\left\lbrace{\mathbb{{V}}},\text{id}_{{{\mathbb{{V}}}}},{r}\right\rbrace}$$

where

• ${\mathbb{{V}}}$: is the set of voters.

• $\text{id}_{{{\mathbb{{V}}}}}$: is the authority set ID (Definition 73).

• ${r}$: is the voting round number.

Definition 75. GRANDPA Vote

A GRANDPA vote or simply a vote for block ${B}$ is an ordered pair defined as

$${V}{\left({B}\right)}\:={\left({H}_{{h}}{\left({B}\right)},{H}_{{i}}{\left({B}\right)}\right)}$$

where ${H}_{{h}}{\left({B}\right)}$ and ${H}_{{i}}{\left({B}\right)}$ are the block hash (Definition 12) and the block number (Definition 10).

Definition 76. Voting Rounds

Voters engage in a maximum of two sub-rounds of voting for each round ${r}$. The first sub-round is called pre-vote and the second sub-round is called pre-commit.

By ${{V}_{{v}}^{{{r},\text{pv}}}}$ and ${{V}_{{v}}^{{{r},\text{pc}}}}$ we refer to the vote cast by voter ${v}$ in round ${r}$ (for block ${B}$) during the pre-vote and the pre-commit sub-round respectively.

Voting is done by means of broadcasting voting messages (Section 4.8.6.) to the network. Validators inform their peers about the block finalized in round ${r}$ by broadcasting a commit message (Play-Grandpa-Round).

Definition 77. Vote Signature

${\text{Sign}_{{{v}_{{i}}}}^{{{r},\text{stage}}}}$ refers to the signature of a voter for a specific message in a round and is formally defined as:

$${\text{Sign}_{{{v}_{{i}}}}^{{{r},\text{stage}}}}\:=\text{Sig}_{{\text{ed25519}}}{\left(\text{msg},{r},\text{id}_{{{\mathbb{{V}}}}}\right)}$$

where

• $\text{msg}$: is a byte array containing the message to be signed (Definition 75).

• ${r}$: is an unsigned 64-bit integer is the round number.

• $\text{id}_{{{\mathbb{{V}}}}}$: is an unsigned 64-bit integer indicating the authority set Id (Definition 73).

Definition 78. Justification

The justification for block ${B}$ in round ${r}$, ${J}^{{{r},\text{stage}}}{\left({B}\right)}$, is a vector of pairs of the type:

$${\left({V}{\left({B}'\right)},{\text{Sign}_{{{v}_{{i}}}}^{{{r},\text{stage}}}}{\left({B}'\right)},{v}_{{\text{id}}}\right)}$$

in which either

${B}'\ge{B}$

or ${{V}_{{{v}_{{i}}}}^{{{r},\text{pc}}}}{\left({B}'\right)}$ is an equivocatory vote.

In all cases, ${\text{Sign}_{{{v}_{{i}}}}^{{{r},\text{stage}}}}{\left({B}'\right)}$ is the signature (Definition 77) of voter ${v}_{{\text{id}}}\in{\mathbb{{V}}}_{{B}}$ broadcasted during either the pre-vote (stage = pv) or the pre-commit (stage = pc) sub-round of round r. A valid justification must only contain up-to-one valid vote from each voter and must not contain more than two equivocatory votes from each voter.

Definition 79. Finalizing Justification

We say ${J}^{{{r},\text{pc}}}{\left({B}\right)}$ justifies the finalization of ${B}'\ge{B}$ for a non-voter node ${n}$ if the number of valid signatures in ${J}^{{{r},\text{pc}}}{\left({B}\right)}$ for ${B}'$ is greater than $\frac{{2}}{{3}}{\left|{\mathbb{{V}}}_{{B}}\right|}$.

Note that ${J}^{{{r},\text{pc}}}{\left({B}\right)}$ can only be used by a non-voter node to finalize a block. In contrast, a voter node can only be assured of the finality (Definition 90) of block ${B}$ by actively participating in the voting process. That is by invoking Play-Grandpa-Round.

The GRANDPA protocol dictates how an honest voter should vote in each sub-round, which is described by Play-Grandpa-Round. After defining what constitutes a vote in GRANDPA, we define how GRANDPA counts votes.

Definition 80. Equivocation

Voter ${v}$ equivocates if they broadcast two or more valid votes to blocks during one voting sub-round. In such a situation, we say that ${v}$ is an equivocator and any vote ${{V}_{{v}}^{{{r},\text{stage}}}}{\left({B}\right)}$ cast by ${v}$ in that sub-round is an equivocatory vote, and

$${\mathcal{{E}}}^{{{r},\text{stage}}}$$

represents the set of all equivocators voters in sub-round stage of round ${r}$. When we want to refer to the number of equivocators whose equivocation has been observed by voter ${v}$ we refer to it by:

$${{\mathcal{{E}}}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}$$

The Polkadot Host must detect equivocations committed by other validators and submit those to the Runtime as described in Section C.10.3..

A vote ${{V}_{{v}}^{{{r},\text{stage}}}}={V}{\left({B}\right)}$ is invalid if

• ${H}{\left({B}\right)}$ does not correspond to a valid block.

• ${B}$ is not an (eventual) descendant of a previously finalized block.

• ${{M}_{{v}}^{{{r},\text{stage}}}}$ does not bear a valid signature.

• $\text{id}_{{{\mathbb{{V}}}}}$ does no match the current ${\mathbb{{V}}}$.

• ${{V}_{{v}}^{{{r},\text{stage}}}}$ is an equivocatory vote.

Definition 81. Set of Observed Direct Votes

For validator ${v}$, the set of observed direct votes for Block ${B}$ in round ${r}$, formally denoted by ${\text{VD}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}{\left({B}\right)}$ is equal to the union of:

• set of valid votes ${{V}_{{{v}_{{i}}}}^{{{r},\text{stage}}}}$ cast in round ${r}$ and received by ${v}$ such that ${{V}_{{{v}_{{i}}}}^{{{r},\text{stage}}}}={V}{\left({B}\right)}$.

Definition 82. Set of Total Observed Votes

We refer to the set of total votes observed by voter ${v}$ in sub-round stage of round ${r}$ by ${{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}$.

The set of all observed votes by ${v}$ in the sub-round stage of round ${r}$ for block ${B}$, ${{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}$ is equal to all of the observed direct votes cast for block ${B}$ and all of the ${B}$’s descendants defined formally as:

$${{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}{\left({B}\right)}\:=\bigcup_{{{v}_{{i}}\in{\mathbb{{V}}},{B}<{B}'}}{\text{VD}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}{\left({B}'\right)}$$

The total number of observed votes for Block ${B}$ in round ${r}$ is defined to be the size of that set plus the total number of equivocator voters:

$${{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}{\left({B}\right)}\:={\left|{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}{\left({B}\right)}\right|}+{\left|{{\mathcal{{E}}}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}\right|}$$

Note that for genesis state we always have $\#{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{pv}}}}{\left({B}\right)}={\left|{\mathbb{{V}}}\right|}$.

Definition 83. Set of Total Potential Votes

Let ${{V}_{{\text{unobs}{\left({v}\right)}}}^{{{r},\text{stage}}}}$ be the set of voters whose vote in the given stage has not been received. We define the total number of potential votes for Block ${B}$ in round ${r}$ to be:

$$\#{{V}_{{\text{obs}{\left({v}\right)},\text{pot}}}^{{{r},\text{stage}}}}{\left({B}\right)}\:={\left|{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}{\left({B}\right)}\right|}+{\left|{{V}_{{\text{unobs}{\left({v}\right)}}}^{{{r},\text{stage}}}}\right|}+\text{Min}{\left(\frac{{1}}{{3}}{\left|{\mathbb{{V}}}\right|},{\left|{\mathbb{{V}}}\right|}-{\left|{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{stage}}}}{\left({B}\right)}\right|}-{\left|{{V}_{{\text{unobs}{\left({v}\right)}}}^{{{r},\text{stage}}}}\right|}\right)}$$

Definition 84. Current Pre-Voted Block

The current pre-voted block ${{B}_{{v}}^{{{r},\text{pv}}}}$ also know as GRANDPA GHOST is the block chosen by GRANDPA-GHOST:

$${{B}_{{v}}^{{{r},\text{pv}}}}\:=\text{GRANDPA-GHOST}{\left({r}\right)}$$

Finally, we define when a voter ${v}$ sees a round as completable, that is when they are confident that ${{B}_{{v}}^{{{r},\text{pv}}}}$ is an upper bound for what is going to be finalized in this round.

Definition 85. Completable Round

We say that round ${r}$ is completable if ${\left|{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{pc}}}}\right|}+{{\mathcal{{E}}}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{pc}}}}>\frac{{2}}{{3}}{\mathbb{{V}}}$ and for all ${B}'>{{B}_{{v}}^{{{r},\text{pv}}}}$:

$${\left|{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{pc}}}}\right|}-{{\mathcal{{E}}}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{pc}}}}-{\left|{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{pc}}}}{\left({B}'\right)}\right|}>\frac{{2}}{{3}}{\left|{\mathbb{{V}}}\right|}$$

Note that in practice we only need to check the inequality for those ${B}'>{{B}_{{v}}^{{{r},\text{pv}}}}$ where ${\left|{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},\text{pc}}}}{\left({B}'\right)}\right|}>{0}$.

Definition 86. GRANDPA Consensus Message

$\text{CM}_{{g}}$, the consensus message for GRANDPA, is of the following format:

$$\text{CM}_{{g}}={\left\lbrace\begin{matrix}{1}&{\left(\text{Auth}_{{C}},{N}_{{\text{delay}}}\right)}\\{2}&{\left({m},\text{Auth}_{{C}},{N}_{{\text{delay}}}\right)}\\{3}&\text{A}_{{i}}\\{4}&{N}_{{\text{delay}}}\\{5}&{N}_{{\text{delay}}}\end{matrix}\right.}$$

where

$N_{\text{delay}}$	is an unsigned 32-bit integer indicating how deep in the chain the announcing block must be before the change is applied.
1	Implies scheduled change: Schedule an authority set change after the given delay of ${N_{\text{delay}} := \|\text{SubChain}(B,B')\|}$ where ${B'}$ is the block where the change is applied. The earliest digest of this type in a single block will be respected, unless a force change is present, in which case the force change takes precedence.
2	Implies forced change: Schedule a forced authority set change after the given delay of ${N_{\text{delay}} := \|\text{SubChain}(B,m + B')\|}$ where ${B'}$ is the block where the change is applied. The earliest digest of this type in a block will be respected. Forced changes are explained further in Section 6.5..
3	Implies on disabled: An index to the individual authority in the current authority list (Definition 33) that should be immediately disabled until the next authority set changes. When an authority gets disabled, the node should stop performing any authority functionality from that authority, including authoring blocks and casting GRANDPA votes for finalization. Similarly, other nodes should ignore all messages from the indicated authority which pertain to their authority role.
4	Implies pause: A signal to pause the current authority set after the given delay of ${N_{\text{delay}} := \|\text{SubChain}(B,B')\|}$ where ${B'}$ is a block where the change is applied. Once applied, the authorities should stop voting.
5	Implies resume: A signal to resume the current authority set after the given delay of ${N_{\text{delay}} := \|\text{SubChain}(B,B')\|}$ where ${B'}$ is the block where the change is applied. Once applied, the authorities should resume voting.

Definition 87. BEEFY Consensus Message

danger

The BEEFY protocol is still under construction. The following part will be updated in the future and certain information will be clarified.

$\text{CM}_{{y}}$, the consensus message for BEEFY (Section 6.7.), is of the following format:

$$\text{CM}_{{y}}={\left\lbrace\begin{matrix}{1}&{\left({V}_{{B}},{V}_{{i}}\right)}\\{2}&{A}_{{i}}\\{3}&{R}\end{matrix}\right.}$$

where

1	implies that the remote authorities have changed. ${V}_{{B}}$ is the array of the new BEEFY authorities’s public keys and ${V}_{{i}}$ is the identifier of the remote validator set.
2	implies on disabled: an index to the individual authorty in ${V}_{{B}}$ that should be immediately disabled until the next authority change.
3	implies MMR root: a 32-byte array containing the MMR root.

6.2. Initiating the GRANDPA State

In order to participate coherently in the voting process, a validator must initiate its state and sync it with other active validators. In particular, considering that voting is happening in different distinct rounds where each round of voting is assigned a unique sequential round number ${r}_{{v}}$, it needs to determine and set its round counter ${r}$ equal to the voting round ${r}_{{n}}$ currently undergoing in the network. The mandated initialization procedure for the GRANDPA protocol for a joining validator is described in detail in Initiate-Grandpa.

The process of joining a new voter set is different from the one of rejoining the current voter set after a network disconnect. The details of this distinction are described further in this section.

6.2.1. Voter Set Changes

A GRANDPA voter node which is initiating GRANDPA protocol as part of joining a new authority set is required to execute Initiate-Grandpa. The algorithm mandates the initialization procedure for GRANDPA protocol.

info

The GRANDPA round number reset to 0 for every authority set change.

Voter set changes are signaled by Runtime via a consensus engine message (Section 3.3.2.). When Authorities process such messages they must not vote on any block with a higher number than the block at which the change is supposed to happen. The new authority set should reinitiate GRANDPA protocol by executing Initiate-Grandpa.

Algorithm 13. Initiate Grandpa

\begin{algorithm}
\caption{Initiate-Grandpa}
\begin{algorithmic}
    \input $r_{last}, B_{last}$
    \state \textsc{Last-Finalized-Block} $\leftarrow B_{last}$
    \state \textsc{Best-Final-Candidate}$(0) \leftarrow B_{last}$
    \state \textsc{GRANDPA-GHOST}$(0) \leftarrow B_{last}$
    \state \textsc{Last-Completed-Round}$ \leftarrow 0$
    \state $r_n \leftarrow 1$
    \state \call{Play-Grandpa-round}{$r_n$}
\end{algorithmic}
\end{algorithm}

where ${B}_{{\text{last}}}$ is the last block which has been finalized on the chain (Definition 90). ${r}_{{\text{last}}}$ is equal to the latest round the voter has observed that other voters are voting on. The voter obtains this information through various gossiped messages including those mentioned in Definition 90. ${r}_{{\text{last}}}$ is set to 0 if the GRANDPA node is initiating the GRANDPA voting process as a part of a new authority set. This is because the GRANDPA round number resets to 0 for every authority set change.

6.3. Rejoining the Same Voter Set

When a voter node rejoins the network after a disconnect from the voter set and with the condition that there has been no change to the voter set at the time of the disconnect, the node must continue performing the GRANDPA protocol at the same state as before getting disconnected from the network, ignoring any possible progress in GRANDPA finalization. Following reconnection, the node eventually gets updated to the current GRANDPA round and synchronizes its state with the rest of the voting set through the process called Catchup (Section 6.6.1.).

6.4. Voting Process in Round ${r}$

For each round ${r}$, an honest voter ${v}$ must participate in the voting process by following Play-Grandpa-Round.

Algorithm 14. Play Grandpa Round

\begin{algorithm}
\caption{Play-Grandpa-Round}
\begin{algorithmic}
    \REQUIRE($r$)
    \STATE $t_{r, v} \leftarrow$ Current local time
    \STATE $\textrm{primary} \leftarrow$ \call{Derive-Primary}{$r$}
    \IF{$v = \textrm{primary}$}
      \STATE \call{Broadcast}{$M_{v}^{r - 1, \textrm{Fin}}($\call{Best-Final-Candidate}{$r - 1$}$)$}
      \IF{\call{Best-Final-Candidate}{$r - 1$} $\geqslant$ \textsc{Last-Finalized-Block}}
        \STATE \call{Broadcast}{$M_{v}^{r - 1, \textrm{Prim}}($\call{Best-Final-Candidate}{$r - 1$}$)$}
      \ENDIF
    \ENDIF
    \STATE \call{Receive-Messages}{\textbf{until} Time $\geqslant t_{r_,v} + 2 \times T$ \or $r$ \textbf{is} completable}
    \STATE $L \leftarrow$ \call{Best-Final-Candidate}{$r - 1$}
    \STATE $N \leftarrow$ \call{Best-PreVote-Candidate}{$r$}
    \STATE \call{Broadcast}{$M_v^{r, \textrm{pv}} (N)$}
    \STATE \call{Receive-Messages}{\textbf{until} $B^{r,\textrm{pv}}_v \geqslant L$ \and $($ Time $\geqslant t_{r_,v} + 4 \times T$ \or $r$ \textbf{is} completable $)$}
    \STATE \call{Broadcast}{$M_v^{r, \textrm{pc}}(B_v^{r, \textrm{pv}})$}
    
    \REPEAT
      \STATE \call{Receive-Messages}{}
      \STATE \call{Attempt-To-Finalize-At-Round}{$r$}
    \UNTIL{$r$ \textbf{is} completable \and \call{Finalizable}{$r$} \and \textsc{Last-Finalized-Block} $\geqslant$ \call{Best-Final-Candidate}{$r - 1$}}
    
    \STATE \call{Play-Grandpa-round}{$r + 1$}
    
    \REPEAT
      \STATE \call{Receive-Messages}{}
      \STATE \call{Attempt-To-Finalize-At-Round}{$r$}
    \UNTIL{\textsc{Last-Finalized-Block} $\geqslant$ \call{Best-Final-Candidate}{$r$}}
    
    \IF{$r > $ \textsc{Last-Completed-Round}}
      \STATE \textsc{Last-Completed-Round} $\leftarrow r$
    \ENDIF
\end{algorithmic}
\end{algorithm}

where

• ${T}$ is sampled from a log-normal distribution whose mean and standard deviation are equal to the average network delay for a message to be sent and received from one validator to another.

• $\text{Derive-Primary}$ is described in Derive-Primary.

• The condition of completablitiy is defined in Definition 85.

• $\text{Best-Final-Candidate}$ function is explained in Best-Final-Candidate.

• $\text{Attempt-To-Finalize-At-Round}{\left({r}\right)}$ is described in Attempt-To-Finalize-At-Round.

• $\text{Finalizable}$ is defined in Finalizable.

Algorithm 15. Derive Primary

\begin{algorithm}
\caption{Derive-Primary}
\begin{algorithmic}
    \input $r$
    \return $r \bmod |\mathbb{V}|$
\end{algorithmic}
\end{algorithm}

where ${r}$ is the GRANDPA round whose primary is to be determined.

Algorithm 16. Best Final Candidate

\begin{algorithm}
\caption{Best-Final-Candidate}
\begin{algorithmic}
    \input $r$
    \state $B_v^{r, pv} \leftarrow$ \call{GRANDPA-GHOST}{$r$}
    \if{$r = 0$}
        \return $B_v^{r, pv}$
    \else
        \state $\mathcal{C} \leftarrow \{ B' | B' \leqslant B_v^{r,pv} | \#V^{r, pc}_{\operatorname{obv}(v), pot}(B') > \frac{2}{3} |\mathbb{V}| \}$
        \if{$\mathcal{C} = \phi$}
            \return $B_v^{r, pv}$
        \else
            \return $E \in \mathcal{C} : H_n (E) = \operatorname{max}\left(H_n (B') | B' \in \mathcal{C}\right)$
        \endif
    \endif
\end{algorithmic}
\end{algorithm}

where $\#{{V}_{{\text{obv}{\left({v}\right)},{p}{o}{t}}}^{{{r},{p}{c}}}}$ is defined in Definition 83.

Algorithm 17. GRANDPA GHOST

\begin{algorithm}
\caption{GRANDPA-GHOST}
\begin{algorithmic}
    \input $r$
    \if{$r = 0$}
        \state $G \leftarrow B_{last}$
    \else
        \state $L \leftarrow$ \call{Best-Final-Candidate}{$r - 1$}
        \state $\mathcal{G} = \{ \forall B > L | \#V_{\operatorname{obs}(v)}^{r, pv}(B) \geqslant \frac{2}{3} |\mathbb{V}| \}$
        \if{$\mathcal{G} = \phi$}
            \state $G \leftarrow L$
        \else
            \state $G \in \mathcal{G} | H_n(G) = \operatorname{max}\left( H_n (B) | \forall B \in \mathcal{G} \right)$
        \endif
    \endif
    \return $G$
\end{algorithmic}
\end{algorithm}

where

• ${B}_{{\text{last}}}$ is the last block which has been finalized on the chain (Definition 90).

• $\#{{V}_{{\text{obs}{\left({v}\right)}}}^{{{r},{p}{v}}}}{\left({B}\right)}$ is defined in Definition 82.

Algorithm 18. Best PreVote Candidate

\begin{algorithm}
\caption{Best-PreVote-Candidate}
\begin{algorithmic}
    \input $r$
    \state $B^{r, pv}_v \leftarrow$ \call{GRANDPA-GHOST}{$r$}
    \if{\call{Received}{$M_{v_{primary}}^{r, prim}(B))$ \and $B^{r, pv}_v \geqslant B > L$}}
        \state $N \leftarrow B$
    \else
        \state $N \leftarrow B^{r, pv}_v$
    \endif
\end{algorithmic}
\end{algorithm}

Algorithm 19. Attempt To Finalize At Round

\begin{algorithm}
\caption{Attempt-To-Finalize-At-Round}
\begin{algorithmic}
    \REQUIRE($r$)
    \STATE $L \leftarrow$ \textsc{Last-Finalized-Block}
    \STATE $E \leftarrow$ \call{Best-Final-Candidate}{$r$}
    \IF{$E \geqslant L$ \and ${V^{r, \textrm{pc}}_{\textrm{obs}(v)}}(E) > 2 / 3 |\mathbb{V}|$}
    \STATE{\textsc{Last-Finalized-Block}$\leftarrow E$}
    \IF{$M_v^{r, \textrm{Fin}} (E) \notin $\textsc{Received-Messages}}
        \STATE \call{Broadcast}{$M_v^{r, \textrm{Fin}}(E)$}
        \RETURN
    \ENDIF
    \ENDIF
\end{algorithmic}
\end{algorithm}

Algorithm 20. Finalizable

\begin{algorithm}
\caption{Finalizable}
\begin{algorithmic}
    \REQUIRE($r$)
    \IF{$r$ \textbf{is not} Completable}
        \RETURN \textbf{False}
    \ENDIF
    \STATE $G \leftarrow$ \call{GRANDPA-GHOST}{$J^{r, pv}(B)$}
    \IF{$G = \phi$}
        \RETURN \textbf{False}
    \ENDIF
    \STATE $E_r \leftarrow$ \call{Best-Final-Candidate}{$r$}
    \IF{$E_r \neq \phi$ \and \call{Best-Final-Candidate}{$r - 1$} $\leqslant E_r \leqslant G$}
        \RETURN \textbf{True}
    \ELSE
        \RETURN \textbf{False}
    \ENDIF
\end{algorithmic}
\end{algorithm}

where the condition for completability is defined in Definition 85.

Note that we might not always succeed in finalizing our best final candidate due to the possibility of equivocation. We might even not finalize anything in a round (although Play-Grandpa-Round prevents us from moving to the round ${r}+{1}$ before finalizing the best final candidate of round ${r}-{1}$) The example in Definition 88 serves to demonstrate a situation where the best final candidate of a round cannot be finalized during its own round:

Definition 88. Unfinalized Candidate

Let us assume that we have 100 voters and there are two blocks in the chain (${B}_{{1}}<{B}_{{2}}$). At round 1, we get 67 pre-votes for ${B}_{{2}}$ and at least one pre-vote for ${B}_{{1}}$ which means that $\text{GRANDPA-GHOST}{\left({1}\right)}={B}_{{2}}$.

Subsequently, potentially honest voters who could claim not seeing all the pre-votes for ${B}_{{2}}$ but receiving the pre-votes for ${B}_{{1}}$ would pre-commit to ${B}_{{1}}$. In this way, we receive 66 pre-commits for ${B}_{{1}}$ and 1 pre-commit for ${B}_{{2}}$. Henceforth, we finalize ${B}_{{1}}$ since we have a threshold commit (67 votes) for ${B}_{{1}}$.

At this point, though, we have ${\mathtt{\text{Best-Final-Candidate}}}{\left({r}\right)}={B}_{{2}}$ as $\#{{V}_{{\text{obs}{\left({v}\right)},\text{pot}}}^{{{r},\text{stage}}}}{\left({B}_{{2}}\right)}={67}$ and ${2}>{1}$.

However, at this point, the round is already completable as we know that we have ${\mathtt{\text{GRANDPA-GHOST}}}{\left({1}\right)}={B}_{{2}}$ as an upper limit on what we can finalize and nothing greater than ${B}_{{2}}$ can be finalized at ${r}={1}$. Therefore, the condition of Play-Grandpa-Round is satisfied and we must proceed to round 2.

Nonetheless, we must continue to attempt to finalize round 1 in the background as the condition of Attempt-To-Finalize-At-Round has not been fulfilled.

This prevents us from proceeding to round 3 until either:

• We finalize ${B}_{{2}}$ in round 2, or

• We receive an extra pre-commit vote for ${B}_{{1}}$ in round 1. This will make it impossible to finalize ${B}_{{2}}$ in round 1, no matter to whom the remaining pre-commits are going to be cast for (even with considering the possibility of 1/3 of voter equivocating) and therefore we have ${\mathtt{\text{Best-Final-Candidate}}}{\left({r}\right)}={B}_{{1}}$.

Both scenarios unblock Play-Grandpa-Round, ${\mathtt{\text{Last-Finalized-Block}}}\ge{\mathtt{\text{Best-Final-Candidate}}}{\left({r}-{1}\right)}$ albeit in different ways: the former with increasing the ${\mathtt{\text{Last-Finalized-Block}}}$ and the latter with decreasing ${\mathtt{\text{Best-Final-Candidate}}}{\left({r}-{1}\right)}$.

6.5. Forced Authority Set Changes

In a case of emergency where the Polkadot network is unable to finalize blocks, such as in an event of mass validator outage, the Polkadot governance mechanism must enact a forced change, which the Host must handle in a specific manner. Given that in such a case finality cannot be relied on, the Host must detect the forced change (Definition 86) in a (valid) block and apply it to all forks.

The ${m}\in{C}{M}_{{g}}$, which is specified by the governance mechanism, defines the starting block at which ${N}_{{\text{delay}}}$ is applied. This provides some degree of probabilistic consensus to the network with the assumption that the forced change was received by most participants and that finality can be continued.

Image 6. Applying a scheduled change

Image 7. Applying a forced change

6.6. Block Finalization

Definition 89. Justified Block Header

The Justified Block Header is provided by the consensus engine and presented to the Polkadot Host, for the block to be appended to the blockchain. It contains the following parts:

• block_header the complete block header (Definition 10) and denoted by $\text{Head}{\left({B}\right)}$.

• justification: as defined by the consensus specification indicated by $\text{Just}{\left({B}\right)}$ as defined in Definition 78.

• authority Ids: This is the list of the Ids of authorities, which have voted for the block to be stored and is formally referred to as ${A}{\left({B}\right)}$. An authority Id is 256-bit.

Definition 90. Finalized

A Polkadot relay chain node ${n}$ should consider block ${B}$ as finalized if any of the following criteria hold for ${B}'\ge{B}$:

• ${{V}_{{\text{obs}{\left({n}\right)}}}^{{{r},\text{pc}}}}{\left({B}'\right)}>\frac{{2}}{{3}}{\left|{\mathbb{{V}}}_{{{B}'}}\right|}$.

• It receives a ${{M}_{{v}}^{{{r},\text{Fin}}}}{\left({B}'\right)}$ message in which ${J}^{{r}}{\left({B}\right)}$ justifies the finalization (Definition 78).

• It receives a block data message for ${B}'$ with $\text{Just}{\left({B}'\right)}$ (Definition 89) which justifies the finalization.

for:

• Any round ${r}$ if the node ${n}$ is not a GRANDPA voter.

• Only for round ${r}$ for which the node ${n}$ has invoked Play-Grandpa-Round and round ${r}+{1}$ if ${n}$ is a GRANDPA voter and has already caught up to its peers according to the process described in Section Section 6.6.1..

Note that all Polkadot relay chain nodes are supposed to process GRANDPA commit messages regardless of their GRANDPA voter status.

6.6.1. Catching up

When a Polkadot node (re)joins the network, it requests the history of state transitions in the form of blocks, which it is missing.

Nonetheless, the process is different for a GRANDPA voter node. When a voter node joins the network, it needs to gather the justification (Definition 78) of the rounds it has missed. Through this process, they can safely join the voting process of the current round, on which the voting is taking place.

6.6.1.1. Sending the catch-up requests

When a Polkadot voter node has the same authority list as a peer voter node who is reporting a higher number for the finalized round field, it should send a catch-up request message (Definition 48) to the reporting peer. This will allow the node to to catch up to the more advanced finalized round, provided that the following criteria hold:

• The peer node is a GRANDPA voter, and:

• The last known finalized round for the Polkadot node is at least 2 rounds behind the finalized round for the peer.

6.6.1.2. Processing the catch-up requests

Only GRANDPA voter nodes are required to respond to the catch-up requests. Additionally, it is only GRANDPA voters who are supposed to send catch-up requests. As such GRANDPA voters could safely ignore the catch-up requests from non-voter nodes. When a GRANDPA voter node receives a catch-up request message, it needs to execute Process-Catchup-Request. Note: a voter node should not respond to catch-up requests for rounds that are actively being voted on, those are the rounds for which Play-Grandpa-Round is not concluded.

Algorithm 21. Process Catchup Request

\begin{algorithm}
\caption{Process-Catchup-Request}
\begin{algorithmic}
    \input $M_{i, v}^\text{Cat-q}(\text{id}_\mathbb{V}, r)$
    \if{$M_{i, v}^\text{Cat-q}(\text{id}_\mathbb{V}, r).\text{id}_\mathbb{V} \neq \text{id}_\mathbb{V}$}
        \state \textbf{error} ``Catching up on different set''
    \endif
    \if{$i \notin \mathbb{P}$}
        \state \textbf{error} ``Requesting catching up from a non-peer''
    \endif
    \if{$r >$ \textsc{Last-Completed-Round}}
        \state \textbf{error} ``Catching up on a round in the future''
    \endif
    \state \call{Send}{$i, M_{v, i}^\text{Cat-s}(\text{id}_\mathbb{V}, r)$}
\end{algorithmic}
\end{algorithm}

where

• ${{M}_{{{i},{v}}}^{{\text{Cat}-{q}}}}{\left(\text{id}_{{{\mathbb{{V}}}}},{r}\right)}$ is the catch-up message received from peer ${i}$ (Definition 48).

• $\text{id}_{{{\mathbb{{V}}}}}$ (Definition 73) is the voter set id with which the serving node is operating

• ${r}$ is the round number for which the catch-up is requested for.

• ${\mathbb{{P}}}$ is the set of immediate peers of node ${v}$.

• ${\mathtt{\text{Last-Completed-Round}}}$ is initiated in Initiate-Grandpa and gets updated by Play-Grandpa-Round.

• ${{M}_{{{v},{i}}}^{{\text{Cat}-{s}}}}{\left(\text{id}_{{{\mathbb{{V}}}}},{r}\right)}$ is the catch-up response (Definition 49).

6.6.1.3. Processing catch-up responses

A Catch-up response message contains critical information for the requester node to update their view on the active rounds which are being voted on by GRANDPA voters. As such, the requester node should verify the content of the catch-up response message and subsequently updates its view of the state of the finality of the Relay chain according to Process-Catchup-Response.

Algorithm 22. Process Catchup Response

\begin{algorithm}
\caption{Process-Catchup-Response}
\begin{algorithmic}
    \input $M_{v,i}^\text{Cat-s}(\text{id}_{\mathbb{V}}, r)$
    \state $M_{v,i}^\text{Cat-s}(\text{id}_{\mathbb{V}}, r).\text{id}_{\mathbb{V}}, r, J^{r, pv}(B), J^{r, pc}(B), H_h(B'), H_i(B') \leftarrow \text{Dec}_{SC}(M_{v, i}^{Cat-s}(\text{id}_{\mathbb{V}}, r)$
    \if{$M_{v, i}^\text{Cat-s}(\text{id}_{\mathbb{V}}, r).\text{id}_{\mathbb{V}} \neq \text{id}_{\mathbb{V}}$}
        \state \textbf{error} ``Catching up on different set''
    \endif
    \if{$r \leqslant$ \textsc{Leading-Round}}
        \state \textbf{error} ``Catching up in to the past''
    \endif
    \if{$J^{r, pv}(B)$ \textbf{is not} valid}
        \state \textbf{error} ``Invalid pre-vote justification''
    \endif
    \if{$J^{r, pc}(B)$ \textbf{is not} valid}
        \state \textbf{error} ``Invalid pre-commit justification''
    \endif
    \state $G \leftarrow$ \call{GRANDPA-GHOST}{$J^{r, pv}(B)$}
    \if{$G = \phi$}
        \state \textbf{error} ``GHOST-less Catch-up''
    \endif
    \if{$r$ \textbf{is not} completable}
        \state \textbf{error} ``Catch-up round is not completable''
    \endif
    \if{$J^{r, pc}(B)$ justifies $B'$ finalization}
        \state \textbf{error} ``Unjustified Catch-up target finalization''
    \endif
    \state \textsc{Last-Completed-Round} $\leftarrow r$
    \if{$i \in \mathbb{V}$}
        \state \call{Play-Grandpa-round}{$r + 1$}
    \endif
\end{algorithmic}
\end{algorithm}

where ${{M}_{{{v},{i}}}^{{\text{Cat}-{s}}}}{\left(\text{id}_{{{\mathbb{{V}}}}},{r}\right)}$ is the catch-up response received from node ${v}$ (Definition 49).

6.7. Bridge design (BEEFY)

caution

The BEEFY protocol is currently in early development and subject to change. The specification has not been completed yet.

The BEEFY (Bridge Effiency Enabling Finality Yielder) is a secondary protocol to GRANDPA to support efficient bridging between the Polkadot network (relay chain) and remote, segregated blockchains, such as Ethereum, which were not built with the Polkadot interchain operability in mind. The protocol allows participants of the remote network to verify finality proofs created by the Polkadot relay chain validators. In other words: clients in the Ethereum network should able to verify that the Polkadot network is at a specific state.

Storing all the information necessary to verify the state of the remote chain, such as the block headers, is too expensive. BEEFY stores the information in a space-efficient way and clients can request additional information over the protocol.

6.7.1. Preliminaries

Definition 91. Merkle Mountain Ranges

Merkle Mountain Ranges, MMR, are used as an efficient way to send block headers and signatures to light clients.

info

MMRs have not been defined yet.

Definition 92. Statement

The statement is the same piece of information which every relay chain validator is voting on. Namely, the MMR root of all the block header hashes leading up to the latest, finalized block.

Definition 93. Witness Data

Witness data contains the statement (Definition 92), an array indicating which validator of the Polkadot network voted for the statement (but not the signatures themselves) and a MMR root of the signatures. The indicators of which validator voted for the statement are just claims and provide no proofs. The network message is defined in Definition 53 and the relayer saves it on the chain of the remote network.

Definition 94. Light Client

A light client is an abstract entity in a remote network such as Ethereum. It can be a node or a smart contract with the intent of requesting finality proofs from the Polkadot network. A light client reads the witness data (Definition 93 from the chain, then requests the signatures directly from the relayer in order to verify those.

The light client is expected to know who the validators are and has access to their public keys.

Definition 95. Relayer

A relayer (or "prover") is an abstract entity which takes finality proofs from the Polkadot network and makes those available to the light clients. Inherently, the relayer tries to convince the light clients that the finality proofs have been voted for by the Polkadot relay chain validators. The relayer operates offchain and can for example be a node or a collection of nodes.

6.7.2. Voting on Statements

The Polkadot Host signs a statement (Definition 92) and gossips it as part of a vote (Definition 51) to its peers on every new, finalized block. The Polkadot Host uses ECDSA for signing the statement, since Ethereum has better compatibility for it compared to SR25519 or ED25519.

6.7.3. Committing Witnesses

The relayer (Definition 95) participates in the Polkadot network by collecting the gossiped votes (Definition 51). Those votes are converted into the witness data structure (Definition 93). The relayer saves the data on the chain of the remote network. The occurrence of saving witnesses on remote networks is undefined.

6.7.4. Requesting Signed Commitments

A light client (Definition 94) fetches the witness data (Definition 93) from the chain. Once the light client knows which validators apparently voted for the specified statement, it needs to request the signatures from the relayer to verify whether the claims are actually true. This is achieved by requesting signed commitments (Definition 52).

How those signed commitments are requested by the light client and delivered by the relayer varies among networks or implementations. On Ethereum, for example, the light client can request the signed commitments in form of a transaction, which results in a response in form of a transaction.