Sublinear-round Byzantine agreement under corrupt majority
type: Item
instance of: scholarly article
title: Sublinear-round Byzantine agreement under corrupt majority
zbMATH Open document ID: 1482.94044
DOI: 10.1007/978-3-030-45388-6_9
author: T.-H. Hubert Chan
author: Rafael Pass
author: Elaine Shi
publication date: 2021-12-01T00:00:00Z
review text: 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].
reviewed by: Roberto Civino
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 7436974
zbMATH Keywords: Byzantine agreement
zbMATH Keywords: sub-linear round complexity
zbMATH Keywords: corrupt majority
MaRDI profile type: Publication
full work available at URL: 978-3-030-45388-6 9
OpenAlex ID: W3022867264
cites work: Communication Complexity of Byzantine Agreement, Revisited
cites work: Synchronous Byzantine agreement with expected \(O(1)\) rounds, expected \(O(n^2)\) communication, and optimal resilience
cites work: Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs
cites work: Fast byzantine agreement
cites work: Algorand: a secure and efficient distributed ledger
cites work: Simple constant-time consensus protocols in realistic failure models
cites work: Probabilistic Termination and Composability of Cryptographic Protocols
cites work: Authenticated Algorithms for Byzantine Agreement
cites work: An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
cites work: On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement
cites work: Adaptively secure broadcast, revisited
cites work: New Techniques for Noninteractive Zero-Knowledge
cites work: Adaptively Secure Broadcast
cites work: Fast asynchronous Byzantine agreement and leader election with full information
cites work: On expected constant-round protocols for Byzantine agreement
cites work: Ouroboros: a provably secure proof-of-stake blockchain protocol
cites work: Breaking the O ( n 2 ) bit barrier
cites work: Scalable leader election
cites work: The Byzantine Generals Problem
cites work: On the round complexity of randomized Byzantine agreement
description: scientific article; zbMATH DE number 7436974