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.
Abstract Blockchain technology is transforming traditional financial systems. Cross-border money remittance industry is in a crossroad being challenged. The traditional SWIFT system is facing new comers like Ripple system which is based on the blockchain distributed ledger technology with its own crypto tokens. This paper conducts a SWOT analysis on both technologies to find out whether the blockchain technology has the potential to transform a traditional industry and how this may be possible. We conclude that Ripple has all of the advantages over SWIFT despite some minor issues. In short-term, SWIFT will still take the lead in the remittance market due to the economy of scale. However, in long-term, emerging technology like Ripple will eventually revolutionize the remittance industry or even other financial systems.
Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou
In his PODC’2017 keynote address, Maurice Herlihy pointed out that 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. We then provide a variation of the ledger – the validated ledger – which requires that each record in the ledger satisfies a particular validation rule. A (validated) ledger is distributed if it is implemented on top of multiple (possibly geographically dispersed) computing devices.
Ingo Weber, Vincent Gramoli, Alex Ponomarev, Mark Staples · 7 authors
Blockchain has recently gained momentum. Startups, enterprises, banks, and government agencies around the world are exploring the use of blockchain for broad applications including public registries, supply chains, health records, and voting. Dependability properties, like availability, are critical for many of these applications, but the guarantees offered by the blockchain technology remain unclear, especially from an application perspective. In this paper, we identify the availability limitations of two mainstream blockchains, Ethereum and Bitcoin. We demonstrate that while read availability of blockchains is typically high, write availability - for transaction management - is actually low. For Ethereum, we collected 6 million transactions over a period of 97 days. First, we measured the time for transactions to commit as required by the applications. Second, we observed that some transactions never commit, due to the inherent blockchain design. Third and perhaps even more dramatically, we identify the consequences of the lack of built-in options for explicit abort or retry that can maintain the application in an uncertain state, where transactions remain pending (neither aborted nor committed) for an unknown duration. Finally we propose techniques to mitigate the availability limitations of existing blockchains, and experimentally test the efficacy of these techniques.
Almost all real world activities have been digitized and there are various client server architecture based systems in place to handle them. These are all based on trust on third parties. There is an active attempt to successfully implement blockchain based systems which ensures that the IT systems are immutable, double spending is avoided and cryptographic strength is provided to them. A successful implementation of blockchain as backbone of existing information technology systems is bound to eliminate various types of fraud and ensure quicker delivery of the item on trade. To adapt IT systems to blockchain architecture, an efficient consensus algorithm need to be designed. Blockchain based on proof of work first came up as the backbone of cryptocurrency. After this, several other methods with variety of interesting features have come up. In this paper, we conduct a survey on existing attempts to achieve consensus in block chain. A federated consensus method and a proof of validation method are being compared.
Blockchain is a distributed timestamp server technology introduced for realization of Bitcoin, a digital cash system. It has been attracting much attention especially in the areas of financial and legal applications. But such applications would fail if they are designed without knowledge of the fundamental differences in blockchain from existing technology. We show that blockchain is a probabilistic state machine in which participants can never commit on decisions, we also show that this probabilistic nature is necessarily deduced from the condition where the number of participants remains unknown. This work provides useful abstractions to think about blockchain, and raises discussion for promoting the better use of the technology.
We give an explicit definition of decentralization and show you that\ndecentralization is almost impossible for the current stage and Bitcoin is the\nfirst truly noncentralized currency in the currency history. We propose a new\nframework of noncentralized cryptocurrency system with an assumption of the\nexistence of a weak adversary for a bank alliance. It abandons the mining\nprocess and blockchain, and removes history transactions from data\nsynchronization. We propose a consensus algorithm named Converged Consensus for\na noncentralized cryptocurrency system.\n
The minmax regret problem for combinatorial optimization under uncertainty\ncan be viewed as a zero-sum game played between an optimizing player and an\nadversary, where the optimizing player selects a solution and the adversary\nselects costs with the intention of maximizing the regret of the player. The\nexisting minmax regret model considers only deterministic solutions/strategies,\nand minmax regret versions of most polynomial solvable problems are NP-hard. In\nthis paper, we consider a randomized model where the optimizing player selects\na probability distribution (corresponding to a mixed strategy) over solutions\nand the adversary selects costs with knowledge of the player's distribution,\nbut not its realization. We show that under this randomized model, the minmax\nregret version of any polynomial solvable combinatorial problem becomes\npolynomial solvable. This holds true for both the interval and discrete\nscenario representations of uncertainty. Using the randomized model, we show\nnew proofs of existing approximation algorithms for the deterministic model\nbased on primal-dual approaches. Finally, we prove that minmax regret problems\nare NP-hard under general convex uncertainty.\n
In the Grid computing environment, computation, services, and storage belong to different organizations or individuals with different objectives. Entities in this domain are autonomous and self-interested; however, they are willingly to share their resources to achieve their individual and collective goals. In such open environment, the scheduling decision is a challenge given the decentralized nature of the environment. Each entity has specific requirements that need to achieve. This work analysis the environment structure for the Grid, proposes a bidding language that is expressive and a winner determination algorithm that is adequate for the Grid computing environment.
In recent decades, there has been an increasing interest in systems comprised of several autonomous mobile robots, and as a result, there has been a substantial amount of development in the eld of Articial Intelligence, especially in Robotics. There are several studies in the literature by some researchers from the scientic community that focus on the creation of intelligent machines and devices capable to imitate the functions and movements of living beings. Multi-Robot Systems (MRS) can often deal with tasks that are dicult, if not impossible, to be accomplished by a single robot. In the context of MRS, one of the main challenges is the need to control, coordinate and synchronize the operation of multiple robots to perform a specic task. This requires the development of new strategies and methods which allow us to obtain the desired system behavior in a formal and concise way. This PhD thesis aims to study the coordination of multi-robot systems, in particular, addresses the problem of the distribution of heterogeneous multi-tasks. The main interest in these systems is to understand how from simple rules inspired by the division of labor in social insects, a group of robots can perform tasks in an organized and coordinated way. We are mainly interested on truly distributed or decentralized solutions in which the robots themselves, autonomously and in an individual manner, select a particular task so that all tasks are optimally distributed. In general, to perform the multi-tasks distribution among a team of robots, they have to synchronize their actions and exchange information. Under this approach we can speak of multi-tasks selection instead of multi-tasks assignment, which means, that the agents or robots select the tasks instead of being assigned a task by a central controller. The key element in these algorithms is the estimation ix of the stimuli and the adaptive update of the thresholds. This means that each robot performs this estimate locally depending on the load or the number of pending tasks to be performed. In addition, it is very interesting the evaluation of the results in function in each approach, comparing the results obtained by the introducing noise in the number of pending loads, with the purpose of simulate the robot's error in estimating the real number of pending tasks. The main contribution of this thesis can be found in the approach based on self-organization and division of labor in social insects. An experimental scenario for the coordination problem among multiple robots, the robustness of the approaches and the generation of dynamic tasks have been presented and discussed. The particular issues studied are: Threshold models: It presents the experiments conducted to test the response threshold model with the objective to analyze the system performance index, for the problem of the distribution of heterogeneous multitasks in multi-robot systems; also has been introduced additive noise in the number of pending loads and has been generated dynamic tasks over time. Learning automata methods: It describes the experiments to test the learning automata-based probabilistic algorithms. The approach was tested to evaluate the system performance index with additive noise and with dynamic tasks generation for the same problem of the distribution of heterogeneous multi-tasks in multi-robot systems. Ant colony optimization: The goal of the experiments presented is to test the ant colony optimization-based deterministic algorithms, to achieve the distribution of heterogeneous multi-tasks in multi-robot systems. In the experiments performed, the system performance index is evaluated by introducing additive noise and dynamic tasks generation over time.
Alessandro Di Giorgio, Laura Pimpinella, Alessandra Quaresima, Simone Curti
This paper proposes the design of a Smart Home Controller strategy providing efficient management of electric energy in a domestic environment. The problem is formalized as a binary linear programming problem, the output of which specifies the best time to run of Smart Household Appliances, under a Virtual Power Threshold constraint, taking into account the real power threshold and the forecast of consumption from not plannable loads. This problem formulation allows to analyze relevant scenarios from consumer and energy retailer point of view: here optimization of economic saving in case of multi-tariff contract and Demand Side Management have been discussed and simulated. Simulations have been performed on relevant test cases, based on real load profiles provided by the smart appliance manifacturer Electrolux S.p.A. and on energy tariffs suggested by the energy retailer Edison. Results provide a proof of concept about the consumers benefits coming from the use of local energy management systems and the relevance of automated Demand Side Management for the general target of efficient and cost effective operation of electric networks.