Paper 2022/711

Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement

Abstract

We present a new abstraction based on crusader agreement called $\mathit{\text{Binding Crusader Agreement}}$ (BCA) for solving binary consensus in the $\mathit{\text{asynchronous}}$ setting against an $\mathit{\text{adaptive}}$ adversary. BCA has the validity, agreement, and termination properties of crusader agreement in addition to a new property called $\mathit{\text{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 $$-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 $$-good common coin.

Note: Full version of our PODC 2022 paper