Welcome to the resource topic for 2024/1682
Title:
Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience
Authors: Jovan Komatovic, Joachim Neu, Tim Roughgarden
Abstract:Multi-valued validated Byzantine agreement (MVBA), a fundamental primitive of distributed computing, enables n processes to agree on a valid \ell-bit value, despite t faulty processes behaving arbitrarily. Among hash-based protocols for the asynchronous setting with adaptive faults, the state-of-the-art HMVBA protocol
has optimal O(1) time complexity and near-optimal O(n \ell + n^2 \kappa \log n) bit complexity, but tolerates only t < n/5 faults. We present REDUCER, an MVBA protocol that matches HMVBA’s time and bit complexity and improves resilience to t < n/4. Like HMVBA, REDUCER relies solely on collision-resistant hash functions. Toward optimal one-third resilience, we also propose REDUCER++, an MVBA protocol
with further improved t < (1/3 - \epsilon)n resilience, for any fixed \epsilon > 0, assuming hash functions modeled as random oracles. Time and bit complexity of REDUCER++ remain constant and quasi-quadratic, respectively, with constants depending on \epsilon.
ePrint: https://eprint.iacr.org/2024/1682
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 .