Welcome to the resource topic for 2025/143
Title:
A New Way to Achieve Round-Efficient Asynchronous Byzantine Agreement
Authors: Simon Holmgaard Kamp
Abstract:We translate the expand-and-extract framework by Fitzi, Liu-Zhang, and Loss (PODC 21) to the asynchronous setting.
While they use it to obtain a synchronous BA with 2^{-\lambda} error probability in \lambda+1 rounds, we make it work in asynchrony in \lambda+3 rounds. At the heart of their solution is a generalization of crusader agreement and graded agreement to any number of grades called proxcensus. They achieve graded consensus with 2^r+1 grades in r rounds by reducing proxcensus with 2s-1 grades to proxcensus with s grades in one round. The expand-and-extract paradigm uses proxcensus to expand binary inputs to 2^\lambda+1 grades in \lambda rounds before extracting a binary output by partitioning the grades using a \lambda bit common coin. However, the proxcensus protocol by Fitzi et al. does not translate to the asynchronous setting without lowering the corruption threshold or using more rounds in each recursive step.
This is resolved by attaching justifiers to all messages: forcing the adversary to choose between being ignored by the honest parties, or sending messages with certain validity properties. Using these we define validated proxcensus and show that it can be instantiated in asynchrony with the same recursive structure and round complexity as synchronous proxcensus. In asynchrony the extraction phase incurs a security loss of one bit which is recovered by expanding to twice as many grades using an extra round of communication. This results in a \lambda+2 round VABA and a \lambda+3 round BA, both with 2^{-\lambda} error probability and communication complexity matching Fitzi et al.
ePrint: https://eprint.iacr.org/2025/143
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .