c01-extrinsics.tex

\newpage
\chapter{Extrinsics}

\section{Introduction}

An extrinsic is a SCALE encoded array consisting of a version number,
signature, and varying data types indicating the resulting Runtime function to
be called, including the parameters required for that function to be executed.
\newline

\section{Preliminaries}

\begin{definition}
    An extrinsic , $tx$, is a tuple consisting of the extrinsic version,
    $T_v$ (Definition \ref{defn-extrinsic-version}), and the body of the extrinsic, $T_b$.

    \[
        tx := (T_v, T_b)
    \]

    The value of $T_b$ varies for each version. The current version 4 is
    described in section \ref{sect-version-four}.
\end{definition}

\begin{definition}
    \label{defn-extrinsic-version}
    $T_v$ is a 8-bit bitfield and defines the extrinsic version. The required
    format of an extrinsic body, $T_b$, is dictated by the Runtime. Older or
    unsupported version are rejected.
    \newline

    The first bit of $T_v$ indicates whether the transaction is \textbf{signed}
    ($1$) or \textbf{unsigned} ($0$). The remaining 7-bits represent the version
    number. As an example, for extrinsic format version 4, an signed extrinsic
    represents $T_v$ as \verb|132| while a unsigned extrinsic represents it as
    \verb|4|.
\end{definition}

\section{Extrinsics Body}

\subsection{Version 4}
\label{sect-version-four}

Version 4 of the Polkadot extrinsic format is defined as follows:

\[
    T_b := (A_i, Sig, E, M_i, F_i(m))
\]

where each values represents:
\begin{itemize}
    \item $A_i$: the 32-byte address of the sender (Definition \ref{defn-extrinsic-address}).
    \item $Sig$: the signature of the sender (Definition \ref{defn-extrinsic-signature}).
    \item $E$: the extra data for the extrinsic (Definition \ref{defn-extra-data}).
    \item $M_i$: the indicator of the Polkadot module (Definition \ref{defn-module-indicator}).
    \item $F_i(m)$: the indicator of the function of the Polkadot module (Definition \ref{defn-function-indicator}).
\end{itemize}

\begin{definition}
    \label{defn-extrinsic-address}
    Account Id, $A_i$, is the 32-byte address of the sender of the extrinsic as
    described in the
    \href{https://github.com/paritytech/substrate/wiki/External-Address-Format-(SS58)}{external
    SS58 address format}.
\end{definition}

\begin{definition}
    \label{defn-extrinsic-signature}
    The signature, $Sig$, is a varying data type indicating the used signature
    type, followed by the signature created by the extrinsic author. The
    following types are supported:

    \[
        Sig :=
        \begin{cases}
        0, & \text{Ed25519, followed by: } (b_0, ...,b_{63}) \\
        1, & \text{Sr25519, followed by: } (b_0, ...,b_{63}) \\
        2, & \text{Ecdsa, followed by: } (b_0, ...,b_{64})
        \end{cases}
    \]

    Signature types vary in sizes, but each individual type is always fixed-size
    and therefore does not contain a length prefix. \verb|Ed25519| and
    \verb|Sr25519| signatures are 512-bit while \verb|Ecdsa| is 520-bit, where
    the last 8 bits are the recovery ID.
    \newline

    The signature is created by signing payload $P$.

    \begin{equation}
        \begin{aligned}
        P &:= \begin{cases}
            Raw, & \text{if } |Raw| \leq 256\\
            Blake2(Raw), & \text{if } |Raw| > 256\\
        \end{cases}\\
        Raw &:= (M_i, F_i(m), E, R_v, F_v, H_h(G), H_h(B))\\
        \end{aligned}
    \end{equation}

    where each value represents:
    \begin{itemize}
        \item $M_i$: the module indicator (Definition \ref{defn-module-indicator}).
        \item $F_i(m)$: the function indicator of the module
        (Definition \ref{defn-function-indicator}).
        \item $E$: the extra data (Definition \ref{defn-extra-data}).
        \item $R_v$: a UINT32 containing the specification version of \verb|14|.
        \item $F_v$: a UINT32 containing the format version of \verb|2|.
        \item $H_h(G)$: a 32-byte array containing the genesis hash.
        \item $H_h(B)$: a 32-byte array containing the hash of the block which
        starts the mortality period, as described in Definition
        \ref{defn-extrinsic-mortality}.
    \end{itemize}
