c02-weights.tex

\chapter{Weights}

\section{Motivation}

The Polkadot network, like any other permissionless system, needs to implement a
mechanism to measure and to limit the usage in order to establish an economic
incentive structure, to prevent the network overload, and to mitigate DoS
vulnerabilities. In particular, Polkadot enforces a limited time-window for
block producers to create a block, including limitations on block size, which
can make the selection and execution of certain extrinsics too expensive and
decelerate the network.
\newline

In contrast to some other systems such as Ethereum which implement fine
measurement for each executed low-level operation by smart contracts, known as
gas metering, Polkadot takes a more relaxed approach by implementing a measuring
system where the cost of the transactions (referred to as 'extrinsics') are
determined before execution and are known as the weight system.
\newline

The Polkadot weight system introduces a mechanism for block producers to measure
the cost of running the extrinsics and determine how "heavy" it is in terms of
execution time. Within this mechanism, block producers can select a set of
extrinsics and saturate the block to its fullest potential without exceeding any
limitations (as described in section \ref{sec:limitations}). Moreover, the
weight system can be used to calculate a fee for executing each extrinsics
according to its weight (as described in section \ref{sec:fee-calculation}).
\newline

Additionally, Polkadot introduces a specified block ratio (as defined in section
\ref{sec:limitations}), ensuring that only a certain portion of the total block
size gets used for regular extrinsics. The remaining space is reserved for
critical, operational extrinsics required for the functionality by Polkadot
itself.
\newline

To begin, we introduce in Section \ref{sec:assumptions} the assumption upon
which the Polkadot transaction weight system is designed. In Section
\ref{sec:limitations}, we discuss the limitation Polkadot needs to enforce on
the block size. In Section \ref{sec:runtime-primitives}, we describe in detail
the procedure upon which the weight of any transaction should be calculated. In
Section \ref{sec:practical-examples}, we present how we apply this procedure to
compute the weight of particular runtime functions.

\section{Assumptions}\label{sec:assumptions}

In this section, we define the concept of weight and we discuss the
considerations that need to be accounted for when assigning weight to
transactions. These considerations are essential in order for the weight system
to deliver its fundamental mission, i.e. the fair distribution of network
resources and preventing a network overload. In this regard, weights serve as an
indicator on whether a block is considered full and how much space is left for
remaining, pending extrinsics. Extrinsics which require too many resources are
discarded. More formally, the weight system should:

\begin{itemize}
\item prevent the block from being filled with too many extrinsics
\item avoid extrinsics where its execution takes too long, by assigning a
transaction fee to each extrinsic proportional to their resource consumption.
\end{itemize}

These concepts are formalized in Definitions \ref{def:block-length} and
\ref{def:polkadot-block-limits}:

\begin{definition}
  \label{def:block-length}
  For a block $B$ with $Head(B)$ and $Body(B)$ the {\b block length of $B$},
  $Len(B)$, is defined as the amount of raw bytes of $B$.
\end{definition}

\begin{definition}
  \label{def:target-time-per-block}
  {\b Targeted time per block} denoted by $T(B)$ implies the amount of seconds
  that a new block should be produced by a validator. The transaction weights
  must consider $T(B)$ in order to set restrictions on time intensive
  transactions in order to saturate the block to its fullest potential until
  $T(B)$ is reached.
\end{definition}

\begin{definition}
  \label{def:block-target-time}
  Available block ration reserved for normal, noted by $R(B)$, is defined as the
  maximum weight of none-operational transactions in the Body of $B$ divided by
  $Len(B)$.
\end{definition}

\begin{definition}
  \label{def:polkadot-block-limits}
        {\b Polkadot block limits} as defined here should be respected by each
        block producer for the produced block $B$ to be deemed valid:
        
        \begin{enumerate}
         \item $Len(B) \le 5 \times 1'024 \times 1'024 = 5'242'880$ Bytes
         \item $T(B) = 6\ seconds$
         \item $R(B) \le 0.75$
        \end{enumerate}
        
\end{definition}

\begin{definition}
  \label{defn:weight-function}
  The {\b Polkadot transaction weight function} denoted by $\mathcal{W}$ as follows:

  \begin{alignat*}{2}
    \mathcal{W} &: \mathcal{E} \rightarrow \mathbb{N} \\
    \mathcal{W} &: E \mapsto w
  \end{alignat*}

  where $w$ is a non-negative integer representing the weight of the extrinsic
  $E$. We define the weight of all inherent extrinsics as defined in the
  \href{https://github.com/w3f/polkadot-spec/tree/master/host-spec}{Polkadot
  Host Specification} to be equal to 0. We extend the definition of \TWF\
  function to compute the weight of the block as sum of weight of all extrinsics
  it includes:

  \begin{alignat*}{2}
    \mathcal{W} &: \mathcal{B}\rightarrow \mathbb{N} \\
    \mathcal{W} &: B \mapsto \sum_{E\in B}(W(E))
  \end{alignat*}
  
\end{definition}

In the remainder of this section, we discuss the requirements to which the
weight function needs to comply to.

\begin{itemize}

\item Computations of function $\mathcal{W}(E)$  must be determined before
execution of that $E$.

\item Due to the limited time window, computations of $\TWF$ must be done
      quickly and consume few resources themselves.
\item $\TWF$ must be self contained and must not require I/O on the chain state.
$\TWF(E)$ must depend solely on the Runtime function representing $E$ and its
parameters.

\end{itemize}

