2024/10/16 by Komatovic, Jovan, Neu, Joachim, Roughgarden, Tim
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2410.12755
Multi-valued validated Byzantine agreement (MVBA), a fundamental primitive of distributed computing, allows n processes to agree on a valid ℓ-bit value, despite t faulty processes behaving maliciously. Among hash-based solutions for the asynchronous setting with adaptive faults, the state-of-the-art HMVBA protocol achieves optimal O(n2) message complexity, (near-)optimal O(nℓ+n2 λlog n) bit complexity, and optimal O(1) time complexity. However, it only tolerates up to t < \frac15 n adaptive failures. In contrast, the best known optimally resilient protocol, FIN-MVBA, exchanges O(n3) messages and O(n2ℓ + n3λ) bits. This highlights a fundamental question: can a hash-based protocol be designed for the asynchronous setting with adaptive faults that simultaneously achieves both optimal complexity and optimal resilience? In this paper, we take a significant step toward answering the question. Namely, we introduce Reducer, an MVBA protocol that retains HMVBA's complexity while improving its resilience to t<\frac14 n. Like HMVBA and FIN-MVBA, Reducer relies exclusively on collision-resistant hash functions. A key innovation in Reducer's design is its internal use of strong multi-valued Byzantine agreement (SMBA), a variant of strong consensus we introduce and construct, which ensures agreement on a correct process's proposal. To further advance resilience toward the optimal one-third bound, we then propose Reducer++, an MVBA protocol that tolerates up to t < (\frac13-ε)n adaptive failures, for any fixed constant ε> 0. Unlike Reducer, Reducer++ does not rely on SMBA. Instead, it employs a novel approach involving hash functions modeled as random oracles to ensure termination. Reducer++ maintains constant time complexity, quadratic message complexity, and quasi-quadratic bit complexity, with constants dependent on ε.