\end{definition}

\begin{definition}
    \label{defn-extra-data}
    Extra data, $E$, is a tuple containing additional meta data about the
    extrinsic and the system it is meant to be executed in.

    \[
        E := (T_{mor}, N, P_t)
    \]

    where each value represents:
    \begin{itemize}
        \item $T_{mor}$: contains the SCALE encoded mortality of the extrinsic (Definition
        \ref{defn-extrinsic-mortality}).
        \item $N$: a compact integer containing the nonce of the sender. The
        nonce must be incremented by one for each extrinsic created, otherwise
        the Polkadot network will reject the extrinsic.
        \item $P_t$: a compact integer containing the transactor pay including tip.
    \end{itemize}

\end{definition}

\begin{definition}
    \label{defn-extrinsic-mortality}
    Extrinsic \textbf{mortality} is a mechanism which ensures that an extrinsic
    is only valid within a certain period of the ongoing Polkadot lifetime.
    Extrinsics can also be immortal, as clarified in Section
    \ref{sect-mortality-encoding}.
    \newline

    The mortality mechanism works with two related values:

    \begin{itemize}
        \item $M_{per}$: the period of validity in terms of block numbers from
        the block hash specified as $H_h(B)$ in the payload (Definition
        \ref{defn-extrinsic-signature}). The requirement is $M_{per} \geq 4$ and
        $M_{per}$ must be the power of two, such as \verb|32|, \verb|64|,
        \verb|128|, etc.
        \item $M_{pha}$: the phase in the period that this extrinsic's lifetime
        begins. This value is calculated with a formula and validators can use
        this value in order to determine which block hash is included in the
        payload. The requirement is $M_{pha} < M_{per}$.
    \end{itemize}

    In order to tie a transaction's lifetime to a certain block ($H_i(B)$) after
    it was issued, without wasting precious space for block hashes, block
    numbers are divided into regular periods and the lifetime is instead
    expressed as a "phase" ($M_{pha}$) from these regular boundaries:

    \[
        M_{pha} = H_i(B)\ mod\ M_{per}
    \]

    $M_{per}$ and $M_{pha}$ are then included in the extrinsic, as clarified in
    Definition \ref{defn-extra-data}, in the SCALE encoded form of $T_{mor}$ (Sect.
    \ref{sect-mortality-encoding}). Polkadot validators can use $M_{pha}$
    to figure out the block hash included in the payload, which will therefore
    result in a valid signature if the extrinsic is within the specified period 
    or an invalid signature if the extrinsic "died".

    \subsubsection*{Example}

    The extrinsic author choses $M_{per} = 256$ at block \verb|10'000|,
    resulting with $M_{pha} = 16$. The extrinsic is then valid for blocks
    ranging from \verb|10'000| to \verb|10'256|.

    \subsubsection*{Encoding}\label{sect-mortality-encoding}

    $T_{mor}$ refers to the SCALE encoded form of type $M_{per}$ and $M_{pha}$.
    $T_{mor}$ is the size of two bytes if the extrinsic is considered mortal,
    or simply one bytes with the value equal to zero if the extrinsic is
    considered immortal.

    \[
        T_{mor} := Enc_{SC}(M_{per}, M_{pha})
    \]

    The SCALE encoded representation of mortality $T_{mor}$ deviates from most
    other types, as it's specialized to be the smallest possible value, as
    described in Algorithm \ref{algo-encode-mortality} and
    \ref{algo-decode-mortality}.

    \begin{algorithm}[H]
        \caption[]{\sc Encode Mortality}
        \label{algo-encode-mortality}
        \begin{algorithmic}[1]
            \Require{$M_{per}, M_{pha}$}
            \Statex // If the extrinsic is immortal, specify
            \Statex // a single byte with the value equal to zero.
            \State $\vcenter{
                \begin{flalign*}
                    \Return & 
                    \begin{cases}
                    0 & if\ extrinsic\ is\ immortal 
                    \end{cases}&
                \end{flalign*}
            }$
            \State \textbf{Init} $factor = \textsc{Limit}(M_{per} >> 12,\ 1,\ \phi)$
            \State \textbf{Init} $left = \textsc{Limit}(\textsc{TZ}(M_{per})-1,\ 1,\ 15)$
            \State \textbf{Init} $right = \frac{M_{pha}}{factor} << 4$
            \Statex
            \Statex // Returns a two byte value
            \State \Return $left|right$
        \end{algorithmic}
    \end{algorithm}

    \begin{algorithm}[H]
        \caption[]{\sc Decode Mortality}
        \label{algo-decode-mortality}
        \begin{algorithmic}[1]
            \Require{$T_{mor}$}
            \State $\vcenter{
                \begin{flalign*}
                    \Return & 
                    \begin{cases}
                    \textit{Immortal} & if\ T^{b0}_{mor} = 0
                    \end{cases}&
                \end{flalign*}
            }$
            \Statex 
            \State \textbf{Init} $enc = T^{b0}_{mor} + (T^{b1}_{mor} << 8)$
            \State \textbf{Init} $M_{per} = 2 << (enc\ mod\ (1 << 4))$
            \State \textbf{Init} $factor = \textsc{Limit}(M_{per} >> 12,\ 1,\ \phi)$
            \State \textbf{Init} $M_{pha} = (enc >> 4) * factor$
            \State \Return $(M_{per}, M_{pha})$
        \end{algorithmic}
    \end{algorithm}

    \begin{itemize}
        \item $T^{b0}_{mor}$: the first byte of $T_{mor}$.
        \item $T^{b1}_{mor}$: the second byte of $T_{mor}$.
        \item {\sc Limit($num$, $min$, $max$)}: Ensures that $num$ is between
        $min$ and $max$. If $min$ or $max$ is defined as $\phi$, then there is
        no requirement for the specified minimum/maximum.
        \item {\sc TZ($num$)}: returns the number of trailing zeros in the
        binary representation of $num$. For example, the binary
        representation of \verb|40| is \verb|0010 1000|, which has three
        trailing zeros.
        \item $>>$: performs a binary right shift operation.
        \item $<<$: performs a binary left shift operation.
        \item $|$ : performs a bitwise OR operation.
    \end{itemize}
