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.
Chrysoula Stathakopoulou, Tudor David, Matej Pavlovič, Marko Vukolić
This paper presents Mir-BFT, a robust Byzantine fault-tolerant (BFT) total order broadcast protocol aimed at maximizing throughput on wide-area networks (WANs), targeting deployments in decentralized networks, such as permissioned and Proof-of-Stake permissionless blockchain systems. Mir-BFT is the first BFT protocol that allows multiple leaders to propose request batches independently (i.e., parallel leaders), in a way that precludes request duplication attacks by malicious (Byzantine) clients, by rotating the assignment of a partitioned request hash space to leaders. As this mechanism removes a single-leader bandwidth bottleneck and exposes a computation bottleneck related to authenticating clients even on a WAN, our protocol further boosts throughput using a client signature verification sharding optimization. Our evaluation shows that Mir-BFT outperforms state-of-the-art and orders more than 60000 signed Bitcoin-sized (500-byte) transactions per second on a widely distributed 100 nodes, 1 Gbps WAN setup, with typical latencies of few seconds. We also evaluate Mir-BFT under different crash and Byzantine faults, demonstrating its performance robustness. Mir-BFT relies on classical BFT protocol constructs, which simplifies reasoning about its correctness. Specifically, Mir-BFT is a generalization of the celebrated and scrutinized PBFT protocol. In a nutshell, Mir-BFT follows PBFT "safety-wise", with changes needed to accommodate novel features restricted to PBFT liveness.
Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, Dahlia Malkhi
Financial institutions are currently looking into technologies for permissioned blockchains. A major effort in this direction is Hyperledger, an open source project hosted by the Linux Foundation and backed by a consortium of over a hundred companies. A key component in permissioned blockchain protocols is a byzantine fault tolerant (BFT) consensus engine that orders transactions. However, currently available BFT solutions in Hyperledger (as well as in the literature at large) are inadequate for financial settings; they are not designed to ensure fairness or to tolerate selfish behavior that arises when financial institutions strive to maximize their own profit. We present FairLedger, a permissioned blockchain BFT protocol, which is fair, designed to deal with rational behavior, and, no less important, easy to understand and implement. The secret sauce of our protocol is a new communication abstraction, called detectable all-to-all (DA2A), which allows us to detect participants (byzantine or rational) that deviate from the protocol, and punish them. We implement FairLedger in the Hyperledger open source project, using Iroha framework, one of the biggest projects therein. To evaluate FairLegder's performance, we also implement it in the PBFT framework and compare the two protocols. Our results show that in failure-free scenarios FairLedger achieves better throughput than both Iroha's implementation and PBFT in wide-area settings.
We introduce Unity, a new consensus algorithm for public blockchain settings. Unity is an eventual consistency protocol merging the Proof-of-Work (PoW) and Proof-of-Stake (PoS) into a coherent stochastic process. It encompasses hardware and economic security without sacrificing availability, unpredictability and decentralization. Empirical results indicate that the proposed protocol is fair and scalable to an arbitrary number of miners and stakers.
With the rapid evolution of technological, economic, and regulatory landscapes, contemporary blockchain platforms are all but certain to undergo major changes. Therefore, the applications that rely on them will eventually need to migrate from one blockchain instance to another to remain competitive and secure, as well as to enhance the business process, performance, cost efficiency, privacy, and regulatory compliance. However, the differences in data and smart contract representations, modes of hosting, transaction fees, as well as the need to preserve consistency, immutability, and data provenance introduce unique challenges over database migration. We first present a set of blockchain migration scenarios and data fidelity levels using an illustrative example. We then present a set of migration patterns to address those scenarios and the above data management challenges. Finally, we demonstrate how the effort, cost, and risk of migration could be minimized by choosing a suitable set of data migration patterns, data fidelity level, and proactive system design. Practical considerations and research challenges are also highlighted.
Mohammad M. Jalalzai, Costas Busch, Golden G. Richard
There have been numerous solutions to improve the message complexity of Byzantine Fault Tolerant (BFT) protocols. Unfortunately, these solutions do not guarantee consistent performance and fall back to quadratic message complexity if a certain threshold of node failures is encountered in the network. Furthermore, reliance on a single primary to forward a proposed blockchain block to all replicas in the network can provide a potential attack vector, in which the primary can create discrepancies among histories of honest replicas. This results in increased latency during the view change (denial of service). Therefore, we propose a BFT-based protocol that guarantees consistent performance and shifts the reliance from a single primary to broadcast a candidate block to a sub-committee of replicas.
Blockchain technology comes with the promise to revolutionize the way current IT systems are organized as well as to revise how trust is perceived in the wider society. In spite of the wide attention that crypto-currencies (such as Bitcoin) have attracted, Blockchain technology is more likely to make an impact beyond ongoing speculations on crypto-currencies. Decentralized identity management, transparent supply-chain systems, and IoT governance and security are only few examples of research challenges for which this technology may hold substantial potential. Blockchain technology has emerged at the intersection of two well established research areas: peer-to-peer (P2P) computing and cryptography. In this tutorial, we provide a general overview of the main components behind this technology, we present the difference between the types of Blockchain available today, and we make a high level discussion on its potentials and limitations as well as possible research challenges.
We develop new foundations on transaction untraceability for CryptoNote-style blockchain systems. In particular, we observe new attacks; develop theoretical foundations to model transaction untraceability; provide the least upper bound of transaction untraceability guarantee; provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability; and provide a general solution that achieves provably optimal transaction untraceability. Unlike previous cascade effect attacks (ESORICS' 17 and PETS' 18) on CryptoNote-style transaction untraceability, we consider not only a passive attacker but also an active adaptive attacker. Our observed attacks allow both types of attacker to trace blockchain transactions that cannot be traced by using the existing attacks. We develop a series of new games, which we call "The Sun-Tzu Survival Problem", to model CryptoNote-style blockchain transaction untraceability and our identified attacks. In addition, we obtain seven novel results, where three of them are negative and the rest are positive. In particular, thanks to our abstract game, we are able to build bipartite graphs to model transaction untraceability, and provide reductions to formally relate the hardness of calculating untraceability to the hardness of calculating the number of perfect matchings in all possible bipartite graphs. We prove that calculating transaction untraceability is a #P-complete problem, which is believed to be even more difficult to solve than NP problems. In addition, we provide the first result on the least upper bound of transaction untraceability. Moreover, through our theoretical results, we are able to provide ways to efficiently and automatically verify whether a given ledger achieves optimal transaction untraceability. Furthermore, we propose a simple strategy for CryptoNote-style blockchain systems to achieve optimal untraceability. We take Monero as a concrete example to demonstrate how to apply this strategy to optimise the untraceability guarantee provided by Monero.
In this paper, the security problem for mobile satellite communication networks (MSNET) has been investigated. With the rapidly growth of communication needs, mobile satellite systems represent a significant solution to provide high-quality communication services to mobile users in under-populated regions, in emergency areas, on planes, trains and ships. However, lacking an effective framework to secure mobile satellite communication networks seriously limited the practicality of satellite services. Therefore, a new security framework have been developed in this paper to address the security challenges in mobile satellite communication network. Firstly, the mobile satellite communication networks have been formulated as delay-tolerance network (DTN). Then, the blockchain technique has been adopted and used in two aspects, i.e. 1) integrating with DTN structure to secure the data communication, 2) combing with the practical satellite constellation management algorithm to defend the unexpected cyber attacks physically. Through integrating emerging blockchain techniques with both communication and physical aspects, the developed framework cannot only effectively detect the cyber attacks, but also better defend the mobile satellite communication networks through communication and satellite management aspects. Eventually, the numerical simulation and experimental tests have been provided to demonstrate the effectiveness of developed MSNET-Blockchain framework.
The rise of blockchain technology has paved the way for an increasing number of blockchain systems, each having different characteristics. The need for distributed applications that span across multiple blockchain systems is increasing. However, it is currently not possible to write a single-description smart contract which can be compiled to span across multiple blockchain systems. In this paper we present PORTHOS, a macroprogramming framework and domain specific language for writing commitment-based smart contracts that span multiple blockchain systems. The language allows programmers to write smart contracts at a higher level of abstraction by composing together contract blocks, without the need to specify how logic should be split across different blockchain instances. A runtime framework, including both on-chain and off-chain functionality, harmonises the features of different blockchain systems as well as enables communication across the smart contracts. A proof of concept, built on the Ethereum and Hyperledger Fabric blockchain systems and extendible to other systems, illustrates the technique and framework. We also show how the PORTHOS language is expressive enough to define a variety of applications.
A blockchain based system integrity (BCSI) framework for assuring the integrity of information system processes is presented. BCSI is well suited for a broad class of large scale real-world information systems. Under the BCSI framework, the integrity of any information system I is assured by executing the finite state machine model for system I processes in a blockchain network. The BCSI framework is compared and contrasted with the Clark-Wilson (CW) system integrity model, and existing blockchain based frameworks like Ethereum.
The relationship between customers, Facility managements and Utility companies can be a challenge. The persistent lack of trust leads to a fraud doubts, disputes and arbitration which results are expensive. Such kind of issues generate expenses for all participants. We have developed three models based on Hyperledger Fabric and we have revealed different difficulties in an every one. Usage of Distributed Ledger Technology based solutions will bring a real value to all actors in the system.
A blockchain is a tamper-proof distributed transaction registry; first popularized by Bitcoin [1], it has now been extended to support storage of arbitrary state and computations in-ledger. Ethereum [2] and its smart contract model have proven to be a very popular choice for this task, routinely managing assets valued in the billions. However, development of such contracts has been anything but easy. While formally specified, the Ethereum execution platform is based on a low-level machine, quite similar to assembly; semantics for contract operations such as call are quite complex, and the need for resource management creates unanticipated modes of failure. The dominant day-to-day programming platform for Ethereum is Solidity [3], an Object-Oriented language that identifies contracts with objects. While reasoning about Solidity programs is much easier than for their bytecode counterparts, it is not extent of challenges either, and moreover, Solidity lacks a source-level semantics, which forces developers to reason over output bytecode again. In this short paper we explore the main barriers to lift in order to achieve a principled compilation strategy for Solidity. We will review the standard concepts on verified and secure compilation, and frame them in the context of the Ethereum platform.
A key issue for Distributed Ledger Technologies is how to agree on any changes to the Ledger; the way to reach such an agreement is known as consensus protocol. There are currently many platforms and implementations of DLTs, each offering a more or less effective way to reach consensus. As a result, it is sometimes difficult to know which consensus mechanism is most appropriate for a given use case. We propose in this short paper a draft methodology to choose between a lottery-based consensus and a voting-based consensus. We take in account several indicators, both related to the requirements of the use case in question, but also to its position relatively to the tradeoff ”Security - Scalability - Decentralization”.
I. INTODUCTION Blockchain technology was first introduced as Bitcoin's underlying technology but soon later its extendable capabilities have been recognized. The peer-to-peer cryptocurrency, Bitcoin, is a core innovation in the financial sector nowadays. Its underlying technology, blockchain, is a type of a distributed ledger especially suitable for processing time ordered data. In addition, embedded cryptography functions of blockchain technology enable integrity of ledgers, authenticity of transactions, and privacy of transactions without a centralized control actor. Those make the blockchain different from traditional distributed database systems being used in the financial sector, e.g., it is practically impossible to modify or delete records of a ledger in the blockchain. This distributed and decentralized nature of the blockchain has attracteded financial institutions over the world to replace existing backbone technologies with blockchain technology. Blockchain keeps a record of all data exchanges -this record is referred to as a "ledger" in the cryptocurrency world, and each data exchange is a "transaction". Every verified transaction is added to the ledger as a "block" It utilizes a distributed system to verify each transaction -a peer-to-peer network of nodes. Once signed and verified, the new transaction is added to the blockchain and cannot be altered In the cryptocurrency world, your wallet address represents public key and your private key is what let's you authorize transfers, withdrawals, and other actions with your digital property like cryptocurrencies. As an aside, this is why it's so important to keep your private key safe -anyone who has your private key can use it to access any of your digital assets associated with your public key and do what they want with it! Each transaction in that ledger will have the same data: a digital signature, a public key, a timestamp, and a unique ID. For instance, the logistics sector considers blockchain technology for real-time visibility, improved efficiency, transparency, verifiability, and cost reduction for logistics. The property sector is adopting blockchain technology as well for digital but unforgeable property records, few disputes, transparency, verifiability, and lower transfer fees. The food sector is also investing blockchain technology to trace the movements of foods and tackle contamination faster.
This article discusses the theoretical composition of the two consensus algorithms in order to obtain a fundamentally new solution to the problem of consensus in a distributed ledger technologies.
Victor Cook, Zachary Painter, Christina Peterson, Damian Dechev
Smart contract transactions demonstrate issues of performance and correctness that application programmers must work around. Although the blockchain consensus mechanism approaches ACID compliance, use cases that rely on frequent state changes are impractical due to the block publishing interval of $O(10^1)$ seconds. The effective isolation level is Read-Committed, only revealing state transitions at the end of the block interval. Values read may be stale and not match program order, causing many transactions to fail when a block is committed. This paper perceives the blockchain as a transactional data structure, using this analogy in the development of a new algorithm, Hash-Mark-Set (HMS), that improves transaction throughput by providing a Read-Uncommitted view of state variables. HMS creates a directed acyclic graph (DAG) from the pending transaction pool. The transaction order derived from the DAG is used to provide a Read-Uncommitted view of the data for new transactions, which enter the DAG as they are received. An implementation of HMS is provided, interoperable with Ethereum and ready for use in smart contracts. Over a wide range of transaction mixes, HMS is demonstrated to improve throughput. A side product of the implementation is a new technique, Runtime Argument Augmentation (RAA), that allows smart contracts to communicate with external data services before submitting a transaction. RAA has use cases beyond HMS and can serve as a lightweight replacement for blockchain oracles.
Yixin Li, Bin Cao, Mugen Peng, Long Zhang · 7 authors
Direct Acyclic Graph (DAG)-based ledger and the corresponding consensus algorithm has been identified as a promising technology for Internet of Things (IoT). Compared with Proof-of-Work (PoW) and Proof-of-Stake (PoS) that have been widely used in blockchain, the consensus mechanism designed on DAG structure (simply called as DAG consensus) can overcome some shortcomings such as high resource consumption, high transaction fee, low transaction throughput and long confirmation delay. However, the theoretic analysis on the DAG consensus is an untapped venue to be explored. To this end, based on one of the most typical DAG consensuses, Tangle, we investigate the impact of network load on the performance and security of the DAG-based ledger. Considering unsteady network load, we first propose a Markov chain model to capture the behavior of DAG consensus process under dynamic load conditions. The key performance metrics, i.e., cumulative weight and confirmation delay are analysed based on the proposed model. Then, we leverage a stochastic model to analyse the probability of a successful double-spending attack in different network load regimes. The results can provide an insightful understanding of DAG consensus process, e.g., how the network load affects the confirmation delay and the probability of a successful attack. Meanwhile, we also demonstrate the trade-off between security level and confirmation delay, which can act as a guidance for practical deployment of DAG-based ledgers.
This paper presents a novel leaderless protocol (FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures) with a low communicational complexity and which allows a set of nodes to come to a consensus on a value of a single bit. The paper makes the assumption that part of the nodes are Byzantine, and are thus controlled by an adversary who intends to either delay the consensus, or break it (this defines that at least a couple of honest nodes come to different conclusions). We prove that, nevertheless, the protocol works with high probability when its parameters are suitably chosen. Along this the paper also provides explicit estimates on the probability that the protocol finalizes in the consensus state in a given time. This protocol could be applied to reaching consensus in decentralized cryptocurrency systems. A special feature of it is that it makes use of a sequence of random numbers which are either provided by a trusted source or generated by the nodes themselves using some decentralized random number generating protocol. This increases the overall trustworthiness of the infrastructure. A core contribution of the paper is that it uses a very weak consensus to obtain a strong consensus on the value of a bit, and which can relate to the validity of a transaction.
Lachlan J. Gunn, Jian Liu, Bruno Vavala, N. Asokan
Consensus mechanisms used by popular distributed ledgers are highly scalable but notoriously inefficient. Byzantine fault tolerance (BFT) protocols are efficient but far less scalable. Speculative BFT protocols such as Zyzzyva and Zyzzyva5 are efficient and scalable but require a trade-off: Zyzzyva requires only $3f + 1$ replicas to tolerate $f$ faults, but even a single slow replica will make Zyzzyva fall back to more expensive non-speculative operation. Zyzzyva5 does not require a non-speculative fallback, but requires $5f + 1$ replicas in order to tolerate $f$ faults. BFT variants using hardware-assisted trusted components can tolerate a greater proportion of faults, but require that every replica have this hardware. We present SACZyzzyva, addressing these concerns: resilience to slow replicas and requiring only $3f + 1$ replicas, with only one replica needing an active monotonic counter at any given time. We experimentally evaluate our protocols, demonstrating low latency and high scalability. We prove that SACZyzzyva is optimally robust and that trusted components cannot increase fault tolerance unless they are present in greater than two-thirds of replicas.
Abstract Modern distributed data management systems face a new challenge: how can autonomous, mutually distrusting parties cooperate safely and effectively? Addressing this challenge brings up familiar questions from classical distributed systems: how to combine multiple steps into a single atomic action, how to recover from failures, and how to synchronize concurrent access to data. Nevertheless, each of these issues requires rethinking when participants are autonomous and potentially adversarial. We propose the notion of a cross-chain deal , a new way to structure complex distributed computations that manage assets in an adversarial setting. Deals are inspired by classical atomic transactions, but are necessarily different, in important ways, to accommodate the decentralized and untrusting nature of the exchange. We describe novel safety and liveness properties, along with two alternative protocols for implementing cross-chain deals in a system of independent blockchain ledgers. One protocol, based on synchronous communication, is fully decentralized, while the other, based on semi-synchronous communication, requires a globally shared ledger. We also prove that some degree of centralization is required in the semi-synchronous communication model.
Kun Wu, Guohao Dai, Xing Hu, Shuangchen Li · 7 authors
Blockchain applications have shown huge potential in various domains. Proof of Work (PoW) is the key procedure in blockchain applications, which exhibits the memory-bound characteristic and hinders the performance improvement of blockchain accelerators. In order to mitigate the "memory wall" and improve the performance of memory-hard PoW accelerators, using Ethash as an example, we optimize the memory architecture from two perspectives: 1) Hiding memory latency. We propose specialized context switch design to overcome the uncertain cycles of repetitive memory requests. 2) Increasing memory bandwidth utilization. We introduce on-chip memory that stores a portion of the Ethash directed acyclic graph (DAG) for larger effective memory bandwidth, and further propose adopting embedded NOR flash to fulfill the role. Then, we conduct extensive experiments to explore the design space of our optimized memory architecture for Ethash, including number of hash cores, on-chip/off-chip memory technologies and specifications. Based on the design space exploration, we finally provide the guidance for designing the memory-bound PoW accelerator. The experiment results show that our optimized designs achieve 8.7% -- 55% higher hash rate and 17% -- 120% higher hash rate per Joule compared with the baseline design in different configurations.
Victor Zakhary, Mohammad Javad Amiri, Sujaya Maiyya, Divyakant Agrawal · 5 authors
Permissionless blockchains (e.g., Bitcoin, Ethereum, etc) have shown a wide success in implementing global scale peer-to-peer cryptocurrency systems. In such blockchains, new currency units are generated through the mining process and are used in addition to transaction fees to incentivize miners to maintain the blockchain. Although it is clear how currency units are generated and transacted on, it is unclear how to use the infrastructure of permissionless blockchains to manage other assets than the blockchain's currency units (e.g., cars, houses, etc). In this paper, we propose a global asset management system by unifying permissioned and permissionless blockchains. A governmental permissioned blockchain authenticates the registration of end-user assets through smart contract deployments on a permissionless blockchain. Afterwards, end-users can transact on their assets through smart contract function calls (e.g., sell a car, rent a room in a house, etc). In return, end-users get paid in currency units of the same blockchain or other blockchains through atomic cross-chain transactions and governmental offices receive taxes on these transactions in cryptocurrency units.