$$ \newcommand \Propose {\mathit{propose}} \newcommand \Soft {\mathit{soft}} \newcommand \Cert {\mathit{cert}} \newcommand \Late {\mathit{late}} \newcommand \Redo {\mathit{redo}} \newcommand \Down {\mathit{down}} \newcommand \Next {\mathit{next}} \newcommand \CommitteeSize {\mathrm{CommitteeSize}} \newcommand \CommitteeThreshold {\mathrm{CommitteeThreshold}} \newcommand \Proposal {\mathrm{Proposal}} \newcommand \Digest {\mathrm{Digest}} \newcommand \Encoding {\mathrm{Encoding}} \newcommand \Hash {\mathrm{Hash}} \newcommand \pk {\mathrm{pk}} \newcommand \sk {\mathrm{sk}} \newcommand \fv {\text{first}} \newcommand \lv {\text{last}} \newcommand \Vote {\mathrm{Vote}} \newcommand \Equivocation {\mathrm{Equivocation}} \newcommand \Seed {\mathrm{Seed}} \newcommand \Record {\mathrm{Record}} \newcommand \Stake {\mathrm{Stake}} \newcommand \Sign {\mathrm{Sign}} \newcommand \Verify {\mathrm{Verify}} \newcommand \abs[1] {\lvert #1 \rvert} \newcommand \Bundle {\mathrm{Bundle}} \newcommand \ValidEntry {\mathrm{ValidEntry}} \newcommand \VRF {\mathrm{VRF}} \newcommand \Prove {\mathrm{Prove}} \newcommand \ProofToHash {\mathrm{ProofToHash}} \newcommand \DigestLookup {\mathrm{DigestLookup}} $$

Messages

Players communicate with each other by exchanging messages.

A message is an opaque object containing arbitrary data, save for the fields defined below.

Note

For a detailed overview of message composition, whether consensus or other types, see the Algorand Network non-normative section.

Elementary Data Types

A period \( p \) is a 64-bit integer.

A step \( s \) is an 8-bit integer.

Steps are named for clarity and are defined as follows:

The following functions are defined on \( s \):

• \( \CommitteeSize(s) \) is a 64-bit integer defined as follows:

$$ \CommitteeSize(s) = \left\{ \begin{array}{rl} 20 & : s = \Propose \\ 2990 & : s = \Soft \\ 1500 & : s = \Cert \\ 500 & : s = \Late \\ 2400 & : s = \Redo \\ 6000 & : s = \Down \\ 5000 & : \text{otherwise} \end{array} \right. $$

• \( \CommitteeThreshold(s) \) is a 64-bit integer defined as follows:

$$ \CommitteeThreshold(s) = \left\{ \begin{array}{rl} 0 & : s = \Propose \\ 2267 & : s = \Soft \\ 1112 & : s = \Cert \\ 320 & : s = \Late \\ 1768 & : s = \Redo \\ 4560 & : s = \Down \\ 3838 & : \text{otherwise} \end{array} \right. $$

A proposal-value is a tuple \( v = (I, p, \Digest(e), \Hash(\Encoding(e))) \) where:

• \( I \) is an address (the “original proposer”),

• \( p \) is a period (the “original period”),

• \( \Hash \) is some cryptographic hash function.

The special proposal-value where all fields are the zero-string is called the bottom proposal \( \bot \).

Votes

Let

• \( I \) be an address,

• \( r \) be a round,

• \( p \) be a period,

• \( s \) be a step,

• \( v \) be a proposal-value.

Let \( x \) be a canonical encoding of the 5-tuple \( (I, r, p, s, v) \), and let \( x’ \) be a canonical encoding of the 4-tuple \( (I, r, p, s) \).

Let \( y \) be an arbitrary bitstring.

Then we say that the tuple

$$ (I, r, p, s, v, y) $$

is a vote from \( I \) for \( v \) at round \( r \), period \( p \), step \( s \) (or a vote from \( I \) for \( v \) at \( (r, p, s) \)), denoted

$$ \Vote(I, r, p, s, v) $$

Important

IMPLEMENTATION:

Vote reference implementation.

Moreover, let \( L \) be a ledger where \( \abs{L} \geq \delta_b \).

Let

• \( (\sk, \pk) \) be a keypair,
• \( B, \bar{B} \) be 64-bit integers,
• \( Q \) be a 256-bit integer,
• \( \tau, \bar{\tau} \) 32-bit integers.

We say that this vote is valid with respect to \( L \) (or simply valid if \( L \) is unambiguous) if the following conditions are true:

Important

IMPLEMENTATION:

The reference implementation builds an asynchronous vote verifier, which builds a verification pool and under the hood uses two different verifying routines: one for regular unauthenticated votes, and one for unauthenticated equivocation votes.

Note

See the Algorand ABFT non-normative section for further details.

• \( r \leq |L| + 2 \)

• Let \( v = (I_{orig}, p_{orig}, d, h )\).

  • If \( s = 0 \), then \( p_{orig} \le p \).
  • Furthermore, if \( s = 0 \) and \( p = p_{orig} \), then \( I = I_{orig} \).

• If \( s \in \{ \Propose, \Soft, \Cert, \Late, \Redo\} \), \( v \neq \bot \). Conversely, if \( s = \Down \), \( v = \bot \).

• Let

  • \( (\pk, B, r_\fv, r_\lv) = \Record(L, r - \delta_b, I) \),
  • \( \bar{B} = \Stake(L, r - \delta_b, r) \),
  • \( Q = \Seed(L, r - \delta_s) \),
  • \( \tau = \CommitteeThreshold(s) \),
  • \( \bar{\tau} = \CommitteeSize(s) \).

  Then

  • \( \Verify(y, x, x’, \pk, B, \bar{B}, Q, \tau, \bar{\tau}) \neq 0 \),
  • \( r_\fv \leq r \leq r_\lv \).

Observe that valid votes contain outputs of the \( \Sign \) procedure; i.e., \( y := \Sign(x, x’, \sk, B, \bar{B}, Q, \tau, \bar{\tau}) \).

Informally, these conditions check the following:

• The vote is not too far in the future for \( L \) to be able to validate.

• “Propose”-step votes can either propose a new proposal-value for this period (\( p_{orig} = p \)) or claim to “re-propose” a value originally proposed in an earlier period (\( p_{orig} < p \)). But they can’t claim to “re-propose” a value from a future period. And if the proposal-value is new (\( p_{orig} = p \)) then the “original proposer” must be the voter.

• The \( \Propose \), \( \Soft \), \( \Cert \), \( \Late \), and \( \Redo \) steps must vote for an actual proposal. The \( \Down \) step must only vote for \( \bot \).

• The last condition checks that the vote was properly signed by a voter who was selected to serve on the committee for this round, period, and step. The committee selection process uses the voter’s stake and keys as of \( \delta_b \) rounds before the vote and the seed as of \(\delta_s\) rounds before the vote. It also checks if the vote’s round is within the range associated with the voter’s participation key.

An equivocation vote pair or equivocation vote \( \Equivocation(I, r, p, s) \) is a pair of votes that differ in their proposal values. In other words,

$$ \begin{aligned} \Equivocation(I, r, p, s) = (&\Vote(I, r, p, s, v_1), \\ &\Vote(I, r, p, s, v_2)) \end{aligned} $$

for some \( v_1 \neq v_2 \).

An equivocation vote pair is valid with respect to \( L \) (or simply valid if \( L \) is unambiguous) if both of its constituent votes are also valid with respect to \( L \).

Bundles

Let \( V \) be any set of votes and equivocation votes.

We say that \( V \) is a bundle for \( v \) in round \( r \), period \( p \), and step \( s \) (or a bundle for \( v \) at \( (r, p, s) \)), denoted \( \Bundle(r, p, s, v) \).

Important

IMPLEMENTATION:

Bundle reference implementation.

Moreover, let \( L \) be a ledger where \( \abs{L} \geq \delta_b \).

We say that this bundle is valid with respect to \( L \) (or simply valid if \( L \) is unambiguous) if the following conditions are true:

Important

IMPLEMENTATION:

The reference implementation makes use of an asynchronous Bundle verifying function.

Note

See the Algorand ABFT non-normative section for further details.

• Every element \( a_i \in V \) is valid with respect to \( L \).

• For any two elements \( a_i, a_j \in V \), \( I_i \neq I_j \).

• For any element \( a_i \in V \), \( r_i = r, p_i = p, s_i = s \).

• For any element \( a_i \in V \), either \( a_i \) is a vote and \( v_i = v \), or \( a_i \) is an equivocation vote.

• Let \( w_i \) be the weight of the signature in \( a_i \). Then \( \sum_i w_i \geq \CommitteeThreshold(s) \).

Proposals

Let \( e = (o, s) \) be an entry and \( y \) be the output of a \( \Sign \) procedure.

The pair \( (e, y) \) is a proposal or a proposal payload.

Moreover, let

• \( L \) be a ledger where \( \abs{L} \geq \delta_b \),

• \( v = (I, p, h, x) \) be some proposal-value.

We say that this proposal is a valid proposal matching \( v \) with respect to \( L \) (or simply that this proposal matches \( v \) if \( L \) is unambiguous) if the following conditions are true:

• \( \ValidEntry(L, e) = 1 \),

• \( h = \Digest(e) \),

• \( x = \Hash(\Encoding(e)) \),

• The seed \( s \) and seed proof are valid as specified in the following section,

• Let \( (\pk, B, r_\fv, r_\lv) = \Record(L, r - \delta_b, I) \),

  • If \( p = 0 \), then \( \Verify(y, Q_0, Q_0, \pk, 0, 0, 0, 0, 0) \neq 0 \),

• Let \( (\pk, B, r_\fv, r_\lv) = \Record(L, r - \delta_b, I) \). Then \( r_\fv \leq r \leq r_\lv \).

If \( e \) matches \( v \), we write \( e = \Proposal(v) \).

Seed

Informally, the protocol interleaves \( \delta_s \) seeds in an alternating sequence. Each seed is derived from a seed \( \delta_s \) rounds in the past through either a hash function or through a \( \VRF \), keyed on the entry proposer. Additionally, every \( \delta_s\delta_r \) rounds, the digest of a previous entry (specifically, from round \( r-\delta_s\delta_r \)) is hashed into the result. The seed proof is the corresponding VRF proof, or 0 if the \( \VRF \) was not used.

More formally, suppose \( I \) is a correct proposer in round \( r \) and period \( p \).

Let

• \( (\pk, B, r_\fv, r_\lv) = \Record(L, r - \delta_b, I) \),

• \( \sk \) be the secret key corresponding to \( \pk \),

• \( \alpha \) be a 256-bit integer.

Then \( I \) computes the seed proof \( y \) for a new entry as follows:

• If \( p = 0 \):

  • \( y = \VRF.\Prove(\Seed(L, r-\delta_s), \sk) \),
  • \( \alpha = \Hash(\VRF.\ProofToHash(y), I) \).

• If \( p \ne 0 \):

  • \( y = 0 \),
  • \( \alpha = \Hash(\Seed(L, r-\delta_s)) \).

Now \( I \) computes the seed \( Q \) as follows:

$$ Q = \left\{ \begin{array}{rl} H(\alpha, \DigestLookup(L, r-\delta_s\delta_r)) & : (r \bmod \delta_s\delta_r) < \delta_s \\ H(\alpha) & : \text{otherwise} \end{array} \right. $$

Important

IMPLEMENTATION:

Seed computation reference implementation.

The seed is valid if the following verification procedure succeeds:

1. Let \( (\pk, B, r_\fv, r_\lv) = \Record(L, r-\delta_b, I) \); let \( q_0 = \Seed(L, r-\delta_s) \).

2. If \( p = 0 \), check \( \VRF.\Verify(y, q_0, \pk) \), immediately returning failure if verification fails. Let \( q_1 = \Hash(\VRF.\ProofToHash(y), I) \) and continue to step 4.

3. If \( p \ne 0 \), let \( q_1 = \Hash(q_0) \). Continue.

4. If \( r \equiv (r \bmod \delta_s) \mod \delta_r\delta_s \), then check \( Q = \Hash(q_1||\DigestLookup(L, r-\delta_s\delta_r)) \). Otherwise, check \( Q = q_1 \).

Note

Round \( r \) leader selection and committee selection both use the seed from \( r-\delta_s \) and the balances / public keys from \( r-\delta_b \).

Note

For re-proposals, the period \( p \) used in this section is the original period, not the reproposal period.

Note

For a detailed overview of the seed computation algorithm and some explanatory examples, refer to the Algorand ABFT non-normative specification.