\end{definition}

\begin{definition}
    \label{defn-module-indicator}
    $M_i$ is an indicator for the Runtime to which Polkadot \textit{module},
    $m$, the extrinsic should be forwarded to.
    \newline

    $M_i$ is a varying data type pointing to every module exposed to the
    network.

    \[
    M_i :=
    \begin{cases}
    0, & \text{System} \\
    1, & \text{Utility} \\
    ... & \\
    7, & \text{Balances} \\
    ... &
    \end{cases}
    \]
\end{definition}

\begin{definition}
    \label{defn-function-indicator}
    $F_i(m)$ is a tuple which contains an indicator, $m_i$, for the Runtime to
    which \textit{function} within the Polkadot \textit{module}, $m$, the
    extrinsic should be forwarded to. This indicator is followed by the
    concatenated and SCALE encoded parameters of the corresponding function,
    $params$.

    \[
        F_i(m) := (m_i, params)
    \]

    The value of $m_i$ varies for each Polkadot module, since every module
    offers different functions. As an example, the \verb|Balances| module has
    the following functions:

    \[
        Balances_i :=
        \begin{cases}
        0, & \text{transfer} \\
        1, & \text{set\_balance} \\
        2 & \text{force\_transfer} \\
        3 & \text{transfer\_keep\_alive} \\
        \end{cases}
    \]
\end{definition}