Lecture 21: Algorand¶

Throughout this course, we have studied four fundamental topics.

Cryptocurrencies and the blockchains within them, which enable financial transactions in a decentralized way, without the need to give your money to trusted intermediaries (aka, banks).
Broadcast protocols in the (a)synchronous setting, which enable consensus over the Internet without needing to rely on trusted intermediaries (aka, leaders).
Secure multi-party computation, which enables data analysis without the need to give your data to trusted intermediaries (aka, clouds).
Zero knowledge proofs, which enable the world to hold an entity (such as a bank, leader, cloud, or any one of us) accountable, without the need for trusted intermediaries (aka, auditors).

The first two topics provide integrity and availability, and the final two topics added confidentiality as a concern to protect.

Our objective today is to combine blockchains and Byzantine broadcast... or more precisely, Byzantine agreement.

Byzantine generals

Source:Wikipedia

This might sound strange! After all, a blockchain is just a continuously-running version of Byzantine agreement.

Remember the abstract definition of a blockchain protocol from Lecture 10.

Definition. Let's define a blockchain protocol (in the synchronous setting) as any interactive protocol that distributes a log. It must satisfy the following two properties:

Consistency: all parties have the "same" view of the linearly-ordered log. But since the chain may take some time to propagate, it's acceptable if some parties record a block in their chain before other ones do. Formally: for any pair of honest parties $i$ and $j$ and at any round $r$, it must be the case that party $i$'s log is a subset of party $j$'s log, or the other way around. (Note: these need not be proper subsets; the two parties could fully agree on the log.)
Liveness: there is some upper bound $\Delta$ on the number of rounds that it takes for a transaction to be included in the agreed-upon log. Formally: if an honest party receives a transaction $tx$ at some round $r$, then by the end of round $r + \Delta$ all honest parties' logs must include this transaction.

If you remember, back in Lecture 10 we constructed a blockchain from a broadcast protocol, in the synchronous setting.

Today, we will do something similar but in a (somewhat) asynchronous setting.

Our objective is to design a new way to select the "leader" who gets to mine the next block.

In Bitcoin, leader election is done via a proof-of-work puzzle. Bitcoin's system is nice because:

It guarantees consistency and liveness as long as the attacker doesn't control 51% of the mining resources.
It doesn't require knowing anybody's identity. That is, it is resistant to sybil attacks.

But in order to achieve these goals, Bitcoin is purposely designed to be:

Bounded, in that only a small number of transactions can be inserted in each block.
Slow, in that transactions take awhile to become finalized.
Computationally intensive, in order to distinguish the honest majority from the dishonest minority.

Back in January I showed this graph that the Bitcoin miners collectively perform about $295 \cdot 10^{18}$ hashes per second.

Nowadays the number is closer to $342 \cdot 10^{18}$ hashes per second... about 16% more.

[Image source: blockchain.info]

Today, we will investigate the cryptocurrency Algorand. It uses a proof of stake system to elect a leader, rather than proof of work.

Ethereum also uses a proof of stake mechanism. But Algorand's specific system uses a different set of tools from cryptography and distributed algorithms.

The result is that new blocks can be created and finalized in a matter of seconds (so it is fast), and using only the amount of energy on a typical laptop (so it is computationally unintensive).

In the remainder of today's lecture, I will use presentation slides from three sources:

Also, here is a link to the Algorand paper.