Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse
Classic BFT consensus protocols guarantee safety and liveness for all clients if fewer than one-third of replicas are faulty. However, in applications such as high-value payments, some clients may want to prioritize safety over liveness. Flexible consensus allows each client to opt for a higher safety resilience, albeit at the expense of reduced liveness resilience. We present the first construction that allows optimal safety--liveness tradeoff for every client simultaneously. This construction is modular and is realized as an add-on applied on top of an existing consensus protocol. The add-on consists of an additional round of voting and permanent locking done by the replicas, to sidestep a sub-optimal quorum-intersection-based constraint present in previous solutions. We adapt our construction to the existing Ethereum protocol to derive optimal flexible confirmation rules that clients can adopt unilaterally without requiring system-wide changes. This is possible because existing Ethereum protocol features can double as the extra voting and locking. We demonstrate an implementation using Ethereum's consensus API.
Through cooperation, robot swarms can perform tasks or solve problems that a single robot from the swarm could not perform/solve by itself. However, it has been shown that a single Byzantine robot (such as a malfunctioning or malicious robot) can disrupt the coordination strategy of the entire swarm. Therefore, a versatile swarm robotics framework that addresses security issues in inter-robot communication and coordination is urgently needed. Here, we show that security issues can be addressed by setting up a token economy between the robots. To create and maintain the token economy, we used blockchain technology, originally developed for the digital currency Bitcoin. The robots were given crypto tokens that allowed them to participate in the swarm's security-critical activities. The token economy was regulated via a smart contract that decided how to distribute crypto tokens among the robots depending on their contributions. We designed the smart contract so that Byzantine robots soon ran out of crypto tokens and could therefore no longer influence the rest of the swarm. In experiments with up to 24 physical robots, we demonstrated that our smart contract approach worked: The robots could maintain blockchain networks, and a blockchain-based token economy could be used to neutralize the destructive actions of Byzantine robots in a collective-sensing scenario. In experiments with more than 100 simulated robots, we studied the scalability and long-term behavior of our approach. The obtained results demonstrate the feasibility and viability of blockchain-based swarm robotics.
Darcy Camargo, Andreas Penzkofer, Sebastian Müller, William H. Sanders
The robust construction of the ledger data structure is an essential ingredient for the safe operation of a distributed ledger. While in traditional linear blockchain systems, permission to append to the structure is leader-based, in Directed Acyclic Graph-based ledgers, the writing access can be organised leaderless. However, this leaderless approach relies on fair treatment of non-referenced blocks, i.e. tips, by honest block issuers. We study the impact of a deviation from the standard tip selection by a subset of block issuers with the aim of halting the confirmation of honest blocks entirely. W e provide models on this so-called orphanage of blocks and validate these through open-sourced simulation studies. A critical threshold for the adversary issuance rate is shown to exist, above which the tip pool becomes unstable, while for values below the orphanage decrease exponentially. We study the robustness of the protocol with an expiration time on tips, also called garbage collection, and modification of the parent references per block.
Abstract We introduce semitopology, a generalization of point-set topology that removes the restriction that intersections of open sets need necessarily be open. The intuition is that points represent participants in a decentralized system, and open sets represent collections of participants that collectively have the authority to collaborate to update their local state; we call this an actionable coalition. Examples of actionable coalition include: majority stakes in proof-of-stake blockchains; communicating peers in peer-to-peer networks; and even pedestrians working together to not bump into one another in the street. Where actionable coalitions exist, they have in common that collaborations are local (updating the states of the participants in the coalition, but not immediately those of the whole system); collaborations are voluntary (up to and including breaking rules); participants may be heterogeneous in their computing power or in their goals (not all pedestrians want to go to the same place); participants can choose with whom to collaborate; and they are not assumed subject to permission or synchronization by a central authority. We develop a topology-flavoured mathematics that goes some way to explaining how and why these complex decentralized systems can exhibit order, and gives us new ways to understand existing practical implementations. Semitopology is also interesting in and of itself, having a rich and interesting theory that quickly deviates from standard accounts on topological spaces. It soon becomes clear that the most interesting semitopologies are rather ill-behaved from the usual viewpoint, as they are never Hausdorff. A notion of ‘transitive open sets’ (topens) becomes central to the story, as topens define subsets of participants who should decide the same value in a distributed system that tries to achieve consensus, and points are called ‘regular’ when they have a topen neighbourhood. The theory is then further developed by introducing intertwined points, closures, closed sets and two interesting characterizations of regularity.
Ali Nikhalat-Jahromi, Ali Mohammad Saghiri, Mohammad Reza Meybodi
Learning Automaton (LA) is an adaptive self-organized model that improves its action-selection through interaction with an unknown environment. LA with finite action set can be classified into two main categories: fixed and variable structure. Furthermore, variable action-set learning automaton (VASLA) is one of the main subsets of variable structure learning automaton. In this paper, we propose VDHLA, a novel hybrid learning automaton model, which is a combination of fixed structure and variable action set learning automaton. In the proposed model, variable action set learning automaton can increase, decrease, or leave unchanged the depth of fixed structure learning automaton during the action switching phase. In addition, the depth of the proposed model can change in a symmetric (SVDHLA) or asymmetric (AVDHLA) manner. To the best of our knowledge, it is the first hybrid model that intelligently changes the depth of fixed structure learning automaton. Several computer simulations are conducted to study the performance of the proposed model with respect to the total number of rewards and action switching in stationary and non-stationary environments. The proposed model is compared with FSLA and VSLA. In order to determine the performance of the proposed model in a practical application, the selfish mining attack which threatens the incentive-compatibility of a proof-of-work based blockchain environment is considered. The proposed model is applied to defend against the selfish mining attack in Bitcoin and compared with the tie-breaking mechanism, which is a well-known defense. Simulation results in all environments have shown the superiority of the proposed model.
Ali Nikhalat Jahromi, Ali Mohammad Saghiri, Mohammad Reza Meybodi
The Bitcoin cryptocurrency has received much attention recently. In the network of Bitcoin, transactions are recorded in a ledger. In this network, the process of recording transactions depends on some nodes called miners that execute a protocol known as mining protocol. One of the significant aspects of mining protocol is incentive compatibility. However, literature has shown that Bitcoin mining's protocol is not incentive-compatible. Some nodes with high computational power can obtain more revenue than their fair share by adopting a type of attack called the selfish mining attack. In this paper, we propose an artificial intelligence-based defense against selfish mining attacks by applying the theory of learning automata. The proposed defense mechanism ignores private blocks by assigning weight based on block discovery time and changes current Bitcoin's fork resolving policy by evaluating branches' height difference in a self-adaptive manner utilizing learning automata. To the best of our knowledge, the proposed protocol is the literature's first learning-based defense mechanism. Simulation results have shown the superiority of the proposed mechanism against tie-breaking mechanism, which is a well-known defense. The simulation results have shown that the suggested defense mechanism increases the profit threshold up to 40\% and decreases the revenue of selfish attackers.
Rui Morais, Paul Crocker, Valderi Reis Quietinho Leithardt
This paper presents the research undertaken with the goal of designing a consensus algorithm for cryptocurrencies with less latency than the current state-of-the-art while maintaining a level of throughput and scalability sufficient for real-world payments. The result is Nero, a new deterministic leaderless byzantine consensus algorithm in the partially synchronous model that is especially suited for Directed Acyclic Graph (DAG)-based cryptocurrencies. In fact, Nero has a communication complexity of O(n3) and terminates in two message delays in the good case (when there is synchrony). The algorithm is shown to be correct, and we also show that it can provide eventual order. Finally, some performance results are given based on a proof of concept implementation in the Rust language.
Chryssis Georgiou, Michel Raynal, Elad M. Schiller
Numerous distributed applications, such as cloud computing and distributed ledgers, necessitate the system to invoke asynchronous consensus objects an unbounded number of times, where the completion of one consensus instance is followed by the invocation of another. With only a constant number of objects available, object reuse becomes vital. We investigate the challenge of object recycling in the presence of Byzantine processes, which can deviate from the algorithm code in any manner. Our solution must also be self-stabilizing, as it is a powerful notion of fault tolerance. Self-stabilizing systems can recover automatically after the occurrence of arbitrary transient faults, in addition to tolerating communication and (Byzantine or crash) process failures, provided the algorithm code remains intact. We provide a recycling mechanism for asynchronous objects that enables their reuse once their task has ended, and all non-faulty processes have retrieved the decided values. This mechanism relies on synchrony assumptions and builds on a new self-stabilizing Byzantine-tolerant synchronous multivalued consensus algorithm, along with a novel composition of existing techniques.
We propose a novel model for teaching and learning called Decentralized Autonomous Education (DAE for short). DAE exploits the dual principles of freedom and responsibility, meritocracy and inclusivity, privacy and transparency in the educational process. It also fits well the philosophy of blockchain technology, and more generally of Web3 – the third iteration of the World Wide Web – specifically the tenets of decentralization, disintermediation, incentive and sovereignty of the individual. In this paper, we fully illustrate the DAE model, highlighting the theoretical and practical links between DAE and Web3, dissecting the pros and cons of the proposed learning method and reviewing related pedagogical approaches. Finally, we describe the front-end and back-end design of the DAE app, a decentralized application that implements the DAE learning model.
As a distributed ledger technology, blockchain can be used in the fields of information sharing, logistics chain, certificate storage and anti-counterfeiting. However, due to the isolated nature of the blockchain network and the high degree of heterogeneity between chains, the connection between different chains is hindered, which makes each blockchain form a value island and cannot serve the practical applications well. The emergence of cross chain technology realizes the value circulation between different chains and enhances the interoperability and scalability of blockchains. Among them, the cross-chain technology of notary mechanism transforms the trust problem among cross-chain users into the loyalty problem of notary, and is favored for its ability to support different types of underlying blockchain systems in a more flexible manner. However, the introduction of notaries in the notary mechanism also leads to the risk of centralization, and the loyalty of notaries will directly determine the success of cross-chain transactions. In this paper, by introducing the improved PageRank algorithm, we design a dynamic notary group election mechanism based on reputation value, which effectively avoids malicious nodes from becoming notaries and improves the success rate of cross-chain transactions while preventing the over-concentration of rights in a single node. The experimental analysis shows that selecting notary representatives by dynamically adjusting the reputation value ranking of notary nodes increases the selection probability of loyal nodes, which is more reasonable than the method of randomly selecting notaries.
Alexis Asseman, Tomasz Kornuta, Patel, Anirudh, Matt Deible · 5 authors
The Graph Protocol indexes historical blockchain transaction data and makes it available for querying. As the protocol is decentralized, there are many independent Indexers that index and compete with each other for serving queries to the Consumers. One dimension along which Indexers compete is pricing. In this paper, we propose a bandit-based algorithm for maximization of Indexers' revenue via Consumer budget discovery. We present the design and the considerations we had to make for a dynamic pricing algorithm being used by multiple agents simultaneously. We discuss the results achieved by our dynamic pricing bandits both in simulation and deployed into production on one of the Indexers operating on Ethereum. We have open-sourced both the simulation framework and tools we created, which other Indexers have since started to adapt into their own workflows.
Sahar Salimpour, Farhad Keramat, Jorge Peña Queralta, Tomi Westerlund
Multiple opportunities lie at the intersection of multi-robot systems and distributed ledger technologies (DLTs). In this work, we investigate the potential of new DLT solutions such as IOTA, for detecting anomalies and byzantine agents in multi-robot systems in a decentralized manner. Traditional blockchain approaches are not applicable to real-world networked and decentralized robotic systems where connectivity conditions are not ideal. To address this, we leverage recent advances in partition-tolerant and byzantine-tolerant collaborative decision-making processes with IOTA smart contracts. We show how our work in vision-based anomaly and change detection can be applied to detecting byzantine agents within multiple robots operating in the same environment. We show that IOTA smart contracts add a low computational overhead while allowing to build trust within the multi-robot system. The proposed approach effectively enables byzantine robot detection based on the comparison of images submitted by the different robots and detection of anomalies and changes between them.
Yunming Xiao, Sarit Markovich, Aleksandar Kuzmanovic
Having enabled numerous applications, blockchains have attracted not only much attention, in the past decade, but also huge amount of resources: talent, capital, energy, etc. Focusing on the mining side of the market, in this paper, we aim at understanding how to efficiently use the resources mining and staking pools attract. We start with developing predictions about factors that increase the efficient allocation of pools' resources. We then test our predictions based on a general model for optimal resource allocation that we develop, as well as data we collected on pools' actual resource allocations. We find that pools can increase resource efficiency by mining for more blockchains as well as by increasing the frequency of resource re-allocation. Further, we enroll to mining pools as a miner to understand and comment on how pools can encourage their miners to increase the efficiency of their allocation. While our empirical investigation mostly focuses on the BTC family, we show that our theory and results are general and applicable to the Ethereum family as well as other proof-of-work (PoW) and proof-of-stake (PoS) chains.
This perspective highlights some recent progress on the research of Byzantine fault tolerant (BFT) consensus protocol in the era of blockchains, including both partially synchronous BFT and asynchronous BFT protocols, their fundamental building blocks, and their variants.
Warlley Paulo Freire, Wilson S. Melo, Vinicius D. do Nascimento, Paulo R. Nascimento · 5 authors
Maritime Domain Awareness (MDA) is a strategic field of study that seeks to provide a coastal country with an effective monitoring of its maritime resources and its Exclusive Economic Zone (EEZ). In this scope, a Maritime Monitoring System (MMS) aims to leverage active surveillance of military and non-military activities at sea using sensing devices such as radars, optronics, automatic Identification Systems (AISs), and IoT, among others. However, deploying a nation-scale MMS imposes great challenges regarding the scalability and cybersecurity of this heterogeneous system. Aiming to address these challenges, this work explores the use of blockchain to leverage MMS cybersecurity and to ensure the integrity, authenticity, and availability of relevant navigation data. We propose a prototype built on a permissioned blockchain solution using HyperLedger Fabric-a robust, modular, and efficient open-source blockchain platform. We evaluate this solution's performance through a practical experiment where the prototype receives sensing data from a Software-Defined-Radio (SDR)-based low-cost AIS receiver built with a Raspberry Pi. In order to reduce scalability attrition, we developed a dockerized blockchain client easily deployed on a large scale. Furthermore, we determined, through extensive experimentation, the client optimal hardware configuration, also aiming to reduce implementation and maintenance costs. The performance results provide a quantitative analysis of the blockchain technology overhead and its impact in terms of Quality of Service (QoS), demonstrating the feasibility and effectiveness of our solution in the scope of an MMS using AIS data.
Margarita Capretto, MartÃn Ceresa, Antonio Fernández Anta, Antonio Russo · 5 authors
Blockchain technologies are facing a scalability challenge, which must be overcome to guarantee a wider adoption of the technology. This scalability issue is mostly caused by the use of consensus algorithms to guarantee the total order of the chain of blocks (and of the operations within each block). However, total order is often overkilling, since important advanced applications of smart-contracts do not require a total order of all the operations. Hence, if a more relaxed partial order (instead of a total order) is allowed under certain safety conditions, a much higher scalability can be achieved. In this paper, we propose a distributed concurrent data type, called Setchain, that allows implementing this partial order and increases significantly blockchain scalability. A Setchain implements a grow-only set object whose elements are not totally ordered, unlike conventional blockchain operations. When convenient, the Setchain allows forcing a synchronization barrier that assigns permanently an epoch number to a subset of the latest elements added. With the Setchain, operations in the same epoch are not ordered, while operations in different epochs are. We present different Byzantine-tolerant implementations of Setchain, prove their correctness and report on an empirical evaluation of a direct implementation. Our results show that Setchain is orders of magnitude faster than consensus-based ledgers to implement grow-only sets with epoch synchronization. Since the Setchain barriers can be synchronized with block consolidation, Setchain objects can be used as a sidechain to implement many smart contract solutions with much faster operations than on basic blockchains.
This dissertation is composed of two main research projects. The first, which was conducted with my adviser Xiaoming Song as a continuation of her work with with her previous student Nathan Anderson-Stahl. In that chapter, we consider a class of general backward stochastic differential equations and backward doubly stochastic differential equations to provide a standard method to prove the existence and uniqueness of the Lp solutions and to obtain the Lp estimates for the solutions. The other project was conducted in collaboration with Josh McGinnis and corresponds to the second chapter in which we provide a physical zero knowledge proof for the popular app game Flow Free. We then show that the methodology can be extended to provide zero knowledge proofs for the related graph problems of the paired many-to-many disjoint covering path problem, the unpaired many-to-many disjoint covering path problem and Hamiltonian cycles.
Eduardo Castelló Ferrer, Ivan Berman, Aleksandr Kapitonov, Vadim Manaenko · 6 authors
The physical autonomy of robots is well understood both theoretically and practically. By contrast, there is almost no research exploring their potential economic autonomy. In this paper, we present the first economically autonomous robot -- a robot able to produce marketable goods while having full control over the use of its generated income. Gaka-chu ("painter" in Japanese) is a 6-axis robot arm that creates paintings of Japanese characters from an autoselected keyword. By using a blockchain-based smart contract, Gaka-chu can autonomously list a painting it made for sale in an online auction. In this transaction, the robot interacts with the human bidders as a peer not as a tool. Using the blockchain-based smart contract, Gaka-chu can then use its income from selling paintings to replenish its resources by autonomously ordering materials from an online art shop. We built the Gaka-chu prototype with an Ethereum-based smart contract and ran a 6-month long experiment, during which the robot created and sold four paintings, simultaneously using its income to purchase supplies and repay initial investors. In this work, we present the results of the experiments conducted and discuss the implications of economically autonomous robots.
In distributed computations and cryptography, it is desirable to record events on a public ledger, such that later alterations are computationally infeasible. An implementation of this idea is called blockchain, which is a distributed protocol that allows the creation of an immutable ledger. While such an idea is very appealing, the ledger may be contaminated with incorrect, illegal, or even dangerous data, and everyone running the blockchain protocol has no option but to store and propagate the unwanted data. The ledger is bloated over time, and it is not possible to remove redundant information. Finally, missing data cannot be inserted later. Redactable blockchains were invented to allow the ledger to be mutated in a controlled manner. To date, redactable blockchains support at most two types of redactions: block modification and removal. The next logical step is to support block insertions. However, we show that this seemingly innocuous enhancement renders all previous constructs insecure. We put forward a model for blockchains supporting all three redaction operations and construct a blockchain that is provably secure under this formal definition.
Blockchain has become one of the most demanding technologies of the decade. Blockchain is a decentralised digital record of information stored in a form of blocks in a chain of blocks called blockchain. It is totally dependent on the addition of new block in its chain. At a single time, there are a number of blocks ready to be added in the blockchain; choosing one valid block from this number of blocks is a complex and most important part of blockchain architecture. As we know that blockchain is a non-centralised system, it has peer-to-peer network in which blocks are added one by one to the chain of blocks only when a consensus is reached amongst the participants of the network. This paper presents a theory summarising of some consensus algorithm used in public, private and consortium blockchain technology along with pros and cons of each algorithms.
Blockchain consensus is a state whereby each node in a network agrees on the current state of the blockchain. Existing protocols achieve consensus via a contest or voting procedure to select one node as a dictator to propose new blocks. However, this procedure can still lead to potential attacks that make consensus harder to achieve or lead to coordination issues if multiple, competing chains (i.e., forks) are created with the potential that an untruthful fork might be selected. We explore the potential for mechanisms to be used to achieve consensus that are triggered when there is a dispute impeding consensus. Using the feature that nodes stake tokens in proof of stake (POS) protocols, we construct revelation mechanisms in which the unique (subgame perfect) equilibrium involves validating nodes propose truthful blocks using only the information that exists amongst all nodes. We construct operationally and computationally simple mechanisms under both Byzantine Fault Tolerance and a Longest Chain Rule, and discuss their robustness to attacks. Our perspective is that the use of simple mechanisms is an unexplored area of blockchain consensus and has the potential to mitigate known trade-offs and enhance scalability.
Christian Cachin, Jovana Mićić, Nathalie Steinhauer, Luca Zanolini
Leader-based protocols for consensus, i.e., atomic broadcast, allow some processes to unilaterally affect the final order of transactions. This has become a problem for blockchain networks and decentralized finance because it facilitates front-running and other attacks. To address this, order fairness for payload messages has been introduced recently as a new safety property for atomic broadcast complementing traditional agreement and liveness. We relate order fairness to the standard validity notions for consensus protocols and highlight some limitations with the existing formalization. Based on this, we introduce a new differential order fairness property that fixes these issues. We also present the quick order-fair atomic broadcast protocol that guarantees payload message delivery in a differentially fair order and is much more efficient than existing order-fair consensus protocols. It works for asynchronous and for eventually synchronous networks with optimal resilience, tolerating corruptions of up to one third of the processes. Previous solutions required there to be less than one fourth of faults. Furthermore, our protocol incurs only quadratic cost, in terms of amortized message complexity per delivered payload.
Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse · 5 authors
Spamming attacks are a serious concern for consensus protocols, as witnessed by recent outages of a major blockchain, Solana. They cause congestion and excessive message delays in a real network due to its bandwidth constraints. In contrast, longest chain (LC), an important family of consensus protocols, has previously only been proven secure assuming an idealized network model in which all messages are delivered within bounded delay. This model-reality mismatch is further aggravated for Proof-of-Stake (PoS) LC where the adversary can spam the network with equivocating blocks. Hence, we extend the network model to capture bandwidth constraints, under which nodes now need to choose carefully which blocks to spend their limited download budget on. To illustrate this point, we show that 'download along the longest header chain', a natural download rule for Proof-of-Work (PoW) LC, is insecure for PoS LC. We propose a simple rule 'download towards the freshest block', formalize two common heuristics 'not downloading equivocations' and 'blocklisting', and prove in a unified framework that PoS LC with any one of these download rules is secure in bandwidth-constrained networks. In experiments, we validate our claims and showcase the behavior of these download rules under attack. By composing multiple instances of a PoS LC protocol with a suitable download rule in parallel, we obtain a PoS consensus protocol that achieves a constant fraction of the network's throughput limit even under worst-case adversarial strategies.