Cryptocurrencies, implemented with blockchain protocols, promise to become a global payment system if they can overcome performance limitations. Rapidly advancing architectures improve on latency and throughput, but most require all participating servers to process all transactions. Several recent works propose to shard the system, such that each machine would only process a subset of the transactions. However, we identify a denial-of-service attack that is exposed by these solutions - an attacker can generate transactions that would overload a single shard, thus delaying processing in the entire system. Moreover, we show that in common scenarios, these protocols require most node operators to process almost all blockchain transactions. We present Ostraka, a blockchain node architecture that shards (parallelizes) the nodes themselves. We prove that replacing a unified node with an Ostraka node does not affect the security of the underlying consensus mechanism. We evaluate analytically and experimentally block propagation and processing in various settings. Ostraka allows nodes in the network to scale, without costly coordination. In our experiments, Ostraka nodes' transaction processing rate grows linearly with the addition of resources.
Blockchain je u proteklih nekoliko godina dobio široku pozornost zbog njegove primjene na kripto valutama i tehnologijama distribuiranih knjiga (Distributed Ledger), kao što su Bitcoin i Ethereum. Složena i decentralizirana priroda blockchain tehnologija otežava razumijevanje ponašanja pojedinih komponenata i njihovog učinka na blockchain sustav. Dolaskom novih konsenzus algoritama, kao što je Proof of Authority (PoA), razumijevanje ovog složenog sustava postaje izazovan zadatak. U ovom radu predlažemo PoASim, podesiv, diskretni simulacijski alat za simulaciju dvaju glavnih PoA algoritama, nazvanih Clique i Aura. PoASim može pomoći korisnicima da bolje razumiju temeljne slojeve Ethereum blockchain-a, kao i razumijevanje razlika konsenzusa i nedostataka između dva konsenzus algoritma. PoASim tako može poslužiti kao koristan alat za bolje razumijevanje ponašanja svakog konsenzusa pokretanjem simulacija s različitim parametrima i analizom ponašanja sustava.
Quan Nguyen, André Cronje, Michael Kong, Alex Kampa · 5 authors
Trustless systems, such as those blockchain enpowered, provide trust in the system regardless of the trust of its participants, who may be honest or malicious. Proof-of-stake (PoS) protocols and DAG-based approaches have emerged as a better alternative than the proof of work (PoW) for consensus. This paper introduces a new model, so-called \emph{\stakedag}, which aims for PoS consensus in a DAG-based trustless system. We address a general model of trustless system in which participants are distinguished by their stake or trust: users and validators. Users are normal participants with a no assumed trust and validators are high profile participants with an established trust. We then propose a new family of stake-based consensus protocols $\mathfrak{S}$, operating on the DAG as in the Lachesis protocol~\cite{lachesis01}. Specifically, we propose a stake-based protocol $S_φ$ that leverages participants' stake as validating weights to achieve more secure distributed systems with practical Byzantine fault tolerance (pBFT) in leaderless asynchronous Directed Acyclic Graph (DAG). We then present a general model of staking for asynchronous DAG-based distributed systems.
Permissioned blockchain protocols generally use voting based algorithms to reach consensus. Scaling such protocols is hard because of their high message complexity and thus, have a limited number of applications. Use cases like banking and healthcare blockchain require a scalable distributed protocol to maintain the consistency of the ledger and ensure its safety. This paper presents Colosseum, a scalable consensus protocol designed for permissioned blockchain systems. It is a knockout tournament based protocol over a structured ring network to reach consensus on the next set of block proposers. Participants compete in the rounds of a novel two-player game in each tournament to become eligible to propose block. Colosseum introduces Proof-of-Win as the certificate for the result of matches to have an efficient and easy way to propose trusted blocks and verify them.
EOSIO is a blockchain platform utilizing a byzantine-fault-tolerance delegated-proof-of-stake (BFT-DPOS) consensus protocol to guarantee scalability. In EOSIO, a group of representatives called block producers (BPs) is elected by voting through a certain period, and is scheduled in an order to produce blocks. And new tokens are given to BPs every time they produce a block as a notion of reward. In this paper, we show that an attacker can disturb fairness of compensation policy by manipulating the production schedule of EOSIO. Such manipulation is possible through an attacker who has enough tokens to abuse the election process. In order to demonstrate the feasibility and the capability of our attack, we created a tool following EOSIO's voting and irreversible block generation procedure. Our simulation shows that an attacker can provide additional rewards or loss up to 3 BPs. Finally, we discuss the applicability of our attack against the real EOSIO mainnet, and at the same time, propose some countermeasures to prevent it.
A stake-bleeding attack is a newly proposed form of long-range attacks against Proof of Stake (PoS) based blockchain systems. However, as shown in this paper, with the decrease of transaction fees in current PoS based blockchain systems, adversaries require several decades to complete this attack, which is unrealistic. In this paper, we make an improvement on the stake-bleeding attack. We propose an eclipse-based stake-bleeding attack that reduces the attack completion time significantly, e.g., the proposed attack only requires 2.4 years of the attack completion time, while the original stake-bleeding attack needs 22.9 years for the successful attack. We also present a preliminary analysis result on the minimum time to complete the proposed attack.
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. However, BFT-based protocols suffer from scalability problems with respect to the number of replicas in the network due to their inherent quadratic message complexity. 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. 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) messages, where c << n, for large number of nodes n. We 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× in terms of throughput as well as latency.
One of the current challenges that faces individual organizations that are attempting to utilize blockchain in making more secure and transparent transaction between organizations are standards. Not all platforms, however, are suitable. In this paper, we provide a comparison of blockchain development platforms for developers to choose the best platform based on their need.
Tezos is an innovative blockchain that improves on several aspects compared to more established blockchains. It offers an original proof-of-stake consensus algorithm and can be used as a decentralized smart contract platform. It has the capacity to amend its own economic protocol through a voting mechanism and focuses on formal methods to improve safety.
Mohammad Javad Amiri, Divyakant Agrawal, Amr El Abbadi
Despite recent intensive research, existing blockchain systems do not adequately address all the characteristics of distributed applications. In particular, distributed applications collaborate with each other following service level agreements (SLAs) to provide different services. While collaboration between applications, e.g., cross-application transactions, should be visible to all applications, the internal data of each application, e.g, internal transactions, might be confidential . In this paper, we introduce CAPER , a permissioned blockchain system to support both internal and cross-application transactions of collaborating distributed applications. In CAPER, the blockchain ledger is formed as a directed acyclic graph where each application accesses and maintains only its own view of the ledger including its internal and all cross-application transactions. CAPER also introduces three consensus protocols to globally order cross-application transactions between applications with different internal consensus protocols. The experimental results reveal the efficiency of CAPER in terms of performance and scalability.
Carlos Henrique Fernandes de Faria, Miguel Correia
A blockchain is a distributed ledger in which participants that do not fully trust each other agree on the ledger's content by running a consensus algorithm. This technology is raising a lot of interest both in academia and industry, but the lack of tools to evaluate design and implementation decisions may hamper fast progress. To address this issue, this paper presents a discrete-event simulator that is flexible enough to evaluate different blockchain implementations. These blockchains can be rapidly modeled and simulated by extending existing models. Running Bitcoin and Ethereum simulations allowed us to change conditions and answer different questions about their performance. For example, we concluded that doubling the number of transactions per block has a low impact on the block propagation delay (10ms) and that encrypting communication has a high impact in that delay (more than 25%).
Blockchain protocols based on Proof-of-Stake (PoS) algorithms aim to provide an alternative to the energy-consuming Proof-of-Work mining procedure. Following a PoS algorithm, nodes have to agree on the miner next eligible to contribute a block and on the point in time he is allowed to broadcast it. The latter requirement raises to the need for synchronous clocks. In this paper we describe BeaconBlocks, a new scheme for constructing PoS protocols. A major difference to former work is incorporating time synchronization as an essential element of the protocol itself, gaining independence of the nodes' clocks and allowing the protocol to resist attacks on clock synchronization infrastructure. To this end, we describe both a mechanism for obtaining the correct time during node startup and for retaining synchronicity of estimated time during a node's lifetime. In contrast to prior work, our approach for miner selection exhibits an interleaved unslotted structure. We show that fairness is achieved when miners follow our scheme and we provide a discussion of attack possibilities, allowing developers to choose secure parameters when adopting the scheme.
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.
Blockchain is the most rapidly improving technology in distributed computing. It has come a long way from being a new paradigm which is gaining momentum in the ledger technology. Bitcoin being the first implementation of distributed ledger brought in many advantages and disadvantages. Later came the applications of the proof-of-stake algorithms into the ledger technology. All of these performed well except that each did not provide a secure way of distributed computing. Thus, researchers brought in a new concept of the cryptographic ledgers which used the whole new Byzantine Agreement protocol and the technology got to be known as the Algorand. It scaled the databases and data warehouses according to the consensus and brought around the transactions very well bringing in more advantages from its applications. The various technologies and protocols which were previously used before algorand are discussed to provide an idea as to what lead to the development of the most evolving technology in the Block- chain. One application of the algorand which is cryptographic sortition algorithm is explained for knowing of the protocols used and the efficient performance provided byalgorand.
Data integration and fast effective data processing are the primary challenges in today’s high-performance computing systems used for Big Data processing and analysis in practical scenarios. Blockchain (BC) is a hot, modern technology that ensures high security of data processes stored in highly distributed networks and ICT infrastructures. BC enables secure data transfers in distributed systems without the need for all operations and processes in the network to be initiated and monitored by any central authority (system manager). This paper presents the background of a generic architectural model of a BC system and explains the concept behind the consensus models used in BC transactions. Security is the main aspect of all defined operations and BC nodes. The paper presents also specific BC use cases to illustrate the performance of the system in practical scenarios..
The Sybil attack plagues all peer-to-peer systems, and modern open distributed ledgers employ a number of tactics to prevent it from proof of work, or other resources such as space, stake or memory, to traditional admission control in permissioned settings. With SybilQuorum we propose an alternative approach to securing an open distributed ledger against Sybil attacks, and ensuring consensus amongst honest participants, leveraging social network based Sybil defences. We show how nodes expressing their trust relationships through the ledger can bootstrap and operate a value system, and general transaction system, and how Sybil attacks are thwarted. We empirically evaluate our system as a secure Federated Byzantine Agreement System, and extend the theory of those systems to do so.
Summary Contemporary blockchain such as Bitcoin and Ethereum execute transactions serially by miners and validators and determine the Proof‐of‐Work (PoW). Such serial execution is unable to exploit modern multi‐core resources efficiently, hence limiting the system throughput and increasing the transaction acceptance latency. The objective of this work is to increase the transaction throughput by introducing parallel transaction execution using a static analysis over the transaction dependencies. We propose the DiPETrans framework for distributed execution of transactions in a block. Here, peers in the blockchain network form a community of trusted nodes to execute the transactions and find the PoW in‐parallel, using a leader–follower approach. During mining, the leader statically analyzes the transactions, creates different groups (shards) of independent transactions, and distributes them to followers to execute concurrently. After execution, the community's compute power is utilized to solve the PoW concurrently. When a block is successfully created, the leader broadcasts the proposed block to other peers in the network for validation. On receiving a block, the validators re‐execute the block transactions and accept the block if they reach the same state as shared by the miner. Validation can also be done in parallel, following the same leader–follower approach as mining. We report experiments using over 5 million real transactions from the Ethereum blockchain and execute them using our DiPETrans framework to empirically validate the benefits of our techniques over a traditional sequential execution. We achieve a maximum speedup of 2.2 and 2.0 and an average speedup of 1.6 and 1.5 for the miner and the validator, respectively, with 100–500 transactions per block when using 6 machines in the community. Further, we achieve a peak of 5 end‐to‐end block creation speedup using a parallel miner over a serial miner.
Sujaya Maiyya, Victor Zakhary, Mohammad Javad Amiri, Divyakant Agrawal · 5 authors
The uprise of Bitcoin and other peer-to-peer cryptocurrencies has opened many interesting and challenging problems in cryptography, distributed systems, and databases. The main underlying data structure is blockchain, a scalable fully replicated structure that is shared among all participants and guarantees a consistent view of all user transactions by all participants in the system. In this tutorial, we discuss the basic protocols used in blockchain, and elaborate on its main advantages and limitations. To overcome these limitations, we provide the necessary distributed systems background in managing large scale fully replicated ledgers, using Byzantine Agreement protocols to solve the consensus problem. Finally, we expound on some of the most recent proposals to design scalable and efficient blockchains in both permissionless and permissioned settings. The focus of the tutorial is on the distributed systems and database aspects of the recent innovations in blockchains.
Ankur Sharma, Felix Schuhknecht, Divya Agrawal, Jens Dittrich
Within the last few years, a countless number of blockchain systems have emerged on the market, each one claiming to revolutionize the way of distributed transaction processing in one way or the other. Many blockchain features, such as byzantine fault tolerance, are indeed valuable additions in modern environments. However, despite all the hype around the technology, many of the challenges that blockchain systems have to face are fundamental transaction management problems. These are largely shared with traditional database systems, which have been around for decades already. These similarities become especially visible for systems, that blur the lines between blockchain systems and classical database systems. A great example of this is Hyperledger Fabric, an open-source permissioned blockchain system under development by IBM. By implementing parallel transaction processing, Fabric's workflow is highly motivated by optimistic concurrency control mechanisms in classical database systems. This raises two questions: (1)~Which conceptual similarities and differences do actually exist between a system such as Fabric and a classical distributed database system? (2)~Is it possible to improve on the performance of Fabric by transitioning technology from the database world to blockchains and thus blurring the lines between these two types of systems even further? To tackle these questions, we first explore Fabric from the perspective of database research, where we observe weaknesses in the transaction pipeline. We then solve these issues by transitioning well-understood database concepts to Fabric, namely transaction reordering as well as early transaction abort. Our experimental evaluation under the Smallbank benchmark as well as under a custom workload shows that our improved version Fabric++ significantly increases the throughput of successful transactions over the vanilla version by up to a factor of 12x, while decreasing the average latency to almost half.
We describe MaGPoS, a novel consensus mechanism which is well suited to decentralized blockchain based protocols. MaGPoS is based on a combination of the well known physics of nano-scale magnetism, and previous implementations of proof of stake. This system has been studied by hundreds of thousands of scientists worldwide for over a hundred years, giving it an extreme level of reliability that is needed for a consensus mechanism. We start by explaining the physics, and study the properties that make it particularly beneficial for use in a consensus mechanism. We then show how to apply the physical model to a decentralized network of nodes, each with their own copy of a blockchain. After this, we describe some example calculations that a node in the decentralized network would make, and provide pseudo code for implementation. Finally, we discuss the how the model achieves all of the important properties that one expects of a consensus mechanism.
Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič · 5 authors
Many blockchain-based algorithms, such as Bitcoin, implement a decentralized asset transfer system, often referred to as a cryptocurrency. As stated in the original paper by Nakamoto, at the heart of these systems lies the problem of preventing double-spending; this is usually solved by achieving consensus on the order of transfers among the participants. In this paper, we treat the asset transfer problem as a concurrent object and determine its consensus number, showing that consensus is, in fact, not necessary to prevent double-spending. We first consider the problem as defined by Nakamoto, where only a single process---the account owner---can withdraw from each account. Safety and liveness need to be ensured for correct account owners, whereas misbehaving account owners might be unable to perform transfers. We show that the consensus number of an asset transfer object is $1$. We then consider a more general $k$-shared asset transfer object where up to $k$ processes can atomically withdraw from the same account, and show that this object has consensus number $k$. We establish our results in the context of shared memory with benign faults, allowing us to properly understand the level of difficulty of the asset transfer problem. We also translate these results in the message passing setting with Byzantine players, a model that is more relevant in practice. In this model, we describe an asynchronous Byzantine fault-tolerant asset transfer implementation that is both simpler and more efficient than state-of-the-art consensus-based solutions. Our results are applicable to both the permissioned (private) and permissionless (public) setting, as normally their differentiation is hidden by the abstractions on top of which our algorithms are based.