SATHISHKUMAR RANGANATHAN, Muralindran Mariappan, M. Karthigayan
Swarm robotics is an evolving realm that aims to achieve a common goal in coordinated way. But the current communication and control mechanism between the robots is not secure, efficient, capable, and it is more centralized. Blockchain, a decentralized, transparent, and immutable P2P communication technology, is the right fit to pair with swarm robotics. This paper discusses the current challenges in paring blockchain with swarm robotics and the applied methodology for the amalgamation of these futuristic technologies.
Eduardo Castelló Ferrer, Ernesto Jiménez, José Luis López-Presa, Javier Martín-Rueda
Interest in multirobot systems is rising rapidly both in academia and in industry. The use of multiple robots working in a coordinated way, rather than a single robot, has several advantages in a diverse range of applications. However, few studies have focused on operations in which robots can behave maliciously and alter the outcome of the collective mission. In this article, we present a set of Byzantine Follow The Leader (BFTL) problems, in which a subset of robots in the system shows unintended or inconsistent behavior (i.e., Byzantine robots). In the BFTL problems,leadersdiscover routes from their starting positions to specific destinations and guide thefollowers, whileByzantinerobots try to hinder the leaders and mislead the followers. In this research, blockchain technology is used as a communication tool within multirobot systems, forleadersto broadcast directions to the whole group. We propose algorithms to tackle the BFTL problems, prove their correctness, and validate them in simulated experiments of realistic scenarios. Results show that the proposed algorithms mitigate the impact of Byzantine robots in multirobot systems conducting a BFTL mission. Our analysis provides minimum and maximum boundary calculations for important metrics including number of robots reaching their destination, number of steps taken, and weight requirements of the chain used during the mission. Our results provide a path toward the deployment of byzantine-resistant real-world multirobot systems.
Proof-of-Stake (PoS) blockchain systems, especially those that allow stakeholders to organize themselves in “stake-pools”, have emerged as a compelling paradigm for the deployment of large scale distributed ledgers. A stake-pool operates a node that engages in the PoS protocol and potentially represents a large number of smaller stakeholders. While such pooled PoS operation is attractive from various angles, it also exhibits a significant shortcoming that, so far and to the best of our knowledge, has not been sufficiently understood or investigated. Pooled PoS operation, to be effective and not lead to sub-optimal dictatorial or cartel-like configurations, should enable the stakeholders to revoke and re-delegate their stake in a way that is aligned with their incentives. However, given that stake-pool operators are exactly those entities who determine what transactions are to be recorded in the ledger, they are quite likely to form a cartel and censor any transaction they want, such as those that attempt to adjust the current stake-pool lineup. In this way, a power grab takes place, where the stake-pool cartel perpetuates its control over the PoS system. We first model and observe formally the emergence of the above problem in pooled PoS systems. Then, we describe an anti-censorship mechanism that takes advantage of the underlying cryptographic functions of the ledger and the nature of peer-to-peer networks to diffuse information without suppression. Specifically, the mechanism exploits digital signatures which can endorse messages that are censored and bind them to delegation transactions, as well as the ability of the underlying ledger to produce unpredictable randomness which can be used to randomly “audit” the suitability of a stake-pool by forcibly expiring it. Upon such expiration, members can evaluate their membership taking into account what information is available, including information potentially not recorded in the ledger but diffused in the peer-to-peer network. We provide a thorough game-theoretic analysis of this mechanism discovering various types of Nash equilibria which demonstrate that the “revolution”, i.e., the strategic decision of pool members to withdraw support from a censoring cartel as well as the pool operators to step down, can be incentivized, under suitable and plausible conditions in the utility functions of the involved participants.
The rise of Ethereum and other blockchains that support smart contracts has led to the creation of decentralized exchanges (DEXs), such as Uniswap, Balancer, Curve, mStable, and SushiSwap, which enable agents to trade cryptocurrencies without trusting a centralized authority. While traditional exchanges use order books to match and execute trades, DEXs are typically organized as constant function market makers (CFMMs). CFMMs accept and reject proposed trades based on the evaluation of a function that depends on the proposed trade and the current reserves of the DEX. For trades that involve only two assets, CFMMs are easy to understand, via two functions that give the quantity of one asset that must be tendered to receive a given quantity of the other, and vice versa. When more than two assets are being exchanged, it is harder to understand the landscape of possible trades. We observe that various problems of choosing a multi-asset trade can be formulated as convex optimization problems, and can therefore be reliably and efficiently solved.
Hyperledger Fabric is an enterprise grade permissioned distributed ledger platform that offers modularity for a broad set of industry use cases. One modular component is a pluggable ordering service that establishes consensus on the order of transactions and batches them into blocks. However, as of the time of this writing, there is no production grade Byzantine Fault-Tolerant (BFT) ordering service for Fabric, with the latest version (v2.3) supporting only Crash Fault-Tolerance (CFT).In this work we describe the design and implementation of a BFT ordering service for Fabric, employing a new BFT consensus library. The new library, based on the BFT-SMART protocol and written in Go, is tailored to the blockchain use-case, yet is general enough to cater to a wide variety of other uses. The BFT library's design and integration into Fabric address crucial aspects that were left unsolved in all prior work, making them unfit for production use. We evaluate the new BFT ordering service by comparing it with the currently supported Raft-based CFT ordering service in Hyperledger Fabric.
The active introduction of robotics swarm systems into life brings the issues of their information security up to date. Known security approaches often do not take into account the peculiarities of the implementation of swarm systems, such as collective design-making, and only consider the presence of Byzantine robots with a strategy of behavior consisting in voting against a majority when a consensus is reached. The aim of this work is to increase the security of the collective design-making process in a swarm robotics system from the imposition of false and ineffective alternatives by Byzantine robots with a random behavior strategy. It is proposed to use an approach based on the use of a distributed ledger and analysis of deviations in the process of collective design-making, which will allow identifying and isolating harmful effects. The solution to the problem of detecting Byzantine robots is based on the application of the criterion of the degree of confidence of a robot in choosing an alternative when a consensus is reached by the swarm system and is based on the assumption that the distribution of the degree of confidence of a Byzantine robot due to ignoring the parameters of the external environment and voting for random alternatives is significantly different from the behavior an ordinary robot. The elements of novelty of the presented solution include the use of the degree of confidence criterion to ensure the safety of collective design-making and the ability to take into account various strategies of behavior of Byzantine robots. The use of the presented solution makes it possible to increase the efficiency of reaching consensus by a swarm robotics system in the presence of Byzantine robots. The simulation for a swarm of 20 robots, including 5 Byzantine ones with random behavior, showed an increase in the probability of correctly reaching a consensus by 12.5%. The practical significance of the presented solutions lies in the possibility of ensuring the stability of reaching consensus by a swarm robotics system in the presence of robots with harmful behavior.
Florian Jacob, Carolin Beer, Norbert Henze, Hannes Hartenstein
Matrix is a new kind of decentralized, topic-based publish-subscribe middleware for communication and data storage that is getting particularly popular as a basis for secure instant messaging. By comparison with traditional decentralized communication systems, Matrix replaces pure message passing with a replicated data structure. This data structure, which we extract and call the Matrix Event Graph (MEG), depicts the causal history of messages. We show that this MEG represents an interesting and important replicated data type for decentralized applications that are based on causal histories of publish-subscribe events: First, we prove that the MEG is a Conflict-Free Replicated Data Type for causal histories and, thus, provides Strong Eventual Consistency (SEC). With SEC being among the best known achievable trade-offs in the scope of the well-known CAP theorem, the MEG provides a powerful consistency guarantee while being available during network partition. Second, we discuss the implications of byzantine attackers on the data type's properties. We note that the MEG, as it does not strive for consensus or strong consistency, can cope with n > f environments with n participants, of which f are byzantine. Furthermore, we analyze scalability: Using Markov chains, we study the number of forward extremities of the MEG over time and observe an almost optimal evolution. We conjecture that this property is inherent to the underlying spatially inhomogeneous random walk. With the properties shown, a MEG represents a promising element in the set of data structures for decentralized applications, but with distinct trade-offs compared to traditional blockchains and distributed ledger technologies.
Vitor N. Coelho, Rodolfo Pereira Araújo, Haroldo Gambini Santos, Wang Yong Qiang · 5 authors
Mixed-integer mathematical programming has been widely used to model and solve challenging optimization problems. One interesting feature of this technique is the ability to prove the optimality of the achieved solution, for many practical scenarios where a linear programming model can be devised. This paper explores its use to model very strong Byzantine adversaries, in the context of distributed consensus systems. In particular, we apply the proposed technique to find challenging adversarial conditions on a state-of-the-art blockchain consensus: the Neo dBFT. Neo Blockchain has been using the dBFT algorithm since its foundation, but, due to the complexity of the algorithm, it is challenging to devise definitive algebraic proofs that guarantee safety/liveness of the system (and adjust for every change proposed by the community). Core developers have to manually devise and explore possible adversarial attacks scenarios as an exhaustive task. The proposed multi-objective model is intended to assist the search of possible faulty scenario, which includes three objective functions that can be combined as a maximization problem for testing one-block finality or a minimization problem for ensuring liveness. Automated graphics help developers to visually observe attack conditions and to quickly find a solution. This paper proposes an exact adversarial model that explores current limits for practical blockchain consensus applications such as dBFT, with ideas that can also be extended to other decentralized ledger technologies.
It is an important decision-making problem for a miner in the blockchain networks if he/she participates in the mining so that he/she earns a reward by creating a new block earlier than other miners. We formulate this decision-making problem as a noncooperative game, because the probability of creating a block depends not only on one's own available computational resources, but also those of other miners. Through theoretical and numerical analyses, we show a hysteresis phenomenon of Nash equilibria depending on the reward and a jump phenomenon of miner decisions by a slight change in reward. We also show that the reward for which miners decide not to participate in the mining becomes smaller as the number of miners increases.
<p class="0abstract">One of the new promising technologies for the future is blockchain. It has become one of the popular techniques for various transactions and applications in many different areas such as economy, business, and government. Blockchain technology started with cryptocurrency and bitcoin applications for a safe and transparent environment. Blockchain is a hybrid technology that incorporates various technologies and tools such as mathematics, peer-peer networking, cryptography algorithms, and consensus algorithms. This survey highlights the latest studies in blockchain and consensus algorithms. The study covers the most recent blockchain applications in various domains and sectors. Furthermore, the study gives an insight into the latest adoption of the blockchain in the real world.</p>
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.
Tiantian Gong, Mohsen Minaei, Wenhai Sun, Aniket Kate
A fixed block reward and voluntary transaction fees are two sources of economic incentives for mining in Bitcoin and other cryptocurrencies. For Bitcoin, the block reward halves every 210,000 blocks and it is supposed to vanish gradually. The remaining incentive of transaction fees is optional and arbitrary, and an undercutting attack becomes a potential threat, where the attacker deliberately forks an existing chain by leaving wealthy transactions unclaimed to attract other miners. We look into the profitability of the undercutting attack in this work.
Our numerical simulations and experiments demonstrate that (i) only miners with mining power > 40% have a reasonable probability of successfully undercutting. (ii) As honest miners do not shift to the fork immediately in the first round, an undercutter's profit drops with the number of honest miners. Given the current transaction fee rate distribution in Bitcoin, with half of the miners being honest, undercutting cannot be profitable at all; With 25% honest mining power, an undercutter with > 45% mining power can expect income more than its fair share; With no honest miners present, the threshold mining power for a profitable undercutting is 42%. (iii) For the current largest Bitcoin mining pool with 17.2% mining power, the probability of successfully launching an undercutting attack is tiny and the expected returns are far below honest mining gains. (iv) While the larger the prize the undercutter left unclaimed, the higher is the probability of the attack succeeding but the attack's profits also go down. Finally, we analyze the best responses to undercutting for other rational miners. (v) For two rational miners and one of them being the potential undercutter with 45% mining power, we find the dominant strategy for the responding rational miner is to typical rational.
Blockchain protocols differ in fundamental ways, including the mechanics of selecting users to produce blocks (e.g., proof-of-work vs. proof-of-stake) and the method to establish consensus (e.g., longest chain rules vs. BFT-inspired protocols). These fundamental differences have hindered "apples-to-apples" comparisons between different categories of blockchain protocols and, in turn, the development of theory to formally discuss their relative merits. This paper presents a parsimonious abstraction sufficient for capturing and comparing properties of many well-known permissionless blockchain protocols, simultaneously capturing essential properties of both proof-of-work and proof-of-stake protocols, and of both longest-chain-type and BFT-type protocols. Our framework blackboxes the precise mechanics of the user selection process, allowing us to isolate the properties of the selection process which are significant for protocol design. We illustrate our framework's utility with two results. First, we prove an analog of the CAP theorem from distributed computing for our framework in a partially synchronous setting. This theorem shows that a fundamental dichotomy holds between protocols (such as Bitcoin) that are adaptive, in the sense that they can function given unpredictable levels of participation, and protocols (such as Algorand) that have certain finality properties. Second, we formalize the idea that proof-of-work (PoW) protocols and non-PoW protocols can be distinguished by the forms of permission that users are given to carry out updates to the state.
Blockchain Technology is exclusively used to make online transactions secure by maintaining a distributed and decentralized ledger of records across multiple computers. Tendermint is a general-purpose blockchain engine that is composed of two parts; Tendermint Core and the blockchain application interface. The application interface makes Tendermint suitable for a wide range of applications. In this paper, we analyze and improve Practical Byzantine Fault Tolerant (PBFT), a consensus-based Tendermint blockchain algorithm. In order to avoid negative issues of locks, we first propose a lock-free algorithm for blockchain in which the proposal and voting phases are concurrent whereas the commit phase is sequential. This consideration in the algorithm allows parallelism. Secondly, a new methodology is used to decide the size of the voter set which is a subset of blockchain nodes, further investigating the block sensitivity and trustworthiness of nodes. Thirdly, to fairly select the voter set nodes, we employ the random walk algorithm. Fourthly, we imply the wait-freedom property by using a timeout due to which all blocks are eventually committed or aborted. In addition, we have discussed voting conflicts and consensuses issues that are used as a correctness property, and provide some supportive techniques.
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.
This paper presents a new consensus protocol based on verifiable delay function. First, we introduce the concept of verifiable delay puzzle (VDP), which resembles the hashing puzzle used in the PoW mechanism but can only be solved sequentially. We then present a VDP implementation based on the continuous verifiable delay function. Further, we show that VDP can be combined with the Nakamoto consensus in a proof-of-stake/proof-of-delay hybrid protocol. We analyze the persistence and liveness of the protocol, and show that compared to PoW, our proposal consumes much less energy; compared to BFT leader-election based consensus algorithms, our proposal achieves better resistance to long-range attacks and DoS attacks targeting the block proposers.
Blockchain is the core technology of many cryptocurrencies. Blockchain as a distributed ledger technology has received extensive research attention. In addition to cryptography and P2P (peer-to-peer) technology, consensus protocols are also a fundamental part of the blockchain technology. A good consensus protocol can guarantee the fault tolerance and security of the blockchain systems. The consensus protocols currently used in most blockchain systems can be broadly divided into two categories: the probabilistic-finality consensus protocols and the absolute-finality consensus protocols. This paper introduces some of the main consensus protocols of these two categories, and analyzes their strengths and weaknesses as well as the applicable blockchain types.
Amos Fiat, Anna R. Karlin, Ηλίας Κουτσουπιάς, Christos H. Papadimitriou
The Bitcoin protocol induces miners, through monetary rewards, to expend energy in order to add blocks to the chain. We show that, when energy costs are substantial and taken into account, counterintuitive and unintended strategic behavior results: In a simple bounded-horizon setting with two identical miners there is a unique pure symmetric equilibrium in which both miners first "slow down" in order to decrease the crypto complexity and then take advantage of this decrease. If miners have different energy efficiencies and are restricted to choose the same hash rate for many epochs, there is a unique pure equilibrium in which miners either participate at low levels that depend in intricate ways on all the other miners' efficiencies, or choose to abstain from mining if their efficiency is too low. In the general setting in which miners can adapt their hash rates over time, we show that, unless the number of miners is very small, the only possible pure equilibria are rather chaotic, with miners quitting and starting again periodically --- or there is no pure equilibrium at all. We discuss the implications of these results for the stability of proof-of-work protocols.
We describe MaGPoS, a novel consensus mechanism which is well suited to decentralized blockchain based protocols. MaGPoS is based on a combination of the well known physics of nano-scale magnetism, and previous implementations of proof of stake. This system has been studied by hundreds of thousands of scientists worldwide for over a hundred years, giving it an extreme level of reliability that is needed for a consensus mechanism. We start by explaining the physics, and study the properties that make it particularly beneficial for use in a consensus mechanism. We then show how to apply the physical model to a decentralized network of nodes, each with their own copy of a blockchain. After this, we describe some example calculations that a node in the decentralized network would make, and provide pseudo code for implementation. Finally, we discuss the how the model achieves all of the important properties that one expects of a consensus mechanism.
Lachlan J. Gunn, Jian Liu, Bruno Vavala, N. Asokan
Consensus mechanisms used by popular distributed ledgers are highly scalable but notoriously inefficient. Byzantine fault tolerance (BFT) protocols are efficient but far less scalable. Speculative BFT protocols such as Zyzzyva and Zyzzyva5 are efficient and scalable but require a trade-off: Zyzzyva requires only $3f + 1$ replicas to tolerate $f$ faults, but even a single slow replica will make Zyzzyva fall back to more expensive non-speculative operation. Zyzzyva5 does not require a non-speculative fallback, but requires $5f + 1$ replicas in order to tolerate $f$ faults. BFT variants using hardware-assisted trusted components can tolerate a greater proportion of faults, but require that every replica have this hardware. We present SACZyzzyva, addressing these concerns: resilience to slow replicas and requiring only $3f + 1$ replicas, with only one replica needing an active monotonic counter at any given time. We experimentally evaluate our protocols, demonstrating low latency and high scalability. We prove that SACZyzzyva is optimally robust and that trusted components cannot increase fault tolerance unless they are present in greater than two-thirds of replicas.
Current swarm robotics systems are not utilized as frequently in surveillance missions due to the limitations of the existing distributed systems' designs. The main limitation of swarm robotics is the absence of a framework for robots to be self-governing, secure, and scalable. As of today, a swarm of robots is not able to communicate and perform tasks in transparent and autonomous ways. Many believe blockchain is the imminent future of distributed autonomous systems. A blockchain is a system of computers that stores and distributes data among all participants. Every single participant is a validator and protector of the data in the blockchain system. The data cannot be modified since all participants are storing and watching the same records. In this thesis, we will focus on blockchain applications in swarm robotics using Ethereum smart contracts because blockchain can make a swarm globally connected and secure. A decentralized application (DApp) is used to deploy surveillance missions. After mission deployment, the swarm uses blockchain to communicate and make decisions on appropriate tasks within Ethereum private networks. We set a test swarm robotics system and evaluate the blockchain for its performance, scalability, recoverability, and responsiveness. We conclude that, although blockchain enables a swarm to be globally connected and secure, there are performance limitations that can become a critical issue.
Jason A. Tran, Gowri Ramachandran, Palash M Shah, Claudiu Danilov · 6 authors
Blockchain technology has the potential to disrupt applications beyond cryptocurrencies. This work applies the concepts of blockchain technology to swarm robotics applications. Swarm robots typically operate in a distributed fashion, wherein the collaboration and coordination between the robots are essential to accomplishing the application goals. However, robot swarms may experience network partitions either due to navigational and communication challenges or in order to perform certain tasks efficiently. We propose a novel protocol, SwarmDAG, that enables the maintenance of a distributed ledger based on the concept of extended virtual synchrony while managing and tolerating network partitions.
While cryptocurrencies and blockchain applications continue to gain popularity, their energy cost is evidently becoming unsustainable. In most instances, the main cost comes from the required amount of energy for the Proof-of-Work, and this cost is inherent to the design. In addition, useless costs from discarded work (e.g., the so-called Forks) and lack of scalability (in number of users and in rapid transactions) limit their practical effectiveness. In this paper, we present an innovative scheme which eliminates the nonce and thus the burden of the Proof-of-Work which is the main cause of the energy waste in cryptocurrencies such as Bitcoin. We prove that our scheme guarantees a tunable and bounded average number of simultaneous mining whatever the size of the population in competition, thus by making the use of nonce-based techniques unnecessary, achieves scalability without the cost of consuming a large volume of energy. The technique used in the proof of our scheme is based on the analogy of the analysis of a green leader election. The additional difference with Proof-of-Work schemes (beyond the suppression of the nonce field that is triggering most of the waste), is the introduction of “empty blocks” which aim are to call regular blocks following a staircase set of values. Our scheme reduces the risk of Forks and provides tunable scalability for the number of users and the speed of block generation.
We present a general consensus framework that allows to easily introduce a customizable Byzantine fault tolerant consensus algorithm to an existing (Delegated) Proof-of-Stake blockchain. We prove the safety of the protocol under the assumption that less than 1/3 of the validators are Byzantine. The framework further allows for consensus participants to choose subjective decision thresholds in order to obtain safety even in the case of a larger proportion of Byzantine validators. Moreover, the liveness of the protocol is shown if less than 1/3 of the validators crash. Based on the framework, we introduce Lisk-BFT, a Byzantine fault tolerant consensus algorithm for the Lisk ecosystem. Lisk-BFT integrates with the existing block proposal mechanism, requires only two additional integers in blocks and no additional messages. The protocol is simple and provides safety in the case of static validators if less than 1/3 of the validators are Byzantine. For the case of dynamically changing validators, we prove the safety of the protocol assuming a bound on the number of Byzantine validators and the number of honest validators that can change at one time. We further show the liveness of the Lisk-BFT protocol for less than 1/3 crashing validators.