Pure Proof of Stake (PPoS) | Consensus explanation in Algorand

In this lesson we will delve into Algorand’s consensus algorithm: Pure Proof of Stake (PPoS), sometimes also called Proof of Weight (PoWeight).

We will try to go into detail and take some basics for granted, so if you do not know what a consensus algorithm is, I refer you to the lecture dedicated to this topic.

Explaining a consensus algorithm in detail but understandable by everyone is not easy. As we know, blockchain was born from the meeting of three fields: game theory, cryptography and computer science.

An extremely detailed explanation of PPoS would require in-depth knowledge in cryptography, as Silvio Micali, the creator of this algorithm, a great expert in cryptography, a professor at MIT, as well as the winner of the prestigious Turing Award in 2012, has, precisely for his work in the field of cryptography.

This should come as no surprise, because the world of blockchain and cryptocurrencies has its roots in the cypherpunk movement, which sees computer cryptography as the key to social and political change.

As further evidence of Micali’s strongly mathematical approach, suffice it to say that the name Algorand is given by the union of “algorithm” (“algorithm”) and “randomic” (“random”), two terms that by the end of this lecture will have acquired a distinct meaning.

1- The blockchain trilemma and the limitations of existing consensus algorithms

When dealing with blockchain technology, it is inevitable to highlight one of its main critical issues: the blockchain trilemma.

It is not the purpose of this lecture to delve into this issue but it is essential to introduce it, since Micali’s algorithm was born precisely to solve this trilemma.

Throughout the history of blockchain, the trilemma has been proposed in various forms but surely the most well-known form is the one presented by Vitalik Buterin, the creator of Ethereum.

According to the trilemma, it is impossible (or very difficult) for a blockchain to be simultaneously:

• Decentralized: that is, without a central entity (in computing, client-server paradigm) but composed of peer entities (in computing, peer-to-peer paradigm);
• Secure: able to resist malicious actors that might attack it;
• Scalable: able to hold a very large number of users and able to process many operations (especially transactions) in a short time.

Each blockchain will be stronger in some of these aspects, but an optimal solution has not yet been arrived at.

Micali’s studies have focused precisely on solving the trilemma and developing a consensus algorithm on which to base a decentralized, secure and scalable blockchain.

Micali started from the limitations of existing consensus algorithms and tried to overcome them and reuse their best aspects.

1.1- Proof of Work (PoW)

The first consensus algorithm, in the blockchain context, was of course the first blockchain: Bitcoin.

Satoshi Nakamoto, the creator of Bitcoin, developed the Proof of Work (PoW) algorithm, which relies on solving cryptographic puzzles at high computational cost, a process called “mining,” in order to come up with a new block to add to the chain.

The critical aspects of PoW are several:

• High power consumption for solving cryptographic puzzles;
• Need to possess dedicated and increasingly high-performance hardware, which, at present, makes it impossible for a single user to compete for block creation, as concentrations of power (mining pools), groups of miners who pool their computational power to increase the chances of success, have arisen. This obviously results in less decentralization, because it means that the block creation process is mostly controlled by the major mining pools;
• Possibility of the chain forking when two blocks are proposed at the same time. In these cases, the chain splits into two branches to which new blocks can be added, until the one that is longer (or rather whose overall computational power used was greater) wins and all the other blocks in the other branch are eliminated, leading to the cancellation of the transactions they contained.
  This leads to a problem from the point of view of scalability, having to wait an hour on average to be sure that a transaction is confirmed.

1.2- Proof of Stake (PoS)

Following PoW, other algorithms have emerged, the best known of which is Proof of Stake (PoS).

PoS does not rely on computational power, but rather on staking, that is, blocking a portion of one’s funds. Users can choose whether to stake a portion of their funds. Each time a block is to be created the creator is drawn from among those who have funds in stakes. The probability of being drawn is proportional to the amount of funds staked.

In addition, in case of malicious behavior, the user is deprived of the amount put into staking.

As can be guessed, some of the problems of PoW, such as the onerous energy cost, are solved, but new issues emerge:

• Once again, it is easy for concentrations of power to arise, and that those who have more money to put into staking (and thus are also more predisposed to the risk of losing it) can easily gain more and more power. Here again then staking pools have arisen, which function similarly to mining pools;
• The fork problem is not solved.

