Algorand: a new consensus agreement for distributed ledgers

The excellent website CoinDesk recently published a story about an italian computer scientist worth to read by anyone interested in Blockchains and Distributed Ledgers. His name is Silvio Micali, an MIT professor and a Turning Award winner. The article is interesting for the new protocol that is proposed by Dr. Micali to solve the current scaling problems of blockchains and cryptocurrencies such as Bitcoin.

The name of the protocol proposed by Silvio Micali is Algorand, which appear also in the title of the following a long paper by the same author and that we will briefly review here today for The Information Age.

Before that here it is some quotes from the CoinDesk article, serving as an appetizer and context framer.

If a public blockchain is to be successful — whether its use is for currencies, smart contracts or something else entirely — it needs a consensus algorithm that can scale.

While the race is on to develop a system that can do just that, a recent design by an eminent scholar could mark an advancement in this long-held quest. That design is called algorand, and its creator is MIT professor Silvio Micali.

A cryptographer and computer theorist, Micali is known for his work in pseudo-random numbers and zero-knowledge proofs (the basis for the zk-SNARKS that power the anonymous blockchain project zcash). He is also the co-winner of the Turing Award (aka the “Nobel Prize” of computing).

(…)

In bitcoin, miners race to solve a cryptographic puzzle. The winner proposes the next block and earns a block reward.

But bitcoin’s proof-of-work (often referred to as “Nakamoto consensus” after its pseudonymous creator) results in the expenditure of an exorbitant amount of energy. Some say that it’s also led to a centralization of bitcoin’s processing, meaning only a few, large entities are able to claim new bitcoins.

In an attempt to democratize this distribution, algorand uses what Micali calls “cryptographic sortition” to select players (maybe a few hundred in a system with as many as a million users) to create and verify blocks.

(…)

Micali borrowed the idea from the ancient Athens, where political officials were chosen at random in a process known as “sortition“. (It was essentially a way of putting everyone’s name into a big hat and pulling out a few names.)

By employing cryptographic sortition, the theory is that algorand can scale on demand. Other benefits include security and speed.

“The system has to be fast,” Micali said. “I don’t want any proof-of-work, and I don’t want an excessive communication.”

The current blockchain protocols, being elegant and impressive software architecture achievements by their own, are plagued by the scaling problem stemming from a limitation with the Byzantine agreement schedule: this agreement becomes cumbersome slow as the number of  agents (nodes) requesting a communication message increases. Dr. Micali believes, and this is only a theoretical speculation at this stage, that Algorand could solve the issue:

Conceived in the 1980s, Byzantine agreement offers a way to reach consensus in a distributed system where none of the nodes can be trusted. In such a design, the system can tolerate up to one-third of the players working against the system.

Byzantine agreement has two properties: If all the players start with the same value, they agree on that value. And, if the players start with different values, all honest players (those who comply with the protocol) will agree on one value. On the blockchain, those values are the candidate blocks and the players are verifiers.

A problem with traditional Byzantine agreement, however, is that it requires many rounds of intense communication between all players, making it difficult to scale the system.

“I cannot run Byzantine agreement with 1 million users or 10 million users or, if a successful system, 100 millions users. It is too much,” Micali said.

To remedy that, he developed a modified version.

(…)

In algorand, a small subset of players run Byzantine consensus on behalf of the entire system. That allows the protocol to be run at higher speeds, and as more players are replaced in each step, the idea is it makes the system secure in an adversarial environment.

This is how Micali’s Byzantine agreement works: Coin holders self-select to be verifiers in the first round. Those verifiers send out their messages along with their credentials to the network.

Now that they have revealed themselves, a resourceful adversary could easily corrupt them. But that doesn’t matter, because once the message is out of the bottle, there is no way to put it back.

“The adversary can no more do this than the government can put back in the bottle a message of Wikileaks. They can arrest him, put him in prison, but that message is now propagated on the network,” said Micali.

Needless to say at this point some eyebrows would be raised by the official regulatory establishment, to say the least about the practical feasibility of the protocol within a real systems testing. Also there might still be issues of different consensus agreements, with different protocol architectures and designs, all functioning within ever more constrained environments. The Ethereum’s several forks events have shown that security within these protocols is still a work in progress, and my intuition leans to the view that a more diverse ecosystem of protocols is good for… malicious hackers, as much as it is good for the efficiency of the protocols. Nevertheless Algorand is a proposal promising to make network forks unnecessary in the event of consensus difficulties. It is still not confirmed that such fact would be a security enhancement or otherwise.

ALGORAND: The Efficient and Democratic Ledger

Abstract

