Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMultidimensional Byzantine Agreement in a Synchronous Setting
70
0
0.0
(
0
)
Added by
Andrea Flamini
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper we will present the Multidimensional Byzantine Agreement (MBA) Protocol, a leaderless Byzantine agreement protocol defined for complete and synchronous networks that allows a network of nodes to reach consensus on a vector of relevant information regarding a set of observed events. The consensus process is carried out in parallel on each component, and the output is a vector whose components are either values with wide agreement in the network (even if no individual node agrees on every value) or a special value $bot$ that signals irreconcilable disagreement. The MBA Protocol is probabilistic and its execution halts with probability 1, and the number of steps necessary to halt follows a Bernoulli-like distribution. The design combines a Multidimensional Graded Consensus and a Multidimensional Binary Byzantine Agreement, the generalization to the multidimensional case of two protocols by Micali and Feldman. We prove the correctness and security of the protocol assuming a synchronous network where less than a third of the nodes are malicious.
rate research
Read More
In this paper we extend the Multidimensional Byzantine Agreement (MBA) Protocol arXiv:2105.13487v2, a leaderless Byzantine agreement for vectors of arbitrary values, into the emph{Cob} protocol, that works in Asynchronous Gossiping (AG) networks. This generalization allows the consensus process to be run by an incomplete network of nodes provided with (non-synchronized) same-speed clocks. Not all nodes are active in every step, so the network size does not hamper the efficiency, as long as the gossiping broadcast delivers the messages to every node in reasonable time. These network assumptions model more closely real-life communication channels, so the Cob protocol may be applicable to a variety of practical problems, such as blockchain platforms implementing sharding. The Cob protocol has the same Bernoulli-like distribution that upper bounds the number of steps required as the MBA protocol, and we prove its correctness and security assuming a supermajority of honest nodes in the network.
We present new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The celebrated PBFT state machine replication protocol tolerates $f$ Byzantine faults in an asynchronous setting using $3f+1$ replicas, and has since been studied or deployed by numerous works. In this work, we improve the Byzantine fault tolerance threshold to $n=2f+1$ by utilizing a relaxed synchrony assumption. We present a synchronous state machine replication protocol that commits a decision every 3 rounds in the common case. The key challenge is to ensure quorum intersection at one honest replica. Our solution is to rely on the synchrony assumption to form a post-commit quorum of size $2f+1$, which intersects at $f+1$ replicas with any pre-commit quorums of size $f+1$. Our protocol also solves synchronous authenticated Byzantine agreement in expected 8 rounds. The best previous solution (Katz and Koo, 2006) requires expected 24 rounds. Our protocols may be applied to build Byzantine fault tolerant systems or improve cryptographic protocols such as cryptocurrencies when synchrony can be assumed.
In the Lattice Agreement (LA) problem, originally proposed by Attiya et al. cite{Attiya:1995}, a set of processes has to decide on a chain of a lattice. More precisely, each correct process proposes an element $e$ of a certain join-semi lattice $L$ and it has to decide on a value that contains $e$. Moreover, any pair $p_i,p_j$ of correct processes has to decide two values $dec_i$ and $dec_j$ that are comparable (e.g., $dec_i leq dec_j$ or $dec_j < dec_i$). LA has been studied for its practical applications, as example it can be used to implement a snapshot objects cite{Attiya:1995} or a replicated state machine with commutative operations cite{Faleiro:2012}. Interestingly, the study of the Byzantine Lattice Agreement started only recently, and it has been mainly devoted to asynchronous systems. The synchronous case has been object of a recent pre-print cite{Zheng:aa} where Zheng et al. propose an algorithm terminating in ${cal O}(sqrt f)$ rounds and tolerating $f < lceil n/3 rceil$ Byzantine processes. In this paper we present new contributions for the synchronous case. We investigate the problem in the usual message passing model for a system of $n$ processes with distinct unique IDs. We first prove that, when only authenticated channels are available, the problem cannot be solved if $f=n/3$ or more processes are Byzantine. We then propose a novel algorithm that works in a synchronous system model with signatures (i.e., the {em authenticated message} model), tolerates up to $f$ byzantine failures (where $f<n/3$) and that terminates in ${cal O}(log f)$ rounds. We discuss how to remove authenticated messages at the price of algorithm resiliency ($f < n/4$). Finally, we present a transformer that converts any synchronous LA algorithm to an algorithm for synchronous Generalised Lattice Agreement.
Consider a distributed system with $n$ processors out of which $f$ can be Byzantine faulty. In the approximate agreement task, each processor $i$ receives an input value $x_i$ and has to decide on an output value $y_i$ such that - the output values are in the convex hull of the non-faulty processors input values, - the output values are within distance $d$ of each other. Classically, the values are assumed to be from an $m$-dimensional Euclidean space, where $m ge 1$. In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph $G$ and the goal is to output vertices that are within distance $d$ of each other in $G$, but still remain in the graph-induced convex hull of the input values. For $d=0$, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any $d ge 1$, we show that the task is solvable in asynchronous systems when $G$ is chordal and $n > (omega+1)f$, where $omega$ is the clique number of~$G$. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures.
Consensus protocols have traditionally been studied in a setting where all participants are known to each other from the start of the protocol execution. In the parlance of the blockchain literature, this is referred to as the permissioned setting. What differentiates Bitcoin from these previously studied protocols is that it operates in a permissionless setting, i.e. it is a protocol for establishing consensus over an unknown network of participants that anybody can join, with as many identities as they like in any role. The arrival of this new form of protocol brings with it many questions. Beyond Bitcoin, what can we prove about permissionless protocols in a general sense? How does recent work on permissionless protocols in the blockchain literature relate to the well-developed history of research on permissioned protocols in distributed computing? To answer these questions, we describe a formal framework for the analysis of both permissioned and permissionless systems. Our framework allows for apples-to-apples comparisons between different categories of protocols and, in turn, the development of theory to formally discuss their relative merits. A major benefit of the framework is that it facilitates the application of a rich history of proofs and techniques in distributed computing to problems in blockchain and the study of permissionless systems. Within our framework, we then address the questions above. We consider the Byzantine Generals Problem as a formalisation of the problem of reaching consensus, and address a programme of research that asks, Under what adversarial conditions, and for what types of permissionless protocol, is consensus possible? We prove a number of results for this programme, our main result being that deterministic consensus is not possible for decentralised permissionless protocols. To close, we give a list of eight open questions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
