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.