Jelena Mišić, Vojislav B. Mišić, Xiaolin Chang
Compact blocks, and compact block protocol are a recent addition to the Bitcoin (BTC) data propagation protocol that aims to reduce bandwidth requirements and, possibly, reduce latency as well. In this work we evaluate operation of BTC network under a mix of regular, and compact block traffic, assuming that nodes randomly leave, and re-join the network, and perform block and, optionally, transaction pool (mempool) synchronization upon returning. Our analysis begins by evaluating block, and transaction deficits accumulated during the node absence and block synchronization. Then, we analyze mempool behavior, and show that mempool synchronization is necessary since it decreases probability of transaction deficit, and the need for transaction retrieval actions. Finally, we analyze the impact of synchronization activities, and transaction deficit on data distribution times in the BTC network with high, and low bandwidth distribution modes for a mix of compact, and regular blocks. Results demonstrate resilience to node absence, and subsequent synchronization, as well as substantial performance improvements for small protocol changes. Furthermore we show that the low bandwidth mode is more resilient to potential security attacks.
Vaivaswatha Nagaraj, Jacob Johannsen, Anton Trunov, George Pîrlea · 6 authors
Scilla is a higher-order polymorphic typed intermediate level language for implementing smart contracts. In this talk, we describe a Scilla compiler targeting LLVM, with a focus on mapping Scilla types, values, and its functional language constructs to LLVM-IR. The compiled LLVM-IR, when executed with LLVM's JIT framework, achieves a speedup of about 10x over the reference interpreter on a typical Scilla contract. This reduced latency is crucial in the setting of blockchains, where smart contracts are executed as parts of transactions, to achieve peak transactions processed per second. Experiments on the Ackermann function achieved a speedup of more than 45x. This talk abstract is aimed at both programming language researchers looking to implement an LLVM based compiler for their functional language, as well as at LLVM practitioners.
This paper proposes an architecture and a protocol suite for a permissioned blockchain for a local IoT network. The architecture is based on a sealed Sequencer and a Fog Server running (post-quantum) Guy Fawkes protocols. The blocks of the blockchain are stored in networked Content Addressable Storage alongside any user data and validity proofs. We maintain that a typical IoT device can, despite its resource limitations, use our blockchain protocols directly, without a trusted intermediary. This includes posting and monitoring transactions as well as off-chain (post-quantum) emergency communications without an explicit public key. Keywords: blockchain, Guy Fawkes protocol, post-quantum, HORS-OTS, LoRa, concurrent transmission
Private and permissioned blockchains are conceptualized and mostly assembled for fulfilling corporations’ demands and needs in the context of their own premises. This paper presents a complete and sophisticated end-to-end permissioned blockchain application for governance and management of musical rights endorsed by smart contract development. In a music industry use case, this disclosed solution monitors and regulates conflicting musical rights of diverse entities under a popular permissioned distributed ledger technology network. The proposed implementation couples various and distinct business domains across the music industry organizations and non-profit blockchain associations.
Jelle Hellings, Daniel P. Hughes, Joshua Primero, Mohammad Sadoghi
To enable high-performance and scalable blockchains, we need to step away from traditional consensus-based fully-replicated designs. One direction is to explore the usage of sharding in which we partition the managed dataset over many shards that independently operate as blockchains. Sharding requires an efficient fault-tolerant primitive for the ordering and execution of multi-shard transactions, however. In this work, we seek to design such a primitive suitable for distributed ledger networks with high transaction throughput. To do so, we propose Cerberus, a set of minimalistic primitives for processing single-shard and multi-shard UTXO-like transactions. Cerberus aims at maximizing parallel processing at shards while minimizing coordination within and between shards. First, we propose Core-Cerberus, that uses strict environmental requirements to enable simple yet powerful multi-shard transaction processing. In our intended UTXO-environment, Core-Cerberus will operate perfectly with respect to all transactions proposed and approved by well-behaved clients, but does not provide any guarantees for other transactions. To also support more general-purpose environments, we propose two generalizations of Core-Cerberus: we propose Optimistic-Cerberus, a protocol that does not require any additional coordination phases in the well-behaved optimistic case, while requiring intricate coordination when recovering from attacks; and we propose Pessimistic-Cerberus, a protocol that adds sufficient coordination to the well-behaved case of Core-Cerberus, allowing it to operate in a general-purpose fault-tolerant environments without significant costs to recover from attacks. Finally, we compare the three protocols, showing their potential scalability and high transaction throughput in practical environments.
To overcome the limitations on the scalability of current blockchain systems, sharding is widely considered as a promising solution that divides the network into multiple disjoint groups processing transactions in parallel to improve throughput while decreasing the overhead of communication, computation, and storage. However, most existing blockchain sharding systems adopt a static sharding policy that cannot efficiently deal with the dynamic environment in the blockchain system, i.e., joining and leaving of nodes, and malicious attack. This paper presents SkyChain, a novel dynamic sharding-based blockchain framework to achieve a good balance between performance and security without compromising scalability under the dynamic environment. We first propose an adaptive ledger protocol to guarantee that the ledgers can merge or split efficiently based on the dynamic sharding policy. Then, to optimize the sharding policy under dynamic environment with high dimensional system states, a deep reinforcement learning-based sharding approach has been proposed, the goals of which include: 1) building a framework to evaluate the blockchain sharding systems from the aspects of performance and security; 2) adjusting the re-sharding interval, shard number and block size to maintain a long-term balance of the system’s performance and security. Experimental results show that SkyChain can effectively improve the performance and security of the sharding system without compromising scalability under the dynamic environment in the blockchain system.
Nowadays, the communication services provided by the e-mail system are used all over the world for formal communication and business negotiation. The traditional e-mail systems provide services based on their centralized servers. If the centralized servers are attacked, the confidential message and the private information will be leaked to the attacker. To this end, this paper uses blockchain technology to build a decentralized e-mail system with trust and accountability. To improve the PBFT algorithm which is widely-used for blockchain consensus and reduce the bad influence brought by the abnormal blockchain nodes, this work proposes a node quality control strategy for blockchain consensus nodes. Moreover, this paper designs the blockchain-based evidence storage module and dispute resolution module to serve our mailbox users. The experiment results show that the blockchain-based e-mail system proposed in this paper can achieve a high-quality consensus mechanism with the node quality control strategy and reduce the transaction delay time.
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.
Atomic broadcast protocols are increasingly used to build distributed ledgers. The most robust protocols achieve byzantine fault tolerance (BFT) and operate in asynchronous networks. Recent proposals such as HoneyBadgerBFT (ACM CCS `16) and BEAT (ACM CCS `18) achieve optimal communication complexity, growing linearly as a function of the number of nodes present. Although asymptotically optimal, their practical performance precludes their use in demanding applications. Further performance improvements to HoneyBadgerBFT and BEAT are not obvious as they run two separate sub-protocols for broadcast and voting, each of which has already been optimized. We describe how hashgraph - an asynchronous BFT atomic broadcast protocol (ABFT) - departs in structure from prior work by not using communication to vote, only to broadcast transactions. We perform an extensive empirical study to understand how hashgraph's structure affects performance. We observe that hashgraph can improve latency by an order of magnitude over HoneyBadgerBFT and BEAT, while keeping throughput constant with the same number of nodes; similarly, throughput can increase by up to an order of magnitude while maintaining latency. Furthermore, we test hashgraph's capability for high performance, and conclude that it can achieve sufficiently high throughput and low latency to support demanding practical applications.
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.
The full-replication data storage mechanism, as commonly utilized in existing blockchains, is the barrier to the system's scalability, since it retains a copy of entire blockchain at each node so that the overall storage consumption per block is O(n) with n participants. Yet another drawback is that this mechanism may limit the throughput in permissioned blockchain. Moreover, due to the existence of Byzantine nodes, existing partitioning methods, though widely adopted in distributed systems for decades, cannot suit for blockchain systems directly, so that it is critical to devise new storage mechanism for blockchain systems. This article proposes a novel storage engine, called BFT-Store, to enhance storage scalability by integrating erasure coding with Byzantine Fault Tolerance (BFT) consensus protocol. The first property of BFT-store is that the storage consumption per block can be reduced to O(1) for the first time, which enlarges overall storage capability when more nodes attend the blockchain. Second, we design an efficient online re-encoding protocol for storage scale-out and a hybrid replication scheme to enhance reading performance. Analysis in theory and extensive experimental results illustrate the scalability, availability and efficiency of BFT-Store via the implementation in an open-source permissioned blockchain Tendermint.
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
The Smart Distributed Ledger (aka blockchain) has attracted much attention in recent years. According to the European Parliament, this technology has the potential to change the lives of many people. The blockchain is a data structure built upon a hashed function in a distributed network, enabled by an incentive mechanism to discourage malicious nodes from participation. The consensus is at the core of the blockchain technology, and is driven by information embedded into a data structure that takes many forms such as linear, tree, and graph chains. The found related information will be subject to various validation incentives among the miners, such as proof of stake and proof of work. However, all the existing solutions suffer from a heavy state transition before dealing with the problem of a validation mechanism which suffers from resource consumption, monopoly or attacks. This work raises the following question: "Why is there a need for consensus where all participants can make a quick and correct decision?", and underlines the fact that sometimes ledger is subject to maintenance from regional parties in the data that leads to partial territories and eliminates monopoly, which is the hurdle to eliminating the trusted party. The validity of the blockchain transaction comes from the related information scattered above the data structure, and the authenticity lies in the digital signature. The aim is to switch from a validator based on incentives to a broadcaster governed by an unsupervised clustering algorithm, and the integrity does lie in the intersection among regions. However, the data structure takes advantage of the Petri network regarding its suitability. Building the entire ledger in the Petri network model will allow parallel processing of the transactions and securing of the total order between the participants on the memory reference layer. Moreover, it takes account of validation criteria quickly and safely before adding the new transaction list using the graph reachability.