Heuristically, "heaviness" corresponds to the execution time of an extrinsic. In
that way, the \TWF\ value for various extrinsics should be proportional to their
execution time. For example, if Extrinsic A takes three times longer to execute
than Extrinsic B, then Extrinsic A should roughly weighs 3 times of Extrinsic B.
Or:

\[
\TWF(A)~3\times \TWF(B)
\]

Nonetheless, $\TWF(E)$ can be manipulated depending on the priority of $E$ the
chain is supposed to endorse.

\subsection{Limitations}\label{sec:limitations}

In this section we discuss how applying the limitation defined in Definition
\ref{def:polkadot-block-limits} can be translated to limitation $\TWF$. In order
to be able to translate those into concrete numbers, we need to identify an
arbitrary maximum weight to which we scale all other computations. For that we
first define the block weight and then assume a maximum on it block length in
Definition \ref{def:block-weight}:

\begin{definition}
  \label{def:block-weight} We define the {\b block weight} of block $B$,
  formally denoted as  $\TWF(B)$, to be:

  \[
    \TWF(B) = \sum^{|\mathcal{E}|}_{n = 0} (W(E_n))
  \]

  We require that:

  \[
    \TWF(B) < 2'000'000'000'000
  \]
\end{definition}

The weights must fulfil the requirements as noted by the fundamentals and
limitations, and can be assigned as the author sees fit. As a simple example,
consider a maximum block weight of 1'000'000'000, an available ratio of 75\% and
a targeted transaction throughput of 500 transactions, we could assign the
(average) weight for each transaction at about 1'500'000. Block producers have
economic incentive to include as many extrinsics as possible (without exceeding
limitations) into a block before reaching the targeted block time. Weights give
indicators to block producers on which extrinsics to include in order to reach
the blocks fullest potential.

\section{Calculation of the weight function}
\label{sec:runtime-primitives}
In order to calculate weight of block $B$, $TWF(B)$, one needs to evaluate the
weight of each transaction included in the block. Each transaction causes the
execution certain Runtime functions. As such, to calculate the weight of a
transaction, those functions must be analyzed in order to determine parts of the
code which can significantly contribute to the execution time and consume
resources such as  loops, I/O operations, and data manipulation. Subsequently
the performance and execution time of each part will be evaluated based on
variety of input parameters. Based on those observations, weights are assigned
Runtime functions or parameters which contribute to long execution times.
These sub component of the code are discussed in Section
\ref{sect:primitive-types}.
\newline

The general algorithm to calculate $\TWF(E)$ is described in the Section
\ref{sect:benchmarking}.

\section{Benchmarking}\label{sect:benchmarking}
Calculating the extrinsic weight solely based on theoretical complexity of the
underlying implementation proves to be too complicated and unreliable at the
same time. Certain decisions in the source code architecture, internal
communication within the Runtime or other design choices could add enough
overhead to make the asymptotic complexity practically meaningless.
\newline

On the other hand, benchmarking an extrinsics in a black-box fashion could
(using random parameters) most centainly results in missing corner cases and
worst case senarios. Instead, we benchmark all available Runtime functions which
are invoked in the course of execution of extrinsics with a large collection of
carefully selected input parameters and use the result of the benchmarking
process to evaluate $\TWF(E)$.
\newline

In order to select useful parameters, the Runtime functions have to be analysed
to fully understand which behaviors or conditions can result in expensive
execution times, which is described closer in section
\ref{sect:primitive-types}. Not every possible benchmarking outcome can be
invoked by varying input parameters of the Runtime function. In some
circumstances, preliminary work is required before a specific benchmark can be
reliably measured, such as creating certain preexisting entries in the storage
or other changes to the environment.
\newline

The Practical Examples Section \ref{sec:practical-examples} covers the analysis
process and the implementation of preliminary work in more detail.

\subsection{Primitive Types}\label{sect:primitive-types}
The Runtime reuses components, known as "primitives", to interact with the state
storage. The execution cost of those primitives can be measured and a weight
should be applied for each occurrence within the Runtime code.
\newline

For storage, Polkadot uses three different types of storage types across its
modules, depending on the context:

\begin{itemize}
  \item \textbf{Value}: Operations on a single value. \newline\newline
  The final key-value pair is stored under the key:\newline
  \begin{verbatim}
    hash(module_prefix) + hash(storage_prefix)
  \end{verbatim}
  \item \textbf{Map}: Operations on mulitple values, datasets, where each entry
  has its corresponding, unique key. \newline\newline
  The final key-value pair is stored under the key:\newline
  \begin{verbatim}
    hash(module_prefix) + hash(storage_prefix) + hash(encode(key))
  \end{verbatim}
  \item \textbf{Double map}: Just like \textbf{Map}, but uses two keys instead
  of one. This type is also known as "child storage", where the first key is the
  "parent key" and the second key is the "child key". This is useful in order to
  scope storage entries (child keys) under a certain \verb|context| (parent
  key), which is arbitrary. Therefore, one can have separated storage entries
  based on the context.
  \newline\newline
  The final key-value pair is stored under the key:\newline
  \begin{verbatim}
    hash(module_prefix) + hash(storage_prefix)
      + hash(encode(key1)) + hash(encode(key2))
  \end{verbatim}
\end{itemize}

It depends on the functionality of the Runtime module (or its sub-processes,
rather) which storage type to use. In some cases, only a single value is
required. In others, multiple values need to be fetched or inserted from/into
the database.
\newline

Those lower level types get abstracted over in each individual Runtime module
using the \verb|decl_storage!| macro. Therefore, each module specifies its own
types that are used as input and output values. The abstractions do give
indicators on what operations must be closely observed and where potential
performance penalties and attack vectors are possible.

