Making Hash-based MVBA Great Again

ePrint Report: Making Hash-based MVBA Great Again

Hanwen Feng, Zhenliang Lu, Tiancheng Mai, Qiang Tang

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) …

abc asynchronous atomic broadcast communication complexity distributed eprint report great hash key making protocols report tang