A blockchain is a distributed ledger of records called as blocks. These blocks are linked using cryptographic hash. Each block contains a hash of the previous block, a timestamp, and transaction data. Consensus layer is the main layer in Blockchain Architecture, in which consensus protocol is configured to decide how new block is added in blockchain. Consensus algorithm solves the problem of trust in blockchain. Consensus algorithms can be classified into two classes. The first class is voting-based consensus, which requires nodes in the blockchain network to broadcast their results of mining a new block or transaction, before appending the block to blockchain. The second class is proof-based consensus, which requires the nodes joining the blockchain network to solve and mathematical puzzle to show that they are more eligible than the others to do the appending or mining work. Performance of blockchain can be increased with the use of suitable consensus algorithm. However, theory and data support for the selecting suitable consensus in private blockchain is very limited. This paper contributes theory and data used for selecting suitable consensus algorithm and would help researchers for further exploring of consensus in private blockchain environment.
Popular blockchain such as Ethereum and several others execute complex transactions in blocks through user defined scripts known as smart contracts. Normally, a block of the chain consists of multiple transactions of smart contracts which are added by a miner. To append a correct block into blockchain, miners execute these smart contract transactions (SCT) sequentially. Later the validators serially re-execute the SCT of the block. In the current era of multi-core processors, by employing serial execution of the transactions, the miners and validators fail to utilize the cores properly and as a result have poor throughput. By adding concurrency using object semantics to smart contracts execution, we can achieve the better efficiency and higher throughput. Some authors have used read-write STMs (RWSTMs) for the concurrent execution of SCT. Working with higher level operations provide greater concurrency, better throughput and reduces the number of aborts than RWSTMs. In this paper, we develop an efficient framework to execute the SCT concurrently by miner using optimistic Object-Based Software Transactional Memory systems (OSTMs) and Multi-Version OSTMs (MV-OSTM). A proposed block includes SCT, final states of the shared data-items, hash of the previous block and a block graph (BG). BG captures the conflicting relations among the transactions. Later, the validators re-execute the same SCT concurrently and deterministically with the help of BG given by miner to verify the final state. If the validation is successful then proposed block appended into the blockchain and miner gets incentive otherwise discard the proposed block. MV-OSTM and OSTM miner performs 4.5x and 3.86x average speedups over serial miner. Along with, MV-OSTM and OSTM validator outperforms average 32.81x and 29.76x than serial validator.
We present a general consensus framework that allows to easily introduce a customizable Byzantine fault tolerant consensus algorithm to an existing (Delegated) Proof-of-Stake blockchain. We prove the safety of the protocol under the assumption that less than 1/3 of the validators are Byzantine. The framework further allows for consensus participants to choose subjective decision thresholds in order to obtain safety even in the case of a larger proportion of Byzantine validators. Moreover, the liveness of the protocol is shown if less than 1/3 of the validators crash. Based on the framework, we introduce Lisk-BFT, a Byzantine fault tolerant consensus algorithm for the Lisk ecosystem. Lisk-BFT integrates with the existing block proposal mechanism, requires only two additional integers in blocks and no additional messages. The protocol is simple and provides safety in the case of static validators if less than 1/3 of the validators are Byzantine. For the case of dynamically changing validators, we prove the safety of the protocol assuming a bound on the number of Byzantine validators and the number of honest validators that can change at one time. We further show the liveness of the Lisk-BFT protocol for less than 1/3 crashing validators.
Andrew Cullen, Pietro Ferraro, Christopher King, Robert Shorten
Distributed ledgers have been proposed for a number of applications in the Internet-of-Things domain where it is essential to have an immutable and irreversible record of transactions. Directed acyclic graph (DAG)-based architectures, in particular, seem to provide a vast array of advantages over the more traditional Blockchain; however, it can be challenging to conduct a thorough analysis of DAG-based ledgers and derive reliable performance guarantees. In this article, we analyze one commonly discussed attack scenario known as the parasite chain attack, which aims at disrupting the immutability and irreversibility of the ledger, in the context of the IOTA Foundation's DAG-based system. Using a Markov chain model, we study the vulnerabilities of IOTA's core tip selection method against this attack and we present an extension of the algorithm to improve the resilience of the ledger in this scenario.
Andrew Cullen, Pietro Ferraro, Christopher King, Robert Shorten
Directed Acyclic Graph (DAG) based Distributed Ledgers can be useful in a number of applications in the IoT domain. A distributed ledger should serve as an immutable and irreversible record of transactions, however, a DAG structure is a more complicated mathematical object than its blockchain counterparts, and as a result, providing guarantees of immutability and irreversibility is more involved. In this paper, we analyse a commonly discussed attack scenario known as a parasite chain attack for the IOTA Foundation DAG based ledger. We analyse the efficacy of IOTA core MCMC algorithm using a matrix model and present an extension which improves the ledger resistance to these attacks.
Holger Kinkelin, Heiko Niedermayer, Marc MĂŒller, Georg Carle
Configuration management in networks with highest security demands must not depend on just one administrator and her device. Otherwise, problems can be caused by mistakes or malicious behavior of this admin, or when her computer got compromised, which allows an attacker to abuse the administrator's far-reaching permissions. Instead, we propose to use a reliable and resilient configuration management process orchestrated by a configuration management system (CMS). This can be achieved by separation of concerns (proposing a configuration vs. authorizing it), employing multi-party authorization (MPA), and enforcing that only authorized configurations can be deployed. This results in a configuration management process that is decentralized on a human, decision-making level, and a technical, device level. However, due to different opinions or adversarial interference, the result of an MPA process can end in a conflict. This raises the question how such conflicts can be mediated in a better way than just employing majority voting, which is insufficient in certain situations. As an alternative, this paper introduces building blocks of customizable conflict mediation strategies which we integrated into our CMS TANCS . The conflict mediation functionality as well as the initial TANCS implementation run on top of the distributed ledger and smart contract framework Hyperledger Fabric which makes all processes resilient and tamper-resistant.
YaoâChieh Hu, TingâTing Lee, Dimitris Chatzopoulos, Pan Hui
Summary Although the primary function of distributed ledgers is to store data related to users' interactions, their capabilities allow them to offer more sophisticated functionalities. Advances in blockchain technologies introduced smart contracts , software programs that define immutable rules as functions stored on the blockchain and can be executed on demand. Smart contracts can interact not only with users but also with each other via message exchange. We compare existing smart contract interactions, and develop an architecture for asynchronous state consensus, a novel type of smart contract interaction required in applications but had rarely been addressed. The proposed architecture is composed of two types of smart contracts, ie, Custodian and Client. Client smart contracts serve as network participants reaching a particular consensus collectively by forming a cluster and issuing votes towards a final state agreement. Custodian smart contracts serve as the arbiters that aggregate and calculate voting results as the finalized state consensus that is shared across the network. To test the feasibility of our proposal, we conduct experiments on the consensus reaching latency and the scalability under different network configurations with standardized Amazon Web Service instances. Lastly, we discuss the robustness our proposal concerning Byzantine Fault tolerance and list possible applications. In the gaming industry, an ERC721 smart contract does not allow contrasting structural features between individual tokens, yet only minor valueâlevel differences. The proposed solution can address the need for character diversity that characters can be created and attached to a gaming smart contract after deployment, which enables fine distinction between characters. The proposal can also achieve sharing states across smart contracts, such as the jackpot, which renovates the flexibility of blockchain gaming.
In this paper, we formulate the consensus problem and its solutions as seen in public blockchains and contrast them to those of the traditional distributed consensus. The Proof of Work (PoW) algorithm introduced in Bitcoin provides the first elegant and practical solution for reaching distributed consensus in a large-scale untrusted environment. Due to the enormous energy cost of PoW, many alternative consensus algorithms have been proposed for public blockchains aiming at drastically reducing the energy consumption for reaching consensus. We examine four blockchain consensus algorithms, namely Proof of Work, Proof of Stake, Proof of Space, and Proof of Elapsed Time, with respect to the consensus model we have formulated and point out the challenges of adopting them in public blockchains.
Summary Proof of stake (PoS) protocols rely on voting mechanisms to reach consensus on the current state. If an enhanced majority of staking nodes, also called validators , agree on a proposed block, then this block is appended to the blockchain. Yet these protocols remain vulnerable to faults caused by validators who abstain either accidentally or maliciously. To protect against such faults while retaining the PoS selection and reward allocation schemes, we study weighted voting in validator committees. We formalize the block creation process and introduce validators' voting profiles which we update by a multiplicative weights algorithm relative to validators' voting behavior and aggregate blockchain rewards. Using this framework, we leverage weighted majority voting rules that optimize collective decision making to show, both numerically and analytically, that the consensus mechanism is more robust if validators' votes are appropriately scaled. We raise potential issues and limitations of weighted voting in trustless, decentralized networks and relate our results to the design of current PoS protocols.
Summary We present an overview of hybrid Casper the Friendly Finality Gadget (FFG), a proofâofâstake checkpointing protocol overlaid onto Ethereum's proofâofâwork blockchain. We describe its core functionalities and reward scheme and explore its properties. Our findings indicate that Casper's implemented incentives mechanism ensures liveness, while providing safety guarantees that improve over standard proofâofâwork protocols. On the basis of a minimal impact implementation of the protocol as a smart contract on the blockchain, we discuss additional issues related to parametrization, funding, throughput, and network overhead and detect potential limitations.
Mohammad M. Jalalzai, Costas Busch, Golden G. Richard
Byzantine Fault Tolerant (BFT) consensus exhibits higher throughput in comparison to Proof of Work (PoW) in blockchains. But BFT-based protocols suffer from scalability problems with respect to the number of replicas in the network. The main reason for this limitation is the quadratic message complexity of BFT protocols. Previously, proposed solutions improve BFT performance for normal operation, but will fall back to quadratic message complexity once the protocol observes a certain number of failures. This makes the protocol performance unpredictable as it is not guaranteed that the network will face a a certain number of failures. As a result, such protocols are only scalable when conditions are favorable (i.e., the number of failures are less than a given threshold). To address this issue we propose Proteus, a new BFT-based consensus protocol which elects a subset of nodes $c$ as a root committee. Proteus guarantees stable performance, regardless of the number of failures in the network and it improves on the quadratic message complexity of typical BFT-based protocols to $O(cn)$, where $c<<n$, for large $n$. Thus, message complexity remains small and less than quadratic when $c$ is asymptotically smaller than $n$, and this helps the protocol to provide stable performance even during the view change process (change of root committee). Our view change process is different than typical BFT protocols as it replaces the whole root committee compared to replacing a single primary in other protocols. We deployed and tested our protocol on $200$ Amazon $EC2$ instances, with two different baseline BFT protocols (PBFT and Bchain) for comparison. In these tests, our protocol outperformed the baselines by more than $2\times$ in terms of throughput as well as latency.
Ibrahim Ahmed I. AlMallohi, Ahmed Saad M. Alotaibi, Rahaf Alghafees, Farzana Azam · 5 authors
Proof-of-Stake (PoS) is getting popularity among low power computing devices as compared to high power and energy demanded proof-of work (PoW). Among the security issues of PoS, Long range attack is declared as one of the major issue by many researchers. Long range attack allows the minority stakeholders to become majority stakeholders over a long time span and then they can control the whole blockchain protocol to produce the valid alternative history. Checkpointing is referred as solution to mitigate the impact of the long range attack but still for the newly joined users as well as the users those will stay offline for long period of time, checkpointing mechanism needs to be re-evaluated. In this paper we studied the checkpointing mechanism and proposed a new strategy to implement the checkpointing inside the blockchain technology. The proposed strategy is designed specifically to mitigate the long range attack or stake bleeding attack.
Information fusion has been a topic of immense interest owing to its applicability in various applications. This brings to the fore the need for a flexible and accurate fusion algorithm that can be versatile. The BrooksâIyengar algorithm is one such fusion algorithm. It has since its inception found numerous applications that deal with the fusion of data from multiple sources. The uniqueness of the BrooksâIyengar algorithm is the ease with which the data from multiple sensors in a local system can be fused and also reach consensus in a distributed system with the added capability of fault tolerance. Blockchain has found its use as a distributed ledger and has successfully supported and fueled many crypto-currencies over the years. Information fusion with regards to Blockchains is a topic of great research interest in the past couple of years. Since blockchain has no official node, the introduction of a decentralized network and a consensus algorithm is required in making the interactions and exchanges between multiple suppliers easier and thus leads to business being carried out without any hassles. In this paper, we attempt to understand and describe the deployment of multiple sensors to measure various aspects of the physical world. We discuss a novel technique of employing the BrooksâIyengar algorithm in the design of the system that would decentralize the data source from the corresponding measurements and thus ensure the integrity of the transactions in the Blockchain. Finally, a theoretical analysis of the performance of the algorithm when used in a blockchain based decentralized environment is also discussed.
Open access
Distributed systems and fault tolerance
Distributed Sensor Networks and Detection Algorithms
Target Tracking and Data Fusion in Sensor Networks
In this paper, we design and implement the first-ever decentralized replicated relational database with blockchain properties that we term blockchain relational database. We highlight several similarities between features provided by blockchain platforms and a replicated relational database, although they are conceptually different, primarily in their trust model. Motivated by this, we leverage the rich features, decades of research and optimization, and available tooling in relational databases to build a blockchain relational database. We consider a permissioned blockchain model of known, but mutually distrustful organizations each operating their own database instance that are replicas of one another. The replicas execute transactions independently and engage in decentralized consensus to determine the commit order for transactions. We design two approaches, the first where the commit order for transactions is agreed upon prior to executing them, and the second where transactions are executed without prior knowledge of the commit order while the ordering happens in parallel. We leverage serializable snapshot isolation (SSI) to guarantee that the replicas across nodes remain consistent and respect the ordering determined by consensus, and devise a new variant of SSI based on block height for the latter approach. We implement our system on PostgreSQL and present detailed performance experiments analyzing both approaches.
Bruno W. França, Sophie Radermacher, Reto Trinkler
Katal is a new blockchain that provides a standard way to build and deploy decentralized financial applications. It brings together all the components necessary for the backend of a financial application, namely: a high-performance consensus, an authenticated data feed system, a standard for financial contracts and connectivity to the rest of the blockchain ecosystem. Katal enables and simplifies the creation of financial services that are non-custodial, trustless, fast, convenient and interoperable.
Pascal Berrang, Philipp von Styp-Rekowsky, Marvin WiĂfeld, Bruno W. França · 5 authors
The consensus protocol is a critical component of distributed ledgers and blockchains. Achieving consensus over a decentralized network poses challenges to transaction finality and performance. Currently, the highest-performing consensus algorithms are speculative BFT algorithms, which, however, compromise on the transaction finality guarantees offered by their non-speculative counterparts. In this paper, we introduce Albatross, a Proof-of-Stake (PoS) blockchain consensus algorithm that aims to combine the best of both worlds. At its heart, Albatross is a high-performing, speculative BFT algorithm that offers strong probabilistic finality. We complement this by periodically guaranteeing finality through the Tendermint protocol. We prove our protocol to be secure under standard BFT assumptions and analyze its performance both on a theoretical and practical level. For that, we provide an open-source Rust implementation of Albatross. Our real-world measurements support that our protocol has a performance close to the theoretical maximum for single-chain Proof-of-Stake consensus algorithms.
Distributed ledger technology is a system of recording digital transactions in an immutable ledger that is distributed across different locations. It is getting popular day by day not only in the public domain but also among enterprises. Various industry experts are working together to maximize the benefits of distributed ledger technology without affecting their current system flow. Distributed ledger technology not only provides a system of trust between untrusted parties, but it can also be used to improve system security with the use of complex cryptography. Enterprises are interested in distributed ledger technology because it can help in reducing cost and time of transactions but they canât use public ledgers as transactions and business processes should be hidden from everyone except authorized users only. The heart of distributed ledger technology is consensus algorithms which help in the settlement of transactions. Different consensus algorithms that can be helpful to enterprises are reviewed, analyzed, categorized and simplified flow is shown in pictorial form along with their limitations that helps the enterprise to choose best consensus algorithms for their implementation of distributed ledgers.
Cryptocurrencies have seen a massive surge in popularity and behind these new virtual currencies is an innovative technology called the block chain: a distributed digital ledger in which cryptocurrency transactions are recorded after having been verified. The transactions within a ledger are verified by multiple clients or "validators," within the cryptocurrency's peer-to-peer network using one of many varied consensus algorithms for resolving the problem of reliability in a network involving multiple unreliable nodes. The most widely used consensus algorithms are the Proof of Work (PoW) algorithm and the Proof of Stake (PoS) algorithm; however, there are also other consensus algorithms which utilize alternative implementations of PoW and PoS, as well as other hybrid implementations and some altogether new consensus strategies. In this paper, we perform a comparative analysis of typical consensus algorithms and some of their contemporaries that are currently in use in modern blockchains. Our analysis focuses on the algorithmic steps taken by each consensus algorithm, the scalability of the algorithm, the method the algorithm rewards validators for their time spent verifying blocks, and the security risks present within the algorithm. Finally, we present our conclusion and some possible future trends for consensus algorithms used in block chains.
Existing proof-of-work cryptocurrencies cannot tolerate attackers controlling more than 50 percent of the network's computing power at any time, but assume that such a condition happening is âunlikelyâ. However, recent attack sophistication, e.g., where attackers can rent mining capacity to obtain a majority of computing power temporarily, render this assumption unrealistic. This paper proposes RepuCoin, the first system to provide guarantees even when more than 50 percent of the system's computing power is temporarily dominated by an attacker. RepuCoin physically limits the rate of voting power growth of the entire system. In particular, RepuCoin defines a miner's power by its `reputation', as a function of its work integrated over the time of the entire blockchain, rather than through instantaneous computing power, which can be obtained relatively quickly and/or temporarily. As an example, after a single year of operation, RepuCoin can tolerate attacks compromising 51 percent of the network's computing resources, even if such power stays maliciously seized for almost a whole year. Moreover, RepuCoin provides better resilience to known attacks, compared to existing proof-of-work systems, while achieving a high throughput of 10000 transactions per second (TPS).
Yackolley Amoussou-Guenou, Bruno Biais, Maria Potop-Butucaru, Sara Tucci-Piergiovanni
In this paper we analyze from the game theory point of view Byzantine Fault Tolerant blockchains when processes exhibit rational or Byzantine behavior. Our work is the first to model the Byzantine-consensus based blockchains as a committee coordination game. Our first contribution is to offer a game-theoretical methodology to analyse equilibrium interactions between Byzantine and rational committee members in Byzantine Fault Tolerant blockchains. Byzantine processes seek to inflict maximum damage to the system, while rational processes best-respond to maximise their expected net gains. Our second contribution is to derive conditions under which consensus properties are satisfied or not in equilibrium. When the majority threshold is lower than the proportion of Byzantine processes, invalid blocks are accepted in equilibrium. When the majority threshold is large, equilibrium can involve coordination failures , in which no block is ever accepted. However, when the cost of accepting invalid blocks is large, there exists an equilibrium in which blocks are accepted iff they are valid.
Blockchain is an open distributed ledger technology that enables ledger-maintainers on a network to collaboratively synchronize and update their own distributed copies of a single global ledger, with the goal of keeping the ledger copies consistent. This paper presents a theoretical control-model formulation of the founding Satoshi Nakamoto blockchain, aimed at enhancing our operational understanding and development of blockchain systems. The control model is generic of every honest ledger-maintainer's local operations on a blockchain network. The presented research is a logical systematization of operational knowledge that is understandable and explainable for blockchain system engineering and research. Using a software tool supporting a supervisory control theory applied in the formulation, the control model is synthesized and logically validated.
Abstract A shared ledger is a record of transactions that can be updated by any member of a group of users. The notion of independent and consistent record-keeping in a shared ledger is important for blockchain and more generally for distributed ledger technologies. In this paper we analyze a stochastic model for the shared ledger known as the tangle, which was devised as the basis for the IOTA cryptocurrency. The model is a random directed acyclic graph, and its growth is described by a non-Markovian stochastic process. We first prove ergodicity of the stochastic process, and then derive a delay differential equation for the fluid model which describes the tangle at high arrival rate. We prove convergence in probability of the tangle process to the fluid model, and also prove global stability of the fluid model. The convergence proof relies on martingale techniques.
We consider the problem of expected cost analysis over nondeterministic probabilistic programs, which aims at automated methods for analyzing the resource-usage of such programs. Previous approaches for this problem could only handle nonnegative bounded costs. However, in many scenarios, such as queuing networks or analysis of cryptocurrency protocols, both positive and negative costs are necessary and the costs are unbounded as well. In this work, we present a sound and efficient approach to obtain polynomial bounds on the expected accumulated cost of nondeterministic probabilistic programs. Our approach can handle (a) general positive and negative costs with bounded updates in variables; and (b) nonnegative costs with general updates to variables. We show that several natural examples which could not be handled by previous approaches are captured in our framework. Moreover, our approach leads to an efficient polynomial-time algorithm, while no previous approach for cost analysis of probabilistic programs could guarantee polynomial runtime. Finally, we show the effectiveness of our approach by presenting experimental results on a variety of programs, motivated by real-world applications, for which we efficiently synthesize tight resource-usage bounds.
In the light of the recent fame of Blockchain technologies, numerous proposals and projects aiming at better practical viability have emerged. However, formally assessing their particularities and benefits has proven to be a difficult task. The aim of this work is to compare the fundamental differences of such protocols to understand how they lead to different practical performances. To reach this goal, we undertake a complexity analysis of a wide range of prominent distributed algorithms proposed for blockchain systems, under the lens of Total Order Broadcast protocols. We sampled protocols designed for very different settings and that use a broad range of techniques, thus giving a good overview of the achievements of state-of-the-art techniques. By analyzing latency and network usage, we are able to discuss each protocol's characteristics and properties in a consistent manner. One corollary result to our work is a more robust criteria to classify protocols as permissioned or permissionless.