Paper 2021/814
A New Way to Achieve Round-Efficient Byzantine Agreement
Matthias Fitzi, Chen-Da Liu-Zhang, and Julian Loss
Abstract
Minimizing the round complexity of Byzantine Agreement (BA) protocols is a
fundamental problem in distributed computing.
The typical approach to achieve round efficient (randomized) BA
is to have a weak form of BA, called graded consensus (GC), followed by a
distributed coin, and to repeat this process until some termination condition is
met---as introduced by Feldman and Micali (STOC'88).
In this work, we revisit the question of building BA from GC, or, more precisely,
from generalizations of GC.
Concretely, for Monte Carlo style BA, where the protocol is run for a fixed
number of rounds in function of the security parameter (in contrast
to protocols with probabilistic termination),
we demonstrate that this generalization helps to considerably reduce the round
complexity of BA.
In particular, assuming a setup for threshold signatures among the parties and
corruption threshold
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. PODC'21
- Keywords
- byzantine agreementround efficiencyproxcensus
- Contact author(s)
-
matthias fitzi @ iohk io
lichen @ inf ethz ch
lossjulian @ gmail com - History
- 2021-06-16: received
- Short URL
- https://ia.cr/2021/814
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/814, author = {Matthias Fitzi and Chen-Da Liu-Zhang and Julian Loss}, title = {A New Way to Achieve Round-Efficient Byzantine Agreement}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/814}, year = {2021}, url = {https://eprint.iacr.org/2021/814} }