Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

$$ \newcommand \PSfunction {\textbf{function }} \newcommand \PSreturn {\textbf{return }} \newcommand \PSendfunction {\textbf{end function}} \newcommand \PSswitch {\textbf{switch }} \newcommand \PScase {\textbf{case }} \newcommand \PSdefault {\textbf{default}} \newcommand \PSendswitch {\textbf{end switch}} \newcommand \PSfor {\textbf{for }} \newcommand \PSendfor {\textbf{end for}} \newcommand \PSwhile {\textbf{while }} \newcommand \PSendwhile {\textbf{end while}} \newcommand \PSdo {\textbf{ do}} \newcommand \PSif {\textbf{if }} \newcommand \PSelseif {\textbf{else if }} \newcommand \PSelse {\textbf{else}} \newcommand \PSthen {\textbf{ then}} \newcommand \PSendif {\textbf{end if}} \newcommand \PSnot {\textbf{not }} \newcommand \PScomment {\qquad \small \textsf} $$

$$ \newcommand \EventHandler {\mathrm{EventHandler}} \newcommand \BlockProposal {\mathrm{BlockProposal}} \newcommand \BlockAssembly {\mathrm{BlockAssembly}} \newcommand \SoftVote {\mathrm{SoftVote}} \newcommand \CertificationVote {\mathrm{CertificationVote}} \newcommand \Commitment {\mathrm{Commitment}} \newcommand \Recovery {\mathrm{Recovery}} \newcommand \FastRecovery {\mathrm{FastRecovery}} \newcommand \DeadlineTimeout {\mathrm{DeadlineTimeout}} \newcommand \Bundle {\mathrm{Bundle}} \newcommand \HandleProposal {\mathrm{HandleProposal}} \newcommand \HandleVote {\mathrm{HandleVote}} \newcommand \HandleBundle {\mathrm{HandleBundle}} \newcommand \Propose {\mathit{propose}} \newcommand \Soft {\mathit{soft}} \newcommand \Cert {\mathit{cert}} \newcommand \Next {\mathit{next}} \newcommand \Late {\mathit{late}} \newcommand \Redo {\mathit{redo}} \newcommand \Down {\mathit{down}} \newcommand \ev {\mathit{ev}} \newcommand \t {\mathit{time}} \newcommand \s {\mathit{step}} \newcommand \data {\mathit{msg}_\text{data}} \newcommand \TimeoutEvent {\texttt{TimeoutEvent}} \newcommand \MessageEvent {\texttt{MessageEvent}} \newcommand \DynamicFilterTimeout {\mathrm{DynamicFilterTimeout}} $$

Agreement Stages

The Algorand Agreement Protocol can be split into a series of stages.

In the normative section, these stages are univocally associated with infinite subsets of protocol states. These subsets are disjoint and together represent the whole space of possible states for the node state machine to be in.

The stages are, in chronological order within a given round:

  • \( \BlockProposal \),
  • \( \SoftVote \),
  • \( \CertificationVote \), which includes a final \( \Commitment \).

If \( \Commitment \) is not possible because of external reasons (i.e., a network partition), two fallback stages:

  • \( \FastRecovery \),
  • \( \Recovery \).

By abstracting away some implementation-specific complexity, we propose a model for the Agreement Protocol state machine that captures how and when transitions between different states happen.

Algorithm

We may model the state machine’s main algorithm in the following way:

\( \textbf{Algorithm 2} \text{: Main State Machine} \)

$$ \begin{aligned} &\text{1: } \PSfunction \EventHandler(ev) \\ &\text{2: } \qquad \PSif \ev \text{ is a } \TimeoutEvent \PSthen \\ &\text{3: } \qquad \quad \t \gets \ev_\t \\ &\text{4: } \qquad \quad \PSif \t = 0 \PSthen \PScomment{Last round should have left us with s := propose} \\ &\text{5: } \qquad \quad \quad \BlockProposal() \\&\text{6: } \qquad \quad \quad \PSif \text{finished a block} \lor \mathrm{CurrentTime}() = \mathrm{AssemblyDeadline}() \PSthen \\ &\text{7: } \qquad \quad \quad \quad \s \gets \Soft \\ &\text{8: } \qquad \quad \quad \PSendif \\ &\text{9: } \qquad \quad \PSelseif time = \DynamicFilterTimeout(p) \PSthen \\ &\text{10:} \qquad \quad \quad \SoftVote() \\ &\text{11:} \qquad \quad \quad \s \gets \Cert \\ &\text{12:} \qquad \quad \PSelseif \t = \DeadlineTimeout(p) \PSthen \\ &\text{13:} \qquad \quad \quad \s \gets \Next_0 \\ &\text{14:} \qquad \quad \quad \Recovery() \\ &\text{15:} \qquad \quad \PSelseif \t = \DeadlineTimeout(p) + 2^{s_t - 3}\lambda \text{ for } 4 \le s_t \le 252 \PSthen \\ &\text{16:} \qquad \quad \quad \s \gets \Next_{s_t} \\ &\text{17:} \qquad \quad \quad \Recovery() \\ &\text{18:} \qquad \quad \PSelseif \t = k\lambda_f + rnd \text{ for } k, rnd \in \mathbb{Z}, k > 0, 0 \le rnd \le \lambda_f \PSthen \\ &\text{19:} \qquad \quad \quad \FastRecovery() \\ &\text{20:} \qquad \quad \PSendif \\ &\text{21:} \qquad \PSelse \PScomment{MessageEvent could trigger a commitment and round advancement} \\ &\text{22:} \qquad \quad msg \gets ev_{msg} \\ &\text{23:} \qquad \quad \PSif \data \text{ is of type } \texttt{Proposal } pp \PSthen \\ &\text{24:} \qquad \quad \quad \HandleProposal(pp) \\ &\text{25:} \qquad \quad \PSelseif \data \text{ is of type } \texttt{Vote } v \PSthen \\ &\text{26:} \qquad \quad \quad \HandleVote(v) \\ &\text{27:} \qquad \quad \PSelseif \data \text{ is of type } \texttt{Bundle } b \PSthen \\ &\text{28:} \qquad \quad \quad \HandleBundle(b) \\ &\text{29:} \qquad \quad \PSendif \\ &\text{30:} \qquad \PSendif \\ &\text{31: } \PSendfunction \end{aligned} $$

