Welcome to the resource topic for 2024/479
Title:
Making Hash-based MVBA Great Again
Authors: Hanwen Feng, Zhenliang Lu, Tiancheng Mai, Qiang Tang
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 surge of efforts have pushed the communication complexity of such protocols from O(\ell n^2 + \lambda n^2 + n^3) (Cachin et al, CRYPTO’00), to O(\ell n^2 + \lambda n^2) (Abbraham et al, PODC’19) and finally to optimal O(\ell n + \lambda n^2) (Lu et al, PODC’ 20), for \ell-bit inputs across a network of n nodes, with security parameter \lambda.
However, those constructions of \mathsf{MVBA} 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 $\mathsf{MVBA}$ (Duan et al., CCS'23) incurs a large $O(\ell n^2 + \lambda n^3)$-bits communication, which in turn makes the hash-based $\mathsf{MVBA}$ inferior performance-wise comparing with the classical’’ ones. Indeed, this was clearly demonstrated in our experimental evaluations.
To make hash-based \mathsf{MVBA} actually realize its full potential, in this paper, we introduce an \mathsf{MVBA} with adaptive security, and \widetilde{O}(\ell n + \lambda n^2) communication, exclusively leveraging conventional hash functions. Our new \mathsf{MVBA} 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 n = 201 and an input size of 1.75 MB, our \mathsf{MVBA} exhibits a latency that is 81% lower than that of the existing hash-based \mathsf{MVBA} and 47% lower than the threshold signature-based \mathsf{MVBA}. Our new construction also achieves optimal parameters in other metrics such as O(1) rounds and O(n^2) message complexity, except with a sub-optimal resilience, tolerating up to 20\% Byzantine corruptions (instead of 33\%). Given its practical performance advantages, our new hash-based \mathsf{MVBA} naturally leads to better asynchronous distributed protocols, by simply plugging it into existing frameworks.
ePrint: https://eprint.iacr.org/2024/479
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 .