Paper 2024/1682

Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience

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$.