A public ledger is a tamperproof sequence of data that can be read and augmented by everyone. Public ledgers have innumerable and compelling uses. They can secure, in plain sight, all kinds of transactions —such as titles, sales, and payments— in the exact order in which they occur. Public ledgers not only curb corruption, but also enable very sophisticated applications —such as cryptocurrencies and smart contracts. They stand to revolutionize the way a democratic society operates. As currently implemented, however, they scale poorly and cannot achieve their potential. Algorand is a truly democratic and efficient way to implement a public ledger. Unlike prior implementations based on proof of work, it requires a negligible amount of computation, and generates a transaction history that will not fork with overwhelmingly high probability. Algorand works with traditional blockchains, but also puts forward alternative and more efficient ways to structure blocks of data, which may be of independent interest.

silvio
Move over Bitcoin – MIT Cryptographer Silvio Micali and his Public Ledger ALGORAND… The Future of Blockchain?

This is long 70 plus page paper. I won’t review it fully here, that would be infeasible for a Blog like this. But I highlight some of the most relevant points and the main conclusion drawn by the author. The readers are always encouraged to read it fully and submit comments, if appropriate. A common recommendation by The Information Age.

1. New Byzantine Agreement. Algorand replaces proof-of-work consensus with a stronger form of Byzantine agreement [15]. Informally, Byzantine agreement (BA) is a communication protocol enabling a set of players, each of which holds a possibly different initial value, to agree on a single value v. Such agreement is reached by all honest players —that is, by those who scrupulously follow the protocol— despite the fact that a minority of the players are malicious and can deviate from the protocol in an arbitrary and coordinated manner. In our case, the initial values are candidate blocks, and the block on which agreement is reached is certified by the digital signatures of a sufficient number of players, and then propagated through the network, so that all users can add it to the blockchain. As we shall see, we do not just rely on existing Byzantine agreement protocols, but put forward a new BA protocol that is much faster than all previous ones, and enjoys a novel property, player replaceability, that makes it very secure in our very adversarial environment.

2. Cryptographic Sortition. Although very fast, the new BA protocol would still be unwieldy if played by all users in the system. Accordingly, we choose its players to be a much smaller subset of the set of all users. To avoid a different kind of concentration-of-power problem, each new block Bˆr will be constructed and agreed upon, via our new BA protocol, by a separate set of selected verifiers, SVˆr . In principle, selecting such a set might be as hard as selecting Br directly. We traverse this potential problem by an approach that we term, embracing the insightful suggestion of Maurice Herlihy, cryptographic sortition. Sortition is the practice of selecting officials at random from a large set of eligible individuals [33]. Sortition was practiced across centuries: for instance, by the republics of Athens, Florence, and Venice. In modern judicial systems, random selection is often used to choose juries. In our distributed system, however, choosing the random coins necessary to randomly select the members of each verifier set SVˆr is already problematic. We thus resort to cryptography in order to select each verifier set, from the population of all users, in a way that is guaranteed to be automatic (i.e., requiring no message exchange) and random. In essence, we use a cryptographic function to automatically determine, from the previous block Bˆ(r−1) , the verifier set SVˆr in charge to choose the next block Bˆr . Since malicious users can affect the composition of Bˆ(r−1) (e.g., by choosing some of its payments), we specially construct and use additional inputs so as to prove that the verifier set SVˆr is indeed randomly chosen.

The author disclose the two main challenges that ALGORAND might encounter:

Two Main Challenges Our main challenges are that:

(a) Our setting is permissionless. New users can join Algorand at any time they want.

(b) Our adversary is dynamic and very powerful. Our adversary can instantaneously corrupt any user he wants, at any time he wants (subject only to a total “budget”), and perfectly coordinate all malicious users. In particular, he can corrupt the entire, randomly selected, verifier set SVˆr , as soon as it becomes known.

Conclusion

Algorand is a proof-of-stake inspired kind of Blockchain protocol. The author recognizes though that the Bitcoin proof-of-work has gained the most share of attention in research circles. But the kind of consensus agreement protocols similar to Algorand will certainly increase on both business adoption and further computer science advanced research. This is a trend already in place with consortiums such as Hyperledger  or R3CEV.

Closely related work:

Bitcoin has inspired a tremendous amount of research. Most of the literature based on proof-of-work is quite orthogonal to our approach. Our approach, however, is a kind of proof of stake [6], in the sense that users with more money have a proportionally higher “voting power”. The work closest to ours is that of Bentov, Pass and Shi, which appeared last September in the e-print archive [?]. They also replace proof of work with Byzantine agreement, and use hash functions to select leaders.

(…)

Accordingly, running Algorand 0 3 with the help of a PV-Network might be simple and attractive. The users need only to protect their own secret signing key, and enjoy a very fast, secure, convenient, and reasonably distributed system, in which they can choose a potential verifier to partner with in order to participate in the rewards. The potential verifiers may appreciate operating in a controlled network, and unlike in —say— a credit-card system— not be responsible for protecting any sensitive data of someone else.

featured image: Move over Bitcoin – MIT Cryptographer Silvio Micali and his Public Ledger ALGORAND… The Future of Blockchain?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s