Analyses and comparisons of the consensus Consensus Protocols used in Blockchain - Nakamoto Consensus Protocols and it’s variations based on factors like fault tolerance, scalability and limitations
Microsoft Word - Consensus Protocol.docx 1 Survey of Consensus Protocols Abdul Wahab Faculty of Computer Science Institute of Business Administration Karachi, Pakistan
[email protected] Waqas Memood Faculty of Computer Science Institute of Business Administration Karachi, Pakistan
[email protected] 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 records 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 current 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 brief analysis. Keywords—Distributed ledger, consensus protocol, blockchain, cryptocurrency, 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 cryptocurrency 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 hobbyists and academics to enterprises i.e. IBM and Intel. From the emergence of Bitcoin in 2008, there are currently 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 researchers 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 being permissioned. Transactions are public and transparent but 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 breaches 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 referred 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 major 2 adjustments, others propose an entirely different mechanism to reach 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 readers 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-currency 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 resources. 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 current 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 based 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 requires the client to compute a challenge to utilize the server resources. 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 arbitrarily 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 resources. 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 revised in 2002 [7]. Client Puzzle is another implementation of the proof-of- work protocol proposed in 1999, which utilizes cryptographic countermeasures to