The Binary Vector Clock is a simple, yet space-efficient algorithm for generating a partial order of transactions in account-based blockchain systems. The Binary Vector Clock solves the problem of order dependency in systems such as Ethereum, caused by the total order of transactions that come from the same address holder. The proposed algorithm has the same security as using regular transaction nonces, requires very little overhead, and can potentially result in a significant increase in throughput for systems like Ethereum.
The last decade has sparked several valiant efforts in deductive verification of distributed agreement protocols such as consensus and leader election. Oddly, there have been far fewer verification efforts that go beyond the core protocols and target applications that are built on top of agreement protocols. This is unfortunate, as agreement-based distributed services such as data stores, locks, and ledgers are ubiquitous and potentially permit modular, scalable verification approaches that mimic their modular design. We address this need for verification of distributed agreement-based systems through our novel modeling and verification framework, QuickSilver, that is not only modular, but also fully automated. The key enabling feature of QuickSilver is our encoding of abstractions of verified agreement protocols that facilitates modular, decidable, and scalable automated verification. We demonstrate the potential of QuickSilver by modeling and efficiently verifying a series of tricky case studies, adapted from real-world applications, such as a data store, a lock service, a surveillance system, a pathfinding algorithm for mobile robots, and more.
Yibin Xu, Yangyu Huang, Jianhua Shao, George Theodorakopoulos
Blockchain Sharding is a blockchain performance enhancement approach. By splitting a blockchain into several parallel-run committees (shards), it helps increase transaction throughput, reduce resources required, and increase reward expectation for participants. Recently, several flexible sharding methods that can tolerate up to $n/2$ Byzantine nodes ($n/2$ security level) have been proposed. However, these methods suffer from two main drawbacks. First, in a non-sharding blockchain, nodes can have different weight (power or stake) to create a consensus. So an adversary needs to control half of the overall weight of the system in order for a piece of faulty information to be accepted into the blockchain ($p/2$ security level). In blockchain sharding, all nodes carry the same weight. Thus, it is only under the assumption that the honest participants are creating as many nodes as they can that a $n/2$ security level blockchain sharding reaches the $p/2$ security level. Secondly, when some nodes leave the system, other nodes need to be reassigned, frequently, from shard to shard in order to maintain the security level of the system. In this paper, we present Multichain MWPoW, a $p/2$ security level blockchain sharding architecture that does not require honest participants to create multiple nodes and requires less node reassignment when some nodes leave the system. It combines the Multiple Winners Proof of Work consensus protocol (MWPoW) with the flexibility of $n/2$ blockchain sharding. Our experiments show that Multichain MWPoW outperforms existing blockchain sharding approaches in terms of security, transaction throughput and flexibility.
Public key infrastructures (PKIs) provide the foundations for securing Internet communications. Currently, PKIs are operated by centralized authorities, which have been involved in numerous security incidents. Blockchain or smart contract PKIs employ their distributed, fault-tolerant log of transactions to store either all identity records, or, constant-sized data to verify identity records stored off-chain. However, as most of these systems have never been implemented, there is little information regarding their practical implications. In this article, we implement, evaluate, and provide a complete security proof for the smart contract-based PKI of (Patsonakis et al.) on Ethereum. This construction incurs constant-sized storage at the expense of computational complexity. To explore this tradeoff, we propose and implement a second construction which, eliminates the need for trusted setup, preserves its security properties and show that it is the only version with constant-sized state that can be deployed on Ethereum's live chain. We compare these constructions with the simple approach of storing all identity records on the smart contract's state, to illustrate several shortcomings of Ethereum and its cost model. We propose several modifications for fine tuning the model, which should be considered for any smart contract platform like Ethereum so that it may support arbitrary distributed applications.
A key difference between using blockchains to store data and centrally controlled databases is that transactions are accepted to a blockchain via a consensus mechanism, and not by a controlling central party. Hence, once a user has issued a transaction, she cannot be certain if it will be accepted. Moreover, a yet unaccepted transaction cannot be retracted by the user, and may (or may not) be appended to the blockchain at any point in the future. This causes difficulties as the user may wish to formulate new transactions based on the knowledge of which previous transactions will be accepted. Yet this knowledge is inherently uncertain. We introduce a formal abstraction for blockchains as a data storage layer that underlies a database. The main issue that we tackle is the need to reason about possible worlds, due to the uncertainty in transaction appending. In particular, we consider the theoretical complexity of determining whether it is possible for a denial constraint to be contradicted, given the current state of the blockchain, pending transactions, and integrity constraints on blockchain data. We then present practical algorithms for this problem that work well in practice.
The full-replication data storage mechanism, as commonly utilized in existing blockchain systems, is lack of sufficient storage scalability, since it reserves a copy of the whole block data in each node so that the overall storage consumption per block is O(n) with n nodes. Moreover, due to the existence of Byzantine nodes, existing partitioning methods, though widely adopted in distributed systems for decades, cannot suit for blockchain systems directly, thereby it is critical to devise a new storage mechanism. This paper proposes a novel storage engine, called BFT-Store, to enhance storage scalability by integrating erasure coding with Byzantine Fault Tolerance (BFT) consensus protocol. First, the storage consumption per block can be reduced to O(1), which enlarges overall storage capability when more nodes join blockchain. Second, an efficient online re-encoding protocol is designed for storage scale-out and a hybrid replication scheme is employed to improve reading performance. Last, extensive experimental results illustrate the scalability, availability and efficiency of BFT-Store, which is implemented on an open-source permissioned blockchain Tendermint.
Yuechen Tao, Bo Li, Jingjie Jiang, Hok Chu Ng · 6 authors
Current blockchain systems suffer from a number of inherent drawbacks in its scalability, latency, and processing throughput. By enabling parallel confirmations of transactions, sharding has been proposed to mitigate these drawbacks, which usually requires frequent communication among miners through a separate consensus protocol.In this paper, we propose, analyze, and implement a new distributed and dynamic sharding system to substantially improve the throughput of blockchain systems based on smart contracts, while requiring minimum cross-shard communication. Our key observation is that transactions sent by users who only participate in a single smart contract can be validated and confirmed independently without causing double spending. Therefore, the natural formation of a shard is to surround one smart contract to start with. The complication lies in the different sizes of shards being formed, in which a small shard with few transactions tends to generate a large number of empty blocks resulting in a waste of mining power, while a large shard adversely affects parallel confirmations. To overcome this problem, we propose an inter-shard merging algorithm with incentives to encourage small shards to merge with one another and form a larger shard, an intra-shard transaction selection mechanism to encourage miners to select different subsets of transactions for validation, as well as a parameter unification method to further improve these two algorithms to reduce the communication cost and improve system reliability.We analyze our proposed algorithms using the game theoretic approach, and prove that they converge to a Nash Equilibrium. We also present a security analysis on our sharding design, and prove that it resists adversaries who occupy at most 33% of the computation power. We have implemented our designs on go-Ethereum 1.8.0 and evaluated their performance using both real-world blockchain transactions and large-scale simulations. Our results show that throughput has been improved by 7.2×, and the number of empty blocks has been reduced by 90%.
While Proof-of-Work (PoW) is the most widely used consensus mechanism for blockchain, it received harsh criticism due to its massive waste of energy for meaningless hash calculation. Some studies have introduced Proof-of-Stake to address this issue. However, such protocols widen the gap between rich and poor and in the worst case lead to an oligopoly, where the rich control the entire network. Other studies have attempted to translate the energy consumption of PoW into useful work, but they have many limitations, such as narrow application scope, serious security issues and impractical incentive model. In this paper, we introduce AxeChain, which can use the computing power of blockchain to solve practical problems raised by users without greatly compromising decentralization or security. AxeChain achieves this by coupling hard problem solving with PoW mining. We model the security of AxeChain and derive a balance curve between power utilization and system security. That is, under the reasonable assumption that the attack power does not exceed 1/3 of the total power, 1/2 of total power can be safely used to solve practical problems. We also design a novel incentive model based on the amount of work involved in problem solving, balancing the interests of both the users and miners. Moreover, our experimental results show that AxeChain provides strong security guarantees, no matter what kind of problem is submitted.
Institut Teknologi Bandung Bandung, Indonesia, Intan Muchtadi-Alamsyah, Muhammad Thufaili Imdad, Institut Teknologi Bandung Bandung, Indonesia · 6 authors
Smart contracts have enabled blockchain systems to evolve from simple cryptocurrency platforms, such as Bitcoin, to general transactional systems, such as Ethereum. Catering for emerging business requirements, a new architecture called execute-order-validate has been proposed in Hyperledger Fabric to support parallel transactions and improve the blockchain's throughput. However, this new architecture might render many invalid transactions when serializing them. This problem is further exaggerated as the block formation rate is inherently limited due to other factors beside data processing, such as cryptography and consensus. In this work, we propose a novel method to enhance the execute-order-validate architecture, by reducing invalid transactions to improve the throughput of blockchains. Our method is inspired by state-of-the-art optimistic concurrency control techniques in modern database systems. In contrast to existing blockchains that adopt database's preventive approaches which might abort serializable transactions, our method is theoretically more fine-grained. Specifically, unserializable transactions are aborted before ordering and the remaining transactions are guaranteed to be serializable. For evaluation, we implement our method in two blockchains respectively, FabricSharp on top of Hyperledger Fabric, and FastFabricSharp on top of FastFabric. We compare the performance of FabricSharp with vanilla Fabric and three related systems, two of which are respectively implemented with one standard and one state-of-the-art concurrency control techniques from databases. The results demonstrate that FabricSharp achieves 25% higher throughput compared to the other systems in nearly all experimental scenarios. Moreover, the FastFabricSharp's improvement over FastFabric is up to 66%.
Soteria is a user right management system designed to safeguard user-data privacy in a transparent and provable manner in compliance to regulations such as GDPR and CCPA. Soteria represents user data rights as formal executable sharing agreements, which can automatically be translated into a human readable form and enforced as data are queried. To support revocation and to prove compliance, an indelible, audited trail of the hash of data access and sharing agreements are stored on a two-layer distributed ledger. The main chain ensures partition tolerance and availability (PA) properties while side chains ensure consistency and availability (CA), thus providing the three properties of the CAP (consistency, availability, and partition tolerance) theorem. Besides depicting the two-layer architecture of Soteria, this paper evaluates representative consensus protocols and recommends side-chain and inter-chain management strategies for improving latency and throughput.
Blockchain or Distributed Ledger Technology is a disruptive technology that provides the infrastructure for developing decentralized applications enabling the implementation of novel business models even in traditionally centralized domains. In the last years it has drawn high interest from the academic community, technology developers and startups thus lots of solutions have been developed to address blockchain technology limitations and the requirements of applications software engineering. In this paper, we provide a comprehensive overview of DLT solutions analyzing the addressed challenges, provided solutions and their usage for developing decentralized applications. Our study reviews over 100 blockchain papers and startup initiatives from which we construct a 3-tier based architecture for decentralized applications and we use it to systematically classify the technology solutions. Protocol and Network Tier solutions address the digital assets registration, transactions, data structure, and privacy and business rules implementation and the creation of peer-to-peer networks, ledger replication, and consensus-based state validation. Scaling Tier solutions address the scalability problems in terms of storage size, transaction throughput, and computational capability. Finally, Federated Tier aggregates integrative solutions across multiple blockchain applications deployments. The paper closes with a discussion on challenges and opportunities for developing decentralized applications by providing a multi-step guideline for decentralizing the design of traditional systems and implementing decentralized applications.
Klitos Christodoulou, Elias Iosif, Antonios Inglezakis, Marinos Themistocleous
The inception of Bitcoin as a peer-to-peer payment system, and its underlying blockchain data-structure and protocol, has led to an increased interest in deploying scalable and reliable distributed-ledger systems that build on robust consensus protocols. A critical requirement of such systems is to provide enough fault tolerance in the presence of adversarial attacks or network faults. This is essential to guarantee liveness when the network does not behave as expected and ensure that the underlying nodes agree on a unique order of transactions over a shared state. In comparison with traditional distributed systems, the deployment of a distributed-ledger system should take into account the hidden game theoretical aspects of such protocols, where actors are competing with each other in an environment which is likely to experience various well-motivated malicious and adversarial attacks. Firstly, this paper discusses the fundamental principles of existing consensus protocols in the context of both permissioned and permissionless distributed-ledger systems. The main contribution of this work deals with observations from experimenting with Ripple’s consensus protocol as it is embodied in the XRP Ledger. The main experimental finding suggests that, when a low percentage of malicious nodes is present, the centralization degree of the network can be significantly relaxed ensuring low convergence times. Those findings are of particular importance when engineering a consensus algorithm that would like to balance security with decentralization.
Consensus protocols are currently the bottlenecks that prevent blockchain systems from scaling. However, we argue that transaction execution is also important to the performance and security of blockchains. In other words, there are ample opportunities to speed up and further secure blockchains by reducing the cost of transaction execution. Our goal is to understand how much we can speed up blockchains by exploiting transaction concurrency available in blockchain workloads. To this end, we first analyze historical data of seven major public blockchains, namely Bitcoin, Bitcoin Cash, Litecoin, Dogecoin, Ethereum, Ethereum Classic, and Zilliqa. We consider two metrics for concurrency, namely the single-transaction conflict rate per block, and the group conflict rate per block. We find that there is more concurrency in UTXO-based blockchains than in account-based ones, although the amount of concurrency in the former is lower than expected. Another interesting finding is that some blockchains with larger blocks have more concurrency than blockchains with smaller blocks. Next, we propose an analytical model for estimating the transaction execution speed-up given an amount of concurrency. Using results from our empirical analysis, the model estimates that 6x speed-ups in Ethereum can be achieved if all available concurrency is exploited.
This work is about the mutual influence between two technologies: Databases and Blockchain. It addresses two questions: 1. How the database technology has influenced the development of blockchain technology?, and 2. How blockchain technology has influenced the introduction of new functionalities in some modern databases? For the first question, we explain how database technology contributes to blockchain technology by unlocking different features such as ACID (Atomicity, Consistency, Isolation, and Durability) transactional consistency, rich queries, real-time analytics, and low latency. We explain how the CAP (Consistency, Availability, Partition tolerance) theorem known for databases influenced the DCS (Decentralization, Consistency, Scalability) theorem for the blockchain systems. By using an analogous relaxation approach as it was used for the proof of the CAP theorem, we postulate a "DCS-satisfiability conjecture." For the second question, we review different databases that are designed specifically for blockchain and provide most of the blockchain functionality like immutability, privacy, censorship resistance, along with database features.
In this paper, I evaluate a type of denial of service attack, bandwidth depletion, that difficult the block propagation in blockchain networks. Towards the end, I study the attack on Lisk blockchain and explore its effects in the Delegated Proof of Stake consensus. I also propose a methodology joint with two tools I've created as countermeasures against such type of attack. The methodology is composed of the configuration of the same delegate account in more than one node joint with the use of created tools capable to detect the percentage of consensus on each monitored node and activate block forging status in a single node dynamically. Therefore, allowing a block to be forged even when the delegate account is under attack on another node and reducing the chance of forks creation on the blockchain with the same delegate account configured and activated on two or more nodes in the same forging time slot.
We present "Gasper," a proof-of-stake-based consensus protocol, which is an idealized version of the proposed Ethereum 2.0 beacon chain. The protocol combines Casper FFG, a finality tool, with LMD GHOST, a fork-choice rule. We prove safety, plausible liveness, and probabilistic liveness under different sets of assumptions.
Scalability has been a bottleneck for major blockchains such as Bitcoin and Ethereum. Despite the significantly improved scalability claimed by several high-profile blockchain projects, there has been little effort to understand how their transactional throughput is being used. In this paper, we examine recent network traffic of three major high-scalability blockchains---EOSIO, Tezos and XRP Ledger (XRPL)---over a period of seven months. Our analysis reveals that only a small fraction of the transactions are used for value transfer purposes. In particular, 96% of the transactions on EOSIO were triggered by the airdrop of a currently valueless token; on Tezos, 76% of throughput was used for maintaining consensus; and over 94% of transactions on XRPL carried no economic value. We also identify a persisting airdrop on EOSIO as a DoS attack and detect a two-month-long spam attack on XRPL. The paper explores the different designs of the three blockchains and sheds light on how they could shape user behavior.
Scalability has been a bottleneck for major blockchains such as Bitcoin and Ethereum. Despite the significantly improved scalability claimed by several high--profile blockchain projects, there has been little effort to understand how their transactional throughput is being used. In this paper, we examine recent network traffic of three major high-scalability blockchains--EOSIO, Tezos and XRP Ledger (XRPL)--over a period of seven months. Our analysis reveals that only a small fraction of the transactions are used for value transfer purposes. In particular, 96% of the transactions on EOSIO were triggered by the airdrop of a currently valueless token; on Tezos, 76% of throughput was used for maintaining consensus; and over 94% of transactions on XRPL carried no economic value. We also identify a persisting airdrop on EOSIO as a DoS attack and detect a two-month-long spam attack on XRPL. The paper explores the different designs of the three blockchains and sheds light on how they could shape user behavior.
Relational Databases (RDBs) have been widely used for decades. However, new persistence technologies are emerging, such as Blockchain, which is disruptive and has relevant properties, such as immutability and no third parties. Therefore, applications that use RDB can benefit from these properties by migrating part of their data to Blockchains. This article presents the MOON, a hybrid approach to manage data in RDB and Blockchain, which receives SQL queries. A case study was performed with a real health dataset using three scenarios. The conclusion is that the MOON responds to requests correctly and provides RDB and Blockchain features. Moreover, its response time was intermediate between RDB and Blockchains.
Blockchain as an emerging distributed protocol has been widely used in IoT systems. Using blockchain as an IoT data sharing protocol provides precious features including consistency, reliability, and traceability. However, such combination brings high cryptography overhead and consensus latency when sharing data from large number of IoT sensors. To address these issues, we propose a novel blockchain based architecture for IoT data sharing systems. In this architecture, data messages signed by IoT sensors are packaged into data blocks and distributed to the blockchain network. We propose a data block structure with identity-based aggregate signature to protect data reliability from malicious sink nodes and reduce the communication, storage, and computing cost of signatures. We also present a multiple state chain structure with a new consensus algorithm which cuts back consensus phases and accelerate the consensus process. Finally, we evaluate the proportion of data in a block and the blockchain consensus latency, which shows a better performance than PBFT in this scenario.
PBFT is a consensus algorithm based on Byzantine fault tolerance that is widely used in current systems like blockchains. However, this algorithm has some problems that slow down its use on a large scale. In the interest of solving its problems, we have combined it with the Distributed Proof of Stake (DPoS) algorithm and smart contract technology to improve it and make it better. For this, Smart contracts were deployed in the network to improve the selection process of accounting nodes and participated in the operating process of the PBFT algorithm in order to make the selection process more transparent, incorruptible, and secure. Concerning the problem of the scalability of the nodes of the system, it will be possible to make a readjustment of the consensus algorithm to make it more flexible. The modification can be done by implementing readjustment counters, which will count the number of nodes in the network each time a consensus is reached or a node is ejected from the network, then automatically distributes the list of new nodes in the network. This new list of nodes will constitute the new network on which the new consensus will be based. To make it more secure and more sensitive to Byzantine faults, the sensitivity margin is improved.
Distributed Ledger Technologies are one of the pillars of future technologies, prognozing to have a great impact to many aspects of our lives, including social, economic, juristic, security and many others. Bitcoin is still the most popular blockchain currency, but the opportunities to use Distribute Ledger Technologies are much more wide, outperforming financial applications as most known and popular. Besides blockchains, there are also other architectures of Distributed Ledger Technologies. This paper observes and analyses one technology as a very strong alternative to blockchains: hashgraphs, which are promising to outperform blockchains, but also tangles. Basis of their architecture and functionality will be explained and directions and prognosis of the further development will be given. The main paper contribution is a comparison of a hashgraph technology to its concurrent architectures, i.e. blockchains and tangles, considering different segments and different properties that define a quality of Distributed Ledgers.
Zakwan Jaroucheh, Baraq Ghaleb, William J Buchanan
The proof-of-work consensus protocol suffers from two main limitations: waste of energy and offering only probabilistic guarantees about the status of the blockchain. This paper introduces SklCoin, a new Byzantine consensus protocol and its corresponding software architecture. This protocol leverages two ideas: 1) the proof-of-stake concept to dynamically form stake proportionate consensus groups that represent block miners (stakeholders), and 2) scalable collective signing to efficiently commit transactions irreversibly. SklCoin has immediate finality characteristic where all miners instantly agree on the validity of blocks. In addition, SklCoin supports high transaction rate because of its fast miner election mechanism.