Scalable Accountable Byzantine Agreement and Beyond

No t-resilient Byzantine Agreement (or Reliable Broadcast) protocol can guarantee agreement among n correct processes in a non-synchronous network if the actual number of faulty processes f is ≥ n -2t. This limitation highlights the need to augment such fragile protocols with mechanisms that detect safety violations, such as forensic support and accountability.

This paper introduces simple and efficient techniques to address this challenge by proposing a new generic transformation, ABC ++ . The transformation leverages two key primitives: the ratifier and the propagator. By sequentially composing these primitives with any closed-box Byzantine Agreement (or Reliable Broadcast) protocol, ABC ++ produces a robust counterpart that provides both (adaptively-secure) forensic support and (1-delayed adaptively-secure) accountability. The transformation incurs a subquadratic additive communication overhead, with only 1 round of overhead for decision and forensic support, and 2 additional rounds for detection in case of a safety violation (or O log(n) additional rounds with optimized communication).

The generality of ABC ++ offers a compelling general alternative to the subquadratic forensic support solution by Sheng et al. (FC'23) tailored to HotStuff-like protocols, while being more efficient than the (stronglyadaptively-secure) quadratic ABC accountable transformation (IPDPS'22, JPDC'23). Moreover, it provides the first subquadratic accountable Byzantine Agreement (or Reliable Broadcast) protocols against a (1-delayed) adaptive adversary.

Finally, any subquadratic accountable Reliable Broadcast protocol can be integrated into the τscr transformation (ICDCS'22) to produce an improved variant, τ ++ scr . This new version compiles any deterministic (and even beyond) protocol into its accountable counterpart with subquadratic multiplicative communication overhead, significantly improving upon the original quadratic overhead in τscr.

1. The original definition of accountability in [8] involves a judge-based model. Following [9], [10], [11], [12], we adopt the convention that all correct judges (i.e., processes) must reach a verdict.

2. We elaborate on this notion in the related work section.