Paper 2024/479

Making Hash-based MVBA Great Again

Abstract

Multi-valued Validated Asynchronous Byzantine Agreement ($\mathsf{MVBA}$) is one essential primitive for many distributed protocols, such as asynchronous Byzantine fault-tolerant scenarios like atomic broadcast ($\mathsf{ABC}$), asynchronous distributed key generation, and many others. Recent efforts (Lu et al, PODC' 20) have pushed the communication complexity of $$ to optimal $$, which, however, heavily rely on ``heavyweight'' cryptographic tools, such as non-interactive threshold signatures. The computational cost of algebraic operations, the susceptibility to quantum attacks, and the necessity of a trusted setup associated with threshold signatures present significant remaining challenges. There is a growing interest in information-theoretic or hash-based constructions (historically called signature-free constructions). Unfortunately, the state-of-the-art hash-based $$ (Duan et al., CCS'23) incurs a large $$-bits communication, which in turn makes the hash-based $$inferior performance-wise comparing with the ``classical'' ones. Indeed, this was clearly demonstrated in our experimental evaluations. To make hash-based $$ actually realize its full potential, in this paper, we introduce an $$ with adaptive security, and $$ communication, exclusively leveraging conventional hash functions. Our new $$ achieves nearly optimal communication, devoid of heavy operations, surpassing both threshold signature-based schemes and the hash-based scheme in many practical settings, as demonstrated in our experiments. For example, in scenarios with a network size of $$ and an input size of $$ MB, our $$ exhibits a latency that is 81\% lower than that of the existing hash-based $$ and 47\% lower than the threshold signature-based $$. Our new construction also achieves optimal parameters in other metrics such as $$ rounds and $$ message complexity, except with a sub-optimal resilience, tolerating up to $$ Byzantine corruptions (instead of $$). Given its practical performance advantages, our new hash-based $$ naturally leads to better asynchronous distributed protocols, by simply plugging it into existing frameworks.