fault-tolerance are compartmentalized in the consensus protocol.

A consensus protocol involves a collection of parties, some of whom are honest, and follow the protocol, and some of whom are dishonest, and may depart from the protocol for any reason. Consensus is a notion that applies to a broad range of computational models. In some contexts, dishonest parties might simply halt arbitrarily (so-called crash failures), while in other contexts, they may behave arbitrarily, even maliciously (so-called Byzantine failures). In some contexts, parties communicate through objects in a shared memory, and in others, they exchange messages. Some contexts restrict how many parties may be dishonest, some do not.

In consensus, each party proposes a transaction to append to the ledger, and one of these proposed transactions is chosen. Consensus ensures agreement: All honest parties agree on which transaction was selected, termination: All honest parties eventually learn the selected transaction, and validity: The selected transaction is valid for that application.

Consensus protocols have been the focus of decades of research in the distributed computing community. The literature contains many algorithms and impossibility results for many different models of computation (see surveys in Attiya1 and Herlihy14).

Because ledgers are long-lived, they require the ability to do repeated consensus to append a stream of transactions to the ledger. Usually, consensus is organized in discrete rounds, where parties start round r + 1 after round r is complete. Of course, this shared-memory universal construction is not yet a blockchain, because although it is concurrent, it is not distributed. Moreover, it does not tolerate truly malicious behavior (only crashes). Nevertheless, we have already introduced the key concepts underlying blockchains.

Private blockchain ledgers. Alice
also owns a frozen yogurt parlor, and
her business is in trouble. Several re-
cent shipments of frozen yogurt have
been spoiled, and Bob, her supplier,
denies responsibility. When she sued,
Bob’s lawyers successfully pleaded
that not only had Bob never handled
if some parties misbehave, whether
accidentally or maliciously.
Blockchain ledger precursors. It is
helpful to start by reviewing a blockchain
precursor, the so-called universal con-
struction for lock-free data structures. 13
Alice runs an online news service.
Articles that arrive concurrently on
multiple channels are placed in an
in-memory table where they are in-
dexed for retrieval. At first, Alice used
a lock to synchronize concurrent ac-
cess to the table, but every now and
then, the thread holding the lock
would take a page fault or a sched-
uling interrupt, leaving the articles
inaccessible for too long. Despite the
availability of excellent textbooks on
the subject, 14 Alice was uninterested
in customized lock-free algorithms,
so she was in need of a simple way to
eliminate lock-based vulnerabilities.

She decided to implement her data structure in two parts. To record articles as they arrive, she created a ledger implemented as a simple linked list, where each list entry includes the article and a link to the entry before it. When an article arrives, it is placed in a shared pool, and a set of dedicated threads, called miners (for reasons to be explained later), collectively and repeatedly run a protocol, called consensus, to select which article to append to the ledger. Here, Alice’s consensus protocol can be simple: each thread creates a list entry, then calls an atomic compare-and swapb instruction to attempt to make that entry the new head of the list.

Glossing over some technical details, to query for a recent article, a thread scans the linked-list ledger. To add a new article, a thread adds the article to the pool, and waits for a miner to append it to the ledger.

This use of a black-box consensus protocol may seem cumbersome, and indeed, there are many ways it could be made more efficient, but it has two compelling advantages even without further optimization: First, it is universal: it can implement any type of data structure, no matter how complex. Second, all questions of concurrency and b The compare-and-swap instruction atomically compares a memory location’s contents with a given expected value and, if they match, updates that location’s contents to a new given value.

Cryptocurrencies
and blockchains
are very much in
the news.
Much of the
coverage is lurid,
sensationalistic,
and irresistible.