Scaling Consensus? This Turing Winner Thinks He's Found a Way

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).

But while Micali has impressive credentials, his technology also holds big promise. Algorand is a variation of proof-of-stake that uses cryptography to randomly select the players involved in adding the next block (or set of transactions) to the blockchain.

If algorand is successful, Micali believes his system could easily handle millions of nodes – presenting a solution to one of biggest problems in blockchain today.

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 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 to create and verify blocks.

While most proof-of-stake systems rely on some type of randomness, algorand is different in that you self-select by running the lottery on your own computer. The lottery is based on information in the previous block, while the selection is automatic (involving no message exchange) and completely random.

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."

Because algorand’s computational requirements are trivial, anyone can run the system on their laptop in the background. And while bitcoin has classes of users ('consumers' who transact and 'miners' who search for blocks), algorand makes no such distinction.

The vision is that all users would have the same access to the network.

Similar to other proof-of-stake systems, your chance of being selected for a reward is based on the number of coins (algos) you own or otherwise set aside. The more algos you have, the better chance you have of getting picked.

Once you know you are selected as a proposer, you create a block and then propagate it to the network along with a hash proof (a random number easily verified by a digital signature), saying essentially, "Here is my block, and here is proof that I won the lottery."

The proposer with the smallest hash proof (again, random) is the one to present the next candidate block.

The next step in the algorand process is to verify that candidate block and — in the event a block proposer has proposed two or more blocks — insure there is no fork in the chain.

And for that, Micali turns to a decades-old protocol.

One byproduct of Nakamoto consensus is the possibility of network forks, a process that occurs anytime two miners solve the network puzzle at nearly the same time.

As a result, users generally wait 30 minutes (three blocks down the road) to be reasonably sure a transaction has gone through.

"And now you have to deal with a fork, and that creates some anxiety, psychologically and otherwise, because a block is not final, and people need the finality," said Micali.

The way algorand deals with that ambiguity is to reach consensus on one block with a negligible probability of forks. The system does this by employing a modified version of the Byzantine consensus algorithm.

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 with only nine expected steps.

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.

Put simply, Micali’s Byzantine agreement works like this: 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.

And so, even if an adversary does succeed in corrupting the verifiers, it is too late. A new set of players has already self-selected for the next round of communication, and the process continues for eight more rounds until a common agreement is reached.

Once agreement is reached, and the block is certified by the signatures of a sufficient number of players in the last step of byzantine agreement, that block is then gossiped through the network so all users in the system can add it to the blockchain.

Since the only real latency in the system is based on propagating that block through the network, Micali has set his block size at 1MB. When networks get faster, it is possible to increase the block size without any security risks, he contends.

That said, Micali doesn't think algorand will replace bitcoin. He feels different systems can exist concurrently.

Even bartering still exists today, so there is no reason to think bitcoin won't exist in the future, he argues. But he does feel strongly that its energy waste is unnecessary.

"Somehow people make the analogy that when you are digging for gold you also waste energy. The fact that gold was mined that way with a lot of waste doesn't mean we should destroy the planet because our ancestors did," he said.

He also makes the point that algorand is intended to serve as a consensus protocol for all types of blockchain systems, not just cryptocurrencies.

Much like its name, though, algorand exists as a theoretical protocol.

For now, Micali said he is hammering out technical issues in the hopes that, one day soon, they can be put to the test.

Image via Amy Castor for CoinDesk