Paper 2022/711

Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement

Ittai Abraham, VMware Research
Naama Ben-David, VMware Research
Sravya Yandamuri, Duke University

We present a new abstraction based on crusader agreement called $\textit{Binding Crusader Agreement}$ (BCA) for solving binary consensus in the $\textit{asynchronous}$ setting against an $\textit{adaptive}$ adversary. BCA has the validity, agreement, and termination properties of crusader agreement in addition to a new property called $\textit{binding}$. Binding states that before the first non-faulty party terminates, there is a value $v \in \{0,1\}$ such that no non-faulty party can output the value $v$ in any continuation of the execution. We believe that reasoning about binding explicitly, as a first order goal, greatly helps algorithm design, clarity, and analysis. Using our framework, we solve several versions of asynchronous binary agreement against an adaptive adversary in a simple and modular manner that either improves or matches the efficiency of state of the art solutions. We do this via new BCA protocols, given a strong common coin, and via new Graded BCA protocols given an $\epsilon$-good common coin. For crash failures, we reduce the expected time to terminate and we provide termination bounds that are linear in the goodness of the common coin. For Byzantine failures, we improve the expected time to terminate in the computational setting with threshold signatures, and match the state of the art in the information theoretic setting, both with a strong common coin and with an $\epsilon$-good common coin.

Note: Full version of our PODC 2022 paper

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. PODC 2022
Asynchronous Byzantine Agreement
Contact author(s)
iabraham @ vmware com
2022-06-13: revised
2022-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ittai Abraham and Naama Ben-David and Sravya Yandamuri},
      title = {Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2022/711},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.