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

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