The Algorand blockchain uses a decentralized Byzantine agreement protocol based on pure proof-of-stake (PPoS). It can tolerate an arbitrary number of malicious users as long as honest users (those that follow the instructions of the protocol) hold more than two-thirds of the total stake in the system. The following is a brief overview of the Algorand protocol.
In Algorand, every online user who possesses algos can participate in the consensus protocol. To reduce exposure, users do not use their spending keys (i.e., the keys they use to spend stake) for consensus. Instead, a user who wishes to participate in the protocol generates and registers a participation key. With this key, an account can participate in proposing and voting on blocks. Using participation keys ensures that a user's algos are secure even if their participating node is compromised.
Self-Selection via Verifiable Random Function
Every block in Algorand reveals a new random and unpredictable selection seed that determines which users should participate in the next round of the consensus protocol. When a new block gets committed to the blockchain, everyone becomes aware of this seed (and everyone sees the same seed). A user secretly checks whether they were selected to participate by evaluating a Verifiable Random Function (VRF) with their secret participation key and the selection seed. This computation is minimal, so even a limited device such as a Raspberry Pi can do it. The VRF computation produces a pseudorandom output with a cryptographic proof that anyone can use to verify the result. By sending this proof, a user can prove to anyone that they were indeed selected to participate.
What makes this protocol pure proof-of-stake is the fact that users are chosen to participate in the protocol based on the stake (number of algos) that they have. The VRF behaves similarly to a weighted lottery; it is as if every algo in an account gets its own lottery ticket. The more algos in an online account, the better chance the account has of being selected to participate.
The selection of users to participate in the certification of blocks using the VRF is done randomly and secretly, without any communication among the users. Since executing this procedure requires a user’s private key, no one except for that user knows whether they were selected. An adversary does not know who matters in generating the next block (and thus should be targeted) until after a selected user participates in the consensus protocol. And by the time an adversary realizes that a user is selected, it is too late for them to benefit from an attack; the user has already sent their message and fulfilled their responsibility in the consensus protocol. Furthermore, for each step of the protocol a unique subset of participants is randomly and privately selected, independent of earlier subsets.
Consensus refers to the way blocks are selected and written to the blockchain. Algorand uses the VRF described above to select accounts to propose blocks for a given round. When a block is proposed to the blockchain, a committee of voters is selected to vote on the block proposal. If a super majority of the votes are from honest participants, the block can be certified.
Consensus requires three steps to propose, confirm, and write a block to the blockchain: 1) propose, 2) soft vote, and 3) certify vote. Each is described below, assuming the ideal case when there are no malicious users and the network is not partitioned (i.e., none of the network is down due to technical issues or from DoS attacks).
In the block proposal step, accounts are selected to propose new blocks to the network. This phase starts with every node in the network looping through each of the accounts that it manages and, for each account that is online and participating, running Algorand’s VRF to determine if the account is selected to propose the block. Once an account is selected, each node propagates its proposed block along with the VRF output, which proves that the account is a valid proposer. Each node in the network will get block proposals from other nodes, and then validate the VRF output for these proposals.
Next, each node will run the VRF for every participating account it manages to see if they have been chosen to participate in the soft vote committee. If an account is chosen, it will have a weighted vote based on the number of algos it has. Each account chosen will filter the proposals down to one by voting to confirm the block. These votes will be for the lowest VRF block proposal calculated at the timeout and will be sent out to the other nodes along with the VRF proof. Each node will validate the committee membership VRF proof before adding to the vote tally. Once a quorum is reached for the soft vote, the process moves to the certify vote step.
A new committee is then selected to check the block proposal that was voted on in the soft vote phase for overspending, double-spending, or any other problems. If valid, the committee votes again to certify the block. This is done in a similar manner to the soft vote where each node iterates through its managed accounts to select a committee and to send votes. These votes are collected and validated by each node until a quorum is reached, triggering an end to the round and prompting the node to create a certificate for the block and write it to the ledger. At that point, a new round is initiated and the process starts over.