Algorand is a novel blockchain technology introduced by 2015 by the Turing award Silvio Micali [1, 2]. Algorand is an interesting project because it claims solve the Trilemma problem. The term algorand is obtained by mixing together two distinct words: algorithmic and randomness. These two words suggest that Algorand is based on both a mathematical approach and a random process [2]. The algorithmical part and the randomness are both involved in the process of generating a pseudo-random1 number as proposed by Micali, Rabin, and Vadhan in [3]. Later, Micali noticed that this work could be useful to cope with the blockchain’s idea to randomly (and privately) select a leader and imported this pseudo-random generator to be part of the Algorand blockchain. To solve the Trilemma problem, Algorand adopts a new custom version of the BFT protocol called Binary Byzantine Agreement – BA⋆. The BA⋆ allows reaching consensus with low latency [2] while scaling to thousands of nodes. Chapter 6 will give a performance analysis of the BA⋆. Overall, the Algorand consensus procedure promise to be fork-free. Furthermore, Algorand puts in place some technics that allow the safeness of participants. In fact, to mitigate the possibility of attacks, Algorand selects a small set of committees to run the consensus procedure [4] and replaces the committee members soon after they have sent the message.

The Algorand team suggested Pure Proof-of-Stake – Pure PoS – to identify their new consensus procedure. Practically, the Algorand team has redesigned a new consensus procedure from scratch with the ambition to solve many of the problems that affect the old-fashioned consensus procedures. Like in the PoS, anyone can join the network and partake to the consensus procedure proportionally to the stake it bets on the middle of the table.

At high level the Pure PoS works in rounds. During each round a new leader is elected to propose a new block. Afterward, a multi-step voting procedure confirms the new block within a minute. That block is later added to the chain and never removed, allowing what is called consensus finality. The voting procedure guarantees to reach the consensus with low latency thanks to the BA⋆. The main characteristic of this Algorand consensus procedure is to select a different subset of nodes for each step. These nodes must verify the block and propagate their vote to the other members of the network. Algorand guarantees to achieve an overall consensus despite the subset of members who vote for the next block changes at every step (this property is called Player Replaceability). The entire procedure is also safe against malicious parties because attackers could not know in advance who is going to vote for the block proposed by the leader. Finally, the Pure PoS can be employed in permissioned environments and permissionless environment as well in which no central authority is needed to manage the node’s identities.

Before explaining how Algorand works, we propose a review of the main properties.

• Minimal computational effort. In Algorand the nodes do not have to compete each other for solving a mathematical puzzle. Indeed, participants run a simple function called Verifiable Random Function [3] – VRF – to know who will run the consensus. Basically, the VRF is a random number generator that takes a public seed to produce a 256 bits string long. The VRF runs within a Sortition function. Every node privately runs this Sortition function (and the VRF) to find the leader and to elect the committee members proportionally to the stake it bets. The VRF is simply the core part of this Sortition function.
• Consensus finality. Once a block has been added to the chain, it is never removed. The possibility of having forks is 10 to the power of -18 . Hence, Algorand is suitable for small payments (at least theoretically).
• Participants roles. In Algorand, participants can freely join the network. The participants belong to one of these three categories: normal participant, committee member or a leader. In the beginning, every participant has the basic role of Consensus via Pure Proof-of-Stake “normal” participant. A normal participant can just read and broadcast transactions. Periodically, every node runs the Sortition function (based on the VRF) and the node may be elected as leader or as a committee member. The leader proposes the block, while the committee member runs the BA⋆ and votes for those blocks proposed by the leader. Basically, the Sortition function elects a leader and the committee members in a democratic way and based on the money the nodes stake.
• Fast agreement “On-The-Fly". During the BA⋆ the participants vote for a block soon after they receive it and they immediately continue to propagate the block to the remaining nodes. This is why we call the Algorand’s agreement “on-the-fly".

