Tayebeh Rajab, Mohammad Hossein Manshaei, Mohammad Dakhilalian, Murtuza Jadliwala · 5 authors
Bitcoin's single leader consensus protocol (Nakamoto consensus) suffers from significant transaction throughput and network scalability issues due to the computational requirements of it Proof-of-Work (PoW) based leader selection strategy. To overcome this, committee-based approaches (e.g., Elastico) that partition the outstanding transaction set into shards and (randomly) select multiple committees to process these transactions in parallel have been proposed and have become very popular. However, by design these committee or shard-based blockchain solutions are easily vulnerable to the Sybil attacks, where an adversary can easily compromise/manipulate the consensus protocol if it has enough computational power to generate multiple Sybil committee members (by generating multiple valid node identifiers). Despite the straightforward nature of these attacks, they have not been systematically analyzed. In this paper, we fill this research gap by modelling and analyzing Sybil attacks in a representative and popular shard-based protocol called Elastico. We show that the PoW technique used for identifier or ID generation in the initial phase of the protocol is vulnerable to Sybil attacks, and a node with high hash-power can generate enough Sybil IDs to successfully compromise Elastico. We analytically derive conditions for two different categories of Sybil attacks and perform numerical simulations to validate our theoretical results under different network and protocol parameters.
The blockchain paradigm provides a mechanism for content dissemination and distributed consensus on Peer-to-Peer (P2P) networks. While this paradigm has been widely adopted in industry, it has not been carefully analyzed in terms of its network scaling with respect to the number of peers. Applications for blockchain systems, such as cryptocurrencies and IoT, require this form of network scaling. In this paper, we propose a new stochastic network model for a blockchain system. We identify a structural property called \emph{one-endedness}, which we show to be desirable in any blockchain system as it is directly related to distributed consensus among the peers. We show that the stochastic stability of the network is sufficient for the one-endedness of a blockchain. We further establish that our model belongs to a class of network models, called monotone separable models. This allows us to establish upper and lower bounds on the stability region. The bounds on stability depend on the connectivity of the P2P network through its conductance and allow us to analyze the scalability of blockchain systems on large P2P networks. We verify our theoretical insights using both synthetic data and real data from the Bitcoin network.
Suyash Gupta, Sajjad Rahnama, Jelle Hellings, Mohammad Sadoghi
Recent developments in blockchain technology have inspired innovative new designs in resilient distributed and database systems. At their core, these blockchain applications typically use Byzantine fault-tolerant consensus protocols to maintain a common state across all replicas, even if some replicas are faulty or malicious. Unfortunately, existing consensus protocols are not designed to deal with geo-scale deployments in which many replicas spread across a geographically large area participate in consensus. To address this, we present the Geo-Scale Byzantine FaultTolerant consensus protocol (GeoBFT). GeoBFT is designed for excellent scalability by using a topological-aware grouping of replicas in local clusters, by introducing parallelization of consensus at the local level, and by minimizing communication between clusters. To validate our vision of high-performance geo-scale resilient distributed systems, we implement GeoBFT in our efficient ResilientDB permissioned blockchain fabric. We show that GeoBFT is not only sound and provides great scalability, but also outperforms state-of-the-art consensus protocols by a factor of six in geo-scale deployments.
Lăcrămioara Aştefănoaei, Pierre Chambart, Antonella Del Pozzo, Thibault Rieutord · 6 authors
First-generation blockchains provide probabilistic finality: a block can be revoked, albeit the probability decreases as the block "sinks" deeper into the chain. Recent proposals revisited committee-based BFT consensus to provide deterministic finality: as soon as a block is validated, it is never revoked. A distinguishing characteristic of these second-generation blockchains over classical BFT protocols is that committees change over time as the participation and the blockchain state evolve. In this paper, we push forward in this direction by proposing a formalization of the Dynamic Repeated Consensus problem and by providing generic procedures to solve it in the context of blockchains. Our approach is modular in that one can plug in different synchronizers and single-shot consensus. To offer a complete solution, we provide a concrete instantiation, called {{Tenderbake}}, and present a blockchain synchronizer and a single-shot consensus algorithm, working in a Byzantine and partially synchronous system model with eventually synchronous clocks. In contrast to recent proposals, our methodology is driven by the need to bound the message buffers. This is essential in preventing spamming and run-time memory errors. Moreover, {{Tenderbake}} processes can synchronize with each other without exchanging messages, leveraging instead the information stored in the blockchain.
Lăcrămioara Aştefănoaei, Pierre Chambart, Antonella Del Pozzo, Edward Tate · 6 authors
Our work has been originally motivated by Tezos, a public blockchain which focuses on software correctness and which enables formal reasoning and verification. To further strengthen the resilience of Tezos, which now depends on a consensus protocol delivering only probabilistic finality, we propose a consensus protocol that brings deterministic finality. Our solution is backward compatible with the current liquid proof-of-stake system underlying Tezos. The main contributions of this paper are the following: (i) a formal specification of the Dynamic Repeated Consensus (DRC) problem, an adaptation of the repeated consensus problem to dynamic committees, (ii) Tenderbake, a solution to the DRC problem in a Byzantine and partially synchronous system model. In contrast to recent proposals, Tenderbake works with bounded message buffers. This feature represents a countermeasure to spamming and prevents runtime memory errors. For these reasons we think that Tenderbake is suitable for blockchains aiming to guarantee deterministic finality in a public setting.
In recent years, blockchain technology has received unparalleled attention from academia, industry, and governments all around the world. It is considered a technological breakthrough anticipated to disrupt several application domains. This has resulted in a plethora of blockchain systems for various purposes. However, many of these blockchain systems suffer from serious shortcomings related to their performance and security, which need to be addressed before any wide-scale adoption can be achieved. A crucial component of any blockchain system is its underlying consensus algorithm, which in many ways, determines its performance and security. Therefore, to address the limitations of different blockchain systems, several existing as well novel consensus algorithms have been introduced. A systematic analysis of these algorithms will help to understand how and why any particular blockchain performs the way it functions. However, the existing studies of consensus algorithms are not comprehensive. Those studies have incomplete discussions on the properties of the algorithms and fail to analyse several major blockchain consensus algorithms in terms of their scopes. This article fills this gap by analysing a wide range of consensus algorithms using a comprehensive taxonomy of properties and by examining the implications of different issues still prevalent in consensus algorithms in detail. The result of the analysis is presented in tabular formats, which provides a visual illustration of these algorithms in a meaningful way. We have also analysed more than hundred top crypto-currencies belonging to different categories of consensus algorithms to understand their properties and to implicate different trends in these crypto-currencies. Finally, we have presented a decision tree of algorithms to be used as a tool to test the suitability of consensus algorithms under different criteria.
Traditional public distributed ledgers have not been able to scale-out well and work efficiently. Sharding is deemed as a promising way to solve this problem. By partitioning all nodes into small committees and letting them work in parallel, we can significantly lower the amount of communication and computation, reduce the overhead on each node's storage, as well as enhance the throughput of the distributed ledger. Existing sharding-based protocols still suffer from several serious drawbacks. The first thing is that all non-faulty nodes must connect well with each other, which demands a huge number of communication channels in the network. Moreover, previous protocols have faced great loss in efficiency in the case where the honesty of each committee's leader is in question. At the same time, no explicit incentive is provided for nodes to actively participate in the protocol. We present CycLedger, a scalable and secure parallel protocol for distributed ledger via sharding. Our protocol selects a leader and a partial set for each committee, who are in charge of maintaining intra-shard consensus and communicating with other committees, to reduce the amortized complexity of communication, computation, and storage on all nodes. We introduce a novel semi-commitment scheme between committees and a recovery procedure to prevent the system from crashing even when leaders of committees are malicious. To add incentive for the network, we use the concept of reputation, which measures each node's trusty computing power. As nodes with a higher reputation receive more rewards, there is an encouragement for nodes with strong computing ability to work honestly to gain reputation. In this way, we strike out a new path to establish scalability, security, and incentive for the sharding-based distributed ledger.
Traditional Blockchain Sharding approaches can only tolerate up to n/3 of nodes being adversary because they rely on the hyper-geometric distribution to make a failure (an adversary does not have n/3 of nodes globally but can manipulate the consensus of a Shard) hard to happen. The system must maintain a large Shard size (the number of nodes inside a Shard) to sustain the low failure probability so that only a small number of Shards may exist. In this paper, we present a new approach of Blockchain Sharding that can withstand up to n/2 of nodes being bad. We categorise the nodes into different classes, and every Shard has a fixed number of nodes from different classes. We prove that this design is much more secure than the traditional models (only have one class) and the Shard size can be reduced significantly. In this way, many more Shards can exist, and the transaction throughput can be largely increased. The improved Blockchain Sharding approach is promising to serve as the foundation for decentralised autonomous organisations and decentralised database.
We improve the fundamental security threshold of eventual consensus Proof-of-Stake (PoS) blockchain protocols under the longest-chain rule by showing, for the first time, the positive effect of rounds with concurrent honest leaders. Current security analyses reduce consistency to the dynamics of an abstract, round-based block creation process that is determined by three events associated with a round: (i) event $A$: at least one adversarial leader, (ii) event $S$: a single honest leader, and (iii) event $M$: multiple, but honest, leaders. We present an asymptotically optimal consistency analysis assuming that an honest round is more likely than an adversarial round (i.e., $\Pr[S] + \Pr[M] > \Pr[A]$); this threshold is optimal. This is a first in the literature and can be applied to both the simple synchronous communication as well as communication with bounded delays. In all existing consistency analyses, event $M$ is either penalized or treated neutrally. Specifically, the consistency analyses in Ouroboros Praos (Eurocrypt 2018) and Genesis (CCS 2018) assume that $\Pr[S] - \Pr[M] > \Pr[A]$; the analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto 2019) assume that $\Pr[S] > \Pr[A]$. Moreover, all existing analyses completely break down when $\Pr[S] < \Pr[A]$. These thresholds determine the critical trade-off between the honest majority, network delays, and consistency error. Our new results can be directly applied to improve the security guarantees of the existing protocols. We also provide an efficient algorithm to explicitly calculate these error probabilities in the synchronous setting. Furthermore, we complement these results by analyzing the setting where $S$ is rare, even allowing $\Pr[S] = 0$, under the added assumption that honest players adopt a consistent chain selection rule.
We improve the fundamental security threshold of eventual consensus\nProof-of-Stake (PoS) blockchain protocols under the longest-chain rule by\nshowing, for the first time, the positive effect of rounds with concurrent\nhonest leaders.\n Current security analyses reduce consistency to the dynamics of an abstract,\nround-based block creation process that is determined by three events\nassociated with a round: (i) event $A$: at least one adversarial leader, (ii)\nevent $S$: a single honest leader, and (iii) event $M$: multiple, but honest,\nleaders. We present an asymptotically optimal consistency analysis assuming\nthat an honest round is more likely than an adversarial round (i.e., $\\Pr[S] +\n\\Pr[M] > \\Pr[A]$); this threshold is optimal. This is a first in the literature\nand can be applied to both the simple synchronous communication as well as\ncommunication with bounded delays.\n In all existing consistency analyses, event $M$ is either penalized or\ntreated neutrally. Specifically, the consistency analyses in Ouroboros Praos\n(Eurocrypt 2018) and Genesis (CCS 2018) assume that $\\Pr[S] - \\Pr[M] > \\Pr[A]$;\nthe analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto\n2019) assume that $\\Pr[S] > \\Pr[A]$. Moreover, all existing analyses completely\nbreak down when $\\Pr[S] < \\Pr[A]$. These thresholds determine the critical\ntrade-off between the honest majority, network delays, and consistency error.\n Our new results can be directly applied to improve the security guarantees of\nthe existing protocols. We also provide an efficient algorithm to explicitly\ncalculate these error probabilities in the synchronous setting. Furthermore, we\ncomplement these results by analyzing the setting where $S$ is rare, even\nallowing $\\Pr[S] = 0$, under the added assumption that honest players adopt a\nconsistent chain selection rule.\n
Mustafa Safa Özdayi, Murat Kantarcıoğlu, Bradley Malin
BACKGROUND: Blockchain has emerged as a decentralized and distributed framework that enables tamper-resilience and, thus, practical immutability for stored data. This immutability property is important in scenarios where auditability is desired, such as in maintaining access logs for sensitive healthcare and biomedical data. However, the underlying data structure of blockchain, by default, does not provide capabilities to efficiently query the stored data. In this investigation, we show that it is possible to efficiently run complex audit queries over the access log data stored on blockchains by using additional key-value stores. This paper specifically reports on the approach we designed for the blockchain track of iDASH Privacy & Security Workshop 2018 competition. In this track, participants were asked to devise an efficient way to run conjunctive equality and range queries on a genomic dataset access log trail after storing it in a permissioned blockchain network consisting of 4 identical nodes, each representing a different site, created with the Multichain platform. METHODS: Multichain duplicates and indexes blockchain data locally at each node in a key-value store to support retrieval requests at a later point in time. To efficiently leverage the key-value storage mechanism, we applied various techniques and optimizations, such as bucketization, simple data duplication and batch loading by accounting for the required query types of the competition and the interface provided by Multichain. Particularly, we implemented our solution and compared its loading and query-response performance with SQLite, a commonly used relational database, using the data provided by the iDASH 2018 organizers. RESULTS: Depending on the query type and the data size, the run time difference between blockchain based query-response and SQLite based query-response ranged from 0.2 seconds to 6 seconds. A deeper inspection revealed that range queries were the bottleneck of our solution which, nevertheless, scales up linearly. CONCLUSIONS: This investigation demonstrates that blockchain-based systems can provide reasonable query-response times to complex queries even if they only use simple key-value stores to manage their data. Consequently, we show that blockchains may be useful for maintaining data with auditability and immutability requirements across multiple sites.
Blockchains such as the bitcoin blockchain depend on reaching a global consensus on the distributed ledger; therefore, they suffer from well know scalability problems. This paper proposes an algorithm that avoids double-spending in the short term with just O(&radic;n) messages; each node receiving money off-chain performs the due diligence of consulting k&radic;n random nodes to check if any of them is aware of double-spending. Two nodes receiving double-spent money will in this way consult at least one common node with very high probability, due to the &lsquo;birthday paradox&rsquo;, and any common honest node consulted will detect the fraud. Since the velocity of money in the real world has coins circulating through at most a few wallets per day, the size of the due diligence communication is small in the short term. This `k-root-n&rsquo; algorithm is suitable for an environment with synchronous or asynchronous (but with fairly low latency) communication and with Byzantine faults. The presented k-root-n algorithm should be practical to avoid double-spending with arbitrarily high probability, while feasibly coping with the throughput of all world commerce. It is resistant to Sybil attacks even beyond 50% of nodes. In the long term, the k-root-n algorithm is less efficient. Therefore, it should preferably be used as a complement and not a replacement to a global distributed ledger technology.
In the blockchain, the consensus mechanism plays a key role in maintaining the security and legitimation of contents recorded in the blocks. Various blockchain consensus mechanisms have been proposed. However, there is no technical analysis and comparison as a guideline to determine which type of consensus mechanism should be adopted in a specific scenario/application. To this end, this work investigates three mainstream consensus mechanisms in the blockchain, namely, Proof of Work (PoW), Proof of Stake (PoS), and Direct Acyclic Graph (DAG), and identifies their performances in terms of the average time to generate a new block, the confirmation delay, the Transaction Per Second (TPS) and the confirmation failure probability. The results show that the consensus process is affected by both network resource (computation power/coin age, buffer size) and network load conditions. In addition, it shows that PoW and PoS are more sensitive to the change of network resource while DAG is more sensitive to network load conditions.
Abstract Blockchain-based applications have become increasingly popular in recent years. Security concerns are rising as blockchain users are becoming aware of how their private data is stored across this decentralized network of computing nodes. Formal verification allows developers to improve software quality and hence make it more secure. The main hypothesis of this paper is that it is achievable to perform formal verification of a model that represents a smart contract responsible for user registration. In order to test the hypothesis, we have created a model of such a smart contract and checked it against a set of formal constraints. As a result of the conducted study, a conclusion can be made that the hypothesis is correct.
Recent years have witnessed a boom in blockchain systems written in Rust to utilize its efficiency and safety. Unfortunately, deadlock bugs have become one of the ubiquitous banes to these systems due to the heavy use of locks for parallelism and the misunderstanding of the lock mechanism in Rust. This paper analyzed the common lock-related pitfalls in blockchain systems written in Rust and proposed Stuck-me-not, the first MIR-based static deadlock detector, for the most common deadlock type: double-lock. We have discovered 29 previously unknown double-lock bugs in 11 popular blockchain-related projects. We believe our work can greatly improve the concurrency security of the current blockchain ecosystem.
Most people first encounter blockchain technology by way of cryptocurrencies like Bitcoin. Bitcoin came into existence during the start of the 2008 financial crisis and was first disclosed in October 2008.1Because of the timing and some clear indicators embedded into the first (genesis) block of Bitcoin, we know that a primary reason for developing cryptocurrency was a distrust of large institutions that control the world’s fiat currencies. However, what does currency have to do with media technology?
We try to verify properties of the Bitcoin-S library, a Scala implementation of parts of the Bitcoin protocol. We use the Stainless verifier which supports programs in a fragment of Scala called Pure Scala. Since Bitcoin-S is not written in this fragment, we extract the relevant code from it and rewrite it until we arrive at code that we successfully verify. In that process we find and fix two bugs in Bitcoin-S.
We propose a sociotechnical, yet computational, approach to building decentralized applications that accommodates and exploits blockchain technology. Our architecture incorporates the notion of a declarative, violable contract and enables flexible governance based on formal organizational structures, correctness verification without obstructing autonomy, and a basis for trust.
Paweł Śniatała, M. Hadi Amini, Kianoosh G. Boroojeni
Information fusion has been a topic of immense interest owing to its applicability in various applications. This brings to the fore the need for a flexible and accurate fusion algorithm that can be versatile. The Brooks–Iyengar algorithm is one such fusion algorithm. It has since its inception found numerous applications that deal with the fusion of data from multiple sources. The uniqueness of the Brooks–Iyengar algorithm is the ease with which the data from multiple sensors in a local system can be fused and also reach consensus in a distributed system with the added capability of fault tolerance. Blockchain has found its use as a distributed ledger and has successfully supported and fueled many crypto-currencies over the years. Information fusion with regard to blockchains is a topic of great research interest in the past couple of years. Since blockchain has no official node, the introduction of a decentralized network and a consensus algorithm is required in making the interactions and exchanges between multiple suppliers easier and thus leads to business being carried out without any hassles. In this paper, we attempt to understand and describe the deployment of multiple sensors to measure various aspects of the physical world. We discuss a novel technique of employing the Brooks–Iyengar algorithm in the design of the system that would decentralize the data source from the corresponding measurements and thus ensure the integrity of the transactions in the blockchain. Finally, a theoretical analysis of the performance of the algorithm when used in a blockchain based decentralized environment is also discussed.
Open access
Distributed systems and fault tolerance
Distributed Sensor Networks and Detection Algorithms
Blockchain's popularity has seen a historic rise over the last decade. However, existing blockchain systems have a major issue with scalability, which has become one of the main obstacles in technology's adoption in mainstream. There have been several attempts to address this limitation by identifying Blockchain's scalability/performance bottlenecks (e.g. those mainly related to consensus algorithms), and thus proposed different solutions (e.g., new consensus protocols) to address such limitations. Other works applied sharding to tackle the issue. All solutions however have mainly focused on Cryptocurrency applications, and thus addressing the scalability of blockchain systems for general applications remains a concern. This work proposes a scalable blockchain protocol for general applications (i.e., not restricted to Cryptocurrencies). To improve the two major factors affecting transaction scalability, namely throughput and latency, we needed to modify both the blockchain structure as well as the block generation process. ZyConChain, the proposed Blockchain system, introduces three types of blocks that form three separate chains: parentBlock, sideBlock and state block. These blocks are generated based on different consensus algorithms, as each algorithm has specific properties that make it suitable for each type of block. To improve the overall performance, ZyConChain generates sideBlocks (that carry transactions) at a high rate and keep them in a pool. To generate parentBlock, miners, instead of packing transactions into a block as they do in conventional blockchains, pack sideBlocks into a parentBlock. SideBlocks are generated based on an adapted Zyzzyva consensus protocol, with O(\log n) complexity. This has reduced the final consensus complexity per transaction, in comparison to previous work. To enable the protocol to scale out with the increase in the number of nodes, ZyConChain applied sharding technique. Parallel state chains have also been introduced to address cross-shard transactions.
Blaž Podgorelec, Marjan Herieko, Muhamed Turkanović
Currently, developers and researchers are dedicated to finding better ways to achieve greater scalability of various blockchain platforms. Focused on the Ethereum blockchain platform, the state channels are currently the only maturely researched and implemented a solution for achieving scalability. However, there are still several problems, such as transparency of state channel networks, transaction traceability, and the incapability that the off-chain state is transferred back on the blockchain network in an ad-hoc manner. To solve the aforementioned problems, we propose a novel state channel solution in the form of a State Channel as a Service, which, although off-chain, still incorporates a secure distributed and decentralized network. This solves the challenge of transparency and traceability while giving users the confidence that only the valid last off-chain state is transferred back on the blockchain network. With the proposed solution, there is no need for users to monitor state channel activities for possible malicious actions. Implementation was performed in the form of a payment channel system, presenting a potential use case for the SCaaS. Furthermore, we performed a security and performance analysis, which shows that the solution is secure and by a factor of 12 more efficient than the classical on-chain payment systems. To evaluate and prove the contributions of the proposed solution, quantitative, and qualitative comparisons with selected related works (i.e., Raiden and Celer) were also performed.
Abstract A blockchain is a decentralized distributed public database. It does not have a central authority to maintain this public database by running a cryptographic protocol with distributed nodes. Bitcoin is currently the hottest item in the blockchain, and the Bitcoin node can verify the transaction content and package it into the block. The blockchain guarantees the consistency of the books through the underlying consensus agreement. These consensus algorithms are different because the algorithm security assumptions are different from the actual requirements. This paper sorts and compares various blockchain consensus algorithms, sorts out the development based on blockchain consensus, and points out the advantages and disadvantages of various algorithms, and proposes the development direction of blockchain consensus algorithm. CCS Concepts •Anonymity and privacy issues and measures to enhance them➝Consensus protocols for blockchains
We study Nakamoto’s Bitcoin protocol that implements a distributed ledger on peer-to-peer asynchronous networks. In particular, we define a principled formal model of key participants - the miners - as stochastic processes and describe the whole system as a parallel composition of miners. We therefore compute the probability that ledgers turn into a state with more severe inconsistencies, e.g. with longer forks, under the assumptions that messages are not lost and nodes are not hostile. We also study how the presence of hostile nodes mining blocks in wrong positions impacts on the consistency of the ledgers. Our theoretical results agree with the simulations performed on a probabilistic model checker that we extended with dynamic datatypes in order to have a faithful description of miners' behaviour.