Paper 2024/403

DARE to agree: Byzantine Agreement with Optimal Resilience and Adaptive Communication

Pierre Civit, École Polytechnique Fédérale de Lausanne (EPFL)
Muhammad Ayaz Dzulfikar, NUS Singapore
Seth Gilbert, NUS Singapore
Rachid Guerraoui, École Polytechnique Fédérale de Lausanne (EPFL)
Jovan Komatovic, École Polytechnique Fédérale de Lausanne (EPFL)
Manuel Vidigueira, École Polytechnique Fédérale de Lausanne (EPFL)

Byzantine Agreement (BA) enables $n$ processes to reach consensus on a common valid $L_o$-bit value, even in the presence of up to $t<n$ 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 ($n=2t+1$), for both the worst-case scenario and the adaptive scenario, which accounts for the actual number $f \leq t$ of failures. We introduce ADA-DARE (Adaptively Disperse, Agree, Retrieve), a novel universal approach to solve BA efficiently. Let $\kappa$ represent the size of the cryptographic objects required to solve BA when $t>n/3$. Different instantiations of ADA-DARE achieve near-optimal adaptive bit complexity of $O(nL_o + n(f + 1) \kappa)$ for both strong multi-valued validated BA (SMVBA) and interactive consistency (IC). By definition, for IC, $L_o = nL_{in}$, with $L_{in}$ representing the size of an input value. These results achieve optimal $O(n(L_o+f))$ word complexity and significantly improve the previous best results by up to a linear factor, depending on $L_o$ and $f$.

Available format(s)
Publication info
Byzantine AgreementBit ComplexityOptimal Resilience
Contact author(s)
pierre civit @ epfl ch
ayaz dzulfikar @ u nus edu
seth gilbert @ comp nus edu sg
rachid guerraoui @ epfl ch
jovan komatovic @ epfl ch
manuel ribeirovidigueira @ epfl ch
2024-03-08: approved
2024-03-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pierre Civit and Muhammad Ayaz Dzulfikar and Seth Gilbert and Rachid Guerraoui and Jovan Komatovic and Manuel Vidigueira},
      title = {DARE to agree: Byzantine Agreement with Optimal Resilience and Adaptive Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2024/403},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.