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

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

More formally, suppose II is a correct proposer in round rr and period pp.

Let

• (pk,B,rfirst,rlast)=Record(L,r−δb,I)(pk,B,rfirst,rlast)=Record(L,r−δb,I),
• sksk be the secret key corresponding to pkpk,
• αα be a 256-bit integer.

Then II computes the seed proof yy for a new entry as follows:

• If p=0p=0:
  • y=VRF.Prove(Seed(L,r−δs),sk)y=VRF.Prove(Seed(L,r−δs),sk),
  • α=Hash(VRF.ProofToHash(y),I)α=Hash(VRF.ProofToHash(y),I).
• If p≠0p≠0:
  • y=0y=0,
  • α=Hash(Seed(L,r−δs))α=Hash(Seed(L,r−δs)).

Now II computes the seed QQ as follows:

Q={H(α,DigestLookup(L,r−δsδr))H(α):(rmodδsδr)<δs:otherwiseQ={H(α,DigestLookup(L,r−δsδr)):(rmodδsδr)<δsH(α):otherwise

Important

IMPLEMENTATION:

Seed computation reference implementation.

The seed is valid if the following verification procedure succeeds:

1. Let (pk,B,rfirst,rlast)=Record(L,r−δb,I)(pk,B,rfirst,rlast)=Record(L,r−δb,I); let q0=Seed(L,r−δs)q0=Seed(L,r−δs).

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

3. If p≠0p≠0, let q1=Hash(q0)q1=Hash(q0). Continue.

4. If r≡(rmodδs)modδrδsr≡(rmodδs)modδrδs, then check Q=Hash(q1||DigestLookup(L,r−δsδr))Q=Hash(q1||DigestLookup(L,r−δsδr)). Otherwise, check Q=q1Q=q1.

Round rr leader selection and committee selection both use the seed from r−δsr−δs and the balances / public keys from r−δbr−δb.

For re-proposals, the period pp used in this section is the original period, not the reproposal period.

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