Send email Copy Email Address
2024-05-26

Early Stopping Byzantine Agreement in $(1+ε)\cdot f$ Rounds

Summary

In this paper, we present two early stopping Byzantine agreement protocols in the authenticated setting against a corrupt minority t < n/2, where t represents the maximum number of malicious parties. Early stopping protocols ensure termination within a number of rounds determined solely by the actual number of malicious nodes f present during execution, irrespective of t. Our first protocol is deterministic and ensures early stopping termination in (d + 5) · ([f /d] + 2) + 2 rounds, where d is a fixed constant. For example, for all d ≥ 6, our protocol runs in at most (1 + ϵ) · f rounds (where 0 < ϵ < 1), improving (for large f) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg [1], which terminates in min(2f+4, 2t+2) rounds. Additionally, our second protocol is randomized, ensuring termination in an expected constant number of rounds and achieving early stopping in (d + 9) · ([f /d] + 1) + 2 rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank. [2], which always requires an expected constant number of rounds and O(t) rounds in the worst case, i.e., does not have the early stopping property.

Conference Paper

International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)

Date published

2024-05-26

Date last modified

2024-10-08