1.3- Delegated Proof of Stake (DPoS)

A variant of PoS is Delegated Proof of Stake (DPoS), in which a group of delegates is given the power to create blocks for a certain amount of time.

It is easy to see that, in this case, the main problem is the possibility for a malicious actor to corrupt the delegates or for a Denial of Service (DoS) attack to render them inoperative.

Delegating to a part of the actors in fact results in a smaller distribution and thus a smaller number of actors to corrupt or attack.

There are many other consensus algorithms but this brief overview is enough to introduce the problems that Algorand aims to solve.

2- The goals of Algorand’s Pure Proof of Stake

Given the criticality of existing algorithms, Micali in 2017 proposed Pure Proof of Stake, the algorithm that has seen its first practical application in Algorand.

Recall that we are in the realm of distributed systems, where there are therefore multiple distributed nodes located in communication with each other.

The fundamental goal is clearly to reach consensus regarding decisions (the creation of a new block for example).

The classic example is the Byzantine generals problem, which we have already explained in the introductory lesson on consensus algorithms. It is from this example that Byzantine agreement protocols are born, in which one of the fundamental assumptions is that at least 2/3 of the nodes in a system must be honest for the protocol to be successful.

Algorand has its foundation in the Byzantine Agreement procolli but seeks to develop an even better solution, primarily setting itself the following goals:

• Avoid Sybil attacks, i.e., cyber attacks in which a malicious actor creates many pseudonyms in order to have more decision-making weight (we return to the 2/3 honest nodes of Byzantine fault tolerance). Indeed, PoW and PoS have also addressed this problem, in different ways. On the one hand with the computational power required to solve cryptographic puzzles, on the other with staking. In both cases, the intent is to ensure that a malicious actor cannot take advantage of the creation of pseudonyms, which could instead be very dangerous in a system where each actor casts an unweighted vote.
• Scaling to millions of users, reaching sizes impossible to imagine for existing Byzantine consensus protocols;
• Resist DoS attacks, being able to operate even if many nodes in the network fall;
• Avoid forks, causing only one block to be proposed each round, preventing the chain from forking.

3- Algorand’s high-level solution

Micali’s proposed solution is PPoS: a Byzantine consensus algorithm with leader election, which takes elements of PoS and works if at least 2/3 of the actors involved are honest.

Algorand’s consensus algorithm proceeds by rounds, and each round must result in the creation of a new block to be added to the chain.

In each round, users are drawn to compete for the creation of the block and then additional users are drawn to form a committee that must reach consensus on a block to be approved.

The extractions are done through Verifiable Random Functions (VRF), which are functions that take a key and a value as input and produce a pseudo-random output, with a proof that can be used by anyone to verify the result of the function.

The operation of the VRF is similar to that of a lottery: each online account (i.e., an account that participates in the consensus protocol, as we will see more fully in the following section) each round runs the VRF to find out if it has been selected to create the block and later to find out if it will be part of the evaluation committee (there will be a dedicated section later in the lecture on VRFs to explore VRFs in more detail).

This is where the similarity with PoS comes into play; in fact, the more Algoes you own on your account, the greater the chance of being drawn, because each Algo is like a lottery ticket.

Thus the problem of Sybil Attacks is solved, in fact it is useless to create multiple accounts, what matters is the amount of Algo possessed.

Compared to PoS, however, it will be noticed that there is a key advantage: there is no need to put a portion of one’s assets in stakes in order to participate in the consensus.

Every Algo in every account is a lottery ticket, with no need to put it in stakes. It follows that, to participate in the consensus process, it is not a micro-portion of the overall economy but the economy as a whole.

4- How to participate in the consensus protocol

To participate in the consensus process, one must have an online account.

As indicated in theAlgorand overview, accounts can be online or offline. The former do not participate in the consent protocol, the latter do.

In order to make one’s account online, one must sign a transaction that allows one to receive a participation key, a key that is used to participate in the consensus protocol and that is completely separate from spending keys, the keys used to make transactions.

Participation keys are contained in a node.

The choice to distinguish the types of keys was made for security reasons, so that in the event that the partecipation key were to be compromised (or even that an entire node were to be compromised), the spending keys would be safe in any case.

