With the advent of Bitcoin, the interest of the database community in blockchain systems has steadily grown. Many existing blockchain applications use blockchains as a platform for monetary transactions, however. We deviate from this philosophy and present ResilientDB, which can serve in a suite of non-monetary data-processing blockchain applications. Our ResilientDB uses state-of-the-art technologies and includes a novel visualization that helps in monitoring the state of the blockchain application.
Suyash Gupta, Jelle Hellings, Sajjad Rahnama, Mohammad Sadoghi
Since the introduction of Bitcoin---the first widespread application driven by blockchains---the interest in the design of blockchain-based applications has increased tremendously. At the core of these applications are consensus protocols that securely replicate client requests among all replicas, even if some replicas are Byzantine faulty. Unfortunately, these consensus protocols typically have low throughput, and this lack of performance is often cited as the reason for the slow wider adoption of blockchain technology. Consequently, many works focus on designing more efficient consensus protocols to increase throughput of consensus. We believe that this focus on consensus protocols only explains part of the story. To investigate this belief, we raise a simple question: Can a well-crafted system using a classical consensus protocol outperform systems using modern protocols? In this tutorial, we answer this question by diving deep into the design of blockchain systems. Further, we take an in-depth look at the theory behind consensus, which can help users select the protocol that best-fits their requirements. Finally, we share our vision of high-throughput blockchain systems that operate at large scales.
Given that Proof-of-Work (PoW) and Proof-of-Stake (PoS) are plutocratic, and other common consensus protocols are mostly permission-based, we look for a consensus protocol that will suit the needs of e-Democracy. In particular, what we need is a distributed ledger that will record and, to the possible extent, execute the public will. We propose a combination of any given permission-based protocol together with a trust graph between the nodes, which supplies the required permission for new nodes. As a result, the consensus protocol reaches consensus at every iteration between a known list of agents and then updates this list between iterations. This paper is based on prior work that shows the conditions under which a community can grow while maintaining a bounded number of byzantines. It combines a permission-based consensus protocol (such as pBFT) with a community expansion algorithm (such as the one in the prior work) to arrive at a consensus protocol in which the set of agents can change in time, while being sybil-resilient.
Igor Machado Coelho, Vitor N. Coelho, Rodolfo Pereira Araújo, Wang Yong Qiang · 5 authors
Consensus mechanisms are a core feature for handling negotiation and agreements. Blockchain technology has seen the introduction of different sorts of consensus mechanism, ranging from tasks of heavy computation to the subtle mathematical proofs of Byzantine agreements. This paper presents the pioneer Delegated Byzantine Fault Tolerance (dBFT) protocol of Neo Blockchain, which was inspired by the Practical Byzantine Fault Tolerance (PBFT). Besides introducing its history, this study describes proofs and didactic examples, as well as novel design and extensions for Neo dBFT with multiple block proposals. Finally, we discuss challenges when dealing with strong Byzantine adversaries, and propose solutions inspired on PBFT for current weak-synchrony problems and increasing system robustness against attacks. Key Contribution: Presents an overview of the history of PBFT-inspired consensus for blockchain, highlighting its current importance on the literature, challenges and assumptions. Contributes to the field of Distributed Consensus, proposing novel extensions for the Neo dBFT (dBFT 2.0+, dBFT 3.0 and dBFT 3.0+), with new insights on innovative consensus mechanisms.
Sharding is a promising blockchain scaling solution. But it currently suffers from high latency and low throughput when it comes to cross-shard transactions, i.e., transactions that require coordination from multiple shards. The root cause of these limitations arise from the use of the classic two-phase commit protocol, which involves locking assets for extended periods of time. This paper presents Rivet, a new paradigm for blockchain sharding that achieves lower latency and higher throughput for cross-shard transactions. Rivet has a single reference shard running consensus, and multiple worker shards maintaining disjoint states and processing a subset of transactions in the system. Rivet obviates the need for consensus within each worker shard, and as a result, tolerates more failures within a shard and lowers communication overhead. We prove the correctness and security of Rivet. We also propose a more realistic framework for evaluating sharded blockchains by creating a benchmark based on real Ethereum transactions. An evaluation of our prototype implementation of Rivet and the baseline two-phase commit, atop 50+ AWS EC2 instances, using our evaluation framework demonstrates the latency and throughput improvements for cross-shard transactions.
A blockchain is a distributed ledger forming a distributed consensus on a history of transactions, and is the underlying technology for the Bitcoin cryptocurrency. Its applications are far beyond the financial sector. The transaction verification process for cryptocurrencies is much slower than traditional digital transaction systems. One approach to scalability or the speed at which transactions are processed is to design a solution that offers faster Proof of Work. In this paper, we propose a method for accelerating the process of Proof of Work based on parallel mining rather than solo mining. The goal is to ensure that no more than two or more miners put the same effort into solving a specific block. The proposed method includes a process for selection of a manager, distribution of work and a reward system. This method has been implemented in a test environment that contains all the characteristics needed to perform Proof of Work for Bitcoin and has been tested, using a variety of case scenarios, by varying the difficulty level and number of validators. Experimental evaluations were performed locally and in a cloud environment, and experimental results demonstrate the feasibility the proposed method.
To enable roaming of users, the cellular ecosystem integrates many entities and procedures, including specific infrastructure to connect Mobile Network Operators (MNOs), business partnerships or the use of third-party Data Clearing Houses (DCHs) for billing. Many of these rely on specifications rooted in dated and arcane practices, involving long waiting periods for financial clearing, complex billing models, and disparate mechanisms for dealing with inter-MNO disputes. In this paper, we propose a novel solution, DICE (Dynamic Interconnections for the Cellular Ecosystem), aimed at facilitating dynamic collaboration between MNOs, and sustain fluid interconnection models between the end-users and MNOs. DICE uses distributed ledger technology (DLT) to enable MNOs to interact directly, and offer customizable services to their users through the use of crypto-currencies. We leverage real-world data from a major operational MNO in Europe to support our claims, and to extract the requirements for the DICE system. We introduce the DICE protocol, and discuss real-world implementation considerations.
Fault-tolerant distributed systems move the trust in a single party to a majority of parties participating in the protocol. This makes blockchain based crypto-currencies possible: they allow parties to agree on a total order of transactions without a trusted third party. To trust a distributed system, the security of the protocol and the correctness of the implementation must be indisputable. We present the first machine checked proof that guarantees both safety and liveness for a consensus algorithm. We verify a Proof of Stake (PoS) Nakamoto-style blockchain (NSB) protocol, using the foundational proof assistant Coq. In particular, we consider a PoS NSB in a synchronous network with a static set of corrupted parties. We define execution semantics for this setting and prove chain growth, chain quality, and common prefix which together imply both safety and liveness.
The long-standing impossibility of reaching agreement restricts the lifespan of blockchains. In fact, the consensus on a block to be appended to any blockchain succeeds either with some probability or at the condition that two thirds of the $n$ replicas are not Byzantine. In the former case, the probability that the blockchain fails grows exponentially with the number of newly appended blocks. In the latter case, the blockchain fails as soon as a coalition bribes $f=n/3$ replicas. As a result, one may wonder whether blockchains are doomed to fail.
In this paper, we answer this question in the negative by proposing the first Longlasting Blockchain system, \emph{LLB}. LLB builds upon the observation that blockchains are rarely subject to benign faults. As opposed to probabilistic blockchains, LLB solves consensus deterministically when $f<n/3$. As opposed to Byzantine fault tolerant blockchains, it resolves a series of disagreements by reducing eventually the number of deceitful replicas from $n/3\leq f<2n/3$ to $f'<n'/3$ among a new set of $n'$ replicas. To demonstrate its effectiveness, we implement two coalition attacks and a zero loss payment application that forces replicas that misbehave to reimburse conflicting transactions. Finally, LLB outperforms the raw state machine replication at the heart of Facebook's Libra and achieves performance comparable to a scalable blockchain that cannot tolerate $n/3$ failures.
Max DiGiacomo-Castillo, Yiyun Liang, Advay Pal, John C. Mitchell
The Bitcoin Backbone Protocol [GKL15] is an abstraction of the bitcoin proof-of-work consensus protocol. We use a model-checking tool (UPPAALSMC) to examine the concrete security of proof-ofwork consensus by varying protocol parameters and using an adversary that leverages the selfish mining strategy introduced in [GKL15]. We provide insights into modeling proof-of-work protocols and demonstrate tradeoffs between operating parameters. Applying this methodology to protocol design options, we show that the uniform tie-breaking rule from [ES18] decreases the failure rate of the chain quality property, but increases the failure rate of the common prefix property. This tradeoff illustrates how design decisions affect protocol properties, within a range of concrete operating conditions, in a manner that is not evident from prior asymptotic analysis.
This paper presents LinSBFT, a Byzantine Fault Tolerance (BFT) protocol with the capacity of processing over 2000 smart contract transactions per second in production. LinSBFT applies to a permissionless, public blockchain system, in which there is no public-key infrastructure, based on the classic PBFT with 4 improvements: (\romannumeral1) LinSBFT achieves $O(n)$ worst-case communication volume, in contract to PBFT's $O(n^4)$; (\romannumeral2) LinSBFT rotates the leader of protocol randomly to reduce the risk of denial-of-service attacks on leader; and (\romannumeral3) each run of LinSBFT finalizes one block, which is robust against participants that are honest in one run of the protocol, and dishonest in another, and the set of participants is dynamic, which is update periodically. (\romannumeral4) LinSBFT helps the delayed nodes to catch up via a synchronization mechanism to promise the liveness. Further, in the ordinary case, LinSBFT involves only a single round of voting instead of two in PBFT, which reduces both communication overhead and confirmation time, and employs the \emph{proof-of-stake} scheme to reward all participants. Extensive experiments using data obtained from the Ethereum demonstrate that LinSBFT consistently and significantly outperforms existing in-production BFT protocols for blockchains.
Suyash Gupta, Jelle Hellings, Sajjad Rahnama, Mohammad Sadoghi
Since the introduction of Bitcoin---the first wide-spread application driven by blockchains---the interest of the public and private sector in blockchains has skyrocketed. At the core of this interest are the ways in which blockchains can be used to improve data management, e.g., by enabling federated data management via decentralization, resilience against failure and malicious actors via replication and consensus, and strong data provenance via a secured immutable ledger.
Jovan Nikolić, Nursultan Jubatyrov, Evangelos Pournaras
Large-scale decentralized systems of autonomous agents interacting via asynchronous communication often experience the following self-healing dilemma: fault detection inherits network uncertainties making a remote faulty process indistinguishable from a slow process. In the case of a slow process without fault, fault correction is undesirable as it can trigger new faults that could be prevented with fault tolerance that is a more proactive system maintenance. But in the case of an actual faulty process, fault tolerance alone without eventually correcting persistent faults can make systems underperforming. Measuring, understanding and resolving such self-healing dilemmas is a timely challenge and critical requirement given the rise of distributed ledgers, edge computing, the Internet of Things in several energy, transport and health applications. This paper contributes a novel and general-purpose modeling of fault scenarios during system runtime. They are used to accurately measure and predict inconsistencies generated by the undesirable outcomes of fault correction and fault tolerance as the means to improve self-healing of large-scale decentralized systems at the design phase. A rigorous experimental methodology is designed that evaluates 696 experimental settings of different fault scales, fault profiles and fault detection thresholds in a prototyped decentralized network of 3000 nodes. Almost 9 million measurements of inconsistencies were collected in a network, where each node monitors the health status of another node, while both can defect. The prediction performance of the modeled fault scenarios is validated in a challenging application scenario of decentralized and dynamic in-network data aggregation using real-world data from a Smart Grid pilot project. Findings confirm the origin of inconsistencies at design phase and provide new insights how to tune self-healing at an early stage. Strikingly, the aggregation accuracy is well predicted as shown by high correlations and low root mean square errors.
Jovan Nikolić, Nursultan Jubatyrov, Evangelos Pournaras
Large-scale decentralized systems of autonomous agents interacting via\nasynchronous communication often experience the following self-healing dilemma:\nfault detection inherits network uncertainties making a remote faulty process\nindistinguishable from a slow process. In the case of a slow process without\nfault, fault correction is undesirable as it can trigger new faults that could\nbe prevented with fault tolerance that is a more proactive system maintenance.\nBut in the case of an actual faulty process, fault tolerance alone without\neventually correcting persistent faults can make systems underperforming.\nMeasuring, understanding and resolving such self-healing dilemmas is a timely\nchallenge and critical requirement given the rise of distributed ledgers, edge\ncomputing, the Internet of Things in several energy, transport and health\napplications. This paper contributes a novel and general-purpose modeling of\nfault scenarios during system runtime. They are used to accurately measure and\npredict inconsistencies generated by the undesirable outcomes of fault\ncorrection and fault tolerance as the means to improve self-healing of\nlarge-scale decentralized systems at the design phase. A rigorous experimental\nmethodology is designed that evaluates 696 experimental settings of different\nfault scales, fault profiles and fault detection thresholds in a prototyped\ndecentralized network of 3000 nodes. Almost 9 million measurements of\ninconsistencies were collected in a network, where each node monitors the\nhealth status of another node, while both can defect. The prediction\nperformance of the modeled fault scenarios is validated in a challenging\napplication scenario of decentralized and dynamic in-network data aggregation\nusing real-world data from a Smart Grid pilot project. Findings confirm the\norigin of inconsistencies at design phase.\n
This paper intends to propose the architecture of a blockchain-agnostic\nprotocol designed for communication of blockchains amongst each other (i.e.\ncross-chain), and for blockchains with the outside world (i.e. data oracles).\nThe expansive growth of cutting-edge technology in the blockchain industry\noutlines the need and opportunity for addressing oracle consensus in a manner\nboth technologically and economically efficient as well as futureproof.\nBlockchain-agnosticism is inherently limited if proposing a technological\nsolution involves adding one more architectural layer. As such, Gravity\nprotocol is designed to be a truly blockchain-agnostic protocol. By ensuring\nparity through direct integration and by leveraging the stability and security\nof the respective interconnected ecosystems, Gravity circumvents the need for a\ndedicated, public blockchain and a native token. Ultimately, Gravity protocol\nintends to address scalability challenges by providing a solid infrastructure\nfor the creation of gateways, cross-chain applications, and sidechains. This\npaper introduces and defines the concept of Oracle Consensus and its\nimplementation in the Gravity protocol named the Pulse Consensus algorithm. The\nproposed consensus architecture allows Gravity to be considered a singular\ndecentralized blockchain-agnostic oracle.\n
Gamze Gürsoy, Robert Bjornson, Molly E. Green, Mark Gerstein
BACKGROUND: Genomic variants are considered sensitive information, revealing potentially private facts about individuals. Therefore, it is important to control access to such data. A key aspect of controlled access is secure storage and efficient query of access logs, for potential misuse. However, there are challenges to securing logs, such as designing against the consequences of "single points of failure". A potential approach to circumvent these challenges is blockchain technology, which is currently popular in cryptocurrency due to its properties of security, immutability, and decentralization. One of the tasks of the iDASH (Integrating Data for Analysis, Anonymization, and Sharing) Secure Genome Analysis Competition in 2018 was to develop time- and space-efficient blockchain-based ledgering solutions to log and query user activity accessing genomic datasets across multiple sites, using MultiChain. METHODS: MultiChain is a specific blockchain platform that offers "data streams" embedded in the chain for rapid and secure data storage. We devised a storage protocol taking advantage of the keys in the MultiChain data streams and created a data frame from the chain allowing efficient query. Our solution to the iDASH competition was selected as the winner at a workshop held in San Diego, CA in October 2018. Although our solution worked well in the challenge, it has the drawback that it requires downloading all the data from the chain and keeping it locally in memory for fast query. To address this, we provide an alternate "bigmem" solution that uses indices rather than local storage for rapid queries. RESULTS: We profiled the performance of both of our solutions using logs with 100,000 to 600,000 entries, both for querying the chain and inserting data into it. The challenge solution requires 12 seconds time and 120 Mb of memory for querying from 100,000 entries. The memory requirement increases linearly and reaches 470 MB for a chain with 600,000 entries. Although our alternate bigmem solution is slower and requires more memory (408 seconds and 250 MB, respectively, for 100,000 entries), the memory requirement increases at a slower rate and reaches only 360 MB for 600,000 entries. CONCLUSION: Overall, we demonstrate that genomic access log files can be stored and queried efficiently with blockchain. Beyond this, our protocol potentially could be applied to other types of health data such as electronic health records.
The celebrated result of Fischer, Lynch and Paterson is the fundamental lower\nbound for asynchronous fault tolerant computation: any 1-crash resilient\nasynchronous agreement protocol must have some (possibly measure zero)\nprobability of not terminating. In 1994, Ben-Or, Kelmer and Rabin published a\nproof-sketch of a lesser known lower bound for asynchronous fault tolerant\ncomputation with optimal resilience against a Byzantine adversary: if $n\\le 4t$\nthen any t-resilient asynchronous verifiable secret sharing protocol must have\nsome non-zero probability of not terminating.\n Our main contribution is to revisit this lower bound and provide a rigorous\nand more general proof. Our second contribution is to show how to avoid this\nlower bound. We provide a protocol with optimal resilience that is almost\nsurely terminating for a strong common coin functionality. Using this new\nprimitive we provide an almost surely terminating protocol with optimal\nresilience for asynchronous Byzantine agreement that has a new fair validity\nproperty. To the best of our knowledge this is the first asynchronous Byzantine\nagreement with fair validity in the information theoretic setting.\n
The interblockchain communication protocol (IBC) is an end-to-end, connection-oriented, stateful protocol for reliable, ordered, and authenticated communication between modules on separate distributed ledgers. IBC is designed for interoperation between heterogenous ledgers arranged in an unknown, dynamic topology, operating with varied consensus algorithms and state machines. The protocol realises this by specifying the sufficient set of data structures, abstractions, and semantics of a communication protocol which once implemented by participating ledgers will allow them to safely communicate. IBC is payload-agnostic and provides a cross-ledger asynchronous communication primitive which can be used as a constituent building block by a wide variety of applications.
Tactical Data Link (TDL) is a communication system that utilizes a particular message format and a protocol to transmit data via wireless channels in an instant, automatic, and secure way. So far, TDL has shown its excellence in military applications. Current TDL adopts a distributed architecture to enhance anti-destruction capacity. However, It still faces a problem of data inconsistency and thus cannot well support cooperation across multiple militarily domains. To tackle this problem, we propose to leverage blockchain to build an automatic and adaptive data transmission control scheme for TDL. It achieves automatic data transmission and realizes information consistency among different TDL entities. Besides, applying smart contracts based on blockchain further enables adjusting data transmission policies automatically. Security analysis and experimental results based on simulations illustrate the effectiveness and efficiency of our proposed scheme.
Many researchers challenge the possibility of using blockchain and smart contracts to disrupt the Internet of Things (IoT) architecture because of their security and decentralization guarantees. However, the state-of-the-art blockchain architecture is not scalable enough to satisfy the requirements of massive data traffics in the IoT environment. The main reason for this issue is one needs to choose the consensus trade-off between either coping with a high throughput or a high number of nodes. Consequently, this issue prevents the applicability of blockchain for IoT use cases. In this paper, we propose a scalable two-tiered hierarchical blockchain architecture for IoT. The first tier is a Core Engine, which is based on a Practical Byzantine Fault Tolerance (PBFT) consensus to cope with a high throughput, that supervises the underlying subordinate engines (sub-engines) as its second tier. This second tier comprises of the Payment, Compute, and Storage Engine, respectively. We can deploy multiple instances of these sub-engines as many as we need and as local as possible near to the IoT domains, where IoT devices reside, to cope with a high number of nodes. Furthermore, to further extend the scalability of the proposed architecture, we also provide additional scalability features on the Core Engine such as request aggregation, request prioritization, as well as sub-engine parallelism. We implement all of our engines and expose them to IoT applications through the Engine APIs. With these APIs, developers can build and run IoT applications in our architecture. Our evaluation results show that our proposed features on the Core Engine can indeed enhance the overall performance of our architecture. Moreover, based on our proof-of-concept IoT car rental application, we also show that the interoperability between sub-engines through the Core Engine is possible, even when the particular sub-engine is under sub-engine parallelism.
Blockchain protocols differ in fundamental ways, including the mechanics of selecting users to produce blocks (e.g., proof-of-work vs. proof-of-stake) and the method to establish consensus (e.g., longest chain rules vs. BFT-inspired protocols). These fundamental differences have hindered "apples-to-apples" comparisons between different categories of blockchain protocols and, in turn, the development of theory to formally discuss their relative merits. This paper presents a parsimonious abstraction sufficient for capturing and comparing properties of many well-known permissionless blockchain protocols, simultaneously capturing essential properties of both proof-of-work and proof-of-stake protocols, and of both longest-chain-type and BFT-type protocols. Our framework blackboxes the precise mechanics of the user selection process, allowing us to isolate the properties of the selection process which are significant for protocol design. We illustrate our framework's utility with two results. First, we prove an analog of the CAP theorem from distributed computing for our framework in a partially synchronous setting. This theorem shows that a fundamental dichotomy holds between protocols (such as Bitcoin) that are adaptive, in the sense that they can function given unpredictable levels of participation, and protocols (such as Algorand) that have certain finality properties. Second, we formalize the idea that proof-of-work (PoW) protocols and non-PoW protocols can be distinguished by the forms of permission that users are given to carry out updates to the state.
Modern computing systems are highly concurrent. Threads run concurrently in shared-memory multi-core systems, and programs run in different servers communicating by sending messages to each other. Concurrent programming is hard because it requires to cope with many possible, unpredictable behaviors of the processes, and the communication media. The article argues that right from the start in 1960's, the main way of dealing with concurrency has been by reduction to sequential reasoning. It traces this history, and illustrates it through several examples, from early ideas based on mutual exclusion (which was initially introduced to access shared physical resources), passing through consensus and concurrent objects (which are immaterial data), until today distributed ledgers. A discussion is also presented, which addresses the limits that this approach encounters, related to fault-tolerance, performance, and inherently concurrent problems.
Blockchain Technology is exclusively used to make online transactions secure by maintaining a distributed and decentralized ledger of records across multiple computers. Tendermint is a general-purpose blockchain engine that is composed of two parts; Tendermint Core and the blockchain application interface. The application interface makes Tendermint suitable for a wide range of applications. In this paper, we analyze and improve Practical Byzantine Fault Tolerant (PBFT), a consensus-based Tendermint blockchain algorithm. In order to avoid negative issues of locks, we first propose a lock-free algorithm for blockchain in which the proposal and voting phases are concurrent whereas the commit phase is sequential. This consideration in the algorithm allows parallelism. Secondly, a new methodology is used to decide the size of the voter set which is a subset of blockchain nodes, further investigating the block sensitivity and trustworthiness of nodes. Thirdly, to fairly select the voter set nodes, we employ the random walk algorithm. Fourthly, we imply the wait-freedom property by using a timeout due to which all blocks are eventually committed or aborted. In addition, we have discussed voting conflicts and consensuses issues that are used as a correctness property, and provide some supportive techniques.
Marcela Tuler de Oliveira, Lúcio Henrik A. Reis, Dianne S. V. Medeiros, Ricardo C. Carrano · 6 authors
Consensus mechanisms in blockchain applications allow mistrusting peers to agree on the global state of the chain. Most of the existing consensus mechanisms, however, are constrained by low efficiency and high energy consumption. In this paper, we propose the Blockchain Reputation-Based Consensus (BRBC) mechanism in which a node must have the reputation score higher than a given network trust threshold before being allowed to insert a new block in the chain. A randomly-selected set of judges monitors the behaviour of each node involved in the consensus and updates the node reputation score. Every cooperative behaviour results in a reward, and a non-cooperative or malicious behaviour results in a punishment. BRBC also uses the reputation score to revoke access to nodes with a reputation score below a given threshold. We present a security analysis, and we demonstrate that BRBC resists against a set of known attacks in the blockchain network. Finally, we simulate a blockchain network to assert the mechanism scalability and resilience to malicious actions in various network scenarios and different rates of malicious actions. The results show BRBC to be efficient to expel all nodes that acted with more than 50% of malicious actions.