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

• Auto
• Light
• Dark

Algorand Specifications

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.

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

Algorithm 2: Main State Machine

1: function EventHandler(ev)
2: if ev is a TimeoutEvent then
3: time ← ev.time
4: if time = 0 then
   Last round should have left us with s := propose
5: BlockProposal()
6: if finished a block ∨ CurrentTime() = AssemblyDeadline() then
7: step ← soft
8: end if
9: else if time = DynamicFilterTimeout(p) then
10: SoftVote()
11: step ← cert
12: else if time = DeadlineTimeout(p) then
13: step ← next0
14: Recovery()
15: else if time = DeadlineTimeout(p) + 2s−3λ for 4 ≤ s ≤ 252 then
16: step ← nexts
17: Recovery()
18: else if time = kλf + rnd for k, rnd ∈ Z, k > 0, 0 ≤ rnd ≤ λf then
19: FastRecovery()
20: end if
21: else
   MessageEvent could trigger a commitment and round advancement
22: msg ← ev.msg
23: if msg.data is of type Proposal pp then
24: HandleProposal(pp)
25: else if msg.data is of type Vote v then
26: HandleVote(v)
27: else if msg.data is of type Bundle b then
28: HandleBundle(b)
29: end if
30: end if
31: end function

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 nexts−3 with s∈[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 are the only way for the node state machine to transition internally and produce output.

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.

TimeoutEvents 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).

• next0 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 next0 bundle, that would kickstart a new period.

• nexts timeout: this family of timeouts runs whenever the elapsed time since the start of the current period reaches DeadlineTimeout(p)+2s−3λ for some 4≤s≤252. The algorithm run is the same as in the next0 step.

The important note regarding the next vote ranges can be found in the reference implementation.

• (late, redo, down) fast recovery timeouts: on observing a timeout of kλf + rnd with rnd a uniform random sample in [0, λf] and k a positive integer, the fast recovery algorithm is executed. It works very similarly to nextk timeouts, with some subtle differences (besides trigger time).

For a detailed description, refer to its subsection.

MessageEvents are events triggered after observing a specific message carrying data.

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

• Proposal,
• Vote,
• Bundle,

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