Some time ago, I had the chance to attend a talk by Silvio Micali presenting Algorand. Silvio is a legendary figure in Cryptography circles, and has received a Turing award for his contributions to this science (including the co-invention of the idea of Zero-Knowledge, and many of the fundamental concepts, like pseudorandomness, semantic security and cryptographic adversaries), so I was eager to learn of his involvement in the blockchain community. I was not disappointed.
Silvio Micali is the founder of Algorand, a relatively recent proposal for a pure Proof of Stake blockchain, and I was impressed by the neatness of the design. This post is my attempt to capture some of the features of this project that were discussed in that talk.
Scalability and Consensus
It’s been acknowledged for quite some time that one of the main factors preventing wide adoption of blockchain technology is that they are generally not scalable. By this I mean that a Proof of Work network like Bitcoin or Ethereum is severely limited in the number of transactions it can process each second, with numbers in the low tens. By comparison, it is often reported that credit card networks like Visa or MasterCard can handle between 20 000 to 40 000 transactions per second. We need to drastically reduce this discrepancy if we want public unpermissioned blockchains to be viable.
Notice I have qualified the type of blockchain in the above paragraph: I’ve referred to Proof of Work blockchains, and to public unpermissioned blockchains. There is a reason for this, and comes down to the security of the chain. Proof of Work was the key innovation in Satoshi Nakamoto’s original Bitcoin paper, and it theoretically solved the problem of creating agreement (ie “Consensus”) among an unlimited number of unrelated people who do not trust each other.
Different Types of Blockchain
In a private blockchain, where participants are vetted before they are accepted into the network, you can assume good behaviour of every member and full trust between them. Therefore, standard agreement protocols can be reached to agree on each block that is added to the chain.
You may still have a public blockchain where anyone can participate, but with different levels of permissions to interact or create blocks. In this case, we may have trust in the nodes that have the permissions to maintain the network because the process of their choice is fair and adequate. But in general, in a public blockchain where anyone can just connect and participate equally to everyone else, this trust can not just be assumed. We must therefore devise a way to prevent bad actors from introducing fraudulent blocks into the chain.
Proof of Work
Proof of Work was invented for this. It is a kind of election protocol, in which the author of the next block, the leader, is chosen more or less at random, which prevents an attacker from consistently subverting the network. The ‘random’ aspect of this election is dependent on the computing power of each participant to solve a hard problem (like inverting part of a hash) and the more computational power a participant has, the more likely it is to be selected as leader and create the next block.
Each new block must be verified by all the other participants. Each one then takes the decision whether the transactions included in the block are consistent (business rules are not broken, input and output balances of the accounts involved cancel out, etc.) and if so adds the block to their own copy of the blockchain. This mechanism typically allows a chain to grow simultaneously in different directions, as block creators may receive different blocks and add them more or less at the same time. It also requires a long time.
The new blocks are then propagated to the network, but only become valid after a sufficient number of nodes have integrated them in their chains. At any point, a node may know more than one version of the blockchain, in which case it will select the longest as the real one and discard the others.
This whole process is computationally intensive. Block miners are totally occupied during the ‘election’ time in solving the hash as fast as possible, unable to do much other work, and when a block is selected, the work of all other miners will have been wasted. The process is so competitive that to stand any chance participants have to invest in very powerful machines or, nowadays, join a mining pool with other miners around the planet.
The Blockchain Trilemma
There is a well known representation of the scalability difficulties in blockchain, known as the Blockchain Trilemma:
It’s easy, shall we say, to design a blockchain that achieves any two of these properties, but we cannot have all three at the same time. It is not straightforward, at least.
- If we want to have a secure and fully decentralized blockchain, then we have to require heavy work of the the participants, in a way that prevents blocks from being added quickly to the network, because all users have to verify a block before it is accepted.
- Instead, if we want the network to be fast (scalable) and secure, we have a single authority creating, verifying and disseminating the blocks, but this is no longer a decentralized architecture.
- Finally, we can have a fast and fully decentralized network where only a small number of users is required to verify and produce blocks, but this network is likely to produce many conflicting versions of the chain. Without a consensus on which transactions are valid, no one can be certain of having a coin that will be accepted by other members.
Consensus Mechanisms
Proof of Work was the first consensus mechanism proposed for blockchains, but it has major drawbacks. It is costly and slow. The whole process creates a block approximately each 10 minutes (in the Bitcoin network) and the amount of transactions in a block is limited. It is also computationally very intensive, which has created controversy comparing the amount of energy spent on maintaining the Bitcoin network all over the world to that used by a whole country.
There are several technical proposals to improve this throughput, with names like sharding (Ethereum), SegWit (Bitcoin), off-chain networks like Lightning and Raiden, Sidechains, etc. But in this post, I want to focus instead on a different type of solution: the consensus mechanism. Today, we have public blockchains experimenting with different solutions: variations on Proof of Stake, Proof of Authority and other less-frequent varieties like Proof of Reputation.
Proof of Authority
In a Proof of Authority network, the block creators are fixed. This is the model followed by Ripple (and Ethereum’s test network Rinkeby) and it provides for a fast network, but the participants must fully trust the Authorities: who they are and how they were chosen. This is anathema to many blockchain purists, who defend a totally trustless network.
Proof of Stake
In a Proof of Stake, participants can vote in proportion to something they have (their stake). This could be forfeited in case of misbehaving but in other variants it is simply assumed, in game-theoretic terms, that those with the largest stake have the most to lose from any scandal or attack on their network, and so would do the utmost to protect and properly care for it.
There are two notable variants of Proof of Stake:
- in Bonded Proof of Stake, participants deposit some of their tokens as an assurance they will not commit fraud. If they do and are found out, they relinquish that stake in favour of the network.
- in Delegated Proof of Stake, there is a small committee deciding and voting on the next block to add to the network. This committee can change as the importance of nodes in the network (measured by overall tokens held, financial involvement, contributions to the community, etc.) varies, and at any time a fixed size of arguably the most important or involved members are part of it. An example is EOS, which has at any one time 21 elected delegates.
Despite all the differences, the advantage brought by Proof of Stake is this: we no longer need a lengthy computational process to select the next block producer. This can instead be done by an algorithm that quickly and randomly sorts out one address according to the distribution of stake. This makes PoS networks very fast.
Algorand and Pure Proof of Stake
Algorand positions itself in the Proof of Stake camp, and enforces Pure Proof of Stake. By this, they mean that the only factor affecting the choice of the next leader (block creator) is the number of Algorand tokens a participant holds. That keeps the benefits of speed but also keeps full decentralization. So, how do they achieve this?
The solution is clever, and based on cryptographic constructions (not surprising giving the pedigree of its founders). In Algorand lingo, it is called Sortition.
The blockchain grows one block at a time, and the process to propose and accept a new block is organized by rounds. In each round, a new block is proposed by a leader and voted upon by a committee, that decides whether to accept or reject the proposal. Algorand wants to maintain the following properties:
-
each user in the network may be selected to the committee with probability equal to the fraction of total tokens it holds;
-
the protocol should enforce consensus as long as 2/3 of the tokens are held by honest users;
-
adversaries should not be able to target committee members before they vote, nor be able to change their vote afterwards;
-
even if an adversary compromises a committee member after it votes, the protocol should be able to replace this member for the next round.
Main Techniques
Algorand uses a variant of a byzantine agreement, and its design ensures that when 2/3 of the tokens are honest (more accurately, ‘are held by honest users’) the probability of a fraudulent block being proposed and accepted is essentially 0. As usual in science, this assurance is valid only if the assumption holds. If you have more than 1/3 dishonest users (‘tokens’) in your network, Algorand does not give you any guarantees.
The other three properties are the interesting ones, and where Algorand’s innovations happen. The key is to select a new committee and leader every round. These are selected at random, from the whole pool of token holders. This means that even if a member is compromised in one round, most likely it will not be a committee member in the next round. This is possible only because committee members do not need to hold any state information that survives from round to round, and so can be replaced by any newcomer.
Algorand’s Self-Selection
There is no one selecting a committee or a leader. This would be a vulnerable point after all, since it would be enough to attack this chooser instead of attacking committee members. The solution of Algorand is to let users select themselves, and they do so by running a cryptographic lottery in their own machines. This lottery is run only once per user in each round, which is a very fast computation, and returns a proof of selection for the user. In this case, the user then propagates such proof with its vote in tandem in a single signed message.
The core of this process is a cryptographic construct called a Verifiable Random Function. It is a public-key algorithm that is a bit like a pseudorandom function with a twist. The invocation of the VRF takes a secret key and another argument, a public key of the round that everyone knows. It outputs a pseudorandom value (similar to a hash) and a proof. For anyone without the secret key, that value is indistinguishable from a truly random string, but given the proof and the matching public-key, anyone can run a verifier algorithm and check that the output string was created for the input string and the secret key.
Why the Attacker Can’t Win
This specific arrangement ensures the attacker is powerless to target a specific committee member: before the member sends its message, the attacker cannot predict who is going to be selected. The production of a proof requires knowledge of each user’s secret key, and so the attacker cannot brute force calculations until it finds a token that matches the selection threshold.
And because the proof of selection is sent at the same time as the vote, in a bundle of data signed by the voter, the attacker cannot replace it or corrupt it. It’s also too late to prevent the vote from being cast, because the moment the attacker learns the identity of the voter is when the vote has already been propagated to the network.
Common Questions
There were two main questions that were posed in the Q&A after Silvio’s talk, and from the way he answered them, and the insistence with which different versions of the questions were pitched, it sounded as if these were frequently asked:
- How is this different from Proof of Work?
- How can Algorand prevent Sybil attacks?
To be honest, the talk did not address the technical details, and it was only in response to these questions that they were made somehow clear. In case you were wondering about them as well, here are the answers.
Difference to Proof of Work
There is a crucial difference in a VRF and the intensive hash computations in Bitcoin’s Proof of Work. In the latter, a miner looks for a valid block, that is, one where the hash of a block’s fields is less than a certain threshold. One field is not fixed in the block, and a miner can vary this and compute corresponding hashes of each version of the block until one meets the threshold.
In comparison, the VRF is a deterministic function. It takes two inputs, a secret key for each user, and a commonly known string, that is fixed for each round and shared among all participants. This ensures that for each round, every time a user runs the VRF it receives always the same answer. It is therefore pointless to run it several times. This is what makes Algorand so fast: each user computes the VRF once per round and that’s it.
Sybil Attacks are Impossible in Algorand
Sybil attacks are a staple of blockchain research. Whenever a user has many tokens, it can divide them by many different accounts and pretend to be many users instead, in an attempt to get a vote for each account and multiply its voting power. This is impossible in Algorand. The lottery above is for token, not for user (the mathematical details enforcing this are not needed here). Even if you split 1 thousand tokens per 1 thousand different key pairs, and the total number of tokens is 1 million, the probability of each token being selected is still 1/1 000 000 for each token, which makes your probability of having a selected token equal to 1000. Exactly the same as if all the tokens were concentrated in one single account.
How Good is Algorand?
The above is a brief introduction to Algorand, focused on what I found its most interesting aspect, the sortition algorithm. There is more to the whole package that I have not described above:
- the incentives for users to participate in elections,
- recovering from network partitions,
- properly dealing with malicious leaders,
- network governance by voting of all users.
But taking the Algorand papers at their word, Algorand can resist up to 1/3 of all users to be malicious and can deal appropriately with fraudulent blocks and recover from partitions very quickly. It proposes a promising consensus model, that at the same time is scalable, secure and offers some degree of decentralization. The caveat here is, to my view, that those with more money control more of the network which could make it very centralized. This is very similar to how public companies are run by their shareholders (one share, one vote), but may offend some cryptocurrency purists who would like each individual to hold as much power as the next one.
I think this is disingenuous: as long as there is not a strong tie between real-world identity and accounts, you can’t avoid anyone disguising their identity behind many scattered secret/public keys. And there is also the argument that those who invest more in an enterprise should have more to say about it.
So overall, Algorand seems a balanced project to me. If I find other interesting projects and how they solve the blockchain trilemma, I’ll write about them in these pages.
Let me know what you think about Algorand, and whether you believe this is the solution to the scalability trilemma or whether there are more interesting consensus protocols out there.
As always, if you like this post, like below and please register for more regular updates.
See you soon for the next post. Until then, have a good time sailing the crypto-waters.
great post.