This paper presents a novel leaderless protocol (FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures) with a low communicational complexity and which allows a set of nodes to come to a consensus on a value of a single bit. The paper makes the assumption that part of the nodes are , and are thus controlled by an adversary who intends to either delay the consensus, or break it. This defines that at least a couple of honest nodes come to different conclusions. We prove that, nevertheless, the protocol works with high probability when its parameters are suitably chosen. Along this the paper also provides explicit estimates on the probability that the protocol finalizes in the consensus state in a given time. This protocol could be applied to reaching consensus in decentralized cryptocurrency systems. A special feature of it is that it makes use of a sequence of random numbers which are either provided by a trusted source or generated by the nodes themselves using some decentralized random number generating protocol. This increases the overall trustworthiness of the infrastructure. A core contribution of the paper is that it uses a consensus to obtain a consensus on the value of a bit, and which can relate to the validity of a transaction.
A good deal of work focuses on failures within a network infrastructure, rather than on malicious agents. The work of Liu @cite_16 defines FastBFT, and which is a fast and scalable BFT (Byzantine fault tolerance) protocol. Within this, the work integrates trusted execution environments (TEEs) with lightweight secret sharing, and results in a low latency infrastructure. @cite_12 define Democratic Byzantine Fault Tolerance (DBFT) and which is a leaderless Byzantine consensus. This provides a robust infrastructure where there is a failure in the leader of the consensus network. The core contribution is that nodes will process message whenever they receive them, instead of waiting for a co-ordinate to confirm messages. Another Byzantine Fault Tolerant method which does not require a leader node is Honey Badger @cite_18 . This method is asynchronous in its scope and can cope with corrupted nodes. Unfortunately, it does not actually make any commitments around the timing of the delivery of a message, and where even if Eve controls the scheduling of messages, there will be no impact on the overall consensus.
@cite_18 @cite_16 @cite_12
2902905458 2584120063 2114579022 1780011259
This paper introduces a new leaderless Byzantine consensus called the Democratic Byzantine Fault Tolerance (DBFT) for blockchains. While most blockchain consensus protocols rely on a correct leader or coordinator to terminate, our algorithm can terminate even when its coordinator is faulty. The key idea is to allow processes to complete asynchronous rounds as soon as they receive a threshold of messages, instead of having to wait for a message from a coordinator that may be slow. The resulting decentralization is particularly appealing for blockchains for two reasons: (i) each node plays a similar role in the execution of the consensus, hence making the decision inherently “democratic” (ii) decentralization avoids bottlenecks by balancing the load, making the solution scalable. DBFT is deterministic, assumes partial synchrony, is resilience optimal, time optimal and does not need signatures. We first present a simple safe binary Byzantine consensus algorithm, modify it to ensure termination, and finally present an optimized reduction from multivalue consensus to binary consensus whose fast path terminates in 4 message delays. The surging interest in blockchain technology has revitalized the search for effective Byzantine consensus schemes. In particular, the blockchain community has been looking for ways to effectively integrate traditional Byzantine fault-tolerant (BFT) protocols into a blockchain consensus layer allowing various financial institutions to securely agree on the order of transactions. However, existing BFT protocols can only scale to tens of nodes due to their @math message complexity. In this paper, we propose FastBFT, a fast and scalable BFT protocol. At the heart of FastBFT is a novel message aggregation technique that combines hardware-based trusted execution environments (TEEs) with lightweight secret sharing. Combining this technique with several other optimizations (i.e., optimistic execution, tree topology and failure detection), FastBFT achieves low latency and high throughput even for large scale networks. Via systematic analysis and experiments, we demonstrate that FastBFT has better scalability and performance than previous BFT protocols. Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions and they can cause arbitrary behavior, that is, Byzantine faults. This article describes a new replication algorithm, BFT, that can be used to build highly available systems that tolerate Byzantine faults. BFT can be used in practice to implement real services: it performs well, it is safe in asynchronous environments such as the Internet, it incorporates mechanisms to defend against Byzantine-faulty clients, and it recovers replicas proactively. The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1 3 of the replicas become faulty within a small window of vulnerability. BFT has been implemented as a generic program library with a simple interface. We used the library to implement the first Byzantine-fault-tolerant NFS file system, BFS. The BFT library and BFS perform well because the library incorporates several important optimizations, the most important of which is the use of symmetric cryptography to authenticate messages. The performance results show that BFS performs 2p faster to 24p slower than production implementations of the NFS protocol that are not replicated. This supports our claim that the BFT library can be used to build practical systems that tolerate Byzantine faults. This paper investigates the task solvability of mobile robot systems subject to Byzantine faults. We first consider the gathering problem, which requires all robots to meet in finite time at a non-predefined location. It is known that the solvability of Byzantine gathering strongly depends on a number of system attributes, such as synchrony, the number of Byzantine robots, scheduling strategy, obliviousness, orientation of local coordinate systems and so on. However, the complete characterization of the attributes making Byzantine gathering solvable still remains open. In this paper, we show strong impossibility results of Byzantine gathering. Namely, we prove that Byzantine gathering is impossible even if we assume one Byzantine fault, an atomic execution system, the n-bounded centralized scheduler, non-oblivious robots, instantaneous movements and a common orientation of local coordinate systems (where n denote the number of correct robots). Those hypotheses are much weaker than used in previous work, inducing a much stronger impossibility result. At the core of our impossibility result is a reduction from the distributed consensus problem in asynchronous shared-memory systems. In more details, we newly construct a generic reduction scheme based on the distributed BG-simulation. Interestingly, because of its versatility, we can easily extend our impossibility result for general pattern formation problems.