Almost-Surely Terminating Asynchronous Byzantine Agreement Against General Adversaries with Optimal Resilience ✱
Ashish Choudhury · 2023
In this work, we present an almost-surely terminating asynchronous Byzantine agreement (ABA) protocol for n parties. Our protocol requires expected time and is secure against a computationally-unbounded malicious (Byzantine) adversary, characterized by a non-threshold adversary structure , which enumerates all possible subsets of potentially corrupt parties. Our protocol has optimal resilience where satisfies the condition; i.e. union of no three subsets from covers all the n parties. To the best of our knowledge, this is the first almost-surely terminating ABA protocol with condition. Previously, almost-surely terminating ABA protocol is known with non-optimal resilience where satisfies the condition; i.e. union of no four subsets from 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.