Sublinear-round Byzantine agreement under corrupt majority
Byzantine agreement (BA) deals with the problem of reaching consensus in a network in the presence of faulty (and malicious) nodes. In particular, the system reaches a BA when the following conditions are satisfied: \par 1.) all honest nodes agree on the same outcome, \par 2.) all honest nodes agree on the sender's output if the sender is honest. It is known that when the number \(t\) of faulty nodes is larger than one third of the total number of nodes the BA is not possible. Nonetheless, it is possible to have an arbitrary number of faulty nodes \(t < n\), provided that an additional setup is considered and that the protocol features \(t+1\) rounds. It is also known that, although \(t+1\) is the optimal bound in the deterministic setting, randomized protocols can run in expected constant rounds when the majority of the nodes is honest, i.e.\ when \(t< n/2\). The present paper deals with the corresponding problem in the absence of an honest majority. Precisely, the authors wonder if ``randomized protocols [can] help to overcome the \((t+1)\)-round complexity lower bound when the majority of nodes can be corrupt. The only previous results in the sense of sub-linear round complexity are related to the case when \(t=n/2+o(n)\). The authors prove here (see Theorem 1) that, under some cryptographic assumptions in the setting of a public-key infrastructure, \(t\) can be of the form \(t= (1-\varepsilon)n\) for some \(\varepsilon > 0\), provided that a specified number of rounds is considered. For the entire collection see [Zbl 1481.94004].
- Adaptively secure broadcast
- Adaptively secure broadcast, revisited
- Algorand: a secure and efficient distributed ledger
- An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
- Authenticated Algorithms for Byzantine Agreement
- Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary
- Communication Complexity of Byzantine Agreement, Revisited
- Fast asynchronous Byzantine agreement and leader election with full information
- Fast Byzantine agreement
- Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs
- New techniques for noninteractive zero-knowledge
- On expected constant-round protocols for Byzantine agreement
- On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement
- On the round complexity of randomized Byzantine agreement
- Ouroboros: a provably secure proof-of-stake blockchain protocol
- Probabilistic Termination and Composability of Cryptographic Protocols
- Scalable leader election
- Simple constant-time consensus protocols in realistic failure models
- Sublinear-round Byzantine agreement under corrupt majority
- Synchronous Byzantine agreement with expected \(O(1)\) rounds, expected \(O(n^2)\) communication, and optimal resilience
- The Byzantine Generals Problem
- Sublinear-round Byzantine agreement under corrupt majority
- Expected constant round Byzantine broadcast under dishonest majority
- How Byzantine is a send corruption?
- Round-optimal Byzantine agreement
- Byzantine agreement in the full-information model in O( n) rounds
- Efficient Byzantine Agreement with Faulty Minority
- scientific article; zbMATH DE number 176512 (Why is no real title available?)
- Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party
- Gossiping for communication-efficient broadcast
- Efficient adaptively-secure Byzantine agreement for long messages
- Completeness theorems for adaptively secure broadcast
- Network-agnostic security comes (almost) for free in DKG and MPC
- Zombies and ghosts: optimal Byzantine agreement in the presence of omission faults
- Concurrent asynchronous Byzantine agreement in expected-constant rounds, revisited
- Early stopping for any number of corruptions
- Sublinear message bounds of authenticated implicit Byzantine agreement
- Nearly optimal parallel broadcast in the plain public key model
- Expected constant round Byzantine broadcast under dishonest majority
- All Byzantine agreement problems are expensive
- DARE to agree: Byzantine agreement with optimal resilience and adaptive communication
- Communication lower bounds for cryptographic broadcast protocols
- Round-optimal Byzantine agreement without trusted setup
This page was built for publication: Sublinear-round Byzantine agreement under corrupt majority
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2055693)
