Blockchain Papers

Chrysoula Stathakopoulou, Tudor David, Marko Vukolić

No abstract is available for this record.

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.

Yulong Wu, Yunfei Zha, Yao Sun

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.

H. M. N. Dilum Bandara, Xiwei Xu, Ingo Weber

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.

Jiangshan Yu, Man Ho Au, Paulo Esteves-Veríssimo

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.

Emilio Jesús Gallego Arias

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.

Mrs. Divya K V

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.

Weigandt Consulting, Vladimirovich Toporov Mikhail, Oleg Yurievich Sabinin

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.

Serguei Popov, William J. Buchanan

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.

Maurice Herlihy, Barbara Liskov, Liuba Shrira

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.

Mustafa Al-Bassam

We propose LazyLedger, a design for distributed ledgers where the blockchain\nis optimised for solely ordering and guaranteeing the availability of\ntransaction data. Responsibility for executing and validating transactions is\nshifted to only the clients that have an interest in specific transactions\nrelating to blockchain applications that they use. As the core function of the\nconsensus system of a distributed ledger is to order transactions and ensure\ntheir availability, consensus participants do not necessarily need to be\nconcerned with the contents of those transactions. This reduces the problem of\nblock verification to data availability verification, which can be achieved\nprobabilistically with sub-linear complexity, without downloading the whole\nblock. The amount of resources required to reach consensus can thus be\nminimised, as transaction validity rules can be decoupled from consensus rules.\nWe also implement and evaluate several example LazyLedger applications, and\nvalidate that the workload of clients of specific applications does not\nsignificantly increase when the workload of other applications that use the\nsame chain increase.\n

Alain Brenzikofer, Noa Melchior

Quartierstrom creates a peer-to-peer marketplace for locally generated solar power. The marketplace is implemented as a smart contract on a permissioned blockchain governed by all prosumers. Two privacy-by-design concepts are presented which guarantee that the users individual load profile is not leaked to any third party despite using a blockchain. The first approach leverages UTXO based coin mixing protocols in combination with an account-based on-chain smart contract. The second approach relies on an off-chain smart contract running in trusted execution environments.

Shuaifeng Pang, Xiaodong Qi, Zhao Zhang, Cheqing Jin · 5 authors

Although the emergence of the programmable smart contract makes blockchain systems easily embrace a wider range of industrial areas, how to execute smart contracts efficiently becomes a big challenge nowadays. Due to the existence of Byzantine nodes, the mechanism of executing smart contracts is quite different from that in database systems, so that existing successful concurrency control protocols in database systems cannot be employed directly. Moreover, even though smart contract execution follows a two-phase style, i.e, the miner node executes a batch of smart contracts in the first phase and the validators replay them in the second phase, existing parallel solutions only focus on the optimization in the first phase, but not including the second phase. In this paper, we propose a novel efficient concurrency control scheme which is the first one to do optimization in both phases. Specifically, (i) in the first phase, we give a variant of OCC (Optimistic Concurrency Control) protocol based on {\em batching} feature to improve the concurrent execution efficiency for the miner and produce a schedule log with high parallelism for validators. Also, a graph partition algorithm is devised to divide the original schedule log into small pieces and further reduce the communication cost; and (ii) in the second phase, we give a deterministic OCC protocol to replay all smart contracts efficiently on multi-core validators where all cores can replay smart contracts independently. Theoretical analysis and extensive experimental results illustrate that the proposed scheme outperforms state-of-art solutions significantly.

Dumitrel Loghin, Gang Chen, Tien Tuan Anh Dinh, Beng Chin Ooi · 5 authors

Motivated by the massive energy usage of blockchain, on the one hand, and by significant performance improvements in low-power, wimpy systems, on the other hand, we perform an in-depth time-energy analysis of blockchain systems on low-power nodes in comparison to high-performance nodes. We use three low-power systems to represent a wide range of the performance-power spectrum, while covering both x86/64 and ARM architectures. We show that low-end wimpy nodes are struggling to run full-fledged blockchains mainly due to their small and low-bandwidth memory. On the other hand, wimpy systems with balanced performance-to-power ratio achieve reasonable performance while saving significant amounts of energy. For example, Jetson TX2 nodes achieve around 80% and 30% of the throughput of Parity and Hyperledger, respectively, while using 18x and 23x less energy compared to traditional brawny servers with Intel Xeon CPU.

Yu‐Jin Kwon, Jian Liu, Minjeong Kim, Dawn Song · 5 authors

Bitcoin uses blockchain technology and proof-of-work (PoW) mechanism where nodes spend computing resources and earn rewards in return for spending these resources. This incentive system has caused power to be significantly biased towards a few nodes, called mining pools. In fact, poor decentralization appears not only in PoW-based coins but also in coins adopting other mechanisms such as proof-of-stake (PoS) and delegated proof-of-stake (DPoS). In this paper, we target this centralization issue. To this end, we first define (m, \varepsilon, δ)-decentralization as a state that satisfies 1) there are at least m participants running a node and 2) the ratio between the total resource power of nodes run by the richest and δ-th percentile participants is less than or equal to 1+\varepsilon. To see if it is possible to achieve good decentralization, we introduce sufficient conditions for the incentive system of a blockchain to reach (m, \varepsilon, δ)-decentralization. When satisfying the conditions, a blockchain system can reach full decentralization with probability 1. However, to achieve this, the blockchain system should be able to assign a positive Sybil cost, where the Sybil cost is defined as the difference between the cost for one participant running multiple nodes and the total cost for multiple participants each running one node. On the other hand, we prove that when there is no Sybil cost, the probability of reaching (m, \varepsilon, δ)-decentralization is upper bounded by a value close to 0, considering a large rich-poor gap. To determine the conditions that each system cannot satisfy, we also analyze protocols of all PoW, PoS, and DPoS coins in the top 100 coins according to our conditions. Finally, we conduct data analysis of these coins to validate our theory.

Mustafa Bal, Caitlin Ner

Various start-up developers and academic researchers have investigated the\nusage of blockchain as a data storage medium due to the advantages offered by\nits tamper-proof and decentralized nature. However, there have not been many\nattempts to provide a standard platform for virtually storing the states of\nunique tangible entities and their subsequent modifications. In this paper, we\npropose NFTracer, a non-fungible token tracking proof-of-concept based on\nHyperledger Composer and Hyperledger Fabric Blockchain. To achieve the\ncapabilities of our platform, we use NFTracer to build an artwork auction and a\nreal estate auction, which vary in technical complexity and demonstrate the\nadvantages of being able to track entities and their resulting modifications in\na decentralized manner. We also present its accompanying modular architecture\nand system components, and discuss possible future works on NFTracer.\n