Again for security reasons, the participation key is not eternal, but is only valid for a certain number of rounds.

To further increase the security level of the protocol, the partecipation key is used to generate and sign a set of ephemeral keys that are only valid for signing messages for a single round, after which they are discarded.

It is important to emphasize the fact that the keys are deleted after each round, because this makes it impossible to compromise old blocks in the chain using the old keys.

4.1- Practical explanation

Let us now try to explain how to generate a participation key and subsequently how to make an account online.

The process is very technical so we will try to stay fairly high-level so as not to overcomplicate the lesson. For the more experienced and developers I refer to this page of Algorand’s developer resources.

The process is divided into two steps:

• Participation key generation;
• Transaction to register an online account.

The participation key is generated by running the appropriate command

 goal account addpartkey

within a node. The command requires you to specify the address of the account for which you are generating the partecipation key, along with other data.

This command generates the key pair to be used for the VRF, as well as the set of keys to be used for individual rounds.

Once the partecipation key has been generated, it will be necessary to download the newly generated data from the node with the appropriate command

goal account partkeyinfo

which will return an output like this:

EW64GC6F24M7NDSC5R3ES4YUVE3ZXXNMARJHDCCCLIHZU6TBEOC7XRSBG4.6000000.9000000.partkey { "acct": "EW64GC6F24M7NDSC5R3ES4YUVE3ZXXNMARJHDCCCLIHZU6TBEOC7XRSBG4", "first": 6000000, "last": 9000000, "sel": "X84ReKTmp yfgmMCbbokVqeFFFrKQeFZKEXG89SXwm4=", "vote": "eXq34wzh2UIxCZaI1leALKyAvSz/ XOe0wqdHagM bw=", "voteKD": 1730 } ... ```

You can now go to the second step and create the transaction to register the account online.

It should be remembered that it is not enough to be online to be able to participate in the consensus, you must in fact have the partecipation key obtained with the first step. If you skip the first step you will turn out to be online without actually being able to participate in the consensus. If you are online but cannot participate, you will be considered a rogue user.

This is an example of a transaction to register an account online:

{ 
    "txn": { 
        "fee": 2000, 
        "fv": 6002000, 
        "gh": "SGO1GKSzyE7IEPItTxCByw9x8FmnrCDexi9/cOUJOi=" 
        "lv": 6003000, 
        "selkey": "X84ReKTmp yfgmMCbbokVqeFFFrKQeFZKEXG89SXwm4=" 
        "snd": "EW64GC6F24M7NDSC5R3ES4YUVE3ZXXNMARJHDCCCLIHZU6TBEOC7XRSBG4" 
        }, "type": "keyreg", 
        "votefst": 6000000, 
        "votekd": 1730, 
        "votekey": "eXq34wzh2UIxCZaI1leALKyAvSz/ XOe0wqdHagM bw=", 
        }, "votelst": 9000000 
    } 
}

It can be seen that the transaction fee is higher than for normal transactions (2000 microalgo in this case versus the traditional 1000 microalgo, in other words 0.002 Algo versus the traditional 0.001).

The other data are those contained in the output generated by the command seen above, such as the “votekey.”

5- Verifiable Random Function (VRF)

Algorand relies on verifiable random functions (VRFs), functions that enable cryptographic mining, so that a subset of users, from the total users, is chosen based on the weights of the individual users (determined by the amount of Algo they hold).

VRFs allow users to prove that they have been extracted for a particular role and requires that each user have a private/public key pair.

A VRF takes as input a string x and returns as output two values: a hash and a proof.

The hash is uniquely determined by the user’s private key and the input string x and impossible for anyone who does not possess the user’s private key to determine.

The proof, on the other hand, allows anyone who possesses the user’s public key to verify that the hash matches the string x entered as input to the VRF, without needing to know the user’s private key.

The output hash of the VRF is called hashed credential and will return several times throughout this lesson.

6- Gossip Protocol

In Algorand, users communicate with each other via a gossip protocol, similar to that implemented by Bitcoin.

Users send each other messages signed with private keys so that other users can verify their authenticity.

These messages can be of different types, from transactions, to block proposals, to votes.

PPoS is based precisely on this gossip protocol, which is necessary for the various parties to communicate and come to an agreement.

7- Pure Proof of Stake in detail

Let us now go on to explain how PPoS works in detail.

In Algorand, consensus is reached in three mandatory steps, plus one optional step:

• Block Proposal;
• Soft Vote;
• Certify Vote;
• Recovery mode.

We describe the first three steps, considering the ideal case in which there are no malicious actors and the network is not partitioned (i.e., there are no network nodes down), and then look at the last step, which deals with failure cases.

7.1- Block Proposal

In this step, the accounts that will propose new blocks to the network in a given round are selected.

First, each node performs the VRF for each Online account it manages that has a valid participation key.

This draws the accounts that have “won” the lottery in that round. It should always be remembered that this is a weighted lottery, so the VRF is performed on each Algo owned by each Online account.

Two things follow from this:

• The more Algo’s owned, the greater the probability of being selected;
• There is the possibility of being selected more than once per round, since each Algo is like a lottery ticket and therefore there could be multiple winning tickets within a single account (refer to the section on this topic).

Once the accounts have been selected, the nodes propagate the blocks proposed by the accounts into the network along with the output of the VRF, which is necessary to verify that the account has indeed been selected to propose the block.

Here it is worth going into even more detail by introducing some new concepts.

First, it must be specified that in each round a leader is selected to propose the block. As we said various accounts are drawn that can propose the block but there will always be one leader in each round, who will be the one whose hashed credential (i.e., the VRF-generated selection certificate) is the smallest among all the potential leaders drawn to create the block.

Second, as we said before, the blocks proposed by the extracted users must be propagated along with the credentials (output of the VRF) to verify the validity of the selection.

Here the Algorand algorithm provides two tricks that it is only fair to point out, as they make it well understood the great work that has been done to speed up the network and thus make it more scalable:

• The messages sent by the nodes at this stage are of two types: messages containing blocks whose weight is on the order of a few mega-bytes and control messages, those containing only the output of the VRF in relation to an account, which weigh a few hundred bits.
  In this way, nodes can read the shorter messages first to check the validity of the VRF output and only then read the messages containing the blocks, thus saving time and bandwidth.
• The second expedient is perhaps even more useful. As just mentioned, the leader of a round is the one who will have the shortest hashed credential. Individual nodes have a record of participation keys related to a number of accounts but obviously do not know all existing accounts.
  So an individual node will not be able to know, without communicating with the network, who will be the leader. The thing it can do, however, is to send to the network only the block and VRF output related to the account, among those it manages, with the shortest hashed credential, so as to transmit less data and speed up the process.
  This mechanism called selective propagation also allows nodes, when receiving messages from other nodes, to check with the message containing only the credentials of the extracted accounts, the length of the hashed credential and decide based on this whether to also open the message containing the proposed block and propagate it in turn in the network.
  In this way, very quickly the blocks of potential leaders are reduced, until only one remains, that of the real leader of the round.
  But here we are already encroaching on the soft vote phase.

7.2- Soft voting

By this time each node in the network will have received and sent several proposals. The goal of soft voting is to gradually filter the proposals until there is only one left, thus leading to only one certified block, as just mentioned in reference to selective propagation.

Each node checks the signature of the received messages and checks the output of the VRF to see if the user who proposed the block was really extracted.

Next, each node re-runs the VRF for each consensus participant account it handles in order to extract the soft vote committee. Again, this is a weighted lottery based on the number of Algo owned by the accounts.

If an account is chosen, it will be entitled to a weighted vote based on the number of Algo’s owned. Accounts will vote for the blocking proposal with the lowest hashed credential.

This process continues for a fixed period of time (given by the propagation time of the control messages, those containing only the VRF result), and chosen in such a way as to optimize two factors:

• The duration should not be too long, so as not to slow down the process of creating and adding the new block to the chain, which would compromise scalability;
• The duration should not be too short, so that votes can be propagated among the entire netowrk.

At the end of the voting period, they will send the votes to the other nodes, along with the output of the VRF to verify that they have been drawn as participants of the soft vote committee.

Each node will validate the VRF evidence of the committee members before counting the votes.

This process is run as many times as necessary to reach a quorum.

Each time it is rerun, a new committee is selected, of a different size, quantified by the number of votes, not accounts.

A certain percentage of votes is required to reach a quorum, based on the size of the committee.

It should be specified that at this stage the committee does not need to see the content of the blocks but only the hashed credential, to select the smaller one. In this way the network can proceed very quickly, without risking being clogged.

7.3- Certify vote

In this third step, called certify vote, a new committee is drawn, again via VRF, as in the previous step.

The new committee will have to check the proposed block from the soft vote step, checking for various problems such as overspending or double-spending.

The committee members will vote (again weighted vote based on Algo owned) whether the block is valid or not.

The votes are propagated throughout the network, validated by the nodes via VRF, until a quorum is reached.

At this point, if a quorum has been reached, the block is added to the blockchain and a new round is started, which will follow the steps outlined so far.

The process is thus repeated indefinitely.

7.4- Recovery mode

There is a fourth, optional phase that comes into play in cases where the certify vote committer does not reach a quorum in a given time frame.

Recovery mode is a phase that is entered when the newtork stalls, which can occur for essentially two reasons:

• Network problems;
• Malicious behavior by malicious actors.

In either case, the network enters recovery mode, waiting for recovery messages, in which nodes signal to the network that it should either continue processing the last known blocking proposal or propose a new block.

Again, a vote takes place, by the nodes, and once one of the two options is chosen, the system will resume normal operation.

In case of malicious behavior by malicious actors, the protocol may choose a new leader.

In case of network problems, on the other hand, the current block proposal will continue to be processed or a new block will be proposed for analysis.

7.5- Consensus dataflow in Algorand

To conclude, it may be useful to have a summary diagram illustrating the various steps exhibited from the time a transaction is sent to when it is placed in a block.

For convenience, we will take the example of a transaction starting from Algorand Wallet, it should be specified that the flow might change in case you decide to manually create transactions and send them to a node.

1. You create the transaction from Algorand Wallet and send it to the network. Specifically, for Algorand Wallet, an http (POST) call is made to a predetermined endpoint;
2. The transaction is received by a node that propagates it to the network via gossip protocol;
3. Each node will have a set of transactions to be placed inside a new block;
4. Start round;
5. Block proposition;
6. Soft Vote;
7. Certify vote;
8. Recovery mode (optional, if quorum is not reached after some time);
9. End of round; Block created;
10. Start new round.

8- What happens if the same account is drawn several times in the same round

As mentioned so far, VRF is in fact a weighted lottery, where each Algo equals one vote. Each online account is submitted to the VRF, which checks each Algo held by the account to see if it is a winning ticket for a particular round.

This is to avoid Sybil Attacks and results in a user being able to be selected multiple times within a round, which is all the more likely the more Algoes he or she possesses.

So, it is possible for a user X who possesses as many Algo to be selected N times for the same role within a round.

In such cases, user X will participate with N different sub-users, where each Algo is considered as a sub-user (each Algo is worth one vote).

Here we come to an important concept, which relates to the hashed credential (or block priority) that we have discussed several times.

In fact, for each sub-user of user X, a hash function will be applied to which the output of the VRF concatenated to the index of the sub-user will be passed as input.

From the obtained hashes, the one with the highest priority (i.e., the shortest hash) will be chosen and will be used as the hashed credential for the block proposed by user X.

9- What happens in case of malicious actors (adversaries)

Let us go into more detail regarding the presence of malicious actors.

First let us see what types of malicious actors (adversaries) there can be:

• Static ad versary = is a malicious actor that controls a group of users, chosen before protocol execution begins;
• Dynamic adversary = is a malicious actor that dynamically corrupts users at any stage of the protocol;
• Network adversary = is a malicious actor that can control the network communication used by users. It can cause message delays or even fail to deliver messages.

PPoS, being a consensus algorithm based on the Byzantine Agreement, needs the super-majority of honest (2/3) users in order to work. Given this initial assumption, it is able to resist all three types of adversaries.

Let us now look at different types of attacks and how Algorand is able to resist them:

9.1- Sybil Attacks

Regarding Sybil Attacks, we have already specified how Algorand makes pseudonym creation unnecessary in the consensus process by making votes weighted by the amount of Algo held by users.

9.2- Corrupting honest users

There can then be an attack aimed at corrupting honest users. Algorand is specifically made to prevent an adversary from bribing enough users to gain control of block creation.

There is no stable group of delegates, as in DPoS, the committees chosen by VRFs change at each stage, that is, after a few seconds. Moreover, it is a random and secret selection, with no communication between users.

Therefore, an opponent will not be able to find out who the drawn leader is until after the block has already been proposed.

9.3- Network Attacks

Finally we see the case of network attacks, the most dangerous for any distributed system.

This is a type of attack in which an adversary creates partitions within the network, dividing it and making communication between users difficult or impossible.

In this way the various user partitions will not be aware of what is happening in the other partitions.

At these times, the network is completely asynchronous and malicious actors control communication within the network. Adversaries could convince different partitions to accept different blocks at the same time, which would lead, among other things, to problems such as double-spending.

In Algorand, only one block can be accepted per round, even if the network is split, despite the duration of the attack. Only one block can always be accepted.

In addition, Algorand, as seen in the previous section, has a Recovery Mode, which is activated when nodes see no progress in reaching consensus after a certain amount of time.

When in Recovery Mode, nodes exchange particular messages, seen above, that allow them to choose how to act.

As soon as the network is back up and running, the nodes realign and block creation resumes, allowing virtually instantaneous recovery from the attack.

10- Mining vs. Staking vs. Rewards

A final issue to be addressed is that of Algorand rewards.

As explained in theoverview, from 2019 to 2022 Algorand provides participation rewards that are obtained just for owning Algo’s in one’s address.

It may be reminiscent of the rewards obtained by miners in PoW or those obtained by staking in PoS.

In the case of PoW, the reward is justified by the fact that high computing power made available to miners is required to solve cryptographic quizzes. This involves substantial energy consumption and thus cost on the part of miners, who are therefore rewarded, when they succeed in winning a block, with rewards.

Similarly in PoS, by staking a portion of one’s assets, one has the disadvantage of not being able to use that money as long as it remains in staking.

You also expose yourself to the risk that you could lose it if you misbehave.

In the case of Algorand and PPoS, on the other hand, the rewards are completely untethered from the blockchain creation process, although they are distributed each round, in proportion to the amounts of Algo owned by the various accounts.

In fact, the computational cost of creating a block in Algorand is almost zero, and one can safely install a node in an ordinary laptop, keeping it running in the background while performing other tasks.

Because the computational cost is negligible, it does not require a payoff, as is the case with PoW.

Similarly, it is a pure form of Stake, so one does not have to tie up a portion of one’s money to participate in the consensus process, one just has to own it and can use it at any time.

Even in this case, therefore, a reward would not be justified, because in fact you are not risking anything.

In Algorand therefore, the participation rewards (which, as explained in this lecture, will be replaced in 2022 by governance rewards) serve essentially to attract new users and gradually distribute the Algo supply that was mined in the first block (10 bn).

Bibliography and sitography

• Algorand, Silvio Micali, Jing Chen
• Algorand: Scaling Byzantine Agreements for Cryptocurrencies, Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich
• Algorand: A secure and efficient distributed ledger, Jing Chen, Silvio Micali
• Algorand Agreement: Super Fast and Partition Resilient Byzantine Agreement, Jing Chen, Sergey Gorbunov, Silvio Micali, Georgios Vlachos
• Algorand Protocol Overview
• https://www.algorand.com/technology/security
• https://www.algorand.com/technology/faq
• https://www.algorand.com/technology/core-blockchain-innovation
• https://www.algorand.com/technology/protocol-overview
• https://www.algorand.com/technology/pure-proof-of-stake
• https://www.algorand.com/resources/blog/proof-of-stake-vs-pure-proof-of-stake-consensus
• https://www.algorand.com/resources/algorand-announcements/secure-blockchain-decentralization-via-committees
• https://www.algorand.com/technology/algorand-protocol
• https://developer.algorand.org/docs/run-a-node/participate/generate_keys/
• https://developer.algorand.org/docs/clis/goal/account/addpartkey/
• https://developer.algorand.org/docs/get-details/algorand_consensus/#verifiable-random-function
• https://developer.algorand.org/docs/clis/goal/account/addpartkey/
• https://developer.algorand.org/docs/get-details/transactions/#register-account-online
• https://developer.algorand.org/docs/run-a-node/participate/
• https://developer.algorand.org/docs/get-details/algorand_consensus/#participation-keys