DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication

Byzantine Agreement (BA) enables processes to reach consensus on a common valid -bit value, even in the presence of up to < faulty processes that can deviate arbitrarily from their prescribed protocol.Despite its significance, the optimal communication complexity for key variations of BA has not been determined within the honest majority regime ( = 2 +1), for both the worst-case scenario and the adaptive scenario, which accounts for the actual number ≤ of failures.We introduce ada-Dare (Adaptively Disperse, Agree, Retrieve), a novel universal approach to solve BA efficiently.Let represent the size of the cryptographic objects required to solve BA when > /3.Different instantiations of ada-Dare achieve near-optimal adaptive bit complexity of ( + ( + 1)) for both strong multi-valued validated BA (SMVBA) and interactive consistency (IC).By definition, for IC, = , where is the size of an input value.These results achieve optimal (( + )) word complexity and significantly improve the previous best results by up to a linear factor, depending on and .