The white paper [4] cites three main challenges that Algorand had to face. Firstly, the procedure should not allow the Sybil attack. This attack happens when participants create many accounts (as pseudonyms) increasing their opportunity to get elected and to become the leader, influencing the BA⋆. Practically, a participant who owns 1M tokens may think to create 1M accounts and split his tokens among these addresses with the aim to have a better chance to be elected as leader. So that, 1 token for each address. Algorand has been designed to withstand this kind of attack. Secondly, Algorand must be able to scale to millions of nodes and to continue to work even when a set of nodes goes offline. Finally, the entire procedure must resist to denial-of-service attacks. With the aim to avoid these issues, Algorand employed several techniques that are listed below.

Weighted participants. Each participant has a weight proportional to the tokens he owns. Typically, the more the tokens, the more the weight. But the best part of this approach is that every account is automatically split between several addresses. Typically, there is one address for each token that the participant owns. All these addresses are linked to the same owner. This approach makes practically infeasible for a participant to defraud the network by creating several accounts and splitting his tokens into all these accounts with the aim to increase his opportunity to get a reward.

Furthermore, compared with the PoS in which the 2/3 majority of the nodes’ stake must be owned by honest parties, Algorand assumes that the 2/3 majority of the nodes’ weight must be handed by honest participants. Roughly, achieving the majority of the money is harder than achieving the majority of the stakes, that is what Algorand does. Hence, the Algorand consensus is more secure than the PoS against malicious parties.

Round. Algorand is organized in logical units called rounds. In every round, a new block is appended to the chain. Every round consists of several steps. In particular, for each round, five steps can be highlighted: from (1) value proposal, to (2) soft-votes, (3) cert-votes (4) first finishing step and finally a (5) second finishing step. The most important thing to say, is that every step selects a different subset of nodes to carry out the procedure.

Committee members. In each round several sets of representatives are randomly selected among all participants to run the BA⋆. Changing the set of nodes at every step of the round, prevents attackers from targeting a specific group of nodes and to get control of the network. In fact, attackers do not know in advance neither who will be the leader nor who are going to be the committee members.

Participant replacement. This is a new property provided by Algorand also known as Player Replaceability. This property means that Algorand reaches consensus even if at each step a different set of committee members is selected. The committee group may vary in size. The committee members as well as the leader are selected through a Sortition function.

Sortition function. Sortition is the practice of selecting the committee members at random from a large set of eligible individuals [2]. The BA⋆ selects the committees in a private way. This means, every participant secretly runs the sortition function to determine if they have been chosen to be part of the committee.

We said that differently from the previously mentioned PoW and PoS, the Algorand’s team has redesigned the consensus procedure from scratch with the ambition to solve many of the problems that affect the previously cited consensus procedures.

At first, the nodes issue their transactions. Algorand implements a gossip protocol over a TCP network. Every message is digitally signed by the private key of the sender. Namely, according to [2], a payment P of a user j is identified by a transaction that has this format:

Where j and j' are respectively the payer and the payee's ID. sk is the sender secret key. The value a is the amount of money transferred. For obvious reasons, a must be lower than the total amount of money owned by a participant. I is a sensible data, for example a timestamp. H indicates the hash function. Algorand uses a SHA-256 hash function. H ( I ) is the hash of I and that hash is used to check the payment. Finally, SIG sk is the digital signature performed using the secret key sk.

Soon after the transaction propagation, the Algorand consensus takes place. This consensus works in rounds and for each round two phases are highlighted. During the first phase every participant runs a Sortition function to elect the leader. As usual, the leader is in charge to propose the next block. In the second phase, a subset of members is pseudo-randomly selected to become part of a committee group and runs the Algorand Agreement – BA⋆ [4]. At this point, two questions need an answer. First, how does the Sortition function work?

We might see the Sortition function as a fair lottery that cannot be manipulated by malicious parties. The lottery elects the leader as well as the committee members and takes into account the number of tokens owned by each node, in the same way the PoS does. Hence, if a node owns a lot of tokens, its opportunity to be elected increases. The key factor of the Sortition function is the so-called “Verifiable Random Function” (VRF) [3], which is a random number generator that takes a public seed and the node’s role to generate a random value. Sortition returns three values: a random number generated by the VRF, a proof that the output provided by the VRF is correct and a number j that expresses the probability of a node to become a committee member. A higher value of j means a higher probability of election. Every node can later verify the validity of the value j using a VerifySortition function. We should take into account that the entire

Once a leader is elected, he propagates the block to the committee members who run the BA⋆. The main innovation of this new consensus protocol is the property called Player Replaceability [4]. The Player Replaceability allows Algorand to rely on a different subset of users for each round, still continuing to reach an agreement. Thus, in the beginning of each round nobody knows in advance who will be elected to run the consensus. In this way, nodes are protected against targeted attacks because the attacker will not know in advance who is going to win the lottery.

During the BA⋆ three kinds of messages are exchanged between the committee members [5]: a CERT-VOTE, a SOFT-VOTE and a NEXT-VOTE. When a majority of votes is received a node switches its status from SOFT-VOTE to CERT-VOTE and halts from propagating further messages. Citing the white paper [4], the following definitions are provided:

Definition 1. Cert-vote. A node i during a round r cert-votes a value v when he propagates SIG i (v, “ cert”, r).

Definition 2. Soft-vote. A node i during a round r soft-votes a value v when he propagates SIG i (v, “ so f t”, r).

Definition 3. Next-vote. A node i during a round r next-votes a value v when he propagates SIG i (v, “ next”, r ).

Moreover, the entire procedure assures a lower number of forks. In order to avoid overwhelming the network, when a fork happens and two parties are not able to find an agreement, the Pure PoS switches to a so-called CommonCoin procedure that forces the nodes to accept one value between 0 or 1 with probability p = 0, 5. In this way, adversaries have a lower chance to manipulate the vote.

The reader should keep in mind that Algorand elects several leaders (not just one) at each round. In real scenarios, at most seventy leaders are elected simultaneously to propose the block. This allows the blockchain to resist from network partitioning. Hence, normal users may receive more blocks, but they propagate only the block with the highest priority and discard the other blocks. This mechanism ensures that, in a concentric way, the number of proposed blocks decreases as blocks move away from the source. The following is a definition of leader.

Definition 4. Leader. The leader l r for round r is the ar gmin j ∈ N H ( SIG j ( seed, r)).

Where ar gmin x f (x) is defined as the value of x for which f (x) attains it’s minimum. Back to our definition, N is the set of all participants from which the node i has received valid credentials. The seed is public and regenerated as new at each round.

Algorand leads to two kinds of consensus: a final consensus or a tentative consensus [4]. If one participant reaches final consensus, all the other nodes must agree on the same block value. By contrast, tentative consensus means that other participants may have reached consensus on a different block.

The Sortition function is based on a Verifiable Random Function – VRF, which is a random number generator that takes a public value (typically a “seed”) and generates a random string [4]. According to [3], a VRF can be defined as a function f (SecretK e y, seed ) such that the function passes all efficient test for oracles. The f function is an oracle because despite the output of the VRF is easily verifiable, for an external user that output is indistinguishable from a random value. The VRF has several fields of application. In any case, the function keeps its strength as long as the owner has nothing to gain from being dishonest. A formal definition of the VRF has been proposed in [3].

Definition 5. A VRF is a random oracle composed by the triplet (G, f , V ).

Roughly, the VRF implements three functions. A function G(•), a function f (•, •) and a function V (•, •).

- Phase 1 - Description of G ( x)

G is the function generator that inputs a value x and outputs a public key pk and a secret key sk and a polynomial Q of degree at most 2k2 − 1 over a GF (2 k ). G generates also a random string of length l , called coins ∈ {0, 1}l that needs to generate a deterministic value.

- Phase 2 - Description of f (SecretK e y, seed)

f is the function evaluator that receives as input the secret key sk and a seed generated at the network bootstrap. The public seed is generated as fresh at each step of the BA⋆ and propagated together with the cert-vote and soft-vote messages. The function f outputs a random value v and a proo f that v is indeed correct. As first step, evaluator returns a ( k + 1) bit integer p x that with high probability is a prime number. Soon after, a PrimalityTest is executed to check whether p x is prime or not. If p x is prime, the number is kept, otherwise it is discarded and the procedure re-done. Starting from p x , as second step, the evaluator function can easily produce a random value v that is the output of the function. That value is not necessarily a prime number, but it is just a random number easily verifiable. At the end of this phase, the value v and its proo f are delivered.

- Phase 3 - Description of V ( P ubl icK e y, v)

The function verifier V outputs YES or NO depending by the correctness of v. Practically the function V re-executes the PrimalityTest to check whether the value is correct or not.

We show below the basic version of the VRF function [3], as implemented in the Algorand blockchain. The VRF does not require to share any information different from the sender public key pk and the seed.

In a nutshell, the sender (in Algorand is the leader in charge to propagate the next block) gets the hash of the signature of both seed and role together. The output provided by the VRF is a 256 bit string long and a proof that the hash is indeed correct. The seed is a value secretly generated by each leader before propagating the block. The seed is refreshed at every round and cannot be manipulated by adversaries. The role value can be: committee, leader or normal participant. While sk instead, is the leader secret key. Nobody knows the sender secret key sk, but the correctness of the hash can be verified using the corresponding public key and the PrimalityTest. Of course, sk must be hard to compute from pk. The secret key enables both to evaluate f and to prove the correctness of such evaluation. Practically, it is impossible to find a public key (even a “fake” one) of a VRF for which one can “prove” the correctness of two different VRF outputs for the same VRF input [3].

Algorand adopts a Sortition function (also called Crypto- graphic sortition) to select the leader and the committee members. But how does Sortition function work?

The pseudocode of the Algorand Sortition function is shown in Figure 4.1. The function brings as input, the node secret key sk, a seed , a value τ that represents the expected number of users selected as committee , a role and the total amount of currency units in Algorand, W . The first line in Figure below of the Sortition function implements the VRF, returning two parameters as explained above. In the second line of the same picture, the value p is the probability of a participant to be selected to become a committee member. p depends by τ that is a parameter chosen by design. j is an index starting from zero.

The image below was taken from the Algorand white paper.

To select nodes in proportion to their money, Algorand considers each token as a different “sub-user” (or a different address), and each token is selected with a probability p = τ/W . A node can be selected several times using its sub-users. To determine how many sub-users are selected, Sortition function implements a binomial distribution (line 4 of the picture) that picks a value between zero and the maximum number of tokens. The binomial distribution returns a value j that indicates the exact number of selected sub-users for a given node. The binomial distribution B( k ; w, p ) stands for (W k ) p k (1 − p )w− k . Practically the binomial distribution selects a number of sub-user proportional to the node weight. A higher value of j means a higher probability to become a leader or a committee member. The value j is later sent across the network and every node can verify the validity of the Sortition’s output, by using a VerifySortition function that simply reverse the Sortition function to check if the value j is correct.

In this sub-section we magnify the steps required by the BA⋆. The following steps are executed at every round of Algorand and they are performed several times until a final consensus on a block is achieved. As defined in [4], the steps 1, 4 and 5 can be combined together into a single BA⋆ step with the aim to decrease the time needed by the procedure to come to an agreement. When the leader is honest, Algorand claims to achieve the agreement in only one step.

The image below was taken from the Algorand white paper.

The step 5 allows Algorand to recover from network partitioning because in asynchronous networks, messages can be delivered at any moment. When the timer expires without that a node receives enough cert-votes, the nodes quickly move to step 5 and next-votes the block. The procedure daunts the creation of forks.

As a conclusion, the Pure Proof-of-Stake is certainly an interesting consensus procedure that makes things different with respect to the previous ones. At least theoretically, Algorand provides a solution to solve the Trilemma problem but, this blockchain is still in its early stages and it needs to be widely tested also in real scenarios.

[1] Algorand team. https://www.algorand .com/ team

[2] Silvio micali. https://en.wikipedia .org/ wiki/ Silvio_Micali

[3] Jing Chen and Silvio Micali. Algorand. arXiv preprint arXiv:1607.01341, 2016.

[4] Jing Chen, Sergey Gorbunov, Silvio Micali, and Georgios Vlachos. Algorand agreement: Super fast and partition resilient byzantine agreement. IACR Cryptology ePrint Archive, 2018:377, 2018.

[5] Incentiveless consensus: Algorand technical review https://medium.com/ @genesysone/ algorand- enigmatic -incentiveless- digital -money- c06913f3310a