\subsubsection{Considerations}\label{sect:primitive-types-considerations}

The storage layout is mostly the same for every primitive type, primarily
differentiated by using special prefixes for the storage key. Big differences
arise on how the primitive types are used in the Runtime function, on whether
single values or entire datasets are being worked on. Single value operations
are generally quite cheap and its execution time does not vary depending on the
data that's being processed. However, excessive overhead can appear when I/O
operations are executed repeatedly, such as in loops. Especially, when the amount
of loop iterations can be influenced by the caller of the function or by certain
conditions in the state storage.
\newline

Maps, in contrast, have additional overhead when inserting or retrieving
datasets, which vary in sizes. Additionally, the Runtime function has to process
each item inside that list.
\newline

Indicators for performance penalties:

\begin{itemize}
  \item \textbf{Fixed iterations and datasets} - Fixed iterations and datasets
  can increase the overall cost of the Runtime functions, but the execution time
  does not vary depending on the input parameters or storage entries. A base
  Weight is appropriate in this case.
  \item \textbf{Adjustable iterations and datasets} - If the amount of
  iterations or datasets depend on the input parameters of the caller or
  specific entries in storage, then a certain weight should be applied for each
  (additional) iteration or item. The Runtime defines the maximum value for such
  cases. If it doesn't, it unconditionally has to and the Runtime module must be
  adjusted. \newline\newline
  When selecting parameters for benchmarking, the benchmarks should range from
  the minimum value to the maximum value, as described in paragraph
  \ref{para:max-value}.
  \item \textbf{Input parameters} - Input parameters that users pass on to the
  Runtime function can result in expensive operations. Depending on the data
  type, it can be appropriate to add additional weights based on certain
  properties, such as data size, assuming the data type allows varying sizes.
  The Runtime must define limits on those properties. If it doesn't, it
  unconditionally has to and the Runtime module must be adjusted.
  \newline\newline
  When selecting parameters for benchmarking, the benchmarks should range from
  the minimum values to the maximum value, as described in paragraph
  \ref{para:max-value}.
\end{itemize}

\label{para:max-value} What the maximum value should be really depends on the
functionality that the Runtime function is trying to provide. If the choice for
that value is not obvious, then it's advised to run benchmarks on a big range of
values and pick a conservative value below the \verb|targeted time per block|
limit as described in section \ref{sec:limitations}.

\subsection{Parameters}
The inputs parameters highly vary depending on the Runtime function and must
therefore be carefully selected. The benchmarks should use input parameters
which will most likely be used in regular cases, as intended by the authors, but
must also consider worst case scenarios and inputs which might decelerate or
heavily impact performance of the function. The input parameters should be
randomised in order to cause various effects in behaviors on certain values,
such as memory relocations and other outcomes that can impact performance.
\newline

It's not possible to benchmark every single value. However, one should select a
range of inputs to benchmark, spanning from the minimum value to the maximum
value which will most likely exceed the expected usage of that function. This is
described in more detail in section \ref{sect:primitive-types-considerations}.
The benchmarks should run individual executions/iterations within that range,
where the chosen parameters should give insight on the execution time. Selecting
imprecise parameters or too extreme ranges might indicate an inaccurate result
of the function as it will be used in production. Therefore, when a range of
input parameters gets benchmarked, the result of each individual parameter
should be recorded and optionally visualized, then the necessary adjustment can
be made. Generally, the worst case scenario should be assigned as the weight
value for the corresponding runtime function.
\newline

Additionally, given the distinction theoretical and practical usage, the author
reserves the right to make adjustments to the input parameters and assigned
weights according to the observed behavior of the actual, real-world network.

\subsubsection{Weight Refunds}
When assigning the final weight, the worst case scenario of each runtime
function should be used. The runtime can then additional "refund" the amount of
weights which were overestimated once the runtime function is actually executed.
\newline

The Polkadot runtime only returns weights if the difference between the assigned
weight and the actual weight calculated during execution is greater than 20\%.

\subsection{Storage I/O cost}
It is advised to benchmark the raw I/O operations of the database and assign
"base weights" for each I/O operation type, such as insertion, deletion,
querying, etc. When a runtime function is executed, the runtime can then add
those base weights of each used operation in order to calculate the final
weight.

\subsection{Environment}
The benchmarks should be executed on clean systems without interference of other
processes or software. Additionally, the benchmarks should be executed on
multiple machines with different system resources, such as CPU performance, CPU
cores, RAM and storage speed.

\section{Practical examples}\label{sec:practical-examples}

This section walks through Runtime functions available in the Polkadot Runtime
to demonstrate the analysis process as described in section
\ref{sect:primitive-types}.
\newline

In order for certain benchmarks to produce conditions where resource heavy
computation or excessive I/O can be observed, the benchmarks might require some
preliminary work on the environment, since those conditions cannot be created
with simply selected parameters. The analysis process shows indicators on how
the preliminary work should be implemented.

