Microsoft Word - Consensus Protocol.docx
1
Survey of Consensus Protocols
Abdul Wahab
Faculty of Computer Science
Institute of Business Administration
Karachi, Pakistan
XXXXXXXXXX
Waqas Memood
Faculty of Computer Science
Institute of Business Administration
Karachi, Pakistan
XXXXXXXXXX
Abstract-- Distributed ledger technology has gained wide
popularity and adoption since the emergence of bitcoin in
2008 which is based on proof of work (PoW). It is a
distributed, transparent and immutable database of
ecords of all the transactions or events that have been
shared and executed among the participants. All the
transactions are verified and maintained by multiple nodes
across a network without a central authority through a
distributed cryptographic mechanism, a consensus
protocol. It forms the core of this technology that not only
validates the information appended to the ledger but also
ensures the order in which it is appended across all the
nodes. It is the foundation of its security, accountability and
trust. While many researchers are working on improving
the cu
ent protocol to be quantum resistant, fault-tolerant,
and energy-efficient. Others are focused on developing
different variants of the protocol, best suited for specific use
cases. In this paper, we shall review different consensus
protocols of distributed ledger technologies and their
implementations. We shall also review their properties,
concept and similar-work followed by a
ief analysis.
Keywords—Distributed ledger, consensus protocol,
lockchain, cryptocu
ency, block-less ledger,
permissioned and permission less ledger.
I. INTRODUCTION
Distributed ledger technologies have revolutionized the
world by transforming the existing systems to become more
secure, reliable and scalable. It forms a system that provides a
trustworthy ledger among a group of nodes across a network
that doesn’t fully trust each other [1]. Distributed ledgers
especially blockchain has been conceived as a provider of
cryptocu
ency but it has found its applications in different
sectors including finance, academics, IoT, industries, and etc.
That is why, we have witnessed an exponential adoption of this
technology over the last few years. This has also raised the
interest in the distributed ledger development community,
which has scaled from ho
yists and academics to enterprises
i.e. IBM and Intel. From the emergence of Bitcoin in 2008,
there are cu
ently many active development variants of this
technology i.e. Ethereum, Hyperledger, Tangle, Corda, and etc.
[2]
All these variants differ in the way they choose to reach the
consensus, which helps a distributed ledger to function fairly,
securely and efficiently. A consensus protocol, which is the
core of the distributed ledger, performs two tasks: it guarantees
that the next block of the network is the only version of the
truth, and it protects the network from adversarial influences on
the nodes and the network [1] [3]. It allows the network to
confirm the transactions without relying on the intermediaries
i.e. central authority. A consensus protocol makes a ledger
functional and a flaw in the protocol will fail the accountability
of the ledger. That is why, it owns a significant interest of the
esearchers and the industry. It also defines the nature of the
distributed ledger which could be public, private or
consortium/federated [4]. Another popular classification is
permissioned and permissionless protocols.
Public ledger has no authority authorizing a transaction on
the ledger. Anyone can join as a public node, validate
transactions and participate in the consensus process without
eing permissioned. Transactions are public and transparent
ut the identity of the participants remain anonymous. Private
ledger works with designated participants who are empowered
to authorize transactions. Since data is unavailable for public
view, it is ideal for implementation of data privacy rules and
other regulatory compliance. However, this puts the system at
the risk of security
eaches just like in a centralized system for
which it is argued that it is not a distributed ledger. Participants
are identifiable in these systems but transactions remain
encrypted and private. Consortium ledger is partially private
ledger with the only difference lies in governance as the ledger
is operated under the leadership of a group, not an entity. This
way it provides all the benefits of the private chain without
consolidating power to an individual and is also refe
ed to as
partial decentralized. [1] [4] [5]
The first consensus protocol of distributed ledger
technology was proof-of-work (PoW) which powers the
Bitcoin-Blockchain. It is based on a hash puzzle which is not
only intensively resource consuming but also performs useless
hashing. Also, it is not quantum proof and is subjected to
various security threats of the future. That is why many
different variants of the consensus protocols have been
proposed and adopted. While some variants are the derivation
of the existing protocols offering both minor and majo
2
adjustments, others propose an entirely different mechanism to
each the consensus. But collectively, they all are striving to
develop an ideal fault-tolerant and resilient consensus protocol
that not only protects the network from the present and future
security attacks but also enforces an efficient and scalable
implementation of its application.
The purpose of this paper is to provide an overview of some
of the famous public, private and permissioned consensus
protocols. The paper is organized as follows; To familiarize the
eaders with the subject, we will overview the history of the
consensus protocol in Section II. In Section III, we will survey
different consensus protocols, their properties, concept,
implementations, analysis and use cases. We will also identify
and discuss multiple variations of these protocols as similar
work under the same section. Finally, in Section IV, we will
conclude the paper by discussing how consensus protocols
differ in their working and implementation which makes them
ideal for specific use cases.
II. BACKGROUND OF CONSENSUS PROTOCOL
Bitcoin is the first crypto-cu
ency which was introduced
in 2009 and uses proof-of-work as its consensus protocol [6].
The protocol forms the mining algorithm, avoids double
spending and other attacks. The idea of a consensus protocol
was inspired from the Adam Back's Hash cash, published as an
improved revision of his previous paper in 2002, which
proposed a protocol to prevent email spam and denial of service
attacks [7]. In this section, we will visit the founding idea of
proof-of-work, its evolution and different use cases till bitcoin.
The original idea of proof-of-work dates back to 1992, in
which a group of authors presented a strategy to combat junk
emails [8]. It utilizes different cost functions which are hard to
compute and must be computed in order to gain access to the
esources. This idea not only prevented the huge consumption
of resources but also introduced the notion of using
cryptography to increase the scarcity of a resource. The general
idea of the paper was to bind each resource i.e. fax to a
‘resource id’, which can be obtained by computing a cost
function. Unlike cu
ent proof of work model, it is not
anonymous and saves user credentials for logging purpose.
Next idea came in the form of PayWord and MicroMint,
two simple micropayments schemes, were presented by Ronald
and Adi in 1996. They first discussed the faster computation of
hash function as compared to public-key generation which is
10,000 times slower. Also, the verification of hash-based
functions is 100 times faster as compared to the public-key
cryptography [9]. The efficiency and performance of hash
function over public-key cryptography techniques have
welcomed possibilities for micropayments, which were not
feasible earlier because the cryptography computation cost of
the payment exceeds the payment itself. PayWord is a credit
ased micropayment scheme powered by a chain of hash values
known as ‘paywords’. MicroMint is another micropayment
scheme implementation which is based on hash functions. The
scheme comes with an exceptional performance but weaker
security as compared to RSA based implementation.
In 1997, Matthew and Dahlia used the notion of proof-of-
work for metering the popularity of the websites [10]. Website
administrators can fraud the visit count of the website and
charge higher rates for advertisement. By using robot programs
or other tools, an individual can easily generate fake visit
counts on a website. The paper introduced a timing function
that is computed incrementally and whose result can be verified
efficiently. Each visitor is asked to calculate a moderately hard
cryptographic function to log its visit on the website server. To
forge visit logs, a considerable amount of resource is required
which is proportional to the amount of fraud. The output of the
cryptographic function is stored on the server for accountability
and auditability of website hits. The difficulty of the timing
function which leads to resources consumption, security,
accuracy and auditable metering mechanism.
Hashcash [11] implemented the proof-of-work protocol in
terms of money that represents the burnt CPU cycle calculated
as an n-bit partial hash collision. It was proposed as a software
package by Adam Back in 1997 [11]. It offered a systematic
countermeasure for denial of service attacks, junk emails and
abuse of un-metered internet resources [11]. The protocol
equires the client to compute a challenge to utilize the server
esources. Partial hash collision requires the client to keep
computing random hashes until a hash whose n-bits matches
the target hash. It gives the control to a
itrarily alter the
difficulty of the cost function by changing the number of bits
to match, where one increasing bit makes the computing twice
as difficult. As the machines get faster and efficient, the
difficulty of the cost function can be adjusted accordingly. Its
primary use case is to throttle the abuse of un-metered internet
esources. To utilize a recourse or service i.e. email, the client
must provide hashcash token, which results in an output of
computing the cost function. An application of hash cash is to
slow the spamming by generating a token for each email sent.
Each token also has an expiry date to avoid accumulation of
token and depleting resources all at once. Hashcash was further
evised in 2002 [7].
Client Puzzle is another implementation of the proof-of-
work protocol proposed in 1999, which utilizes cryptographic
countermeasures to