The first three steps (\( \Propose, \Soft, \Cert \)) are the fundamental parts, and will be the only steps run in regular “healthy” functioning conditions.

The following steps are recovery procedures if there’s no observable consensus before their trigger times.

Note that in the case of \( \Propose \), if a block is not assembled and finalized in time for the \( \BlockAssembly() \) timeout, this might trigger advancement to the next step.

For more information on this process, refer to the Algorand Ledger non-normative section.

The \( \Next_{s-3} \) with \( s \in [3, 252] \) are recovery steps, while the last three (\( \Late, \Redo, \Down \)) are special fast recovery steps.

A period is an execution of a subset of steps, executed in order until one of them achieves a bundle for a specific value.

A round always starts with a \( \Propose \) step and finishes with a \( \Cert \) step (when a block becomes commitable, it is certified and committed to the Ledger).

However, multiple periods might be executed inside a round until:

  • A certification bundle (\( \Bundle(r,p,s,v) \) where \( s = \Cert \)) is observable by the network, and

  • The corresponding proposal \( Proposal(v) \) has been received and validated, and

  • The proposal payload is available at the moment of commitment.

Events

Events are the only way for the node state machine to transition internally and produce output.

⚙️ IMPLEMENTATION

Events reference implementation.

If an event is not identified as misconstrued or malicious, it will produce a state change. Also, it will almost certainly cause a receiving node to produce and then broadcast or relay an output, consumed by its peers in the network.

There are two main kinds of events:

  • \( \TimeoutEvent \), which are produced once the internal clock of a node reaches a specific time since the start of the current period;

  • \( \MessageEvent \), which are outputs produced by nodes in response to some stimulus (including the receiving node itself).

Internally, we consider the structure of an event to be composed of:

  • A floating point number, representing time (in seconds) from the start of the current period, in which the event has been triggered;

  • An event type, from an enumeration;

  • A data type;

  • Some attached data, plain bytes to be cast and interpreted according to the attached data type, or empty in case of a timeout event.

Time Events

\( \TimeoutEvent \) are triggered when a specific time has elapsed after the start of a new period.

  • \( \Soft \) timeout (a.k.a. Filtering): is run after a timeout of \( \DynamicFilterTimeout(p) \) is observed (where \( p \) is the currently running period). Note that it only depends on the period, whether it’s the first period in the round or a later one. In response to this, the node state machine will perform a filtering action, finding the highest priority proposal observed to produce a soft vote (as detailed in the \( \SoftVote \) algorithm).

  • \( \Next_0 \) timeout: it triggers the first recovery step, only executed if no consensus for a specific value was observed, and no \( \Cert \) bundle is constructible with observed votes. It plays after observing a timeout of \( \DeadlineTimeout(p) \). In this step, the node will next vote a value and attempt to reach a consensus for a \( \Next_0 \) bundle, that would kickstart a new period.

  • \( \Next_s \) timeout: this family of timeouts runs whenever the elapsed time since the start of the current period reaches \( \DeadlineTimeout(p) + 2^{s_t-3}\lambda \) for some \( 4 \le s_t \le 252 \). The algorithm run is the same as in the \( \Next_0 \) step.

⚙️ IMPLEMENTATION

Next vote ranges to reference implementation.

  • (\( \Late, \Redo, \Down \)) fast recovery timeouts: on observing a timeout of \( k\lambda_f + rnd \) with \( rnd \) a uniform random sample in \( [0, \lambda_f] \) and \( k \) a positive integer, the fast recovery algorithm is executed. It works very similarly to \( \Next_k \) timeouts, with some subtle differences (besides trigger time).

For a detailed description, refer to its subsection.

Message Events

\( \MessageEvent \) are events triggered after observing a specific message carrying data.

In Algorithm 2, we focused on three kinds of messages:

  • \( \texttt{Proposal} \),
  • \( \texttt{Vote} \),
  • \( \texttt{Bundle} \),

Each carries the corresponding construct (coinciding with their attached data type field).