\subsection{Practical Example \#1: {\texttt request\_judgement}}

In Polkadot, accounts can save information about themselves on-chain, known as
the "Identity Info". This includes information such as display name, legal name,
email address and so on. Polkadot offers a set of trusted registrars, entities
elected by a Polkadot public referendum, which can verify the specified contact
addresses of the identities, such as Email, and vouch on whether the identity
actually owns those accounts. This can be achieved, for example, by sending a
challenge to the specified address and requesting a signature as a response. The
verification is done off-chain, while the final judgement is saved onchain,
directly in the corresponding Identity Info. It's also note worthy that Identity
Info can contain additional fields, set manually by the corresponding account
holder.

Information such as legal name must be verified by ID card or passport
submission.
\newline

The function \verb|request_judgement| from the \verb|identity| pallet allows
users to request judgement from a specific registrar.

\begin{verbatim}
  (func $request_judgement (param $req_index int) (param $max_fee int))
\end{verbatim}

\begin{itemize}
  \item \verb|req_index|: the index which is assigned to the registrar.
  \item \verb|max_fee|: the maximum fee the requester is willing to pay. The
  judgement fee varies for each registrar.
\end{itemize}

Studying this function reveals multiple design choices that can impact
performance, as it will be revealed by this analysis.
\newline

\subsubsection{Analysis}

First, it fetches a list of current registrars from storage and then searches
that list for the specified registrar index.

\begin{verbatim}
let registrars = <Registrars<T>>::get();
let registrar = registrars.get(reg_index as usize).and_then(Option::as_ref)
  .ok_or(Error::<T>::EmptyIndex)?;
\end{verbatim}

Then, it searches for the Identity Info from storage, based on the sender of the
transaction.

\begin{verbatim}
let mut id = <IdentityOf<T>>::get(&sender).ok_or(Error::<T>::NoIdentity)?;
\end{verbatim}

The Identity Info contains all fields that have a data in them, set by the
corresponding owner of the identity, in an ordered form. It then proceeds to
search for the specific field type that will be inserted or updated, such as
email address. If the entry can be found, the corresponding value is to the
value passed on as the function parameters (assuming the registrar is not
"stickied", which implies it cannot be changed). If the entry cannot be found,
the value is inserted into the index where a matching element can be inserted
while maintaining sorted order. This results in memory reallocation, which
increases resource consumption.

\begin{verbatim}
match id.judgements.binary_search_by_key(&reg_index, |x| x.0) {
  Ok(i) => if id.judgements[i].1.is_sticky() {
    Err(Error::<T>::StickyJudgement)?
  } else {
    id.judgements[i] = item
  },
  Err(i) => id.judgements.insert(i, item),
}
\end{verbatim}

In the end, the function deposits the specified \verb|max_fee| balance, which
can later be redeemed by the registrar. Then, an event is created to insert the
Identity Info into storage. The creation of events is lightweight, but its
execution is what will actually commit the state changes.

\begin{verbatim}
T::Currency::reserve(&sender, registrar.fee)?;
<IdentityOf<T>>::insert(&sender, id);
Self::deposit_event(RawEvent::JudgementRequested(sender, reg_index));
\end{verbatim}

\subsubsection{Considerations}

The following points must be considered:

\begin{itemize}
  \item Varying count of registrars.
  \item Varying count of preexisting accounts in storage.
  \item The specified registrar is searched for in the Identity Info. An
  identity can be judged by as many registrars as the identity owner issues
  requests for, therefore increase its footprint in the state storage.
  Additionally, if a new value gets inserted into the byte array, memory get
  reallocated. Depending on the size of the Identity Info, the execution time
  can vary.
  \item The Identity Info can contain only a few fields or many. It is
  legitimate to introduce additional weights for changes the owner/sender has
  influence over, such as the additional fields in the Identity Info.
\end{itemize}

\subsubsection{Benchmarking Framework}

The Polkadot Runtime specifies the \verb|MaxRegistrars| constant, which will
prevent the list of registrars of reaching an undesired length. This value
should have some influence on the benchmarking process.
\newline

The benchmarking implementation of for the function $request\_judgement$ can be
defined as follows:

\begin{algorithm}[H]
  \caption{Run multiple benchmark iterations for $request\_judgement$ Runtime function}
  \begin{algorithmic}
    \Ensure $\TWF$
    \BlankLine
    \State \Init collection = \{\}
    \BlankLine
    \For{$amount \leftarrow 1,MaxRegistrars$}
      \State \textsc{Generate-Registrars($amount$)}
      \State $caller \leftarrow$ \textsc{Create-Account("caller", $1$)}
      \State \textsc{Set-Balance($caller$, 100)}
      \State $time \leftarrow$ \textsc{Timer(Request-Judgement(Random($amount$), 100))}
      \State \textsc{Add-To($collection$, $time$)}
    \EndFor
    \BlankLine
    \State $\TWF \leftarrow$ \textsc{Compute-Weight($collection$)};
    \State \Return $\TWF$
  \end{algorithmic}
\end{algorithm}

\begin{itemize}
  \item \textsc{Generate-Registrars($amount$)}
  \SubItem{Creates $number$ of registrars and inserts those records into storage.}
  \item \textsc{Create-Account($name$, $index$)} \SubItem{Creates a Blake2 hash
      of the concatenated input of $name$ and $index$ representing the address
      of a account. This function only creates an address and does not conduct
      any I/O.}
  \item \textsc{Set-Balance($account$, $balance$)}
  \SubItem{Sets a initial $balance$ for the specified $account$ in the storage state.}
  \item \textsc{Timer($function$)}
  \SubItem{Measures the time from the start of the specified $function$ to its completion.}
  \item \textsc{Request-Judgement($registrar\_index$, $max\_fee$)}
  \SubItem{Calls the corresponding $request\_judgement$ Runtime function and passes on
  the required parameters.}
  \item \textsc{Random($num$)}
  \SubItem{Picks a random number between 0 and $num$. This should be used when the benchmark
  should account for unpredictable values.}
  \item \textsc{Add-To($collection$, $time$)}
  \SubItem{Adds a returned time measurement ($time$) to $collection$.}
  \item \textsc{Compute-Weight($collection$)}
  \SubItem{Computes the resulting weight based on the time measurements in the
  $collection$. The worst case scenario should be chosen (the highest value).}
\end{itemize}

\subsection{Practical Example \#2 {\texttt payout\_stakers}}\label{sec:practical-example-payout-stakers}

\subsubsection{Analysis}

The function \verb|payout_stakers| from the \verb|staking| Pallet can be called
by a single account in order to payout the reward for all nominators who back a
particular validator. The reward also covers the validator's share. This
function is interesting because it iterates over a range of nominators, which
varies, and does I/O operation for each of them.
\newline

First, this function makes few basic checks to verify if the specified era is
not higher then the current era (as it is not in the future) and is within the
allowed range also known as "history depth", as specified by the Runtime. After
that, it fetches the era payout from storage and additionally verifies whether
the specified account is indeed a validator and receives the corresponding
"Ledger". The Ledger keeps information about the stash key, controller key and
other informatin such as actively bonded balance and a list of tracked rewards.
The function only retains the entries of the history depth, and conducts a
binary search for the specified era.

\begin{verbatim}
let era_payout = <ErasValidatorReward<T>>::get(&era)
  .ok_or_else(|| Error::<T>::InvalidEraToReward)?;

let controller = Self::bonded(&validator_stash).ok_or(Error::<T>::NotStash)?;
let mut ledger = <Ledger<T>>::get(&controller).ok_or_else(|| Error::<T>::NotController)?;
\end{verbatim}

\begin{verbatim}
ledger.claimed_rewards.retain(|&x| x >= current_era.saturating_sub(history_depth));
match ledger.claimed_rewards.binary_search(&era) {
  Ok(_) => Err(Error::<T>::AlreadyClaimed)?,
  Err(pos) => ledger.claimed_rewards.insert(pos, era),
}
\end{verbatim}

The retained claimed rewards are inserted back into storage.

\begin{verbatim}
<Ledger<T>>::insert(&controller, &ledger);
\end{verbatim}

As an optimization, Runtime only fetches a list of the 64 highest staked
nominators, although this might be changed in the future. Accordingly, any lower
staked nominator gets no reward. 

\begin{verbatim}
let exposure = <ErasStakersClipped<T>>::get(&era, &ledger.stash);
\end{verbatim}

Next, the function gets the era reward points from storage.

\begin{verbatim}
let era_reward_points = <ErasRewardPoints<T>>::get(&era);
\end{verbatim}

After that, the payout is split among the validator and its nominators. The
validators receives the payment first, creating an insertion into storage and
sending a deposit event to the scheduler.

\begin{verbatim}
if let Some(imbalance) = Self::make_payout(
  &ledger.stash,
  validator_staking_payout + validator_commission_payout
) {
  Self::deposit_event(RawEvent::Reward(ledger.stash, imbalance.peek()));
}
\end{verbatim}

Then, the nominators receive their payout rewards. The functions loops over the
nominator list, conducting an insertion into storage and a creation of a deposit
event for each of the nominators.

\begin{verbatim}
for nominator in exposure.others.iter() {
  let nominator_exposure_part = Perbill::from_rational_approximation(
    nominator.value,
    exposure.total,
  );

  let nominator_reward: BalanceOf<T> = nominator_exposure_part * validator_leftover_payout;
  // We can now make nominator payout:
  if let Some(imbalance) = Self::make_payout(&nominator.who, nominator_reward) {
    Self::deposit_event(RawEvent::Reward(nominator.who.clone(), imbalance.peek()));
  }
}
\end{verbatim}

\subsubsection{Considerations}

The following points must be considered:

\begin{itemize}
  \item The Ledger contains a varying list of claimed rewards. Fetching,
  retaining and searching through it can affect execution time. The retained
  list is inserted back into storage.
  \item Looping through a list of nominators and creating I/O operations for
  each increases execution time. The Runtime fetches up to 64 nominators.
\end{itemize}

\subsubsection{Benchmarking Framework}

\begin{definition}
  \label{defn-history-depth} {\b History Depth} indicated as
  \texttt{MaxNominatorRewardedPerValidator} is a fixed constant specified by the
  Polkadot Runtime which dictates the number of Eras the Runtime will reward
  nominators and validators for.
\end{definition}

\begin{definition}
  \label{defn-max_nominator_reward_per_validator}
        {\b Maximum Nominator Rewarded Per Validator} indicated as {\texttt MaxNominatorRewardedPerValidator}, specifies the maximum
amount of the highest-staked nominators which will get a reward. Those values
should have some influence in the benchmarking process.
\end{definition}

The benchmarking implementation for the function $payout\_stakers$ can be
defined as follows:
\newline

\begin{algorithm}[H]
  \caption{Run multiple benchmark iterations for $payout\_stakers$ Runtime function}
  \begin{algorithmic}
    \Ensure $\TWF$
    \BlankLine
    \State \Init collection = \{\}
    \BlankLine
    \For{$amount \leftarrow 1,MaxNominatorRewardedPerValidator$}
      \For{$era\_depth \leftarrow 1,HistoryDepth$}
        \State $validator \leftarrow$ \textsc{Generate-Validator()}
        \State \textsc{Validate($validator$)};
        \State $nominators \leftarrow$ \textsc{Generate-Nominators($amount$)}
        \For{$nominator \in nominators$}
          \State \textsc{Nominate($validator$, $nominator$)}
        \EndFor
        \State $era\_index \leftarrow$ \textsc{Create-Rewards($validator$, $nominators$, $era\_depth$)}
        \State $time \leftarrow$ \textsc{Timer(Payout-Stakers($validator$), $era\_index$))}
        \State \textsc{Add-To($collection$, $time$)}
      \EndFor
    \EndFor
    \BlankLine
    \State $\TWF \leftarrow$ \textsc{Compute-Weight($collection$)}
    \State \Return $\TWF$
  \end{algorithmic}
\end{algorithm}

\begin{itemize}
  \item \textsc{Generate-Validator()}
  \SubItem{Creates a validators with some unbonded balances.}
  \item \textsc{Validate($validator$)}
  \SubItem{Bonds balances of $validator$ and bonds balances.}
  \item \textsc{Generate-Nominators($amount$)}
  \SubItem{Creates the $amount$ of nominators with some unbonded balances.}
  \item \textsc{Nominate($validator$, $nominator$)}
  \SubItem{Starts nomination of $nominator$ for $validator$ by bonding balances.}
  \item \textsc{Create-Rewards($validator$, $nominators$, $era\_depth$)}
  \SubItem{Starts an Era and creates pending rewards for $validator$ and $nominators$}
  \item \textsc{Timer($function$)}
  \SubItem{Measures the time from the start of the specified $function$ to its
  completion.}
  \item \textsc{Add-To($collection$, $time$)}
  \SubItem{Adds a returned time measurement ($time$) to $collection$.}
  \item \textsc{Compute-Weight($collection$)}
  \SubItem{Computes the resulting weight based on the time measurements in the
  $collection$. The worst case scenario should be chosen (the highest value).}
\end{itemize}

\subsection{Practical Example \#3: \texttt{balances}}

The $transfer$ function of the \texttt{balances} module is designed to move the specified balance by the sender to the receiver.

\subsubsection{Analysis}

The source code of this function is quite short:

\begin{verbatim}
let transactor = ensure_signed(origin)?;
let dest = T::Lookup::lookup(dest)?;
<Self as Currency<_>>::transfer(
  &transactor,
  &dest,
  value,
  ExistenceRequirement::AllowDeath
)?;
\end{verbatim}

However, one need to pay close attention to the property \verb|AllowDeath| and
to how the function treat existingand non-existing accounts differently. Two
types of behaviors are to consider:

\begin{itemize}
  \item If the transfer completely depletes the sender account balance to zero
  (or bellow the minimum "keep-alive" requirement), it removes the address and
  all associated data from storage.
  \item If recipient account has no balance, the transfer also needs to create
    the recipient account.
\end{itemize}

\subsubsection{Considerations}

Specific parameters can could have a significant impact for this specific function. In
order to trigger the two behaviors mentioned above, the following parameters are
selected:

\begin{center}
  \begin{tabular}{ l|r l l l }
    \textbf{Type} && \textbf{From} & \textbf{To} & \textbf{Description}\\
    \hline
    Account index & \verb|index| in... & 1 & 1000 & Used as a seed for account
    creation \\
    Balance & \verb|balance| in... & 2 & 1000 & Sender balance and transfer
    amount \\
  \end{tabular}
\end{center}

Executing a benchmark for each balance increment within the balance range for
each index increment within the index range will generate too many variants
($1000 \times 999$) and highly increase execution time. Therefore, this
benchmark is configured to first set the balance at value 1'000 and then to
iterate from 1 to 1'000 for the index value. Once the index value reaches 1'000,
the balance value will reset to 2 and iterate to 1'000 (see algorithm
\ref{sec:algo-benchmark-transfer} for more detail):

\begin{itemize}
  \item \verb|index|: 1, \verb|balance|: 1000
  \item \verb|index|: 2, \verb|balance|: 1000
  \item \verb|index|: 3, \verb|balance|: 1000
  \item ...
  \item \verb|index|: 1000, \verb|balance|: 1000
  \item \verb|index|: 1000, \verb|balance|: 2
  \item \verb|index|: 1000, \verb|balance|: 3
  \item \verb|index|: 1000, \verb|balance|: 4
  \item ...
\end{itemize}

The parameters itself do not influence or trigger the two worst conditions and
must be handled by the implemented benchmarking tool. The $transfer$ benchmark
is implemented as defined in algorithm \ref{sec:algo-benchmark-transfer}.

\subsubsection{Benchmarking Framework}

The benchmarking implementation for the Polkadot Runtime function $transfer$ is
defined as follows (starting with the \textsc{Main} function):
\newline

\begin{algorithm}[H]
  \label{sec:algo-benchmark-transfer}
  \caption{Run multiple benchmark iterations for $transfer$ Runtime function}
  \begin{algorithmic}
  \Ensure $collection$: a collection of time measurements of all benchmark iterations
  \BlankLine
    \Function{\textsc{Main}}{}
      \State \Init collection = \{\}
      \State \Init $balance = 1'000$
      \BlankLine
      \For{$index\gets 1,1'000$}
        \State $time \leftarrow$ \textsc{Run-Benchmark($index$, $balance$)}
        \State \textsc{Add-To($collection$, $time$)}
      \EndFor
      \BlankLine
      \State \Init $index = 1'000$
      \For{$balance \gets 2,1'000$}
        \State $time \leftarrow$ \textsc{Run-Benchmark($index$, $balance$)}
        \State \textsc{Add-To($collection$, $time$)}
      \EndFor
      \BlankLine
      \State $\TWF \leftarrow$ \textsc{Compute-Weight($collection$)}
      \State \Return $\TWF$
    \EndFunction
    \BlankLine
    \Function{\textsc{Run-Benchmark}}{$index$, $balance$}
      \State $sender \leftarrow$ \textsc{Create-Account(\textit{"caller"}, $index$)}
      \State $recipient \leftarrow$ \textsc{Create-Account(\textit{"recipient"}, $index$)}
      \State \textsc{Set-Balance($sender$, $balance$)}
      \BlankLine
      \State $time \leftarrow$\textsc{Timer(Transfer($sender$, $recipient$, $balance$))}
      \State \Return $time$
    \EndFunction
  \end{algorithmic}
\end{algorithm}

\begin{itemize}
  \item \textsc{Create-Account($name$, $index$)} \SubItem{Creates a Blake2 hash
      of the concatenated input of $name$ and $index$ representing the address
      of a account. This function only creates an address and does not conduct
      any I/O.}
  \item \textsc{Set-Balance($account$, $balance$)} \SubItem{Sets a initial
      $balance$ for the specified $account$ in the storage state.}
  \item \textsc{Transfer($sender$, $recipient$, $balance$)} \SubItem{Transfers
      the specified $balance$ from $sender$ to $recipient$ by calling the
      corresponding Runtime function. This represents the target Runtime
      function to be benchmarked.}
  \item \textsc{Add-To($collection$, $time$)} \SubItem{Adds a returned time
      measurement ($time$) to $collection$.}
  \item \textsc{Timer($function$)} \SubItem{Measures the time from the start of
      the specified $function$ to its completion.}
  \item \textsc{Compute-Weight($collection$)}
  \SubItem{Computes the resulting weight based on the time measurements in the
  $collection$. The worst case scenario should be chosen (the highest value).}
\end{itemize}

\subsection{Practical Example \#4}

The \verb|withdraw_unbonded| function of the \verb|staking| module is designed to
move any unlocked funds from the staking management system to be ready for
transfer. It contains some operations which have some I/O overhead.

\subsubsection{Analysis}

Similarly to the \verb|payout_stakers| function
(\ref{sec:practical-example-payout-stakers}), this function fetches the Ledger
which contains information about the stash, such as bonded balance and unlocking
balance (balance that will eventually be freed and can be withdrawn).

\begin{verbatim}
if let Some(current_era) = Self::current_era() {
  ledger = ledger.consolidate_unlocked(current_era)
}
\end{verbatim}

The function \verb|consolidate_unlocked| does some cleaning up on the ledger, where
it removes outdated entries from the unlocking balance (which implies that
balance is now free and is no longer awaiting unlock).

\begin{verbatim}
let mut total = self.total;
let unlocking = self.unlocking.into_iter()
  .filter(|chunk| if chunk.era > current_era {
    true
  } else {
    total = total.saturating_sub(chunk.value);
    false
  })
  .collect();
\end{verbatim}

This function does a check on wether the updated ledger has any balance left in
regards to staking, both in terms of locked, staking balance and unlocking balance.
If not amount is left, the all information related to the stash will be deleted.
This results in multiple I/O calls.

\begin{verbatim}
if ledger.unlocking.is_empty() && ledger.active.is_zero() {
  // This account must have called `unbond()` with some value that caused the active
  // portion to fall below existential deposit + will have no more unlocking chunks
  // left. We can now safely remove all staking-related information.
  Self::kill_stash(&stash, num_slashing_spans)?;
  // remove the lock.
  T::Currency::remove_lock(STAKING_ID, &stash);
  // This is worst case scenario, so we use the full weight and return None
  None
\end{verbatim}

The resulting call to \verb|Self::kill_stash()| triggers:

\begin{verbatim}
slashing::clear_stash_metadata::<T>(stash, num_slashing_spans)?;
<Bonded<T>>::remove(stash);
<Ledger<T>>::remove(&controller);
<Payee<T>>::remove(stash);
<Validators<T>>::remove(stash);
<Nominators<T>>::remove(stash);
\end{verbatim}

Alternatively, if there's some balance left, the adjusted ledger simply gets
updated back into storage.

\begin{verbatim}
// This was the consequence of a partial unbond. just update the ledger and move on.
Self::update_ledger(&controller, &ledger);
\end{verbatim}

Finally, it withdraws the unlocked balance, making it ready for transfer:

\begin{verbatim}
let value = old_total - ledger.total;
Self::deposit_event(RawEvent::Withdrawn(stash, value));
\end{verbatim}

\subsubsection*{Parameters}
The following parameters are selected:

\begin{center}
  \begin{tabular}{ l|r l l l }
    \textbf{Type} && \textbf{From} & \textbf{To} & \textbf{Description}\\
    \hline
    Account index & \verb|index| in... & 0 & 1000 & Used as a seed for account
    creation \\
  \end{tabular}
\end{center}

This benchmark does not require complex parameters. The values are used solely
for account generation.

\subsubsection{Considerations}

Two important points in the \verb|withdraw_unbonded| function must be considered.
The benchmarks should trigger both conditions

\begin{itemize}
  \item The updated ledger is inserted back into storage.
  \item If the stash gets killed, then multiple, repetitive deletion calls are
  performed in the storage.
\end{itemize}

\subsubsection{Benchmarking Framework}

The benchmarking implementation for the Polkadot Runtime function
\verb|withdraw_unbonded| is defined as follows:
\newline

\begin{algorithm}[H]
  \label{sec:algo-benchmark-transfer}
  \caption{Run multiple benchmark iterations for $withdraw_unbonded$ Runtime function}
  \begin{algorithmic}
    \Ensure $\TWF$
    \BlankLine
    \Function{\textsc{Main}}{}
      \State \Init collection = \{\}
      \BlankLine
      \For{$balance\gets 1,100$}
        \State $stash \leftarrow$ \textsc{Create-Account(\textit{"stash"}, 1)}
        \State $controller \leftarrow$ \textsc{Create-Account(\textit{"controller"}, 1)}
        \State \textsc{Set-Balance($stash$, 100)}
        \State \textsc{Set-Balance($controller$, 1)}
        \State \textsc{Bond($stash$, $controller$, $balance$)}
        \State \textsc{Pass-Era()}
        \State \textsc{UnBond($controller$, $balance$)}
        \State \textsc{Pass-Era()}
        \State $time \leftarrow$\textsc{Timer(Withdraw-Unbonded($controller$))}
        \State \textsc{Add-To($collection$, $time$)}
      \EndFor
      \BlankLine
      \State $\TWF \leftarrow$ \textsc{Compute-Weight($collection$)}
      \State \Return $\TWF$
    \EndFunction
  \end{algorithmic}
\end{algorithm}

\begin{itemize}
  \item \textsc{Create-Account($name$, $index$)} \SubItem{Creates a Blake2 hash
    of the concatenated input of $name$ and $index$ representing the address of
    a account. This function only creates an address and does not conduct any
    I/O.}
  \item \textsc{Set-Balance($account$, $balance$)} \SubItem{Sets a initial
      $balance$ for the specified $account$ in the storage state.}
  \item \textsc{Bond($stash$, $controller$, $amount$)} \SubItem{Bonds the
    specified $amount$ for the $stash$ and $controller$ pair.}
  \item \textsc{UnBond($account$, $amount$)} \SubItem{Unbonds the specified
    $amount$ for the given $account$.}
  \item \textsc{Pass-Era()}
  \SubItem{Pass one era. Forces the funtion $withdraw\_unbonded$ to update the ledger
  and eventually delete information.}
  \item \textsc{Withdraw-Unbonded($controller$)} \SubItem{Withdraws the the full
    unbonded amount of the specified $controller$ account. This represents the
    target Runtime function to be benchmarked}
  \item \textsc{Add-To($collection$, $time$)} \SubItem{Adds a returned time
    measurement ($time$) to $collection$.}
  \item \textsc{Timer($function$)} \SubItem{Measures the time from the start of
    the specified $function$ to its completion.}
  \item \textsc{Compute-Weight($collection$)}
  \SubItem{Computes the resulting weight based on the time measurements in the
  $collection$. The worst case scenario should be chosen (the highest value).}
\end{itemize}

\section{Fees}
Block producers charge a fee in order to be economically sustainable. That fee
must always be covered by the sender of the transaction. Polkadot has a flexible
mechanism to determine the minimum cost to include transactions in a block.

\subsection{Fee Calculation}\label{sec:fee-calculation}
Polkadot fees consists of three parts:

\begin{itemize}
\item Base fee: a fixed fee that is applied to every transaction and set by the
Runtime.
\item Length fee: a fee that gets multiplied by the length of the transaction,
in bytes.
\item Weight fee: a fee for each, varying Runtime function. Runtime implementers
      need to implement a conversion mechanism which determines the
      corresponding currency amount for the calculated weight.
\end{itemize}

The final fee can be summarized as:
\begin{eqnarray*}
\lefteqn{fee = base\ fee}\\
      &&{} + length\ of\ transaction\ in\ bytes \times length\ fee\\
      &&{} + weight\ to\ fee\\
\end{eqnarray*}

\subsection{Definitions in Polkadot}
The Polkadot Runtime defines the following values:
\begin{itemize}
\item Base fee: 100 uDOTs
\item Length fee: 0.1 uDOTs
\item Weight to fee conversion:
      $$
            weight\ fee = weight \times (100\ uDOTs \div (10 \times 10'000))
      $$
      A weight of 10'000 (the smallest non-zero weight) is mapped to
      $\frac{1}{10}$ of 100 uDOT.
      \newline
      This fee will never exceed the max size of an unsigned 128 bit integer.
\end{itemize}

\subsection{Fee Multiplier}
Polkadot can add a additional fee to transactions if the network becomes too
busy and starts to decelerate the system. This fee can create an incentive to
avoid the production of low priority or insignificant transactions. In contrast,
those additional fees will decrease if the network calms down and it can execute
transactions without much difficulties.
\newline

That additional fee is known as the \verb|Fee Multiplier| and its value is
defined by the Polkadot Runtime. The multiplier works by comparing the
saturation of blocks; if the previous block is less saturated than the current
block (implying an uptrend), the fee is slightly increased. Similarly, if the
previous block is more saturated than the current block (implying a downtrend),
the fee is slightly decreased.
\newline

The final fee is calculated as:
$$
      final\ fee = fee \times Fee\ Multiplier
$$

\subsubsection{Update Multiplier}
The \verb|Update Multiplier| defines how the multiplier can change. The Polkadot
Runtime internally updates the multiplier after each block according the
following formula:

\begin{eqnarray*}
diff &=& (target\ weight - previous\ block\ weight)\\
v &=& 0.00004\\
next\ weight &=& weight \times (1 + (v \times diff) + (v \times diff)^2 / 2)\\
\end{eqnarray*}

Polkadot defines the \verb|target_weight| as 0.25 (25\%). More information about
this algorithm is described in the Web3 Foundation research paper:
\url{https://research.web3.foundation/en/latest/polkadot/Token\%20Economics.html#relay-chain-transaction-fees-and-per-block-transaction-limits}.