Vanilla Run - Algorand Specifications

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

Algorand Specifications

For ease of understanding, we present a “vanilla run” of the Algorand consensus algorithm, the simplest scenario in which the agreement protocol produces a valid block and appends it to the Ledger.

The following timeline diagram illustrates the process:

(r   =   i,   p   =   0,   0   <=   s   <=   2)Proposal   (s   =   0)   time=   0Emits   proposals   fori-th   round   fromselected   accountsregistered   on   thenodeSoft   Vote   (s   =   1)time   =DynamicTO(p)Filters   proposals(lowest   hashcriteria)Soft   vote   on   thebest   proposal   forround   iCertification   (s   =   2)time   <DeadlineTO(p)Certification   vote   ofa   proposal   backedby   a   Soft   VoteBundleAppended   i-th   blockto   the   LedgerState   deltas   appliedTransaction   poolpurged(r   =   i+1,   p   =   0,   0   <=   s   <=   2)Proposal   (s   =   0)   time=   0Emits   proposals   fori+1-th   round   fromselected   accountsregistered   on   thenodeSoft   Vote   (s   =   1)time   =DynamicTO(p)Filters   proposals(lowest   hashcriteria)Soft   vote   on   thebest   proposal   forround   i+1Certification   (s   =   2)time   <DeadlineTO(p)Certification   vote   ofa   proposal   backedby   a   Soft   VoteBundleAppended   i+1-thblock   to   the   LedgerState   deltas   appliedTransaction   poolpurgedVanilla Run

Let us assume the network conditions are those described in the initial context.

As the main algorithm starts a round, it is called with a NewRoundNewRound event (node’s clock reset t=0t=0) and calls the BlockProposalBlockProposal procedure.

The BlockProposalBlockProposal algorithm runs a loop in which it iterates over all the accounts registered online in the node. When at least one account gets selected by the SortitionSortition, the node participates in the proposal voting on behalf of the selected accounts, and starts the BlockAssemblyBlockAssembly procedure.

This procedure will traverse the TransactionPoolTransactionPool, calling the Algorand Virtual Machine, and execute one transaction at a time, obtaining a new block ee.

The node will:

  1. Assemble a proposalproposal and a votevote on proposal-value vv,

  2. Set vv as the proposal-value obtained from block ee,

  3. Make two separate broadcasts for Vote(aI,r,p,proposal,v,credentials)Vote(aI,r,p,proposal,v,credentials) and for ee.

Then, the main algorithm enters the softsoft step setting s=1s=1.

Assume that some time has passed, now 0<t<DynamicFilterTimeout(p)0<t<DynamicFilterTimeout(p), and that the node receives a block proposal e′e′ broadcast from another node.

Then, the EventHandlerEventHandler runs the proposal handling subroutine HandleProposal(e′)HandleProposal(e′).

This algorithm receives the proposal e′e′ and unpacks its contents, including the execution state (r′,p′,s′)(r′,p′,s′).

Given the vanilla context assumptions, both nodes have the same context, therefore r=r′r=r′ and p=p′=0p=p′=0.

The algorithm checks if the proposal is valid, calling VerifyProposal(v′)VerifyProposal(v′) on v′=Proposalv(e′)v′=Proposalv(e′), and if periods are equal (p=p′p=p′). Both checks pass given the vanilla context assumptions.

Next, if e′∈Pe′∈P, it returns; else the proposal handler re-broadcasts e′e′, adds e′e′ to the set PP of stored proposals, and exits.

Let us now assume that the node received a broadcasted votevote, and that 0<t<DynamicFilterTimeout(p)0<t<DynamicFilterTimeout(p) still holds.

The EventHandlerEventHandler for the main algorithm thus calls HandleVote(vote)HandleVote(vote). The algorithm exits on failing checks (all passed with the vanilla context assumptions), or if the vote received has already been recorded in the votes set VV. If it is a new vote, the node adds it to the votes set VV and broadcasts it to other nodes.

Since nodes are synchronized (by assumption), it holds that votes=0=proposevotes=0=propose, so the algorithm checks if RetrieveProposal(votev)≠⊥RetrieveProposal(votev)≠⊥ and broadcasts if it is available, ignore it if not.

Until t≥DynamicFilterTimeout(p)t≥DynamicFilterTimeout(p) the main algorithm will execute the above steps whenever a vote or a proposal is received.

Eventually, the node clock reaches t=DynamicFilterTimeout(p)t=DynamicFilterTimeout(p) (that is, the node observes a TimeoutTimeout event for filtering), and the main algorithm calls SoftVoteSoftVote.

The soft vote procedure selects the highest priority block proposal and votes on it. The node goes through all the votes vote′∈Vvote′∈V in its votes set which are in the proposepropose step (vote′s=0votes′=0).

Given the credentialsjcredentialsj of player IjIj for the vote vote′credentialsj=(wj,y,VRF.ProofToHash(y))votecredentialsj′=(wj,y,VRF.ProofToHash(y)), the procedure runs a PriorityPriority function on the vote, as described in the soft vote non-normative section, and keeps track of the one with the highest priority (i.e., the one with the lowest hash).

Next, if there was at least one votevote in VV, for every registered account a∈Aa∈A it computes:

(wj,y,VRF.ProofToHash(y))←credentials′′=Sortition(a,soft)(wj,y,VRF.ProofToHash(y))←credentials′′=Sortition(a,soft)

and, if wj>0wj>0 it broadcasts Vote(r,p,soft,v,credentials′′)Vote(r,p,soft,v,credentials′′).

Moreover, if proposal←RetrieveProposal(v)proposal←RetrieveProposal(v) is not ⊥⊥, it also broadcasts proposalproposal.

When the node receives a event of type ProposalProposal, it runs the HandleProposalHandleProposal procedure as before.

When the node receives a event of type VoteVote, Vote(r,p,soft,v,credentials)Vote(r,p,soft,v,credentials), it

  1. Relays the vote,

  2. Adds the vote to the vote set (if new),

  3. Checks whether the vote can form a bundle with the votes in VV.

After a while, the last condition is met, and a bundle can be formed for the softsoft step.

When a softsoft bundle is observed for round rr, the node adds the accepted rr-th block to the Ledger, updates its state accordingly, garbage collects the information related rr-th round, and sets the round counter to r+1r+1.

In other words, the node:

Starting a new round will reset context variables as follows:

Calling the garbage collection algorithm will compute:

V(r,p−1)P(r,p−1)={vote∈V:voter<r or (voter=r and votep+1<p)}={proposal∈P:proposalr<r or (proposalr=r and proposalp+1<p)}V(r,p−1)={vote∈V:voter<r or (voter=r and votep+1<p)}P(r,p−1)={proposal∈P:proposalr<r or (proposalr=r and proposalp+1<p)}

and then remove these sets from the votes and proposal sets:

∑vote∈Vvotecredentialsj≥CommitteeThreshold(soft).

  1. The node checks if there is a votevvotev, such that for all the vote∈Vvote∈V with voter=r,votep=0,votes=softvoter=r,votep=0,votes=soft, the sum of votes’ weights is bigger than the committee threshold: