We give a straightforward proof for the formula giving the long-term apparent hashrate of the Selfish Mining strategy in Bitcoin using only elementary probabilities and combinatorics, and more precisely, Dyck words. There is no need to compute stationary probabilities on Markov chain nor stopping times for Poisson processes as it was previously done. We consider also several other block withholding strategies.
In Ethereum, many accounts and funds have been managed by smart contracts, thereby making them easy to be targeted. Due to the persistence characteristic of blockchain, revising a deployed smart contract is almost impossible. Both realities heighten the risks of managing funds and thus increase the demand for conducting sufficient testing to Ethereum Smart Contracts (ESC). Different from the conventional software, ESC is a gas-driven program, where developers must charge gases for deploying and testing it. Therefore, it is important to provide a cost-effective yet representative test suite, where its representativeness can be typically measured by its branch coverage. In this paper, we deem the problem of ESC test generation as a Pareto minimization problem, and three objectives, minimizing (1) uncovered branch coverage, (2) time cost, and (3) gas cost are considered. Then, we propose a random based and an NSGA-II based multi-objective approach to seek cost-effective test-suites. Our empirical study on a set of smart contracts in eight of the most widely used Ethereum Decentralized Applications (DApps) verified that the proposed approaches could significantly reduce the gas cost as well as the time cost while retaining the ability to cover branches.
To address the large amount of energy wasted by blockchains, we propose a decentralized consensus protocol for blockchains in which the computation can be used to search for good approximate solutions to any optimization problem. Our protocol allows the wasted energy to be used for finding approximate solutions to problems submitted by any nodes~(called clients). Our protocol works in a similar way to proof-of-work, and it makes nodes evaluate a large number of solution candidates to add a new block to the chain. A client provides a search program that implements any search algorithm that finds a good solution by evaluating a large number of solution candidates. The node that finds the best approximate solution is rewarded by the client. Our analysis shows that the probability of a fork and the variance in the block time with our protocol are lower than those in proof-of-work.
In this paper, we use the credit mechanism of E-commerce platform to evaluate the transaction subject as user reviews, and evaluate the credit degree of the blockchain nodes based on the consensus algorithm of the consortium blockchain as node reviews, then associate the node credit score consisting of user and node reviews with the transaction cost to substitute the incentive effect of the block reward for ledger maintenance. According to the score-pricing strategy we will introduce later, this incentive method can ameliorate the problem of too concentrated bookkeeping permissions and improve the initiative of the accounting node.
Chun‐Wei Chen, Jianwei Su, Tung-Wei Kuo, Kung Chen
In this paper, we focus on the design of consensus algorithms for permission-based blockchains, i.e., private blockchains. In most consensus algorithms, blocks are proposed by a specific role called “leader”. In this paper, we introduce a new role called “witness” to supervise the leader. The presence of the witness facilitates the design of the consensus algorithm. We propose a witness-based consensus algorithm that guarantees safety and liveness. We implemented this consensus algorithm on Go Ethereum. The experimental result shows that in a blockchain where four nodes participate in the consensus process, we can achieve a throughput of 1000 transactions per second (TPS). Even if these four nodes are located on different continents, and one of them is faulty, we can still achieve a throughput of 300 TPS. Finally, we find that during the experiment, a significant portion of time is spent on activities other than the consensus task. The result suggests that to further increase the throughput of a private blockchain, the consensus task and non-consensus activities should be considered jointly.
Distributed Ledger Technology is getting famous day by day. Not only investors, financial organizations and technical personnel are interested in this technology, but also government and nearly every other organization are showing interest in this evolving technology. This technology deals with the settlement of transactions without the need of any third party. But it also requires that different nodes distributed all over the world should have the same state of the data to prevent faulty transactions for which there is a need of consensus algorithms. Many algorithms have already been developed and implemented. This paper discusses some of the algorithms that are widely accepted or talked about and also compares them in terms of centralization, energy consumption, transaction rate etc.
Since the inception of blockchain and Bitcoin (Nakamoto (2008)), a decentralized-distributed ledger system and its associated cryptocurrency, respectively, the world has witnessed a slew of newer adaptations and applications. Although the original distributed ledger technology (DLT) of blockchain is deemed secure and decentralized, the confirmation of transactions is inefficient by design. Recently adopted, directed acyclic graph (DAG)-based distributed ledgers validate transactions efficiently without the physically and environmentally costly building process of blocks (Lerner (2015)). However, centrally-controlled confirmation against the odds of multiple validation disqualifies the DAG as a decentralized-distributed ledger. In this regard, we introduce an innovative DLT by reconstructing a chain of antichains based on a given DAG-pool of transactions. Each antichain (box) contains distinct nodes whose approved transactions are recursively validated by subsequently augmenting nodes. The boxer node closes the box and keeps the hash of all transactions confirmed by the box-genesis node. Designation of boxers and box-geneses is conditionally randomized for decentralization. The boxes are serially concatenated with recursive confirmation (boxchain) without incurring the cost of box generation. Rewards (boxcoin) are paid to the contributing nodes of the ecosystem whose trust is built on the doubly-secure protocol of confirmation. A value-preserving medium of payment (boxdollar) is among numerous practical applications discussed herein.
Blockmania is a byzantine consensus protocol. Nodes emit blocks forming a directed acyclic graph (block DAG) that is subsequently interpreted by each node separately to ensure consensus with safety, liveness and finality. The resulting system has communication complexity $O(N^2)$ even in the worse case, and very low constant factors --- as compared to $O(N^4)$ for PBFT; it is leaderless; and network operations do not depend on the composition of the quorum or node stake. This makes Blockmania very efficient (leading to over 400K transactions per second on a wide area network), and ideal for dynamic membership and flexible and non-interrupted proof-of-stake protocols. A X-Blockmania variant, has $O(N)$ communication cost but also higher latency $O(\log N)$.
This project was focused on designing a tool for optimizing complex transactions in a traditional bank accounts, Bitcoin wallet accounts and Bitcoin exchanges. The challenges include transference fees eroding the amounts transferred, Bitcoin volatility and arbitrage. The tool should support hundreds of accounts with each account identifi ed by a bank or exchange, and a currency. The basic user-case, we call it Debit Scenario, appears when an account consumes it capital and has very little funding (sink or demand account), then the user set a minimum funding for the account, and we need to balance all the accounts of the network, using many currency circulations though many paths to satisfy the specifi ed funding limits. Another user case, we called it Custodian Scenario, is when certain accounts (i.e. supply or non-custodians) has upper limit on the amount of capital so we need to distribute the excess value in other accounts (i.e. demand or custodians) of the network. The problem was modelled as a multi-commodity min-cost max- flow problem with specifi c constraints including arbitrage information, and solved with linear programming. Simple and complex numerical scenarios are presented too.
Sachin M. Kolekar, Rahul P. More, Smita S. Bachal, Anuradha Yenkikar
Blockchain technologies are secure massive power in the last few years. Block chains are distributed ledgers that facilitate parties who do not steady trust each other to maintain a set of ecumenical states. The parties concur on the easiness, standards and histories of the states. As the technology backdrop is enlarge swiftly, it is mutually consequential and arduous to have a rigid grasp of what the foundation technologies have to offer, particularly with difference to their data dealing out capabilities. In this paper, we first survey the state of the art, fixating on secretive block chains. We analyze both in-engenderment and research systems in four dimensions: disseminated ledger, intrusion detection, consortium Blockchain, consensus protocol and perspicacious agreement. We then present BLOCKBENCH, a criterion skeleton for understanding performance of private block chains and public Blockchain. In this chapter we have discussed the circumscriptions of Blockchain.
Blockchain is an emerging technology that gained a lot of attention in the last years. Many different consensus protocols have been proposed to improve both the scalability and the resilience of existing blockchain. However, all these solutions have been defined for rather static settings. We propose a modular approach for analysing and comparing different consensus protocols used in blockchain under churn.
Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, Sara Tucci-Piergiovanni
Tendermint-core blockchains (e.g. Cosmos) are considered today one of the most viable alternatives for the highly energy consuming proof-of-work blockchains such as Bitcoin and Ethereum. Their particularity is that they aim at offering strong consistency (no forks) in an open system combining two ingredients (i) a set of validators that generate blocks via a variant of Practical Byzantine Fault Tolerant (PBFT) consensus protocol and (ii) a selection strategy that dynamically selects nodes to be validators for the next block via a proof-of-stake mechanism. However,the exact assumptions on the system model under which Tendermint underlying algorithms are correct and the exact properties Tendermint verifies have never been formally analyzed. The contribution of this paper is two-fold. First, while formalizing Tendermint algorithms we precisely characterize the system model and the exact problem solved by Tendermint. We prove that in eventual synchronous systems a modified version of Tendermint solves (i) under additional assumptions, a variant of one-shot consensus for the validation of one single block and (ii) a variant of the repeated consensus problem for multiple blocks. These results hold even if the set of validators is hit by Byzantine failures, provided that for each one-shot consensus instance less than one third of the validators is Byzantine. Our second contribution relates to the fairness of the rewarding mechanism. It is common knowledge that in permisionless blockchain systems the main threat is the tragedy of commons that may yield the system to collapse if the rewarding mechanism is not adequate. Ad minimum the rewarding mechanism must be fair, i.e.distributing the rewards in proportion to the merit of participants. We prove, for the first time in blockchain systems, that in repeated-consensus based blockchains there exists an (eventual) fair rewarding mechanism if and only if the system is (eventual) synchronous. We also show that the original Tendermint rewarding is not fair, however, a modification of the original protocol makes it eventually fair.
Hao Xu, Long Yu, Liu Zhiqiang, Zhen Liu · 5 authors
This paper describes a novel Byzantine fault tolerant protocol that allows replicas to join and exit dynamically. With the astonishing success of cryptocurrencies, people attach great importance in “blockchain” and robust Byzantine fault tolerant (BFT) protocols for consensus. Among the conventional wisdom, the Practical Byzantine Fault Tolerance (PBFT), proposed by Miguel and Liskov in 1999, occupies an important position. Although PBFT has many advantages, it has fatal disadvantages. Firstly, it works in a completely enclosed environment, where users who want to add or take out any node must stop the whole system. Secondly, although PBFT guarantees liveness and safety if at most [n-1/ 3] c out of a total n replicas are faulty, it takes no measure to deal with these ineffective or malicious replicas, which is harmful to the system and will cause system crash finally. These drawbacks are unbearable in practice. In order to solve them, we present an alternative, Dynamic PBFT.
Emmanuelle Anceaume, Antonella Del Pozzo, Romaric Ludinard, Maria Potop-Butucaru · 5 authors
The presented work continues the line of recent distributed computing community efforts dedicated to the theoretical aspects of blockchains. This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. Our work is based on an original oracle-based construction that, along with new consistency definitions, captures the eventual convergence process in blockchain systems. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.
Antonio Fernández Anta, Chryssis Georgiou, Kishori M. Konwar, Nicolas Nicolaou
Despite the hype about blockchains and distributed ledgers, no formal abstraction of these objects has been proposed. To face this issue, in this paper we provide a proper formulation of a distributed ledger object. In brief, we define a ledger object as a sequence of records, and we provide the operations and the properties that such an object should support. Implementation of a ledger object on top of multiple (possibly geographically dispersed) computing devices gives rise to the distributed ledger object. In contrast to the centralized object, distribution allows operations to be applied concurrently on the ledger, introducing challenges on the consistency of the ledger in each participant. We provide the definitions of three well known consistency guarantees in terms of the operations supported by the ledger object: (1) atomic consistency (linearizability), (2) sequential consistency, and (3) eventual consistency. We then provide implementations of distributed ledgers on asynchronous message passing crash-prone systems using an Atomic Broadcast service, and show that they provide eventual, sequential or atomic consistency semantics. We conclude with a variation of the ledger - the validated ledger - which requires that each record in the ledger satisfies a particular validation rule.
As proof-of-work blockchains are inherently energy greedy and offer probabilistic guarantees, blockchains based on Byzantine consensus appear as a promising technology to track billions of connected devices. In this paper, we evaluate the performance of prominent blockchains that solve the classic Byzantine consensus problem. Our results show that while offering reasonable throughput their performance usually do not scale to tens of devices and drops dramatically as the number of devices increases. This study motivates the need for solutions that solves the Blockchain consensus problem, a scalable variant of the classic Byzantine consensus problem but dedicated to blockchains.
An atomic cross-chain swap is a distributed coordination task where multiple parties exchange assets across multiple blockchains, for example, trading bitcoin for ether. An atomic swap protocol guarantees (1) if all parties conform to the protocol, then all swaps take place, (2) if some coalition deviates from the protocol, then no conforming party ends up worse off, and (3) no coalition has an incentive to deviate from the protocol. A cross-chain swap is modeled as a directed graph ${\cal D}$, whose vertexes are parties and whose arcs are proposed asset transfers. For any pair $({\cal D},L)$, where ${\cal D} = (V,A)$ is a strongly-connected directed graph and $L \subset V$ a feedback vertex set for ${\cal D}$, we give an atomic cross-chain swap protocol for ${\cal D}$, using a form of hashed timelock contracts, where the vertexes in $L$ generate the hashlocked secrets. We show that no such protocol is possible if ${\cal D}$ is not strongly connected, or if ${\cal D}$ is strongly connected but $L$ is not a feedback vertex set. The protocol has time complexity $O(diam({\cal D}))$ and space complexity (bits stored on all blockchains) $O(|A|^2)$.
Consensus protocols inherently rely on the notion of leader election, in which one or a subset of participants are temporarily elected to authorize and announce the network's latest state. While leader election is a well studied problem, the rise of distributed ledgers (i.e., blockchains) has led to a new perspective on how to perform large-scale leader elections via solving a computationally difficult puzzle (i.e., proof of work). In this paper, we present Caucus, a large-scale leader election protocol with minimal coordination costs that does not require the computational cost of proof-of-work. We evaluate Caucus in terms of its security, using a new model for blockchain-focused leader election, before testing an implementation of Caucus on an Ethereum private network. Our experiments highlight that one variant of Caucus costs only $0.10 per leader election if deployed on Ethereum.
The blockchain is decentralized network system that verifies the validity of the transaction through the consensus of the verifiers without trusted third parties. This mechanism ensures transaction integrity disclosing transaction information transparently. Therefore, it is emerging as the core technology of the 4th industrial revolution by improving reliability and efficiency with features of decentralization, ensuring the integrity, and economic cost reduction. However, there are some problems with the growth of the blockchain. The popularly used PoW (Proof of Work) consensus algorithm applied to the public blockchain requires the price to be compensated in order to agree on the validity of the transaction. This has the disadvantage that the system doesn't operate without compensation. Also, the BFT (Byzantine Fault Tolerance) Algorithm using private blockchain has a limited number of acceptable malicious users. In this case, if the users collude with malicious and exceed the limited number, the transaction is rejected. In this paper, we propose a Smart Manager System and RMBC-DBFT (Randomized Mesh Blockchain Diversity of opinion BFT) enables the safe transaction to the problems above.