Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCommunication Complexity of Byzantine Agreement, Revisited
63
0
0.0
(
0
)
Added by
T-H. Hubert Chan
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an {it adaptive} adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary {it cannot erase the message that was already sent} --- henceforth we say that such an adversary cannot perform after-the-fact removal. By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieves near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.
rate research
Read More
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.
In this paper we address Approximate Agreement problem in the Mobile Byzantine faults model. Our contribution is threefold. First, we propose the the first mapping from the existing variants of Mobile Byzantine models to the Mixed-Mode faults model.This mapping further help us to prove the correctness of class MSR (Mean-Subsequence-Reduce) Approximate Agreement algorithms in the Mobile Byzantine fault model, and is of independent interest. Secondly, we prove lower bounds for solving Approximate Agreement under all existing Mobile Byzantine faults models. Interestingly, these lower bounds are different from the static bounds. Finally, we propose matching upper bounds. Our paper is the first to link the Mobile Byzantine Faults models and the Mixed-Mode Faults models, and we advocate that a similar approach can be adopted in order to prove the correctness of other classical distributed building blocks (e.g. agreement, clock synchronization, interactive consistency etc) under Mobile Byzantine Faults model.
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.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
