Paper 2022/917

Almost-Surely Terminating Asynchronous Byzantine Agreement Against General Adversaries with Optimal Resilience

Abstract

In this work, we present an almost-surely terminating asynchronous Byzantine agreement (ABA) protocol for $n$ parties. Our protocol requires $\mathcal{O}(n^2)$ expected time and is secure against a computationally-unbounded malicious (Byzantine) adversary, characterized by a non-threshold adversary structure $\mathcal{Z}$, which enumerates all possible subsets of potentially corrupt parties. Our protocol has optimal resilience where $\mathcal{Z}$ satisfies the ${\mathcal{Q}}^{(3)}$ condition; i.e. union of no three subsets from $\mathcal{Z}$ covers all the $n$ parties. To the best of our knowledge, this is the first almost-surely terminating ABA protocol with ${\mathcal{Q}}^{(3)}$ condition. Previously, almost-surely terminating ABA protocol is known with non-optimal resilience where $\mathcal{Z}$ satisfies the ${\mathcal{Q}}^{(4)}$ condition; i.e. union of no four subsets from $\mathcal{Z}$ covers all the $n$ parties. To design our protocol, we present a shunning asynchronous verifiable secret-sharing (SAVSS) scheme with $$ condition, which is of independent interest.