Rati Gelashvili, Alexander Spiegelman, Zhuolun Xiang, George Danezis · 8 authors
Block-STM is a parallel execution engine for smart contracts, built around the principles of Software Transactional Memory. Transactions are grouped in blocks, and every execution of the block must yield the same deterministic outcome. Block-STM further enforces that the outcome is consistent with executing transactions according to a preset order, leveraging this order to dynamically detect dependencies and avoid conflicts during speculative transaction execution. At the core of Block-STM is a novel, low-overhead collaborative scheduler of execution and validation tasks.
In blockchain systems, the scarcity of a resource is used as a Sybil protection mechanism. In Proof-of-Work blockchains, that resource is computing power. In the event of a fork, the scarcity of this resource theoretically prevents miners from producing blocks on both branches of a fork. In Proof-of-Stake blockchains, because that resource is token stake, the computational cost of creating a block is negligible. In the event of a fork, and if no specific measures have been taken, rational block producers should extend both branches of the fork. In blockchains with sequential block production, a punishment mechanism known as slashing is often cited as a protection against the nothing-at-stake problem. However, in the context of a blockchain with parallel block production, it seems that slashing is not sufficient against the numerous divergence opportunities. In this paper, we propose a novel protection against the nothing-at-stake problem that takes the most out of BFT and Nakamoto-based consensus. By combining those approaches, we wish to scale up blockchains by allowing parallel block production without reconciliation.
Haytham Qushtom, Jelena Mišić, Vojislav B. Mišić, Xiaolin Chang
Consensus algorithms based on the proof-of-stake (PoS) are becoming a viable alternative to proof-of-work-based distributed blockchain ledgers. In this work, we integrated PoS with Practical Byzantine Fault Tolerance (PBFT) to ensure truthful and honest behavior of all nodes, leaders and ordinary nodes alike, that participate in block validation and ordering processes in a permissioned network environment. The proposed scheme is modeled using Markov Chain and probabilistic analysis, and it is shown to ensure proper consensus-based decision making even in case of substantial probability of dishonest node behavior.
Soosan Naderi Mighan, Jelena Mišić, Vojislav B. Mišić
In this paper, we provide a comprehensive analytical model for transaction distribution time in Ethereum derived from the analytical model of gossip data delivery protocol. We introduce three classes of priority for transactions which corresponds to the current Ethereum fee scheme and investigate the impact of transaction priority on response and delivery times using a Jackson network and priority queuing system. Our results show that the delivery times depend on priority and that their distribution is slightly hyper-exponential. We also note anomalous scenarios where lowest priority transactions receive faster service than medium priority ones.
Margarita Capretto, Martín Ceresa, Antonio Fernández Anta, Antonio Russo · 5 authors
Blockchain technologies are facing a scalability challenge, which must be overcome to guarantee a wider adoption of the technology. This scalability issue is due to the use of consensus algorithms to guarantee the total order of the chain of blocks (and of the transactions within each block). However, total order is often not fully necessary, since important advanced applications of smart-contracts do not require a total order among all operations. A much higher scalability can potentially be achieved if a more relaxed order (instead of a total order) can be exploited. In this article, we propose a novel distributed concurrent data type, Setchain , which significantly improves scalability. A Setchain implements a grow-only set whose elements are not ordered, unlike conventional blockchain operations. When convenient, the Setchain allows forcing a synchronization barrier that assigns permanently an epoch number to a subset of the latest elements added, agreed by consensus. Therefore, two operations in the same epoch are not ordered, while two operations in different epochs are ordered by their respective epoch number. We present different Byzantine-tolerant implementations of Setchain, prove their correctness, and report on an empirical evaluation of a prototype implementation. Our results show that Setchain is orders of magnitude faster than consensus-based ledgers, since it implements grow-only sets with epoch synchronization instead of total order. Since the Setchain barriers can be synchronized with the underlying blockchain, Setchain objects can be used as a sidechain to implement many decentralized solutions with much faster operations than direct implementations on top of blockchains. Finally, we also present an algorithm that encompasses into a single process the combined behavior of the Byzantine servers, which simplifies correctness proofs by encoding the general attacker in a concrete implementation.
Haytham Qushtom, Jelena Mišić, Vojislav B. Mišić, Xiaolin Chang
The consensus algorithm is an essential ingredient of any blockchain system. Many different consensus mechanisms, such as practical Byzantine fault tolerance (PBFT), Proof-of-Work (PoW), Proof-of-Stake (PoS), and their many derivatives, have been proposed over the years, but the complementary problems of performance and resilience to malicious behavior of the nodes have yet to be resolved in a satisfactory manner. In this work, we propose a consensus mechanism that integrates PoS with PBFT, which can effectively deal with dishonest nodes, both individual validators and leaders, while maintaining high performance. Our model incentivized truthful behavior by using trust score and reward mechanisms as crucial components of the block validation and ordering processes. The performance of the proposed scheme is evaluated using an analytical model that employs a semi-Markov process, defined by an ergodic multidimensional Markov chain with a finite number of states. The results show the efficiency of the proposed model in consensus-based decision making, even under a high likelihood of dishonest node behavior.
Decentralized systems built around blockchain technology promise clients an immutable ledger. They add a transaction to the ledger after it undergoes consensus among the replicas that run a Proof-of-Stake (PoS) or Byzantine Fault-Tolerant (BFT) consensus protocol. Unfortunately, these protocols face a long-range attack where an adversary having access to the private keys of the replicas can rewrite the ledger. An existing solution to this problem forces each committed block from these protocols to undergo another consensus, Proof-of-Work (PoW) consensus; POW protocol wastes computational resources as miners compete to solve complex puzzles. In this paper, we present the design of our Power-of-Collaboration (POC) protocol, which guards existing POS/BFT blockchains against long-range attacks and requires miners to collaborate rather than compete. POC guarantees fairness and accountability and only marginally degrades the throughput of the underlying system.
Distributed Ledger Technology (DLT) allows the maintenance of a continuously growing ledger in a peer-to-peer network. Nodes participating in the network require significant computational power and memory to download and verify the ledger. To solve this problem, light clients were developed to verify the integrity of the ledger by downloading only a subset of the ledger, but they are vulnerable to malicious influence. The thesis presents Aurora, a set of three stochastic algorithms that add trustlessness to DLT networks by analyzing the network structure and discovering sets that contain honest nodes that can be used for future interactions. The solution allows a new node to join the network and initiate ledger download with an honest node, or to check the presence of a transaction without downloading the entire ledger or a subset of the ledger. The work provides a comprehensive overview of DLT, pseudocode for the solution, and an evaluation procedure using open-source DLT simulation tools. Furthermore, the solution was integrated into Trinity, a Python-based DLT client for the Ethereum network, and was evaluated on the Ethereum production network, consuming approximately 0.31 MB of RAM and 1 MB of storage at runtime. The proposed solution outperforms other state-of-the-art solutions and can be deployed on resource-constrained devices. It incentivizes users to interact with the ledger in a trustless manner. Overview of scientific contribution: 1. A new probabilistic honest set creation algorithm 2. A new probabilistic transaction history synchronization algorithm 3. A new probabilistic transaction presence checking algorithm 4. A new evaluation procedure in a resource constrained environment
Abstract A consensus protocol is a crucial mechanism of distributed networks by which nodes can coordinate their actions and the current state of data. This article describes a BlockDAG consensus algorithm based on the Proof of Stake approach. The protocol provides network participants with cross‐voting for the order of blocks, which, in the case of a fair vote, guarantees a quick consensus. Under conditions of dishonest behavior, cross‐voting ensures that violations will be quickly detected. In addition, the protocol assumes the existence of a Coordinating network containing information about the approved ordering, which qualitatively increases security and also serves to improve network synchronization.
Hyperledger Fabric is a popular permissioned blockchain system that features a highly modular and extensible system for deploying permissioned blockchains which are expected to have a major effect on a wide range of sectors. Unlike traditional blockchain systems such as Bitcoin and Ethereum, Hyperledger Fabric uses the EOV model for transaction processing: the submitted transactions are executed by the endorsing peer, ordered and batched by the ordering services, and validated by the validating peers. Due to this EOV workflow, a well-documented issue that arises is the multi-version concurrency control conflict. This happens when two transactions try to writes and read the same key in the ledger at the same time. Existing solutions to address this problem includes eliminating blocks in favor of streaming transactions, repairing conflicts during the ordering phase, and automatically merging the conflicting transactions using CRDT (Conflict Free Replicated Data) techniques. In this paper, we propose a novel solution called Early Detection for MVCC Conflicts. Our solution detects the conflicting transactions at an early stage of the transaction execution instead of processing them until the validation phase to be aborted. The advantage of our solution is that it detects conflict as soon as possible to minimize the overhead of conflicting transaction on the network resulting in the reduction of the end-to-end transaction latency and the increase of the system's effective throughput. We have successfully implemented our solution in Hyperledger Fabric. We propose three different implementations which realize early detection. Our results show that our solutions all perform better than the baseline Fabric, with our best solution SyncMap which improves the goodput by up to 23% and reduces the latency by up to 80%.
Majed Abdullah Alrowaily, Mansoor Alghamdi, Ibrahim S. Alkhazi, Ahmad B. Hassanat · 6 authors
Blockchain technology has a wide range of applicability in the fields of transportation infrastructure construction and maintenance, transportation big data analysis and application, expressway toll collection, and logistics. The core technology lies in the distributed, decentralized, immutable, and programmable features brought about by consensus. This paper studies the dynamic analytical modeling of Proof-Based Consensus (PBC) strategies in blockchain systems, focusing on basic strategies, including Proof of Work (PoW), Proof of Stake (PoS), Proof of Authority (PoA), and Proof of Luck (PoL), which can be extended to other PBC models. We focus on modeling these typical strategies and discuss their solution characteristics in terms of algorithmic mechanisms and principles. The relevant results can be used for quantitative analysis and evaluation of distributed consensus based on the model.
Most current cross-blockchain approaches focus on exchanging or transferring tokens between networks. While some concepts foster smart contract invocations across blockchains, they require multiple transactions and operate asynchronously. We present a concept enabling instant smart contract calls by creating synchronized client contracts on arbitrary blockchains. Other smart contracts can query these client contracts on the target blockchain for retrieving information without requiring cross-chain message queues. With this, we reduce the dependency of smart contracts on their host blockchain, as remote contracts become available as read-only instances. The synchronization process does not require trust in the executing intermediary since Merkle proofs based on shared state roots are utilized to guarantee correct execution. We propose a novel concept called transition proofs for efficiently proving the correctness of state updates. The prototypical implementation permits smart contract synchronization between EVM-compatible blockchains. Our evaluation shows the approach’s applicability regarding execution costs and delay. Further, we conduct a case study by synchronizing one of the largest decentralized exchanges deployed to the Ethereum network.
Blockchain consensus protocols have been a focus of attention since the advent of Bitcoin. Although classic distributed consensus algorithms made significant contributions to the development of blockchain consensus protocols, there are still many issues to be resolved due to the complexity and diversity of the blockchain. In this survey, we summarize the state-of-the-art blockchain consensus protocols. We first introduce the theoretical basis, models, and challenges of blockchain consensus protocols. Then, we present the existing blockchain protocols in the categories of proof-based protocols, committee-based protocols, and other miscellaneous protocols. Finally, we analyze their performance and discuss future research directions by comparing existing protocols.
Rui Morais, Paul Crocker, Valderi Reis Quietinho Leithardt
This paper presents the research undertaken with the goal of designing a consensus algorithm for cryptocurrencies with less latency than the current state-of-the-art while maintaining a level of throughput and scalability sufficient for real-world payments. The result is Nero, a new deterministic leaderless byzantine consensus algorithm in the partially synchronous model that is especially suited for Directed Acyclic Graph (DAG)-based cryptocurrencies. In fact, Nero has a communication complexity of O(n3) and terminates in two message delays in the good case (when there is synchrony). The algorithm is shown to be correct, and we also show that it can provide eventual order. Finally, some performance results are given based on a proof of concept implementation in the Rust language.
Lionel Beltrando, Maria Potop-Butucaru, José Alfaro
Blockchain and distributed ledger technologies have emerged as one of the most revolutionary distributed systems, with the goal of eliminating centralised intermediaries and installing distributed trusted services. They facilitate, trustworthy trades and exchanges, over the Internet, power cryptocurrencies, ensure transparency for documents, and much more. Committee-based blockchains are considered today as a viable alternative to the original Proof-ofWork paradigm, since they offer strong consistency and are energy efficient. One of the most popular committee-based blockchains is Tendermint used as core by several popular blockchains such as Tezos, Binance Smart Chain and Cosmos. Tendermint as many other committee-based blockchains is designed to tolerate one-third of Byzantine nodes. In this paper we propose TenderTee, an enhanced version of Tendermint, able to tolerate one half of Byzantine nodes. The resilience improvement is due to the use of a trusted abstraction, a light version of attested append-only memory, which makes the protocol immune to equivocation (i.e. behavior of a faulty node when it sends different faulty messages to different nodes.). Furthermore, we prove the correctness of TenderTee for both one-shot and repeated consensus specifications.
Blockchain is a distributed ledger that uses cryptography and consensus protocols to record a growing list of transactions in a tamper-resistant manner. Scalability is one of the main problems that limit its usage. This paper introduces a full sharding protocol, Geochain, for permissioned blockchains. We first clarify the limitations of state-of-the-art sharding protocols. Then, we propose a locality-based sharding protocol that achieves high scalability. We optimize inter-shard performance by clustering participants using their geographical properties, locality. In addition, the locality is also employed to decide the transaction placement which results in a low ratio of cross-shard transactions for applications, such as everyday banking, retail payments, and electric vehicle charging. We also propose a client-driven efficient mechanism to handle cross-shard transactions and present an analysis. This enables clients to manage their assets across different shards directly. A prototype is implemented on top of Hyperledger Fabric v2.3 and evaluated on Amazon EC2. The experiments show that our protocol doubles the peak throughput, even with a high ratio of cross-shard transactions, while minimizing the transaction latency.
The network formation process in the Bitcoin protocol is designed to hide the global network structure: while most of the nodes of the network can be easily discovered, the existence of an edge between two nodes is only known by the two endpoints. In [Becchetti et al., SODA2020] the authors propose a dynamic random graph model inspired by the network formation process in the Bitcoin protocol and they prove that the evolution of the graph quickly terminates and that the resulting graph is an expander, with high probability.
Santiago Cuéllar Gempeler, Bill Harris, James Parker, Stuart Pernsteiner · 6 authors
Currently, when a security analyst discovers a vulnerability in critical software system, they must navigate a fraught dilemma: immediately disclosing the vulnerability to the public could harm the system’s users; whereas disclosing the vulnerability only to the software’s vendor lets the vendor disregard or deprioritize the security risk, to the detriment of unwittingly-affected users. A compelling recent line of work aims to resolve this by using Zero Knowledge (ZK) protocols that let analysts prove that they know a vulnerability in a program, without revealing the details of the vulnerability or the inputs that exploit it. In principle, this could be achieved by generic ZK techniques. In practice, ZK vulnerability proofs to date have been restricted in scope and expressibility, due to challenges related to generating proof statements that model real-world software at scale and to directly formulating violated properties. This article presents Cheesecloth , a novel proof-statement compiler, which proves practical vulnerabilities in ZK by soundly-but-aggressively preprocessing programs on public inputs, selectively revealing information about executed control segments, and formalizing information leakage using a novel storage-labeling scheme. Cheesecloth ’s practicality is demonstrated by generating ZK proofs of well-known vulnerabilities in (previous versions of) critical software, including the Heartbleed information leakage in OpenSSL, a memory vulnerability in the FFmpeg multimedia encoding framework, a cryptographic implementation bug in the Secure Scuttlebutt decentralised social network, and a denial of service vulnerability in OpenSSL.
In a permissionless system like Ethereum, participation may fluctuate dynamically as some participants unpredictably go offline and some others come back online. In such an environment, traditional Byzantine fault-tolerant consensus algorithms may stall - even in the absence of failures - because they rely on the availability of fixed-sized quorums. The sleepy model formally captures the main requirements for solving consensus under dynamic participation, and several algorithms solve consensus with probabilistic safety in this model assuming that, at any time, more than half of the online participants are well behaved. However, whether safety can be ensured deterministically under these assumptions, especially with constant latency, remained an open question. Assuming a constant adversary, we answer in the positive by presenting a consensus algorithm that achieves deterministic safety and constant latency in expectation. In the full version of this paper, we also present a second algorithm which obtains both deterministic safety and liveness, but is likely only of theoretical interest because of its high round and message complexity. Both algorithms are striking in their simplicity.
In the development of large-scale, integrated systems, the consistent clarity and distribution of knowledge and relevant status is crucial to success. There are many existing methods and commercial tools for providing context and traceability from requirements and specifications to a system's artifacts, but these tools are often vendor-locked and require access to cloud-based services and necessitate high licensing costs. Further, modern large-scale systems development involves multiple business partners, each of which needs to ensure their teams have granular, role-based access to all relevant information without impediment; centralized warehousing and gatekeeping should not be handled by a single entity if the information is to remain readily accessible. Instead, a permissioned, distributed knowledgebase that avoids vendor lock-in enables a consistent, real-time view of information that provides equivalent context for developers and other stakeholders. ChaordicLedger, a free and open source (FOSS) project joins the transparency and smart contract aspects of Distributed Ledger Technology with the storage capabilities of a Distributed File System to fulfill this industrial application while allowing for industry-specific customizations.
Blockchain consensus protocols are responsible for coordinating the nodes to make agreements on the transaction results. Their implementation bugs, including memory-related and consensus logic vulnerabilities, may pose serious threats. Fuzzing is a promising technique for protocol vulnerability detection. However, existing fuzzers cannot deal with complex consensus states of distributed nodes, thus generating a large number of useless packets, inhibiting their effectiveness in reaching the deep logic of consensus protocols.