Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader AgreementSecure Asynchronous Binary Agreement β’ June 13th, 2022
We present a new abstraction based on crusader agreement called Binding Crusader Agreement (BCA) for solving binary consensus in the asynchronous setting against an adaptive adversary. BCA has the validity, agreement, and termination properties of crusader agreement in addition to a new property called binding. Binding states that before the first non-faulty party terminates, there is a value π£ 0, 1 such that no non-faulty party can output the value π£ 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 π-good common coin. For crash failures, we reduce the
