On the round complexity of randomized Byzantine agreement

DOI10.1007/S00145-022-09421-7zbMATH Open1489.94092arXiv1907.11329OpenAlexW4214936143MaRDI QIDQ2121502FDOQ2121502

Authors: Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, Alex Samorodnitsky 

Publication date: 4 April 2022

Published in: Journal of Cryptology (Search for Journal in Brave)

Abstract: We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that: (1) BA protocols resilient against $n/3$ [resp., $n/4$] corruptions terminate (under attack) at the end of the first round with probability at most $o(1)$ [resp., $1/2+o(1)$]. (2) BA protocols resilient against a fraction of corruptions greater than $1/4$ terminate at the end of the second round with probability at most $1-Theta(1)$. (3) For a large class of protocols (including all BA protocols used in practice) and under a plausible combinatorial conjecture, BA protocols resilient against a fraction of corruptions greater than $1/3$ [resp., $1/4$] terminate at the end of the second round with probability at most $o(1)$ [resp., $1/2+o(1)$]. The above bounds hold even when the parties use a trusted setup phase, e.g., a public-key infrastructure (PKI). The third bound essentially matches the recent protocol of Micali (ITCS'17) that tolerates up to $n/3$ corruptions and terminates at the end of the third round with constant probability.

Full work available at URL: https://arxiv.org/abs/1907.11329

Recommendations

• On the round complexity of randomized Byzantine agreement
• On the round complexity of Byzantine agreement without initial set-up
• An O (log n ) expected rounds randomized byzantine generals protocol
• Round-optimal Byzantine agreement
• On expected constant-round protocols for Byzantine agreement
• On Expected Constant-Round Protocols for Byzantine Agreement
• Byzantine agreement in the full-information model in \(O(\log n)\) rounds
• Byzantine agreement in polynomial expected time (extended abstract)
• Byzantine Agreement in Expected Polynomial Time

zbMATH Keywords

lower boundByzantine agreementround complexity

Mathematics Subject Classification ID

Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Cites Work

• Analysis of Boolean Functions
• Boolean functions with low average sensitivity depend on few coordinates
• A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
• Title not available (Why is that?)
• Authenticated Algorithms for Byzantine Agreement
• Early stopping in Byzantine agreement
• Reaching Agreement in the Presence of Faults
• The Byzantine Generals Problem
• Title not available (Why is that?)
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• A lower bound for the time to assure interactive consistency
• Automatically increasing the fault-tolerance of distributed algorithms
• Easy impossibility proofs for distributed consensus problems
• Unconditional Byzantine agreement for any number of faulty processors (extended abstract)
• On reverse hypercontractivity
• Fully polynomial Byzantine agreement in t + 1 rounds
• Tight bounds for asynchronous randomized consensus
• Lower bounds for randomized consensus under a weak adversary
• An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
• New techniques for noninteractive zero-knowledge
• Simple constant-time consensus protocols in realistic failure models
• Adaptively secure coin-flipping, revisited
• On Expected Constant-Round Protocols for Byzantine Agreement
• A tight lower bound for randomized synchronous consensus
• Byzantine agreement in the full-information model in \(O(\log n)\) rounds
• Efficient player-optimal protocols for strong and differential consensus
• The contest between simplicity and efficiency in asynchronous Byzantine agreement
• On the composition of authenticated Byzantine Agreement
• Title not available (Why is that?)
• Byzantine agreement in polynomial expected time (extended abstract)
• Fault-tolerant Computation in the Full Information Model
• Thunderella: blockchains with optimistic instant confirmation
• Probabilistic Termination and Composability of Cryptographic Protocols
• Round-preserving parallel composition of probabilistic-termination cryptographic protocols
• On the round complexity of randomized Byzantine agreement
• Synchronous Byzantine agreement with expected \(O(1)\) rounds, expected \(O(n^2)\) communication, and optimal resilience
• On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement
• Communication Complexity of Byzantine Agreement, Revisited
• Verifiable random functions from standard assumptions
• Hybrid consensus: efficient consensus in the permissionless model

Cited In (12)

• Byzantine Agreement in Expected Polynomial Time
• From Almost Everywhere to Everywhere: Byzantine Agreement with $\tilde{O}(n^{3/2})$ Bits
• A tradeoff between safety and liveness for randomized coordinated attack protocols
• Concurrent asynchronous Byzantine agreement in expected-constant rounds, revisited
• Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds
• On the round complexity of randomized Byzantine agreement
• Sublinear-round Byzantine agreement under corrupt majority
• Round-optimal Byzantine agreement
• The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols
• Round efficient Byzantine agreement from VDFs
• Byzantine agreement in the full-information model in \(O(\log n)\) rounds
• How Byzantine is a send corruption?

This page was built for publication: On the round complexity of randomized Byzantine agreement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2121502)