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.
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.
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.
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.
A distributed ledger is a tamperproof sequence of data that can be publicly accessed and augmented by everyone, without being maintained by a centralized party. Distributed ledgers stand to revolutionize the way a modern society operates. They can secure all kinds of traditional transactions, such as payments, asset transfers and titles, in the exact order in which the transactions occur; and enable totally new transactions, such as cryptocurrencies and smart contracts. They can remove intermediaries and usher in a new paradigm for trust. As currently implemented, however, distributed ledgers scale poorly and cannot achieve their enormous potential. In this paper we propose Algorand, an alternative, secure and efficient distributed ledger. Algorand is permissionless and works in a highly asynchronous environment. Unlike prior implementations of distributed ledgers based on âproof of work,â Algorand dispenses with âminersâ and requires only a negligible amount of computation. Moreover, its transaction history âforksâ only with negligible probability: that is, Algorand guarantees the finality of a transaction the moment the transaction enters the ledger.
Alessio Meneghetti, Tommaso Parise, Massimiliano Sala, Daniele Taufer
The main problem faced by smart contract platforms is the amount of time and computational power required to reach consensus. In a classical blockchain model, each operation is in fact performed by each node, both to update the status and to validate the results of the calculations performed by others. In this short survey we sketch some state-of-the-art approaches to obtain an efficient and scalable computation of smart contracts. Particular emphasis is given to sharding, a promising method that allows parallelization and therefore a more efficient management of the computational resources of the network.
In this paper, we present Tendermint: a Byzantine Fault Tolerant (BFT) application-based blockchain. We show that Tendermint promotes another perception of blockchain programming. Unlike Ethereum which is a blockchain holding many applications, Tendermint proposes to have one application per blockchain. We discuss the idiosyncrasies of Tendermint and how it could, potentially, ease blockchain programming and improve performance. We finish by showing weaknesses of Tendermint, good practices to adopt to hinder security attacks when handling Tendermint nodes, and some potential adjustments in the IBC protocol - an interoperability protocol designed for Tendermint. Our goal is to introduce Tendermint by showing its main characteristics over traditional blockchain platforms such as Bitcoin or Ethereum.
Alberto Sonnino, Shehar Bano, Mustafa Al-Bassam, George Danezis
We present a family of replay attacks against sharded distributed ledgers, that target cross-shard consensus protocols, such as the recently proposed Chainspace and Omniledger. They allow an attacker, with network access only, to double-spend or lock resources with minimal efforts. The attacker can act independently without colluding with any nodes, and succeed even if all nodes are honest; most of the attacks can also exhibit themselves as faults under periods of asynchrony. These attacks are effective against both shard-led and client-led cross-shard consensus approaches. Finally, we present Byzcuit - a new cross-shard consensus protocol that is immune to those attacks. We implement a prototype of Byzcuit and evaluate it on a real cloud-based testbed, showing that our defenses impact performance minimally, and overall performance surpasses previous works.
Alberto Sonnino, Shehar Bano, Mustafa Al-Bassam, George Danezis
We present a family of replay attacks against sharded distributed ledgers,\nthat target cross-shard consensus protocols, such as the recently proposed\nChainspace and Omniledger. They allow an attacker, with network access only, to\ndouble-spend or lock resources with minimal efforts. The attacker can act\nindependently without colluding with any nodes, and succeed even if all nodes\nare honest; most of the attacks can also exhibit themselves as faults under\nperiods of asynchrony. These attacks are effective against both shard-led and\nclient-led cross-shard consensus approaches. Finally, we present Byzcuit - a\nnew cross-shard consensus protocol that is immune to those attacks. We\nimplement a prototype of Byzcuit and evaluate it on a real cloud-based testbed,\nshowing that our defenses impact performance minimally, and overall performance\nsurpasses previous works.\n
Ethereum clients execute transactions in a sequential order prescribed by the consensus protocol. This is a safe and conservative approach to blockchain transaction processing which forgoes running transactions in parallel even when doing so would be beneficial and safe, e.g., when there is no intersection in the sets of accounts that the transactions read or modify. In this work we study the degree of transaction parallelizability and present results from three different simulations using real Ethereum transaction data. Our simulations demonstrate that notable gains are achievable with parallelization, and suggest that the potential for parallelizability improves as transaction rates increase.
Mokka is a partial-synchronous, strong consistent BFT consensus algorithm for reaching the consensus about a certain value in open networks. This algorithm has some common approaches nested from RAFT, but its nature and design make Mokka a better solution for DLT (distributed ledger).
In today's blockchain system, designing a secure and high throughput blockchain on par with a centralized payment system is a difficult task. Sharding is one of the most worthwhile emerging technologies for improving the system throughput while maintain high-security level. However, previous sharding-related designs have two main limitations. First, the security and throughput of their random-based sharding system are not high enough as they did not leverage the heterogeneity among validators. Second, to design an incentive mechanism that promotes cooperation could incur a huge overhead on their system. In this article, we propose RepChain, a reputation-based secure and fast blockchain system via sharding, which also provides high incentive to stimulate node cooperation. RepChain utilizes reputation to explicitly characterize the heterogeneity among the validators and lay the foundation for the incentive mechanism. We propose a new double-chain architecture-a transaction chain and a reputation chain. For the transaction chain, an efficient Raft-based synchronous consensus has been presented. For the reputation chain, the synchronous Byzantine fault tolerance consensus that combines collective signing has been utilized to prevent the attack on both reputation score and the related transaction blocks. It supports a high throughput transaction chain with moderate generation speed. Moreover, we propose a reputation-based sharding and leader selection scheme. To analyze the security of RepChain, we propose a recursive formula to calculate the epoch security within only $\mathcal {O}(km^{2})$ time. Furthermore, we implement and evaluate RepChain on the Amazon Web Service platform. The results show our solution can enhance both throughout and security level of the existing sharding-based blockchain system.
Atomic swaps enable the transfer of value between the cryptocurrencies of various blockchains without the need to trust an intermediary. In this paper, we propose the concept of atomic loans, which utilize atomic swap technology to allow market participants to create overcollateralized debt instruments in a trustless and disintermediated manner. The primary use cases for atomic loans include enabling fiat/stablecoin access for cryptocurrency holders to participate within legacy systems, as well as enabling leverage for margin trading. We also introduce a bidding process for liquidating collateral in the case of default which provides the ability for a more fair distribution of collateral.
Blockchains are distributed secure ledgers to which transactions are issued continuously and each block of transactions is tightly coupled to its predecessors. Permissioned blockchains place special emphasis on transactions throughput. In this paper we present FireLedger, which leverages the iterative nature of blockchains in order to improve their throughput in optimistic execution scenarios. FireLedger trades latency for throughput in the sense that in FireLedger the last f + 1 blocks of each node's blockchain are considered tentative, i.e., they may be rescinded in case one of the last f + 1 blocks proposers was Byzantine. Yet, when optimistic assumptions are met, a new block is decided in each communication step, which consists of a proposer that sends only its proposal and all other participants are sending a single bit each. Our performance study demonstrates that in a single Amazon data-center, FireLedger running on 10 mid-range Amazon nodes obtains a throughput of up to 160K transactions per second for (typical Bitcoin size) 512 bytes transactions. In a 10 nodes Amazon geo-distributed setting with 512 bytes transactions, FireLedger obtains a throughput of 30K tps. Moreover, on higher end Amazon machines, FireLedger obtains $20%-600%$ better throughput than state of the art protocols like HotStuff and BFT-SMaRt, depending on the exact configuration.