tion δ. To do so, when a process invokes
append(X), X consists of a transition
to be applied to the state machine. The
state of the object is obtained through
a read() invocation, which returns
the sequence of operations which have
been sequentially appended to the ledger, and then locally applying them
starting from the initial state of the object (see Raynal37 for more details).
Three remarkable properties. The
apparently innocent idea of a read()
operation that returns the list of commands that have been applied to the
state machine, opens the discussion of
one of the remarkable points of distributed ledgers that has brought them to
such wide attention. The possibility of
guaranteeing a tamperproof list of commands. The blockchain implementation is by using cryptographic hashes
that link each record to the previous one
(although the idea has been known in
the cryptography community for years).
The ledger implementation used in
Bitcoin showed it is possible to have a
state machine replication tolerating
Byzantine failures that scales to hundreds of thousands of processes. The
cost is temporarily sacrificing consistency—forks can happen at the end of
the blockchain, which implies that the
last few records in the blockchain may
have to be withdrawn.
The third remarkable property
brought to the public attention by distributed ledgers is the issue of who
the participants can be. As opposed to
classic algorithms for mastering concurrency through sequential thinking,
the participants do not have to be a pri-ori-known, can vary with time, and may
even be anonymous. Anyone can append a block and read the blockchain
(although there are also permissioned
versions where participants have to be
registered, and even hybrid models). In
a sense, a distributed ledger is an open
distributed database, with no central
authority, where the data itself is distributed among the participants.
Agreement in dynamic, Byzantine sys-
tems. Bitcoin’s distributed ledger im-
plementation is relatively simple to ex-
plain in the framework of state machine
replication. Conceptually it builds on
randomized consensus (something
that had already been carefully studied
in traditional approaches, as noted in
the sidebar “Circumventing Consensus
it has previously invoked M.LL(). The
operation M.LL() is a simple read of
M which returns the current value of
M.LL(). When a process pi invokes
M.SC(v) the value v is written into M if
and only if no other process invoked
M.SC() since its (pi) last invocation of
M.LL(). If the write succeeds
turns true, otherwise it returns false.
Algorithm 6 is a simple implementation of consensus from the pair of
operations LL/SC, which tolerates any
number of process crashes.
In the sidebar “Universal Construction Based on LL/SC,” there is a shared-memory, LL/SC based universal construction.
15 Looking at the algorithm,
one begins to get a feeling for the distributed ledgers discussed next.
Since ancient times, ledgers have been
at the heart of commerce, to represent
concurrent transactions by a permanent
list of individual records sequentialized
by date. Today we are beginning to see
algorithms that enable the collaborative
creation of digital distributed ledgers
with properties and capabilities that go
far beyond traditional physical ledgers.
All participants within a network can
have their own copy of the ledger. Any of
them can append a record to the ledger,
which is then reflected in all copies in
minutes or even seconds. The records
stored in the ledger can stay tamper-proof, using cryptographic techniques.
Ledgers as universal constructions.
Mostly known because of their use
in cryptocurrencies, and due to its
the perspective of this paper a
distributed ledger is a byzantine fault-tolerant
replicated implementation of a specific ledger object. The ledger object
has two operations, read() and append(). Its sequential specification
is defined by a list of blocks. A block
X can be added at the end of the list
with the operation append(X), while
a read() returns the whole list. In the
case of a cryptocurrency, X may contain
a set of transactions.
Thus, a ledger object, as any other
object, can be implemented using a
Byzantine failures-tolerant state machine replication algorithm. Conversely, a ledger can be used as a universal
construction of an object O defined by
a state machine with a transition func-
is digital objects.