Jordan Beason, Gregory Hurlock, Dongbin Kim, Pratheek Manjunath
Unmanned vehicles have continued to become commonplace in modern society, with the recent adoption of small unmanned aerial systems (sUAS) in the commercial, entertainment and defense industries. Despite encouraging trends in sUAS and unmanned systems (UxS) development, these technologies deployed in the field are still, in large part, limited to teleoperation and/or semi-autonomous behaviors of a single agent. The United States Department of Defense (DoD) is interested in elevating this current state of technology, specifically of aerial swarms for intelligence, surveillance, and reconnaissance (ISR) missions. While methods exist for optimal control of multi-agent systems, there remain novel research gaps related to robust field performance. The Robotics Research Center (RRC) at the United States Military Academy (USMA) is working to develop a collaborative aerial swarming architecture (CASA) that enables decentralized command and control (C2) between unmanned aerial systems (UAS). The main factors that support CASA’s decentralized capabilities are found in the dynamic allocation of tasks and the organization of data among sUAS platforms. This paper outlines CASA and its current capabilities. Task Allocation results are presented showing real-time task updates and allocation to a UAS swarm in a simulated environment.
Fuzzing is one of the major techniques for uncovering vulnerabilities in smart contracts. The effectiveness of fuzzing is significantly affected by its throughput but unfortunately existing fuzzers for smart contracts have low throughput due to the slow execution of EVM, the delay introduced by the consensus protocols, the limited parallelization capability of CPUs, and the overhead caused by the instrumented EVM. To tackle this critical issue, in this paper, we take the first step to leverage GPU’s parallel computing power to boost the throughput of smart contract fuzzing. More precisely, by converting the fuzzing workload to a SIMD task, we can activate thousands of GPU cores to test the smart contract simultaneously. To achieve this purpose, we design new solutions to address three major challenges, namely developing incremental storage to reduce GPU memory cost, proposing a stateful bitmap to embed transaction dependency to the feedback metric, and designing a parallel feedback algorithm to rule out undesired seeds that cause redundant overlaps. We implement a prototype named Mau, which first transforms the bytecode of a smart contract to a SIMD application in PTX assembly and then runs it parallelly on the GPU. We evaluate Mau using both a large and small benchmark. The experimental results demonstrate that the throughput of Mau reaches 162.37K execs/sec and 328.06K execs/sec, which leads to an 8.69-15.38X improvement to the state-of-the-art tool. Moreover, the high throughput empowers Mau to detect 1.01-2.50X more bugs and obtain 1.03–4.71X more code coverage than baselines.
Blockchain technology has become a research hotspot in distributed systems, aiming to sustain a decentralized ledger via consensus. Traditional consensus solutions exhibit slow processing speed and response time, resulting in poor performance. To address this issue, several consensus protocols have been proposed. One such popular protocol is HotStuff, a Byzantine fault-tolerant consensus (BFT) that achieves high throughput at the cost of latency. However, its throughput suffers from a proportional decrease with the increase in latency, posing a significant challenge. In this paper, we propose a new protocol called Dolphin that builds upon HotStuff. It operates in a partially synchronous network with$n$replicas, up to$f$byzantine faults, where$n \ge 3f+1$, and achieves higher throughput in high-latency environments by leveraging non-blocking concurrent block generation. Specifically, we formalize our strategy as a generic Asynchronization Procedure Patch and prove that it does not affect the execution process of the original protocol. Theoretical analysis validates that Dolphin preserves the safety, liveness, and responsiveness properties while enhancing the throughput. The evaluation demonstrates that Dolphin typically achieves more than 10x higher throughput in Wide Area Network (WAN) environments with lower latency compared to HotStuff and its variants, and exhibits similar bandwidth utilization to DAG-based protocols such as Narwhal.
Zero-knowledge proofs (ZKPs) are computationally demanding to generate. Their importance for applications like ZK-Rollups has prompted some to outsource ZKP generation to a market of specialized provers. However, existing market designs either do not fit the ZKP setting or lack formal description and analysis. In this work, we propose a formal ZKP market model that captures the interactions between users submitting ZKP tasks and provers competing to generate proofs. Building on this model, we introduce $Prooφ$, an auction-based ZKP market mechanism. We prove that $Prooφ$ is incentive compatible for users and provers, and budget balanced. We augment $Prooφ$ with system-level designs to address the practical challenges of our setting, such as Sybil attacks, misreporting of prover capacity, and collusion. We analyze our system-level designs and show how they can mitigate the various security concerns.
The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.
We construct perfect zero-knowledge probabilistically checkable proofs (PZK-PCPs) for every language in #P. This is the first construction of a PZK-PCP for any language outside BPP. Furthermore, unlike previous constructions of (statistical) zero-knowledge PCPs, our construction simultaneously achieves non-adaptivity and zero knowledge against arbitrary (adaptive) polynomial-time malicious verifiers. Our construction consists of a novel masked sumcheck PCP, which uses the combinatorial nullstellen- satz to obtain antisymmetric structure within the hypercube and randomness outside of it. To prove zero knowledge, we introduce the notion of locally simulatable encodings: randomised encodings in which every local view of the encoding can be efficiently sampled given a local view of the message. We show that the code arising from the sumcheck protocol (the Reed–Muller code augmented with subcube sums) admits a locally simulatable encoding. This reduces the algebraic problem of simulating our masked sumcheck to a combinatorial property of antisymmetric functions.
In a Blockchain network the Certificate Authority (CA) is a vital component. The decentralization feature of the blockchain enables the network to have different CA for different transaction. The CA selection process is executed every time with each new transaction. This process is fine with small size network. However, if the network size increases this selection process can take numerous amounts of time, as the algorithm chosen to select the CA needs to search in entire network which increases the computational time and overhead of the network. If this search space can be decreases then, the resulting computational time and overhead can be decreased. The search space can be reduced by implementing the Agglomerative clustering technique. Each cluster is identified by a cluster index (CV) the average of the response time (R) and Validation Time (V). The nodes want to initiate transaction needs to select a appropriate cluster by entering a target budget (TB). The cluster having the CV less than TB is selected and then, Proof of Stake (PoS) consensus mechanism is applied to select the CA. Finally, the proposed model is evaluated over gas utilization, response time and validation time comparison.
The core of a blockchain network is its consensus algorithm. Starting with the Proof-of-Work, there have been various versions of consensus algorithms, such as Proof-of-Stake (PoS), Proof-of-Authority (PoA), and Practical Byzantine Fault Tolerance (PBFT). Each of these algorithms focuses on different aspects to ensure efficient and reliable processing of transactions. Blockchain operates in a decentralized manner where there is no central authority and the network is composed of diverse users. This openness creates the potential for malicious nodes to disrupt the network in various ways. Therefore, it is crucial to embed a mechanism within the blockchain network to constantly monitor, identify, and eliminate these malicious nodes. However, there is no one-size-fits-all mechanism to identify all malicious nodes. Hence, the dynamic adaptability of the blockchain network is important to maintain security and reliability at all times. This paper introduces MRL-PoS, a Proof-of-Stake consensus algorithm based on multi-agent reinforcement learning. MRL-PoS employs reinforcement learning for dynamically adjusting to the behavior of all users. It incorporates a system of rewards and penalties to eliminate malicious nodes and incentivize honest ones. Additionally, MRL-PoS has the capability to learn and respond to new malicious tactics by continually training its agents.
A growing number of products use layer 2 solutions to expand the capabilities of primary blockchains like Ethereum, where computation is off-loaded from the root chain, and the results are published to it in bulk. Those include optimistic and zero-knowledge rollups, information oracles, and app-specific chains. This work presents an analysis of layer 2 blockchain strategies determining the optimal times for publishing transactions on the root chain. There is a trade-off between waiting for a better layer 1 gas price and the urgency to finalize layer 2 transactions. We present a model for the problem that captures this trade-off, generalizing previous works, and we analyze the properties of optimal publishing strategies. We show that such optimal strategies hold a computable simple form for a large class of cost functions.
Robot swarms are generally considered to be composed of cooperative agents that, despite their limited individual capabilities, can perform difficult tasks by working together. However, in open swarms, where different robots can be added to the swarm by different parties with potentially competing interests, cooperation is but one of many strategies. We envision an information market where robots can buy and sell information through transactions stored on a distributed blockchain, and where cooperation is encouraged by the economy itself. As a proof of concept, we study a classical foraging task, where exchanging information with other robots is paramount to accomplish the task efficiently. We illustrate that even a single robot that lies to others-a so-called Byzantine robot-can heavily disrupt the swarm. Hence, we devise two protection mechanisms. Through an individual-level protection mechanism, robots are more sceptical about others' information and can detect and discard Byzantine information, at the cost of lower efficiency. Through a systemic protection mechanism based on economic rules regulating robot interactions, robots that sell honest information acquire over time more wealth than Byzantines selling false information. Our simulations show that a well-designed robot economy penalises misinformation spreading and protects the swarm from Byzantine behaviour. We believe economics-inspired swarm robotics is a promising research direction that exploits the timely opportunity for decentralised economies offered by blockchain technology.
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.
Finding efficient signature schemes based on coding theory is an important issue for post-quantum cryptography. One can build signature schemes based on zero-knowledge proofs using the Stern protocol and its variants as demonstrated both in Hamming metric [1], [2] and rank metric [3], [4]. These constructions feature a high soundness error hence have a rather large signature size. Recently, some techniques based on secure Multi-Party Computation (MPC) have made it possible to lower this soundness error thus resulting in smaller signatures in both Hamming metric [5], [6] and rank metric [7], [8]. Even more recently, a hypercube-based approach has improved the Hamming metric approach [9]. In this paper, we adapt the idea of [9] to rank metric using the protocol from [8]. Given a fixed number of parties, this hypercube-based approach improves the performances of the underlying scheme. It is thus possible to consider additional trade-offs between sizes and performances thus reducing the signature size up to 4.5kB by increasing the number of parties of the MPC protocol.
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.
In this paper, a trusted multi-task distribution mechanism for Internet of Vehicles based on smart contract is proposed to improve the security and efficiency for the task distribution in Internet of Vehicles. Firstly, a three-tier trusted multi-task distribution framework is presented based on smart contract. The smart contract will be triggered by the task request. As the important part of the smart contract, the task distribution algorithm is stored on the blockchain and run automatically. In the process of the task distribution, the cost of the task distribution and the system stability play a critical role. Therefore, the task distribution problem is formulated to minimize the cost of the task distribution whilst maintaining the stability of the system based on Lyapunov theorem. Unfortunately, this problem is a mixed integer nonlinear programming problem with NP-hard characteristics. To tackle this, the optimization problem is decomposed into two sub problems of computing resource allocation and task distribution decision, and an effective task distribution algorithm is proposed. Simulation results show that the proposed algorithm can effectively improves system performance.
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.
Blockchain being a decentralised, distributed ledger, has attracted industries to implement the solutions on blockchain. The transactions are agreed in a deterministic manner because of the availability of consensus algorithms. The state of the machine is concluded based on the agreement generated by the consensus algorithm. The performance of the blockchain system can be increased to the order of magnitude when the right consensus is used. In this paper, the limitations and performance of various consensus algorithms have been reviewed along with the characteristics of the same. In addition to that, this paper compares the consensus algorithms based on various parameters such as speed, double-spending, 51% attack and many more.
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.